#rustm — Public Fediverse posts
Live and recent posts from across the Fediverse tagged #rustm, aggregated by home.social.
-
HashMap в Rust: SwissTable, SIMD по 16 байт за раз и RawTable, который от вас спрятали
Привет, Хабр! Признавайтесь: вы пользуетесь std::collections::HashMap примерно каждый день и ни разу не задумывались, что под ним. А под ним, если коротко, сидит алгоритм от Google. С Rust 1.36 (это лето 2019-го) стандартный HashMap это порт SwissTable, той самой структуры из абсейловского flat_hash_map . До этого там был Robin Hood hashing, и если вы где-то ещё видите описание std-мапы как «linear probing and Robin Hood bucket stealing», знайте: оно протухло, актуальная документация уже пишет «quadratic probing and SIMD lookup». И вот «SIMD lookup» это самое интересное. Весь фокус скорости SwissTable держится на одном байте служебных данных на элемент, который сканируется по 16 штук за одну инструкцию процессора. В статье глянем, как это устроено внутри, почему ваша мапа по умолчанию устойчива к hash DoS и платит за это скоростью, когда в проде стоит переходить на FxHash, и почему низкоуровневый RawTable существует, но в публичном HashMap его спрятали. Будет много кода и немного ассемблерной романтики .