28.05.2018 07:41
ankh1989 8 3000 Источник

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

Комментарии (8)


  1. dom1n1k
    28.05.2018 12:18
    #15991339

    Ни запушить, ни даже толком отладить на этом компьютере ничего не могу, поэтому код наверняка неправильный. Но идею демонстрирует.

    Код
    module.exports = class {
    constructor() {
        this._data = new Map;
        this._i32 = new Int32Array(2);
    }

    get([hi, lo]) {
        this._i32[0] = lo;
        this._i32[1] = hi;
        return this._data.get((new Float64Array(this._i32.buffer))[0]);
    }

    set([hi, lo], obj) {
        this._i32[0] = lo;
        this._i32[1] = hi;
        return this._data.set((new Float64Array(this._i32.buffer))[0]);
    }

    *entries() {
        for (const [key, obj] of this._data.entries()) {
            let [lo, hi] = new Int32Array(key.buffer);
            yield [[+hi, +lo], obj];
        }
    }
};


    1. ankh1989 Автор
      28.05.2018 12:36
      #16008165

      Интересно. Сделал PR: github.com/cd48b153/hashmap-contest/pull/2. Сейчас посмотрим как оно будет работать.


    1. ankh1989 Автор
      28.05.2018 12:44
      #16008641

      Не прокатило: там что то не сходится (скорее всего потому что не всякие 64 бита будут валидным `double`), но даже если бы сходилось, то получается в 3 раза медленнее чем list-based hashmap. Можно попробовать брать не все 64 бита, а скажем 60 (53 точно можно), а остальные складывать в небольшой массив (16 элементов если берём 60 бит).


    1. mayorovp
      28.05.2018 12:56
      #16017085

      Что-то в этом коде неправильно, но не могу понять что. Даже после исправлений в виде добавления , obj в метод set и создания массива в entries (key — число, у него нет буфера) он все еще выдает неправильный результат.


      Кстати, у этого кода есть еще проблема с NaN и -0, но в тестах они не встречаются.


      1. ankh1989 Автор
        28.05.2018 13:29
        #16052693

        Именно в NAN/0 проблема. Если пара (lo, hi) превращается в NAN/0, я их отправляю в отдельный hashmap. Тогда всё работает и весьма быстро (но медленнее чем list-based hashmap): см. коммент в PR.


  1. vmb
    28.05.2018 19:00
    #16651017
    +1

    A BigInt не поможет?
    https://developers.google.com/web/updates/2018/05/bigint


    1. ankh1989 Автор
      29.05.2018 02:56
      #18617811

      В последнем node его ещё нет.


      1. vmb
        29.05.2018 03:06
        #18665227
        +1

        Насколько я знаю, обновление V8 с 6.6 до 6.7 произойдёт уже скоро, ещё в Node.js 10.