Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
by glandium on Tuesday May 09, 2017 @06:50AM
(#14298944)
Thank you for making me look at the implementation of std::string in GCC's libstdc++... The "small string optimization" indeed makes every std::string at least 1 size_t + 1 pointer + 16 bytes large (for a total of 32 bytes on 64-bits platforms).
Strings smaller than 16 bytes are stored in the 16 bytes inline buffer, which means strings larger than that actually take 32 + their length + 1 bytes in memory on 64-bits platforms.
I guess things are not packed further to allow to just directly use the pointer instead of having to do some computation for each access.
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
by jsnell on Tuesday May 09, 2017 @11:25AM
(#14300799)
> I guess things are not packed further to allow to just directly use the pointer instead of having to do some computation for each access.
There are C++ standard libraries that pack things further. I think clang has a 24 byte std::string, which can store strings of up to 22 bytes inline.
But yes, this means that the author's own hash table implementation is getting a roughly 4-5x density benefit from using a different string representation. That totally invalidates the memory usage testing, and probably also has a major effect on the speed tests.