Как бы вы сделали быстрый hashmap для 64-битных ключей? Если ключи 32-битные, то вряд ли можно сделать что то быстрее чем встроенный ES6 Map, но если ключи 64 битные, то начинаются сложности потому что JS застрял на 32-битном int.
На эту задачу я наткнулся когда надо было сравнить два довольно больших дампа памяти: текстовый файл слева где каждая строчка это 64-битный адрес и тип переменной, и аналогичный файл справа. В каждом файле примерно по миллиону адресов и лишь 50 тысяч из них разные.
Ради интереса я написал несколько простых hashmap-ов и сравнил их на аналогичной задаче: даны два массива пар ключ-значение, где ключ это два 32-битных числа, оба массива больше миллиона элементов и разница между ними 10-100 тысяч элементов — надо найти эту разницу и сгруппировать её по значениям. Получилось, что самый быстрый вовсе не встроенный Map а самописный (на JS) стандартный hashmap с списками для ключей с одинаковыми хешами.
https://github.com/cd48b153/hashmap-contest
| 1M-50K | 2M-100K | 3M-5K | |
|---|---|---|---|
| es6-concat | 1.00 | 0.98 | 0.81 |
| es6-stack | 0.57 | 0.49 | 0.55 |
| hashmap | 1.95 | 2.13 | 1.99 |
| list | 0.41 | 0.27 | 0.25 |
| naive-stack | 1.33 | 1.27 | 1.33 |
| naive | 1.00 | 1.00 | 1.00 |
| trie | 0.75 | 0.74 | 0.58 |
Конструкция вида Map<Map<int, string>> оказывается в 2 раза медленнее самописного hashmap-а. В качестве точки отсчёта взят "наивный" hasmap на основе {}. Самым же медленным оказался npm.js hashtable который написан на C++ и использует std::unordered_map. В таблице его нет потому он портит память и крашит node, но в среднем его скорость была на уровне 2.5, то есть в 2.5 раза медленнее чем наивный {} hashmap.
Кто нибудь сможет сделать быстрее чем мой самописный hashmap? PRs welcome :)