Pull to refresh

64-битный hashmap в JS

Reading time1 min
Views7.4K

Как бы вы сделали быстрый 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 :)

Only registered users can participate in poll. Log in, please.
Что вы знаете про hashmap-ы?
32.84% Первый раз слышу22
44.78% Знаю как пользоваться30
14.93% Могу сделать сам не хуже чем std::unordered_map10
7.46% Я знаю про hashmap-ы всё5
67 users voted. 20 users abstained.
Tags:
Hubs:
Total votes 7: ↑4 and ↓3+1
Comments8

Articles