Comments 28
Стало откровением, что
Спасибо за статью, обязательно попробую hftc в своем проекте.
forEach
только от памяти зависит. Интересно так же, что по всем графикам видно, что hftc самая оптимальная для использования коллекция. Совпадение ли, но Вы и есть автор этих коллекций:) Спасибо за статью, обязательно попробую hftc в своем проекте.
Это называется ошибкой выжившего. Я пилю эти коллекции больше года, а серьезно быстрее других они стали только пару недель назад. Пока бы не стали, я бы не публиковал эту статью :)
быстрее других они стали только пару недель назад
А что случилось пару недель назад, учитывая что последний коммит 3 мес. назад?
где можно точно посмотреть сорцы hftc мапы? качать лень, на гитхабе черт ногу сломит ;)
В репе их по сути нет, только генераторы кода, которые давно прошли точку невозврата по запутанности. Я в таких случаях кидаю зависимость в проект и делаю go-to-definition в Идее.
Это то я понял. В генераторах лень разбираться. ;) Билдить тоже. Кинь сюда сгенерированный код для метода get() из мапы ;)
LHash? QHash? Тип ключа и значения? Изменяемость мапы (Immutable, Updatable или Mutable)?
Интересует выражение — путь от хэшкода до индекса ;)
Приведу код, который участвует в замерах выше, то есть интовые ключ и значение.
На лоадах вплоть до 0,6 используется линейный кеш:
На лоадах от 0,7 и выше — квадратичный:
На лоадах вплоть до 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;
}
}
По первому куску вопросов нет.
А во втором — длина таблицы не выводится до степени двойки? Чтобы избавится от '%'.
А во втором — длина таблицы не выводится до степени двойки? Чтобы избавится от '%'.
Так в этом весь смысл. Иначе зачем вообще нужен второй алгоритм. Он работает только с простыми длинами определенного вида. Размер степени двойки не позволяют гарантировать лоад больше 0,5, да и вообще в этом случае лоад слабоуправляем, поэтому для таких конфигураций выбирается второй алгоритм.
Тогда можно поймать «division trolling effect» :)
www.youtube.com/watch?v=RGFJjQKChNQ примерно с 50 по 65 минуты ;)
www.youtube.com/watch?v=RGFJjQKChNQ примерно с 50 по 65 минуты ;)
Кстати, на хасвелле каком-нибудь эффект сохраняется?
И все-таки QHash в либе не для чистой скорости, а для ультранизкого потребления памяти, которое не достигается ни Trove, ни Mahout, ни тем более всеми остальными.
И все-таки QHash в либе не для чистой скорости, а для ультранизкого потребления памяти, которое не достигается ни Trove, ни Mahout, ни тем более всеми остальными.
И, кстати, в QHash одно деление на операцию, а не два, как в Trove и Mahout, где обычный двойной хеш.
«Взятие значения по ключу (успешный поиск)» — это взятие всех ключей в порядке их укладки в мап? Даёт среднее 100 нс?
А какую картину даёт сравнение объектных мапов в той же конфигурации?
Основание логарифма ~2.78, а рост таблицы ~x2. Значит для любой из 10 точек может легко получиться разница в 2 раза по памяти из-за разного алгоритма перестроения таблицы.
может легко получиться разница в 2 раза по памяти
Разница чего с чем? Не понял. В любом случае, код бенчмарков доступен, если считаете, что есть ошибка в методологии, укажите, или исправьте или перемеряйте.
При заданном количестве элементов и лоад факторе «memory overuse» может легко поменяться в 2 раза, если например сравнивать одну и ту же структуру, но с условиями перестроения (N > threshold) и (N >= threshold).
Кроме того, логично делить испытания не по количествам элементов, а по соотношению org.openjdk.jol.info.GraphLayout.parseInstance(map).totalSize() и размеров L2 и L3.
Ещё действительно интересно, что улучшилось в hftc пару недель назад.
Кроме того, логично делить испытания не по количествам элементов, а по соотношению org.openjdk.jol.info.GraphLayout.parseInstance(map).totalSize() и размеров L2 и L3.
Ещё действительно интересно, что улучшилось в hftc пару недель назад.
Наверное. Но это же проблемы реализаций, а не мои.
Целиком эти замеры занимали часов 12, кажется. Для такого насилия мне доступен только один сервер с одной конфигурацией CPU, L2 и L3.
github.com/OpenHFT/hftc/issues/23
логично делить испытания не по количествам элементов, а по соотношению org.openjdk.jol.info.GraphLayout.parseInstance(map).totalSize() и размеров L2 и L3.
Целиком эти замеры занимали часов 12, кажется. Для такого насилия мне доступен только один сервер с одной конфигурацией CPU, L2 и L3.
что улучшилось в hftc пару недель назад
github.com/OpenHFT/hftc/issues/23
А вариант раздельного хранения таблиц оставлен для случая гетерогенных данных или есть случаи, когда он даёт лучшие результаты?
Koloboke нельзя использовать, там критическая дыра в алгоритме, переодически портятся данные: github.com/leventov/Koloboke/issues/66
Sign up to leave a comment.
Время против памяти на примере хеш-таблиц на Java