immutable-chunkmap

• stop pooling tree nodes, because of notch analysis they can never meet the safety requirements of IsoPoolable.

• add an optional feature "pool". If enabled memory allocation is greatly reduced by reusing tree components instead of freeing them. The performance improvement depends on key type and tree size but can be as high as %30 for plain insert/remove on very large maps. Memory fragmentation will also be greatly reduced, but this is much harder to measure.

• pool is not compatible with no_std

• fix a number of test bugs (actual bugs in the TEST code, not the tree) that cropped up when running model checking for multiple days continuously

• merge #10, no_std support (alloc required)

• merge #8 hand coded packing of height/size to remove the dependency on packed struct

• fix a few bugs in the model checking COW tests

• remove redundant type parameter from iter_mut_cow

• implement iter_mut_cow, range_mut_cow, for copy on write iterators

• implement get_or_insert_cow and get_or_default_cow

• implement get_mut_cow to improve the ergonomics of using nested maps with COW operations

• fix the range api to match the standard library. Sorry about the previous two releases, it's actually quite a subtle api and I consistently got it wrong. I also got semantic versioning wrong, and I'm really sorry about that, I hope nothing broke annoyingly for anyone (aside from for me :))

• fix ?Sized on range

• fix the arguments to range to have the correct borrow type

• add remove_many, a small wrapper around update_many
• fix a bug in update_many where trying to remove elements that don't exist in the map could cause a panic. Add a test for this case.

• add optional rayon support for map and set

• add optional serde support for map and set

• stop depending on serde by default

• replace vec chunks with arrayvec chunks to eliminate an indirection
• implement tree compaction to keep inner chunks from getting too sparse

1.0.0 "the cake is not a lie"

• Add copy on write mutable operations. They are 10x faster than plain insert/remove, and bring update performance within an 2-3x of BTreeMap (with ArcStr keys).

• Chunk size is now configurable with a const generic parameter. Three different sizes are exposed as default type aliases.

• bump dependencies, update readme, and refresh the benchmarks

• feels like 1.0 to me!

• add weak references to maps and sets as well as methods to get the strong and weak count of map/set references.

• further 20% performance improvement on batch update operations.

• improve performance of batch update operations on unsorted data by a large amount (7x on trees of size 10million and chunks of size 100k).

• packed the height and length together, which reduced the size of nodes by 1 word. That reduction gets us a 1-2% improvement in lookup times (more benefit for larger trees). Tree length is now limited to 2^56 elements instead of usize::MAX elements.

• made the tests run faster by wrapping strings in Arcs, which is closer to how you'd use them in a real program anyway.

• small performance optimizations update operations

• Edition 2018

• implement Set::diff, and Map::diff, O(log(N) + M) where M is the number of intersecting chunks. Now all the fundamental set operations are implemented.
• rename Map::merge to Map::union. Sorry for the tiny break in semantic versioning, but given it was just released I don't think it's a huge problem to change it now.

• implement Set::intersect, and Map::intersect, O(log(N) + M) where M is the number of intersecting chunks.

• implement Set::union, and Map::merge, O(log(N) + M) where M is the number of intersecting chunks and N is the size of the largest tree. Should always be as fast as update_many from the other map's iterator, a lot faster in the case of a small intersection.
• remove my silly &mut F requirement for closure arguments to functions in the public interface. Sorry I'm still learning rust, I didn't know FnMut was also implemented by a &mut.

• implement map get_key, get_full
• implement set update_many
• fix some incorrect documentation
• BREAKING change map and set update functions so they are able to work with borrowed forms of the key

• implement get in the set module
• properly implement Ord, PartialOrd, Eq, PartialEq, Hash, and Debug

• add a set module
• remove the rc and arc modules. There is no observable performance difference between rc and arc, so just use arc everywhere. This is especially relevant because all the practical applications of this library than I know about require using Arc.
• BREAKING: fix return type of insert and remove to match BTreeMap

• fix a bug in update_many that could rarely cause a removed item not to be removed

• BREAKING: change the name of insert_sorted to insert_many
• add update, and update_many
• insert 14% performance improvement
• insert_many 42% performance improvement on unsorted data, now faster than insert on random data

• BREAKING: change signature of insert to match BTreeMap as closely as possible. Sorry I was new to rust when I first wrote this module :-(

• iteration runs in constant space
• Implement collection range api
• Implement DoubleEndedIterator
• insert_sorted performance improved on degenerate cases
• BREAKING: insert_sorted now takes IntoIterator instead of an explicit slice
• BREAKING: change the name of length to len, like BTreeMap

• Initial public release