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.
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
by dryman on Tuesday May 09, 2017 @01:18AM
(#14297901)
Thanks for pointing out. I used std::string mainly because I suck at C++ :(. In C I can easily define the key length to be a variable passed to the constructor, but I don't know how to do the same with C++.
> The input is 8 M key-value pairs; size of each key is 6 bytes and size of each value is 8 bytes. The lower bound memory usage is (6+8)⋅2^23= 117MB
In many case, hash table implementation won't (can't) assume fixed size of keys and values, and use pointers. On 64-bit architectures, this can mean there's an uncompressible overhead of 8 * 2 = 16 bytes (one pointer for each key and value) for each item.
In fact, a quick look at the OP's benchmark code shows he's using std::string as keys and uint64 as values. With e.g. std::unordered_map, while pointers won't be used for the values, there obviously will be pointers for the key.
It's actually worse than pointers, since the std::string memory layout is a size_t and a char* pointer. And it looks like his hash table essentially uses the equivalent of char[6] as keys. So a fairer memory overhead comparison should use char[6] as keys, instead of std::string...