Folly Code Review · 33/89

folly::F14FastMap — auto-select 동작

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

#한 줄 요약

F14FastMap은 sizeof(pair<K,V>)를 보고 컴파일 타임에 F14ValueMap(작은 value) 또는 F14VectorMap(큰 value)으로 alias 된다. 사용자가 trade-off를 고민하지 않아도 적절한 변형을 얻는다.

#동기

세 가지 변형(Value/Node/Vector)이 있으면 매번 무엇을 쓸지 결정해야 한다. 대부분의 코드는 굳이 차이를 고민할 필요가 없다 — 대충 빠르면 된다.

value가 작으면 chunk inline이 cache-friendly → ValueMap.
value가 크면 chunk slot에 큰 객체가 들어가면 메모리 낭비 → VectorMap.

이 결정을 컴파일러가 한다. sizeof(Item)이 임계치(48 byte) 이하면 ValueMap, 초과면 VectorMap.

1
folly::F14FastMap<int, int>             // → ValueMap (sizeof(pair) = 8)
2
folly::F14FastMap<std::string, BigObj>  // → VectorMap (sizeof(pair) > 48)

#API & 사용법

API는 ValueMap과 동일하다. 단, 어느 variant로 alias 되었느냐에 따라 세부 동작이 다르다.

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

3
folly::F14FastMap<int, std::string> small;
4
// VectorMap으로 dispatch (pair<int, string> = 40 bytes... 임계치 부근)
5

6
folly::F14FastMap<int, int> tiny;
7
// ValueMap (8 bytes)
8

9
folly::F14FastMap<std::string, std::array<char, 256>> big;
10
// VectorMap
11

12
// 모두 같은 인터페이스
13
small.emplace(1, "a");
14
small.find(1);
15
for (auto& [k, v] : small) { ... }

VectorMap이 선택된 경우 insertion order가 유지된다. ValueMap이면 순서 없다. 코드가 양쪽을 모두 동작해야 하면 순서를 가정하면 안 된다.

#내부 구현

#간단한 type dispatch

1
// 약식 — folly/container/F14Map.h
2
namespace detail {
3
  constexpr size_t kF14VectorMapThreshold = 24;
4

5
  template <typename K, typename V>
6
  using FastSelect = std::conditional_t<
7
      (sizeof(std::pair<K, V>) <= kF14VectorMapThreshold) &&
8
       folly::IsRelocatable<std::pair<K, V>>::value,
9
      F14ValueMap<K, V>,
10
      F14VectorMap<K, V>>;
11
}
12

13
template <typename K, typename V>
14
using F14FastMap = detail::FastSelect<K, V>;

(정확한 임계치와 trait는 folly 버전마다 다르다. core idea는 단순 if constexpr.)

조건:

sizeof(pair) ≤ 임계치 (작은 value).
is_trivially_relocatable (rehash move 안전).

둘 다 만족하면 ValueMap, 아니면 VectorMap.

#Trivially relocatable

folly는 자체 trait IsRelocatable을 가진다. std::pair, primitive, POD는 자동으로 relocatable. 사용자 타입은 다음과 같이 표시.

1
struct Big {
2
  std::array<char, 64> buf;
3
};
4
namespace folly { template <> struct IsRelocatable<Big> : std::true_type {}; }

relocatable이면 rehash 시 byte-wise memmove로 옮길 수 있어 ValueMap이 안전하다. 아니면 VectorMap이 선택돼 옮길 일이 적다.

#사용 결정 — 언제 FastMap

F14FastMap을 쓰는 경우:

정책을 정하기 번거롭고 그냥 빠른 것이면 된다.
workload가 lookup-heavy도, iteration-heavy도 명확하지 않다.
team 코드 베이스에서 일관성을 원한다.

명시적 선택을 쓰는 경우:

lookup만 한다면 F14ValueMap.
순회/snapshot이 잦다면 F14VectorMap.
pointer 안정성이 필요하면 F14NodeMap.
큰 value이고 erase가 잦다면 F14NodeMap (VectorMap의 swap-pop 회피).

대부분 새 코드는 F14FastMap이 default.

#std/abseil 비교

abseil에는 자동 선택이 없다. flat_hash_map 또는 node_hash_map을 사용자가 명시.

항목	abseil	folly
자동 선택	X	F14FastMap
명시 variants	flat, node	Value, Node, Vector
Insertion order	X	VectorMap만
Trait based	X	`is_trivially_relocatable`

folly의 FastMap은 abseil 식 명시적 선택에 대한 한 가지 답. 코드 작성 부담을 낮춘다.

#코드 리뷰 포인트

1
// Good — 일반적 경우 FastMap
2
folly::F14FastMap<int, int> counters;
3

4
// Bad — pointer 안정성 필요한데 FastMap
5
folly::F14FastMap<int, std::string> m;
6
auto* p = &m[1];
7
m[2] = "...";   // rehash 가능, ValueMap으로 alias 되면 UB

FastMap이 어느 variant인지 모르므로 reference 안정성을 요구하는 코드는 명시적으로 NodeMap. FastMap은 “포인터 유지 안 한다”는 약속.

1
// 주의 — order에 의존하면 FastMap 안 됨
2
folly::F14FastMap<int, int> m;
3
m.insert({1, 1}); m.insert({2, 2});
4
for (auto& [k, v] : m) {
5
  // 순서가 1, 2일 수도, 2, 1일 수도
6
}

FastMap의 순서는 컴파일 결과에 따라 다르다. 순서가 의미 있으면 F14VectorMap을 명시.

1
// Good — value 크기 명시적
2
struct Stat { uint64_t count; uint64_t total; };  // 16 byte
3
folly::F14FastMap<int, Stat> stats;  // ValueMap으로 dispatch

작은 POD value면 FastMap이 ValueMap을 선택해 최적.

#안티패턴

F14FastMap을 NodeMap 대체로 사용: FastMap은 절대로 NodeMap을 선택하지 않는다. pointer 안정성 필요하면 NodeMap 명시.
value type을 incomplete type으로 FastMap에: sizeof(pair)를 계산해야 하므로 complete type 필요. forward declared type은 못 씀.
순서가 깨지는 곳에서 VectorMap default 가정: FastMap이 int → int 같은 작은 type을 받으면 ValueMap 선택. 순서 없다.