3 ms·

> Even very popular and reputedly performant data structure implementations like absl::flat_hash_map are pretty easy to beat for specific use cases. In this spe

• anonymoushn 4y ago
  There's a talk about this data structure here: https://www.youtube.com/watch?v=JZE3_0qvrMg https://www.youtube.com/watch?v=JZE3_0qvrMg Basically it stores one array of 1-byte markers that contain a full-or-empty bit and a 7-bit prefix of the hash, then a separate array of buckets. The lookup first loads a neighborhood of bytes in the former array to find entries that match in the first hash byte or empty entries. If the table is very highly loaded or if the hash function is low quality, some checks for equality of the full hash or equality of the value (the former probably just costs a cache miss and the latter might be very expensive) can be skipped, but under better conditions for the hash and load factor and known-pretty-bad conditions for randomness of consecutive lookups, it can be better to avoid the cost of doing one load in the small array of markers and another load in the large array of hash table entries. In the talk the presenter also says that they've changed the first load in such a way that it sometimes spans two cache lines, which makes it a bit more expensive, but that this was nonetheless a win for them.