]> git.lizzy.rs Git - rust.git/commit
Auto merge of #25230 - rayglover:patch-bitset, r=Gankro
authorbors <bors@rust-lang.org>
Mon, 18 May 2015 19:54:24 +0000 (19:54 +0000)
committerbors <bors@rust-lang.org>
Mon, 18 May 2015 19:54:24 +0000 (19:54 +0000)
commit4daa62a55f906bd7ec7ad265cb23d49d9d0db66a
tree151e41c763c3f5344f91fd5e8683858c91b6bc93
parent2dd5ad0be84f8d14dc357fb35a4b21fe5a34030a
parent307fab1aa7540adf8856670c5a1cf44ff508ae2f
Auto merge of #25230 - rayglover:patch-bitset, r=Gankro

Some modest running-time improvements to `std::collections::BitSet` on bit-sets of varying set-membership densities. This is work originally from [here](https://github.com/rayglover/alt_collections). (Benchmarks copied below)
```
std::collections::BitSet / alt_collections::BitSet

copy_dense         ... 3.08x
copy_sparse        ... 4.22x
count_dense        ... 11.01x
count_sparse       ... 8.11x
from_bytes         ... 1.47x
intersect_dense    ... 6.54x
intersect_sparse   ... 4.37x
union_dense        ... 5.53x
union_sparse       ... 5.60x
```

The exception is `from_bytes`, which I've left unaltered since the optimization is rather obscure.

Compiling with the cpu feature `popcnt` gave a further ~10% improvement on my machine, but this wasn't factored in to the benchmarks above.

Similar improvements could be made to `BitVec`, although that would probably require more substantial changes.

criticism welcome!
src/libcollections/bit.rs