rust/src/librustc_data_structures/bitvec.rs, branch perf-tmp

Merge indexed_set.rs into bitvec.rs, and rename it bit_set.rs.

2018-09-17T21:08:09+00:00

Currently we have two files implementing bitsets (and 2D bit matrices). This commit combines them into one, taking the best features from each. This involves renaming a lot of things. The high level changes are as follows. - bitvec.rs --> bit_set.rs - indexed_set.rs --> (removed) - BitArray + IdxSet --> BitSet (merged, see below) - BitVector --> GrowableBitSet - {,Sparse,Hybrid}IdxSet --> {,Sparse,Hybrid}BitSet - BitMatrix --> BitMatrix - SparseBitMatrix --> SparseBitMatrix The changes within the bitset types themselves are as follows. ``` OLD OLD NEW BitArray IdxSet BitSet -------- ------ ------ grow - grow new - (remove) new_empty new_empty new_empty new_filled new_filled new_filled - to_hybrid to_hybrid clear clear clear set_up_to set_up_to set_up_to clear_above - clear_above count - count contains(T) contains(&T) contains(T) contains_all - superset is_empty - is_empty insert(T) add(&T) insert(T) insert_all - insert_all() remove(T) remove(&T) remove(T) words words words words_mut words_mut words_mut - overwrite overwrite merge union union - subtract subtract - intersect intersect iter iter iter ``` In general, when choosing names I went with: - names that are more obvious (e.g. `BitSet` over `IdxSet`). - names that are more like the Rust libraries (e.g. `T` over `C`, `insert` over `add`); - names that are more set-like (e.g. `union` over `merge`, `superset` over `contains_all`, `domain_size` over `num_bits`). Also, using `T` for index arguments seems more sensible than `&T` -- even though the latter is standard in Rust collection types -- because indices are always copyable. It also results in fewer `&` and `*` sigils in practice.

Remove bitslice.rs.

2018-09-13T09:36:03+00:00

This requires the following changes. - It moves parts of bitslice.rs into bitvec.rs: `bitwise()`, `BitwiseOperator`, `bits_to_string()`. - It changes `IdxSet` to just be a wrapper around `BitArray`. - It changes `BitArray` and `BitVec` to use `usize` words instead of `u128` words. (`BitSlice` and `IdxSet` already use `usize`.) Local profiling showed `usize` was better. - It moves some operations from `IdxSet` into `BitArray`: `new_filled()`, `clear()`, `set_up_to()`, `trim_to()` (renamed `clear_above()`), `words()` and `words_mut()`, `encode()` and `decode(). The `IdxSet` operations now just call the `BitArray` operations. - It replaces `BitArray`'s iterator implementation with `IdxSet`'s, because the latter is more concise. It also removes the buggy `size_hint` function from `BitArray`'s iterator, which counted the number of *words* rather than the number of *bits*. `IdxSet`'s iterator is now just a thin wrapper around `BitArray`'s iterator. - It moves some unit tests from `indexed_set.rs` to `bitvec.rs`.

Reorder bitvec.rs.

2018-09-13T03:27:56+00:00

So that the `BitArray` code is all together and before the `BitVector` code, instead of being awkwardly interleaved.

Make SparseBitMatrix a bit lazier.

2018-08-23T08:41:55+00:00

Currently when a row is instantiated in SparseBitMatrix, any missing rows prior to it are also fully instantiated. This patch changes things so that those prior rows are minimally instantiated (with a `None`). This avoids a decent number of allocations in NLL, speeding up several benchmarks by up to 0.5%. The patch also removes two unused methods, `len()` and `iter_enumerated()`.

Rename the fields in `SparseBitMatrix`.

2018-08-23T06:06:16+00:00

The new names are clearer.

A few cleanups for rustc_data_structures

2018-08-09T17:50:12+00:00

Split out growth functionality into BitVector type

2018-08-01T12:50:40+00:00

fix `sparse_matrix_iter` unit test

2018-07-26T13:33:52+00:00

add type parameters to `BitMatrix` and `SparseBitMatrix` unit tests

2018-07-26T13:33:15+00:00

convert tests of `BitVector` to use `BitVector`

2018-07-26T13:32:13+00:00