Comments (3)
I think it would be much more interesting to investigate moving to a layout where all of the fields are in the same allocation as the keys and hashes, with an empty singleton to avoid allocating empty maps. As is done with thin-vec and BTreeMap.
This would make it much cheaper to move HashMaps around, and would dramatically reduce the memory footprint of things which only sometimes actually create a real map. (Option<HashMap>
, Vec<HashMap>
, or just a rarely used HashMap::new()
).
It's non-trivial work though, because it requires carefully ensuring you never mess up the CoW nature of the singleton, as well as carefully ensuring that you never make the size/align mismatch the allocation. That said I think it might be possible, as we should be able to avoid ever looking at the keys for a static ctrl array that's all EMPTY. The BuildHasher is the most annoying part here I think. I think it has to be inline. But that's fine for everyone using FxHasher or any other BuildHasherDefault, which is zero-sized. Sadly RandomState (std's default) needs 16 bytes for the seed.
from hashbrown.
As an aside this would be an exciting experiment because we would have a very optimized implementation to compare the performance difference of this "trick" to in an apples-to-apples way. I'm not aware of any detailed analysis of the second and third-order effects of this optimization, like cache locality and whether it upsets the optimizer, which have historically been reasons to hand-wring over it.
from hashbrown.
The data
pointer could be derived from the ctrl
pointer, which would save 8 bytes. However the other fields can't be derived from each other and must be kept.
from hashbrown.
Related Issues (20)
- Why the identity function can be used as unlikely function? HOT 3
- `hashbrown` fails to compile as a transitive dependency HOT 2
- allocator-api2 default-feature? HOT 2
- Compiling hashbrown 0.14.2 for aarch64-unknown-linux-gnu with "target-cpu=cortex-a53" generates illegal instructions HOT 2
- Switching to GxHash? HOT 9
- Feature: increase capacity according to the actual size returned by the allocator HOT 2
- Hashbrown crash due to bad malloc HOT 1
- 0.14.3 - no method named `clear` found for struct `HashMap` in the current scope HOT 5
- Benchmark biaised due to no fence around input
- assertion failed: buckets.is_power_of_two() HOT 8
- Build breaks on nightly due to use of `stdsimd` rust feature in ahash 0.8.6 HOT 2
- Was swap-remove behavior ever considered when removing entries? HOT 10
- Consider returning to 1.63.0 MSRV HOT 1
- How to calculate the size of the hashbrown::HashMap at runtime? HOT 1
- LLVM failed to use the knowledge from a never-overflow assumption HOT 13
- Library test `map::test_map::test_clone_from_memory_leaks` errors with using uninitialized data under valgrind and miri
- update to ahash 0.8.7 or after to use new stdsimd feature portable_simd HOT 1
- Insertion performance with arena allocators HOT 3
- Do not grow the raw table when lots of deletion and insertion is performed HOT 3
- Unsound usages of unsafe implementation from `usize` to `T` HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from hashbrown.