News for hackers. Stuff that matters.
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints by jsnell on Tuesday May 09, 2017 @01:58AM (#14298014)
Small string optimization should kick in here, so you're probably not looking at a size_t + pointer + a object with the 6 bytes of payload data. Instead it'd be a single object of about 32 bytes (depending on the implementation).

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.

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.