9 ms·
How Google Sparsehash achieves two bits of overhead per entry using sparsetable
- im3w1l 11y agotldr: Open addressing. Group adjacent slots into buckets. Every bucket consists of an occupancy bitmap (1 bit overhead per element), and a pointer (ptrsize / nElementsPerBucket bits overhead, per element) to the elements in the bucket.
- eutectic 11y agoNote that the maximum fill factor of hashtables can be increased well above 90% with comparable or better performance to standard open addressing using Robin Hood collision resolution with backwards shift deletion. The hashtable in the Rust standard library works like this and there is an argument to be made that it should become standard. Of course, this doesn't do away with the need to resize, so it might not be appropriate for low latency or memory constrained systems. I wonder whether a tree-based data structure like a crit-bit tree or a HAMT might be able to do similar things to sparsehash with better performance.
- Kiro 11y agoThis may be a strange and off-topic question but may I ask what you do for a living?
- eutectic 11y agoI'm a student of Physics and Mathematics who takes an amateur interest in programming. :)
- detrino 11y agoMy understanding is that Robin Hood hashing has worse performance than linear probing due to greater cache misses. If you are looking for low memory overhead ordered sets/maps, then B-Trees can provide that.
- signa11 11y agoin case folks are interested in this topic, i would heartily recommend Mihai Pătraşcu blog for some theory :)
- Smerity 11y agoThank you for bringing up Mihai Pătraşcu :) I lightly hinted users towards succinct data structures in the article. His work was exactly the type I meant for people to explore - searches for the extreme lower bounds in computer science! I am saddened to hear that he passed away in 2012 - I had no clue. He gave so much in the time he was active. It is bittersweet that his obituary[1] contains open problems he hoped others would solve. [1]: https://docs.google.com/file/d/0B8ttd1KbGd3EWktsR29qNVdNVEE/edit https://docs.google.com/file/d/0B8ttd1KbGd3EWktsR29qNVdNVEE/...
- TheLoneWolfling 11y agoAny idea how much space overhead malloc has with entries as small as this? (<1 to 4> * 8 bytes) Seems to me it could easily be a significant amount of overhead.
- ekimekim 11y agoCommon practice if you're doing a large number of very small allocations is to pre-allocate a larger area of memory for them, then use a more naive allocation algorithm to parcel it out.
- TheLoneWolfling 11y agoDefine "more naive allocation algorithm".
- eutectic 11y agoWhat about bump-pointer + maintaining a count of live allocations?
- TheLoneWolfling 11y agoThat won't work if you ever want to deallocate things - which, given that due to the compressed arrays you have to deallocate to add elements (deallocate the old array with <0,1,2,3> elements, allocate a new with <1,2,3,4> elements), won't work for this.
- eutectic 11y agoYou can deallocate if you use small enough chunks, although you might need to use some other strategies to minimize fragmentation.
- TheLoneWolfling 11y agoIf you're using "small enough chunks" your space overhead balloons to the point where you may as well not use it.
- dspeyer 11y agoSo we want to insert a value. We find an empty slot. We find the bucket it's in. Do we have to realloc the bucket and move all downstream data down by one? That sounds slow.
- Someone 11y ago'All the data' most of the time are references to all the data. Also, I would not reallocate, but allocate at max size or, possibly, half size and grow if needed. With that change, once you access the array, you likely have all pointers to shift in your level 1 cache. Because of that, I expect it to be plenty fast enough. (Hm, are there CPUs that have instructions for shifting parts of cache lines around?)