Folly Code Review · 31/89

folly::F14NodeMap — stable pointer가 필요할 때

2026년 6월 5일 · Hawk · 4분 읽기

#한 줄 요약

F14NodeMap은 chunk slot에 value pointer만 두고 실제 value는 별도 heap node에 둔다. std::unordered_map처럼 reference/pointer가 rehash 후에도 유효하다. ValueMap보다 한 단계 indirection이 추가되지만 안정성을 얻는다.

#동기

F14ValueMap은 빠르지만 reference가 흔들린다. 다음 상황에서는 ValueMap을 쓸 수 없다.

값이 큰 객체(MB급 buffer)라 복사 비용이 부담.
다른 자료구조가 map value의 pointer를 보관 (graph node 등).
value가 비복사 타입 (mutex, atomic).
iterator가 오래 살아야 한다 (async chain 중간).

이런 use case는 std::unordered_map이 자연스럽지만 lookup 성능이 떨어진다. F14NodeMap은 F14의 SIMD probing + std-like pointer 안정성을 결합한다.

1
folly::F14NodeMap<int, std::mutex> mutex_pool;
2
auto& m = mutex_pool[key];   // mutex는 movable 아님
3
m.lock();
4
// 다른 thread가 insert 해도 &m 유효

#API & 사용법

ValueMap과 동일한 인터페이스.

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

3
folly::F14NodeMap<std::string, BigObject> m;
4
m.emplace("key1", BigObject{...});
5

6
// reference 안정 — rehash 통과
7
const auto& obj = m["key1"];
8
m.reserve(10000);     // rehash 가능
9
LOG(INFO) << obj.id;  // 여전히 OK
10

11
// iterator 안정 — std::unordered_map과 같음
12
auto it = m.find("key1");
13
m.emplace("key2", ...);
14
it->second.UpdateField();   // 여전히 OK

차이는 implementation detail이다. 사용자 코드는 Value ↔ Node만 바꾸면 된다(보통).

#내부 구현

#Slot 구조

1
ValueMap slot:   [ Key | Value ]                   in-place
2
NodeMap slot:    [ Node* ]                          heap node 가리킴
3
                       ↓
4
                  [ Key | Value ]  (별도 heap)

chunk 구조(14 slot + control byte)는 동일. 차이는 slot이 pointer라는 점.

1
// 약식 — folly/container/detail/F14Map-pre.h
2
template <typename Key, typename Value>
3
struct NodeContainerPolicy {
4
  using Item = std::pair<Key, Value>;
5
  using Slot = Item*;     // pointer만 chunk에
6

7
  static Item& itemAt(Slot& s) { return *s; }
8
  static Slot constructSlot(Item&& v, Allocator& a) {
9
    return new (a.allocate(1)) Item(std::move(v));
10
  }
11
};

Slot이 Item*이므로 rehash로 chunk가 옮겨져도 node pointer 자체는 그대로. node 메모리는 처음 emplace 시 할당하고 erase 전까지 안 옮긴다.

#Insert 동작

1
// 약식
2
auto emplace(K key, V value) {
3
  // 1. node를 먼저 heap에 할당
4
  auto* node = allocator_.allocate(1);
5
  new (node) Item(std::move(key), std::move(value));
6

7
  // 2. chunk에 slot pointer 저장 (rehash 가능)
8
  auto [slot, inserted] = tableEmplace(node->first, node);
9
  if (!inserted) {
10
    node->~Item();
11
    allocator_.deallocate(node, 1);
12
  }
13
}

allocation 한 번 extra. 큰 value면 chunk 안에 inline 저장보다 오히려 메모리가 작다(chunk가 빈 slot까지 reserve하므로).

#Rehash 비용

ValueMap rehash는 value를 새 chunk로 move. value의 move cost가 영향.

NodeMap rehash는 pointer만 복사. value는 옮기지 않으므로 rehash 비용이 작다(특히 큰 value에서).

1
N=10K, sizeof(V)=1KB
2
  F14ValueMap rehash:   ~10ms (move 10K개의 1KB)
3
  F14NodeMap  rehash:   ~0.1ms (pointer 10K개만)

ValueMap이 빠르려면 value가 작아야 한다. value가 커지면 NodeMap의 indirection 비용 < ValueMap의 move 비용.

#std/abseil 비교

1
// abseil
2
absl::node_hash_map<K, V> m;   // std-like pointer 안정
3

4
// std
5
std::unordered_map<K, V> std_map;   // pointer 안정 (chaining)
6

7
// folly
8
folly::F14NodeMap<K, V> f14n;

항목	std::unordered_map	absl::node_hash_map	folly::F14NodeMap
pointer 안정	O	O	O
iterator 안정	O (insert/erase 다른 노드는)	O	O
구조	chaining	Swiss + pointer slot	Swiss + pointer slot
Lookup	cache miss 많음	SIMD 가속	SIMD 가속
Insert allocation	node 매번	node 매번	node 매번

absl::node_hash_map과 사상 동일. 성능은 거의 같다. ValueMap 대비 lookup이 한 indirection만큼 (보통 10-20%) 느리다.

#코드 리뷰 포인트

1
// Bad — small value인데 NodeMap
2
folly::F14NodeMap<int, int> tiny;
3
// 매 entry마다 16-byte 정도 heap alloc
4

5
// Good
6
folly::F14ValueMap<int, int> tiny;   // chunk inline

value가 작으면 NodeMap의 heap allocation 오버헤드가 일반 lookup 비용을 압도한다. ValueMap 또는 FastMap.

1
// Good — 큰 value, 외부 pointer 필요
2
folly::F14NodeMap<UserId, UserProfile> profiles;
3
const UserProfile* p = &profiles.at(id);
4
// 다른 thread/chain이 p를 가져다 쓰는 동안 insert 안전

1
// Bad — value가 movable이라고 ValueMap을 쓰지만 lifetime 위반
2
folly::F14ValueMap<int, std::string> m;
3
auto& s = m[1];
4
m.insert({2, "..."});       // rehash 가능
5
s += "x";                   // UB
6

7
// Good — NodeMap
8
folly::F14NodeMap<int, std::string> mn;
9
auto& s = mn[1];
10
mn.insert({2, "..."});
11
s += "x";                   // OK

#안티패턴

mutex/atomic/condition_variable 같은 비이동 타입을 ValueMap에: rehash 시 move가 컴파일 에러 또는 UB. 항상 NodeMap.
node hash 함수와 key compare가 같지 않은 두 map을 섞기: extract/merge 시 ABI 호환이 깨진다. 두 map 모두 동일 trait.
node를 직접 delete 시도: extract() API로 안전한 ownership transfer. 임의 delete는 chunk 상태 무효화.