3 ms·
Very interesting ! You mentioned the memory usage at the end, BTreeMaps are actually better than HashMaps most of the time, at least for Rust Here's a good bre
by kibo_money 2y ago
Very interesting ! You mentioned the memory usage at the end, BTreeMaps are actually better than HashMaps most of the time, at least for Rust
Here's a good break down: https://ntietz.com/blog/rust-hashmap-overhead/ https://ntietz.com/blog/rust-hashmap-overhead/
- pclmulqdq 2y agoBtrees don't waste much memory, while hash tables have to have excess capacity if you want them to go fast.
- marginalia_nu 2y agoThat's true for on-disk b-trees which typically have large node sizes (typically 4KB), but in-memory btrees tend to aim for CPU cache lines (typically a small multiple of 32B), and thus do actually waste a fair amount of memory with their comparatively low branching factor, and thus relatively large number of branches compared to their number of leaves.
- pclmulqdq 2y agoThe waste of abseil's b-tree, for example, is small per value: https://abseil.io/about/design/btree https://abseil.io/about/design/btree The efficiency compared to hash tables very much does carry over to the small b-trees used for in-memory data.