News for hackers. Stuff that matters.
Re:Open-sourcing F14 for memory-efficient hash tables by dkural on Friday April 26, 2019 @09:42PM (#19763248)
https://github.com/sparsehash/sparsehash was for a decade+ hands down the most memory efficient map implementation, originally written by Craig Silverstein of Google. I am not sure how the more recent SIMD stuff impacts it.
Re:Open-sourcing F14 for memory-efficient hash tables by ngbronson on Friday April 26, 2019 @10:03PM (#19763309)
sparsehash is still more memory efficient, but it is quite slow in comparison. Also, in practice it doesn't reach the ultra-low space overheads claimed by the documentation. It allocates memory blocks of many different sizes, so the dominant space overhead becomes internal fragmentation in the allocator. For sparsehash using JEMalloc's default allocation classes (spaced about a factor of 1.2 apart) the memory used relative to useful data varies from about 1.3 for small values to 1.1 for large values.