Pull to refresh

Comments 17

Интересно, почему подход до сих пор не прижился в современных СУБД? На первый взгляд, скоростная многопоточная хеш таблица, — что может быть лучше для джойнов в OLAP запросах?
Для postgres есть проект, который позволяет проводить такие операции на gpu. (https://github.com/heterodb/pg-strom) Причем, он реально работает, особенно на большом количестве джойнов.

Я видимо ничего не понимаю, кто-нибудь объясните мне, зачем нужна хэш таблица которая умеет хранить только пары int,int? Почему нельзя просто взять массив int'ов? Какой вообще смысл хэшировать int?

Для массива int,int понадобится ~18 гигабайт памяти без учета выравнивания.
Но ведь у нас уже используется массив интов
uint32_t slot = hash(key);
Здесь мы получили хэш от ключа как беззнаковый инт32
hashtable[slot].value = value;
А здесь обратились к массиву по индексу хэша.
Размер массива в хэштаблице ограничен. Если взять просто массив, то его размер должен быть равен максимально возможному значению int. Это очень много. Особенно, если вы хотите хранить в таблице всего миллион записей, например.
Ага, нашел, пришлось лезть на хитхаб, вся магия в функции хэширования, там не просто murmur там его еще накладывают на размер таблицы.
__device__ uint32_t hash(uint32_t k)
{
k ^= k >> 16;
k *= 0x85ebca6b;
k ^= k >> 13;
k *= 0xc2b2ae35;
k ^= k >> 16;
return k & (kHashTableCapacity-1);
}

Только я все-равно не понимаю, зачем нужно было этот самый int хэшировать, сразу бы на размер таблицы наложили и все счастливы были.

Тогда вставка неравномерно распределенных ключей будет очень тормозит.

Так у нас же все-равно инты. На числах меньше размера таблицы колизии не будет, на числах больше начнутся колизии с периодом в размер таблицы. В той же Java hashcode от integer'a равен исходному значению.
Ну так если у нас, например, все ключи четные или кратны какому то еще числу, являющемуся степенью двойки? Тогда и хэши будут кратны этому числу и будет все печально.
Не будут же. Проблема будет только если все ключи кратны размеру таблицы. Или являются последовательностью c, c+n, c+2n, c+3n, c+4n. Где с — константа, а n — размер таблицы.
В таком случае возможное значение ключа будет вообще только одно.
Я писал о другом, причем в предположении, что размер хэш-таблицы — степень двойки, как здесь.
Допустим размер хэш таблицы 16, тогда для четных ключей возможны только 8 значений хэшей: 0, 2, 4, 8, 10, 12, 14, т.е. будет использоваться только половина таблицы. Если ключи кратны 4, то хэшей будет только 4 и использовать 1/4 таблицы и т.д.
будет использована вся таблица, просто будет больше коллизий и пролистываний. С другой стороны я не уверен, что для хэша будет меньше коллизий.
В данном алгоритме в любом случае будет использована вся таблица, но коллизий будет больше. В стандартных алгоритмах, будет использоваться не вся.
Это был просто пример данных, на которых такой подход — использование напрямую значения ключа в качестве хэша, будет работать неэффективно. Причем это достаточно реалистичный пример — например, такое может быть, если ключи являются адресами в памяти.
Ключи не удаляются с помощью функции delete и со временем загромождают таблицу.

Это больше похоже не на хэш-таблицу, а на хэш-свалку.
Присоединяюсь к предыдущему товарищу- а где такое применяется? и скорость 300 млн вставок в секунду- это скорость вставок куда? это явно чтото в озу- хочется понять для чего оно там нужно?
это не ОЗУ, это память видеокарты. Суть магии в том, что там овердофига ядер и можно давать бешеную параллельную нагрузку.
Only those users with full accounts are able to leave comments. Log in, please.