(video) Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step
Рассматривается в чем недостаток

std::unordered_map

и как написать свою более быструю реализацию мапы.
Исходники тут: abseil.

absl::flat_hash_map

- не поддерживает стабильные указатели на элементы мапы, так что в некоторых случаях придется использовать

std::unordered_map

или

absl::node_hash_map

.

Тесты
Для теста использовал

set<uint>

чтобы минимизировать затраты на выделение памяти и кэш промахи.
Также проверял tsl::sparse_set, spp::sparse_hash_set и самописные реализации, но все они были где-то посередине как по производительности так и по количеству аллокаций.

Ryzen 9 3900X

 
search test: 
  absl::flat_hash_set: 41.79 ms             alloc: 1 
  absl::node_hash_set: 77.90 ms  +86.4%     alloc: 1 999 557 
  std::unordered_set : 99.51 ms  +138.1%    alloc: 1 999 559 
insertion test: 
  absl::flat_hash_set: 35.91 ms             alloc: 1 
  absl::node_hash_set: 0.10 s  +187.3%      alloc: 1 999 545 
  std::unordered_set : 0.14 s  +279.6%      alloc: 1 999 547 

i5 8250U, LPDDR3

 
search test: 
  absl::flat_hash_set: 0.10 s 
  std::unordered_set : 0.14 s  +31.3% 
  absl::node_hash_set: 0.19 s  +82.2% 
insertion test: 
  absl::flat_hash_set: 67.56 ms 
  absl::node_hash_set: 0.12 s  +78.7% 
  std::unordered_set : 0.15 s  +128.7% 

По какой-то причине на интеле поиск по

absl::node_hash_set

оказался заметно медленее.
#cpp #cpu_opt

(video) CppCon 2021 - Branchless Programming
Интересные способы оптимизации ветвлений.
Рекомендуют использовать операторы + и | вместо || , а лучше выполнять обе ветви, записывать в массив tmp[2], затем

читать о

дно из значений.
Тернарный оператор ? часто выполняется без бранчей.
В некоторых случаях компилятор сам делает такие оптимизации.
#cpp #cpu_opt