Время против памяти на примере хеш-таблиц на Java

[lNevermore]

Стало откровением, что forEach только от памяти зависит. Интересно так же, что по всем графикам видно, что hftc самая оптимальная для использования коллекция. Совпадение ли, но Вы и есть автор этих коллекций:)

Спасибо за статью, обязательно попробую hftc в своем проекте.

[leventov]

Это называется ошибкой выжившего. Я пилю эти коллекции больше года, а серьезно быстрее других они стали только пару недель назад. Пока бы не стали, я бы не публиковал эту статью :)

[doom369]

быстрее других они стали только пару недель назад

А что случилось пару недель назад, учитывая что последний коммит 3 мес. назад?

[leventov]

Последний коммит сегодня

[doom369]

Точно, перепутал с HPPC.

[Walrus]

где можно точно посмотреть сорцы hftc мапы? качать лень, на гитхабе черт ногу сломит ;)

[leventov]

В репе их по сути нет, только генераторы кода, которые давно прошли точку невозврата по запутанности. Я в таких случаях кидаю зависимость в проект и делаю go-to-definition в Идее.

[Walrus]

Это то я понял. В генераторах лень разбираться. ;) Билдить тоже. Кинь сюда сгенерированный код для метода get() из мапы ;)

[leventov]

LHash? QHash? Тип ключа и значения? Изменяемость мапы (Immutable, Updatable или Mutable)?

[Walrus]

Интересует выражение — путь от хэшкода до индекса ;)

[leventov]

Приведу код, который участвует в замерах выше, то есть интовые ключ и значение.

На лоадах вплоть до 0,6 используется линейный кеш:

UpdatableLHashParallelKVIntIntMapGO#get

@Override
public int get(int key) {
    int free;
    if (key != (free = freeValue)) {
        long[] tab = table;
        int capacityMask, index;
        int cur;
        long entry;
        if ((cur = (int) (entry = tab[index = ParallelKVIntKeyMixing.mix(key) & (capacityMask = tab.length - 1)])) == key) {
            // key is present
            return (int) (entry >>> 32);
        } else {
            if (cur == free) {
                // key is absent
                return defaultValue();
            } else {
                while (true) {
                    index = (index - 1) & capacityMask;
                    if ((cur = (int) (entry = tab[index])) == key) {
                        // key is present
                        return (int) (entry >>> 32);
                    } else if (cur == free) {
                        // key is absent
                        return defaultValue();
                    }
                }
            }
        }
    } else {
        // key is absent
        return defaultValue();
    }
}

Где ParallelKVIntKeyMixing это статический внутренний класс, который в данном случае выглядит так:

/** = round(2 ^ 32 * (sqrt(5) - 1)), Java form of unsigned 2654435769 */
static final int INT_PHI_MAGIC = -1640531527;
...
static class ParallelKVIntKeyMixing {
    static int mix(int key) {
        int h = key * INT_PHI_MAGIC;
        return h ^ (h >> 16);
    }
}

На лоадах от 0,7 и выше — квадратичный:

UpdatableQHashParallelKVIntIntMapGO#get

@Override
public int get(int key) {
    int free;
    if (key != (free = freeValue)) {
        long[] tab = table;
        int capacity, index;
        int cur;
        long entry;
        if ((cur = (int) (entry = tab[index = ParallelKVIntKeyMixing.mix(key) % (capacity = tab.length)])) == key) {
            // key is present
            return (int) (entry >>> 32);
        } else {
            if (cur == free) {
                // key is absent
                return defaultValue();
            } else {
                int bIndex = index, fIndex = index, step = 1;
                while (true) {
                    if ((bIndex -= step) < 0) bIndex += capacity;
                    if ((cur = (int) (entry = tab[bIndex])) == key) {
                        // key is present
                        return (int) (entry >>> 32);
                    } else if (cur == free) {
                        // key is absent
                        return defaultValue();
                    }
                    int t;
                    if ((t = (fIndex += step) - capacity) >= 0) fIndex = t;
                    if ((cur = (int) (entry = tab[fIndex])) == key) {
                        // key is present
                        return (int) (entry >>> 32);
                    } else if (cur == free) {
                        // key is absent
                        return defaultValue();
                    }
                    step += 2;
                }
            }
        }
    } else {
        // key is absent
        return defaultValue();
    }
}

ParallelKVIntKeyMixing тут такой:

static class ParallelKVIntKeyMixing {
    static int mix(int key) {
        return (key * INT_PHI_MAGIC) & Integer.MAX_VALUE;
    }
}

[Walrus]

По первому куску вопросов нет.
А во втором — длина таблицы не выводится до степени двойки? Чтобы избавится от '%'.

[leventov]

Так в этом весь смысл. Иначе зачем вообще нужен второй алгоритм. Он работает только с простыми длинами определенного вида. Размер степени двойки не позволяют гарантировать лоад больше 0,5, да и вообще в этом случае лоад слабоуправляем, поэтому для таких конфигураций выбирается второй алгоритм.

[Walrus]

Тогда можно поймать «division trolling effect» :)
www.youtube.com/watch?v=RGFJjQKChNQ примерно с 50 по 65 минуты ;)

[leventov]

Кстати, на хасвелле каком-нибудь эффект сохраняется?

И все-таки QHash в либе не для чистой скорости, а для ультранизкого потребления памяти, которое не достигается ни Trove, ни Mahout, ни тем более всеми остальными.

[Walrus]

да, на хасвелле тоже есть. ;)
Ну и да — на памяти можно выиграть гораздо больше.

[leventov]

И, кстати, в QHash одно деление на операцию, а не два, как в Trove и Mahout, где обычный двойной хеш.

[Teapot]

«Взятие значения по ключу (успешный поиск)» — это взятие всех ключей в порядке их укладки в мап? Даёт среднее 100 нс?

[leventov]

Порядок не имеет значения. Только на java.util.HashMap. Посмотрите в сырые результаты, там отклонение неправдоподобное, я чувствую, в замер подмешивается сборка мусора.

[Teapot]

А какую картину даёт сравнение объектных мапов в той же конфигурации?

[leventov]

Не мерил.

[Teapot]

Основание логарифма ~2.78, а рост таблицы ~x2. Значит для любой из 10 точек может легко получиться разница в 2 раза по памяти из-за разного алгоритма перестроения таблицы.

[leventov]

может легко получиться разница в 2 раза по памяти

Разница чего с чем? Не понял. В любом случае, код бенчмарков доступен, если считаете, что есть ошибка в методологии, укажите, или исправьте или перемеряйте.

[Teapot]

При заданном количестве элементов и лоад факторе «memory overuse» может легко поменяться в 2 раза, если например сравнивать одну и ту же структуру, но с условиями перестроения (N > threshold) и (N >= threshold).
Кроме того, логично делить испытания не по количествам элементов, а по соотношению org.openjdk.jol.info.GraphLayout.parseInstance(map).totalSize() и размеров L2 и L3.
Ещё действительно интересно, что улучшилось в hftc пару недель назад.

[leventov]

Наверное. Но это же проблемы реализаций, а не мои.

логично делить испытания не по количествам элементов, а по соотношению org.openjdk.jol.info.GraphLayout.parseInstance(map).totalSize() и размеров L2 и L3.

Целиком эти замеры занимали часов 12, кажется. Для такого насилия мне доступен только один сервер с одной конфигурацией CPU, L2 и L3.

что улучшилось в hftc пару недель назад

github.com/OpenHFT/hftc/issues/23

[Teapot]

А вариант раздельного хранения таблиц оставлен для случая гетерогенных данных или есть случаи, когда он даёт лучшие результаты?

[leventov]

Я таких случаев не нашел. Кстати, int-float и long-double тоже идут в параллель. Есть даже идея адаптировать схему для пар ключ-значение, которые различаются в 2 раза по ширине, например int-long, int-short.

[strcpy]

Koloboke нельзя использовать, там критическая дыра в алгоритме, переодически портятся данные: github.com/leventov/Koloboke/issues/66