Ellipsis-Labs / sokoban

Compact, efficient data structures in contiguous byte arrays
https://docs.rs/lib-sokoban/latest/sokoban
MIT License
102 stars 17 forks source link

add filter functionality #16

Open cavemanloverboy opened 11 months ago

cavemanloverboy commented 11 months ago

This provides a drain_filter and filter functionality on the red black tree implementation.

Inspiration: in phoenix-v1's CancelAllOrders instruction, the tree is traversed and matching ids are collected. These ids are then used via book.remove(...) which traverses the tree to remove the entry. Instead of traversing the tree, this implementation records allocator node addresses and removes them all upon dropping the new RedBlackTreeDrainFilter type.

A quick and dirty benchmark of 128 removals from a full tree of 4096 items yields the following results on an M2 Max:

./target/release/examples/bench_filter
average id + remove: 59280 micros
average drain_alloc: 44410 micros
average drain: 43759 micros

which is an O(30%) reduction in the wall time of the removals.

cavemanloverboy commented 11 months ago

Clever change! Please bump the version in the Cargo.toml

Will do. Also, it's come to my attention that the drain_filter method for std::vec::Vec that this was supposed to be analogous to has been renamed to extract_if:

https://github.com/rust-lang/rust/issues/43244

I'll try to come up with some better names for the methods.

cavemanloverboy commented 11 months ago
  1. I switched to extract_if to match the method on std collections (btreemap, vec, etc, e.g. https://doc.rust-lang.org/nightly/std/vec/struct.Vec.html#method.extract_if).
  2. I added a docstring w/ test on the method w/ some notes.
  3. I removed the filter method since you can just do extract_if and collect into collection of your choice -- instead of locking user into Vec.
  4. Bumped to 0.4.0
cavemanloverboy commented 11 months ago

One final thing we may want to do is either implement DoubleEndedIterator or remove the rev fields from the ExtractIf type