folly::F14ValueMap vs std::unordered_map

1
std::unordered_map<int, int>의 lookup 비용
2
  1. bucket 인덱스 계산 (hash & mask)
3
  2. bucket 배열 접근   (cache miss 1회)
4
  3. linked list 순회   (cache miss N회, N=avg chain length)
5
  4. key 비교

1
folly::F14ValueMap<std::string, int> m;
2
m["a"] = 1;
3
m["b"] = 2;
4
// internally: chunks of 14 slots, SIMD가 14개 동시 검사

1
#include <folly/container/F14Map.h>
2

3
folly::F14ValueMap<std::string, int> m;
4

5
// 표준 인터페이스
6
m.emplace("hello", 1);
7
m["world"] = 2;
8
m.find("hello");
9
m.contains("world");      // C++20 식 (folly는 더 일찍 제공)
10
m.erase("hello");
11

12
// F14 전용
13
m.reserve(1000);          // chunk 할당 미리
14
m.bucket_count();         // chunk 수 × 14
15
m.computeStats();         // chunk fullness, collision 등

1
folly::F14ValueMap<int, std::string> m;
2
auto& ref = m[1];          // 1을 추가
3
ref = "hello";
4
for (int i = 0; i < 100; ++i) m[i] = "x";   // rehash 가능
5
// ref는 이제 invalid — UB

1
[ control bytes (16B) | slot[0] | slot[1] | ... | slot[13] | overflow counter (1B) ]

1
control byte:
2
  bit 7   : empty/full
3
  bit 6   : tombstone/live
4
  bit 5-1 : 5-bit hash fragment (H2)
5
  bit 0   : reserved

1
// 약식
2
Iterator find(const Key& k) {
3
  size_t h = hash(k);
4
  size_t chunk_idx = (h >> 7) & mask_;     // H1
5
  uint8_t fragment = h & 0x7F;             // H2
6

7
  while (true) {
8
    Chunk& c = chunks_[chunk_idx];
9
    // SIMD 비교: 14 control bytes vs fragment
10
    uint32_t hits = SimdMatch(c.controls, fragment);
11
    while (hits) {
12
      int slot = __builtin_ctz(hits);
13
      if (c.slots[slot].key == k) return Iterator{...};
14
      hits &= hits - 1;                    // 다음 hit
15
    }
16
    if (!c.hasOverflow()) return end();    // 빈 slot 있음
17
    chunk_idx = (chunk_idx + 1) & mask_;
18
  }
19
}

1
std::unordered_map<int, int> 64개 항목 메모리:
2
  bucket[]          : 128 * 8 = 1024 B
3
  node[]            : 64 * (sizeof(int)*2 + next ptr) = 1024 B  (다른 영역)
4
  총                : ~2 KB, 두 영역 cache miss
5
  per entry        : ~32 B
6

7
folly::F14ValueMap<int, int> 64개 항목:
8
  chunks[5]         : 5 * (16 + 14*8 + 1) = ~640 B  (한 영역)
9
  per entry        : ~10 B

1
// std
2
std::unordered_map<K, V> std_map;
3

4
// abseil
5
absl::flat_hash_map<K, V> abs_map;     // open addressing, value in slot
6
absl::node_hash_map<K, V> abs_node;    // 별도 node, pointer 안정
7

8
// folly
9
folly::F14ValueMap<K, V> f14v;         // value in chunk slot
10
folly::F14NodeMap<K, V>  f14n;         // 별도 node, pointer 안정
11
folly::F14VectorMap<K, V> f14vec;      // value in vector
12
folly::F14FastMap<K, V>  f14fast;      // 크기에 따라 자동 선택

1
// Bad — pointer를 long-lived 저장
2
folly::F14ValueMap<int, std::string> m;
3
const std::string* p = &m[1];
4
m.emplace(...);             // rehash 가능
5
LOG(INFO) << *p;            // UB
6

7
// Good — Node map 또는 key로 보관
8
folly::F14NodeMap<int, std::string> mn;
9
const std::string* p = &mn[1];   // stable
10

11
// 또는
12
int key = 1;
13
LOG(INFO) << m[key];        // 매번 lookup, stable

1
// Bad — reserve 없이 큰 insert
2
folly::F14ValueMap<int, int> m;
3
for (int i = 0; i < 1'000'000; ++i) m.emplace(i, i);
4
// rehash 여러 번
5

6
// Good
7
folly::F14ValueMap<int, int> m;
8
m.reserve(1'000'000);
9
for (int i = 0; i < 1'000'000; ++i) m.emplace(i, i);