petgraph / fixedbitset

A simple bitset container for Rust
https://docs.rs/fixedbitset/
Apache License 2.0
124 stars 47 forks source link

Added `insert_range`, `set_range` functions. #14

Closed kennytm closed 7 years ago

kennytm commented 7 years ago

This is used to quickly set a range of bits to ones, especially the whole bit set. This is much more efficient (~100x) than loop-and-insert.


Benchmarks for this commit:

test bench_insert_range                            ... bench:      11,929 ns/iter (+/- 3,610)
test bench_insert_range_using_loop                 ... bench:   1,603,755 ns/iter (+/- 425,971)
test bench_iter_ones_all_ones                      ... bench:   3,214,317 ns/iter (+/- 319,040)
test bench_iter_ones_all_zeros                     ... bench:      67,466 ns/iter (+/- 20,117)
test bench_iter_ones_using_contains_all_ones       ... bench:     865,560 ns/iter (+/- 375,256)
test bench_iter_ones_using_contains_all_zeros      ... bench:     769,844 ns/iter (+/- 308,139)
test bench_iter_ones_using_slice_directly_all_ones ... bench:     720,331 ns/iter (+/- 288,132)
test bench_iter_ones_using_slice_directly_all_zero ... bench:      37,800 ns/iter (+/- 10,259)

(Benchmarks for 0.1.6 (master) for reference, though not relevant for this PR):

test bench_iter_ones_all_ones                      ... bench:   3,336,585 ns/iter (+/- 455,084)
test bench_iter_ones_all_zeros                     ... bench:      68,508 ns/iter (+/- 18,640)
test bench_iter_ones_using_contains_all_ones       ... bench:     893,454 ns/iter (+/- 148,149)
test bench_iter_ones_using_contains_all_zeros      ... bench:     780,992 ns/iter (+/- 333,253)
test bench_iter_ones_using_slice_directly_all_ones ... bench:     737,119 ns/iter (+/- 123,984)
test bench_iter_ones_using_slice_directly_all_zero ... bench:      36,513 ns/iter (+/- 5,356)
bluss commented 7 years ago

Thanks a lot, and sorry for the delay!

bluss commented 7 years ago

Now in 0.1.7.