Почти всегда в многопоточном коде нужны mutex'ы, и я достаточно часто видел во всех языках без исключения код который берёт лок у модифицированной хэштаблицы. Наверное, не стоит объяснять, что такое нужно достаточно часто
Псевдокод:
В хэш таблицах всегда вычисляется хэш ключа при добавлении и при поиске. В итоге вычисляется хэш, потом идёт поиск или вставка, во втором случае контейнер меняется.
Погодите-ка, а весь вычисление хэша никак не связано с изменениями контейнера, зачем его то под лок брать? В итоге если есть две операции с ключами key1, key2, то будет
Я написал какой-то простецкий бенчмарк, он показал для hinted vs non hinted версий следующий результат для строк размера 64 и 2млн элементов в хэш-таблице
В последнее время latency проблемы всё больше и больше нахожу через сausal profiler (coz), который замедляет всю остальную программу помимо сегментов, которые вы поставите, и он смотрит на то, как изменилось время исполнения из-за этого. Поистине прекрасная идея.
[1] absl::flat_hash_map с ::find(key, hash)
[2] Микробенчмарк
[3] Container insert with hint (другой хинт, по итераторам, не по хэшу)
[4] Causal Profiler (в README есть великолепные видео и презентации)
Псевдокод:
class LockedHashTable {
public:
Optional<Value> Find(const Key& k) {
MutexLock lock(mu_);
return map_.find(k);
}
void Insert(const Key& k, const Value& v) {
MutexLock lock(mu_);
return map_.insert(k, v);
}
private:
Mutex mu_;
HashMap map_;
};
От лока не избавиться, так как есть две параллельные операции, одна из которых это запись.В хэш таблицах всегда вычисляется хэш ключа при добавлении и при поиске. В итоге вычисляется хэш, потом идёт поиск или вставка, во втором случае контейнер меняется.
Погодите-ка, а весь вычисление хэша никак не связано с изменениями контейнера, зачем его то под лок брать? В итоге если есть две операции с ключами key1, key2, то будет
hash key1
find key1
hash key2
find key2
или hash key2
find key2
hash key1
find key1
В С++ Abseil есть отдельная перегрузка функции .find именно для этого, она принимает вторым аргументом значение хэша, чтобы сэкономить на его вычислении. В итоге теперь мы разрешим исполнять вычисление хэша в параллель:class LockedHashTable {
public:
Optional<Value> Find(const Key& k) {
size_t hash = hash<Key>()(k);
MutexLock lock(mu_);
return map_.find(k, hash);
}
void Insert(const Key& k, const Value& v) {
MutexLock lock(mu_);
return map_.insert(k, v);
}
private:
Mutex mu_;
HashMap map_;
};
hash key1, key2
find key1
find key2
илиhash key1, key2
find key2
find key1
Такие оптимизации сложно заметить на графиках потребления CPU, количество циклов никак не уменьшилось, но зато такие оптимизации уменьшают latency программ, а latency мы всё ещё плохо умеем выражать через обычный тулинг:Я написал какой-то простецкий бенчмарк, он показал для hinted vs non hinted версий следующий результат для строк размера 64 и 2млн элементов в хэш-таблице
Benchmark Time CPU Iterations UserCounters...
BM_HashTable/64/2097152/threads:1 294 ns 294 ns 2401796 String Size=64 Use hinted=0
BM_HashTable/64/2097152/threads:2 314 ns 560 ns 1109024 String Size=64 Use hinted=0
BM_HashTable/64/2097152/threads:4 413 ns 863 ns 778116 String Size=64 Use hinted=0
BM_HashTable/64/2097152/threads:8 382 ns 825 ns 837920 String Size=64 Use hinted=0
BM_HashTable/64/2097152/threads:16 377 ns 817 ns 830112 String Size=64 Use hinted=0
BM_HashTable/64/2097152/threads:1 292 ns 290 ns 2433275 String Size=64 Use hinted=1
BM_HashTable/64/2097152/threads:2 240 ns 479 ns 1397926 String Size=64 Use hinted=1
BM_HashTable/64/2097152/threads:4 198 ns 692 ns 869408 String Size=64 Use hinted=1
BM_HashTable/64/2097152/threads:8 209 ns 843 ns 775768 String Size=64 Use hinted=1
BM_HashTable/64/2097152/threads:16 208 ns 707 ns 777776 String Size=64 Use hinted=1
CPU time почти не уменьшилось, зато как уменьшилось суммарное время бенчмарка. В других языках (например, в Rust) или даже том же C++ STL такого не нашёл (find с хинтом по хэшу).В последнее время latency проблемы всё больше и больше нахожу через сausal profiler (coz), который замедляет всю остальную программу помимо сегментов, которые вы поставите, и он смотрит на то, как изменилось время исполнения из-за этого. Поистине прекрасная идея.
[1] absl::flat_hash_map с ::find(key, hash)
[2] Микробенчмарк
[3] Container insert with hint (другой хинт, по итераторам, не по хэшу)
[4] Causal Profiler (в README есть великолепные видео и презентации)