folly::F14VectorMap — cache-friendly iteration

1
folly::F14VectorMap<int, Metric> metrics;
2
// ... insert N개
3
for (auto& [k, v] : metrics) {
4
  v.Aggregate();    // vector를 그대로 도는 효과
5
}

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

3
folly::F14VectorMap<std::string, int> m;
4
m["a"] = 1;
5
m["b"] = 2;
6
m["c"] = 3;
7

8
// 순회 — insertion order 보장!
9
for (auto& [k, v] : m) {
10
  // a, b, c 순서
11
}
12

13
// 표준 API
14
m.find("b");
15
m.erase("b");
16
m.contains("a");
17

18
// VectorMap 전용 — index 접근
19
auto vec_view = m.values();    // const std::vector& 비슷한 view
20
for (size_t i = 0; i < vec_view.size(); ++i) {
21
  // ...
22
}

1
Chunks (Swiss table):
2
  [ controls | slot[0] = vec_index | ... | slot[13] = vec_index ]
3
                       |
4
                       v
5
Vector:
6
  [ pair<K,V>[0] | pair<K,V>[1] | pair<K,V>[2] | ... ]

1
// 약식
2
template <typename Key, typename Value>
3
class F14VectorMap {
4
  std::vector<Item> values_;     // contiguous
5
  ChunkTable indexes_;           // chunk → vec index
6
  // ...
7
};

1
// 약식
2
Iterator find(const Key& k) {
3
  auto h = hash(k);
4
  // 1. SIMD probing으로 chunk slot 찾기
5
  uint32_t vec_idx = indexes_.find(k, h);
6
  if (vec_idx == kNotFound) return end();
7
  // 2. vector에서 actual value
8
  return Iterator{&values_[vec_idx]};
9
}

1
// 약식 — Insert
2
void insert(K k, V v) {
3
  size_t new_idx = values_.size();
4
  values_.emplace_back(std::move(k), std::move(v));
5
  indexes_.insert(values_.back().first, new_idx);
6
}
7

8
// Erase — 가장 미묘
9
void erase(const Key& k) {
10
  auto vec_idx = indexes_.find(k);
11
  if (vec_idx == values_.size() - 1) {
12
    values_.pop_back();        // 마지막이면 그냥 pop
13
    indexes_.erase(k);
14
  } else {
15
    // 마지막 entry를 erase 자리로 swap
16
    values_[vec_idx] = std::move(values_.back());
17
    values_.pop_back();
18
    // 마지막 entry의 chunk index 갱신
19
    indexes_.updateIndex(values_[vec_idx].first, vec_idx);
20
    indexes_.erase(k);
21
  }
22
}

1
m.reserve(N);
2
// 1. vector.reserve(N) — contiguous block
3
// 2. chunk 배열 reserve
4
// 큰 entry 수에서도 한 번에 끝남

1
benchmark: N=1M entries
2
                              Lookup    Insert    Iteration
3
  std::unordered_map          120 ns    180 ns    250 ms (전체)
4
  folly::F14ValueMap           45 ns     60 ns    180 ms
5
  folly::F14NodeMap            50 ns     90 ns    220 ms
6
  folly::F14VectorMap          55 ns     65 ns     45 ms ← !

1
// Good — iteration-heavy workload
2
folly::F14VectorMap<int, Metric> m;
3
for (auto& [id, metric] : m) ProcessAll(metric);
4

5
// Bad — lookup-heavy
6
folly::F14VectorMap<int, int> m;
7
for (int i = 0; i < 1'000'000; ++i) {
8
  Use(m.at(i));   // 매번 indirection
9
}
10
// Better: F14ValueMap

1
// 주의 — erase가 insertion order를 깨뜨림
2
folly::F14VectorMap<std::string, int> ordered;
3
ordered["a"] = 1;
4
ordered["b"] = 2;
5
ordered["c"] = 3;
6
ordered.erase("a");
7
// 순회 결과: b, c가 아니라 c, b (swap-pop)

1
// Good — bulk insert 후 freeze
2
folly::F14VectorMap<Key, Value> immutable;
3
for (auto& kv : initial_data) immutable.insert(kv);
4
immutable.reserve(immutable.size());   // shrink to fit
5
// 이후 read-only로 사용