Поиск по известному набору целочисленных ключей
Gperf постоянно уступает массиву Judy в моей среде, и мне интересно, есть ли еще одна совершенная библиотека хешей, созданная специально для целочисленных ключей. Я заранее знаю набор ключей, и я хотел бы использовать это в качестве преимущества производительности / размера.
Есть ~1000 ключей, и поиск не в последовательном порядке. Пары ключей являются целыми числами. Ключи 32-битные, а полученные значения 8-битные. Размер является наиболее важным фактором.
Если есть способ настроить Gperf для целочисленных клавиш или просто другой подход в целом, я тоже на уши.:)
(Sidenote:... Когда я набирал этот вопрос, я понял, что бинарный поиск, вероятно, забирает торт, и я просто обдумал проблему. Я все еще хотел бы услышать любые ваши мысли, чтобы узнать, хоть!)
Изменить: ключи не распределяются равномерно. Большинство из них случайно сгруппированы по всему возможному диапазону.
Правка 2: бинарный поиск в худшем случае был слишком медленным, на мой вкус, поэтому я в конечном итоге поиграл с ключами, пока не нашел 8 бит для каждого из них, чтобы получить 256 хорошо распределенных сегментов. Я держал минимальное и максимальное значения каждого сегмента (24 бита для каждого элемента сегмента) и создал один большой массив структур для пар ключей. По номиналу / быстрее и меньше, чем все остальное, что я тестировал для моего конкретного случая, так что я думаю, что я собираюсь с этим сейчас.:)
5 ответов
Держите ваши ключи отсортированными и используйте M-дерево для получения любого ключа.
M-дерево имеет M записей на узел, вместо 2 для двоичных файлов. Это очень поможет для производительности. Используйте размер строки кэша в качестве основы размера вашего узла, следовательно, 64 байта. Вы можете хранить 16 32-битных значений в этом размере.
Поскольку у вас есть 1000 значений, для получения правильного ключа будет достаточно 3 уровней (в отличие от 10 уровней для двоичного дерева).
Другая идея заключается в том, чтобы хэшировать ваши ключи в небольшую хеш-таблицу, такую как 12-битная (4K записи), и решать потенциальные коллизии с помощью простой цепочки. Скорее всего, вы получите большинство своих ключей в одном поиске.
/*
** Proof of concept for constructing a {fixed-size,lookup-only} hashtable
** needing only (2*N* sizeof(int)) additional storage for storing N num=value pairs.
** The key is supposed to be an int,
** the 'value' is a char.
** Note: some people would like to include <stdint.h> and replace all the ints by {uint32_t,uint16_t,uint8_t}.
**
** (c)opyright Wildplasser, 2011-11-12
** href = http://stackru.com/questions/8059591/lookups-on-known-set-of-integer-keys
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
struct tinyhash {
unsigned key;
unsigned short link;
unsigned char value;
unsigned is_linked :1;
};
#define LINK_DEAD ((unsigned short)-1)
/* A hashtable with N slots for N entries (100% full) */
#define THE_SIZE 1000
struct tinyhash table[THE_SIZE] ;
void tiny_fill(void);
void tiny_init(void);
int tiny_find(unsigned key);
void tiny_print(void);
void tiny_count(void);
static int tiny_cmp( const void *l, const void *r);
static unsigned short * tiny_hnd(unsigned key);
static unsigned tiny_hash(unsigned key);
int main (void)
{
assert(sizeof table == 2 * THE_SIZE * sizeof(int));
fprintf (stderr, "Size=%u\n", (unsigned int) sizeof table);
tiny_fill();
tiny_init();
tiny_print();
tiny_count();
return 0;
}
/* Perform a table lookup.
** Return the "value" that belongs to "key"..
** If not found -1 is returned.
*/
int tiny_find(unsigned key)
{
unsigned short *ptr;
ptr = tiny_hnd(key);
return *ptr==LINK_DEAD ? -1 : table[*ptr].value ;
}
/* Find the place where key is located, or
** (if not found) where it should be appendend.
** The returned value is a pointer to the parent's .link field.
*/
static unsigned short * tiny_hnd(unsigned key)
{
unsigned hash;
unsigned short slot, *ptr;
hash = tiny_hash(key);
slot = hash % THE_SIZE;
for (ptr = &table[slot].link; *ptr != LINK_DEAD; ptr = &table[*ptr].link ) {
if ( !table[*ptr].is_linked ) break;
if ( table[*ptr].key == key) break;
}
return ptr;
}
/* For testing: fill hashtable with garbage */
void tiny_fill(void)
{
unsigned idx;
for (idx=0; idx < THE_SIZE; idx++ ) {
table[idx].key = rand() + 543 * rand();
table[idx].value = rand() ;
table[idx].link = LINK_DEAD;
table[idx].is_linked = 0;
}
}
/* Build hashtable, that is:
** shuffle the entries and build linked list.
*/
void tiny_init(void)
{
unsigned idx;
/* Phase 0: set all to unused.
** The link field is temporaly abused to store the intended
** slotnumber.
*/
for (idx=0; idx < THE_SIZE; idx++ ) {
table[idx].link = tiny_hash(table[idx].key) % THE_SIZE;
table[idx].is_linked = 0;
}
/* Phase 0a: sort on (intended) slotnumber. */
qsort (table, THE_SIZE, sizeof table[0] , tiny_cmp);
/* Phase 1: put enties at their intended slotnumber
** but only if the entry that lives there does not belong there
** (is uninitialized).
*/
for (idx=0; idx < THE_SIZE; idx++) {
unsigned slot;
/* [idx] has allready been placed */
if (table[idx].is_linked) continue;
slot = table[idx].link;
/* [idx] belongs here. freeze it */
if (slot==idx) {
table[idx].link = LINK_DEAD;
table[idx].is_linked = 1;
}
/* try to swap [idx] with the item at its intended slot */
else {
struct tinyhash tmp;
/* item[slot] belongs there: keep off */
if (table[slot].is_linked) continue;
tmp = table[idx];
table[idx] = table[slot];
table[slot] = tmp;
table[slot].is_linked = 1;
table[slot].link = LINK_DEAD;
/* Don't bump idx: [idx] and [slot] have been swapped,
** we need to inspect the new item[idx] at the next cycle.
*/
idx--; /* idx will be re-incremented in the loop; */
}
}
/* Phase 2: link any remaining unplaced item to its
** parent in the LL-chain.
*/
for (idx=0; idx < THE_SIZE; idx++ ) {
unsigned short *parent;
if (table[idx].is_linked) continue;
parent = tiny_hnd(table[idx].key);
if (*parent != LINK_DEAD) continue; /* duplicate */
*parent = idx;
table[idx].is_linked = 1;
table[idx].link = LINK_DEAD;
}
}
/* Compare function for qsort()
*/
static int tiny_cmp( const void *vl, const void *vr)
{
struct tinyhash *l = (struct tinyhash *)vl;
struct tinyhash *r = (struct tinyhash *)vr;
#if 0
unsigned slot_l, slot_r;
slot_l = tiny_hash(l->key) %THE_SIZE;
slot_r = tiny_hash(r->key) %THE_SIZE;
if (slot_l < slot_r ) return -3;
if (slot_l > slot_r ) return 3;
#else
if (l->link < r->link ) return -3;
if (l->link > r->link ) return 3;
#endif
if (l->key < r->key) return -2;
if (l->key > r->key) return 2;
if (l < r) return -1;
if (l > r) return 1;
return 0;
}
/* Stupid hashfunction, to be replaced with something usefull..
** (works good for random ints) Use at your own risk.
*/
static unsigned tiny_hash(unsigned key)
{
return key * 98765;
}
void tiny_print(void)
{
unsigned idx;
for (idx=0; idx < THE_SIZE; idx++ ) {
unsigned slot;
int dir;
slot = tiny_hash(table[idx].key) % THE_SIZE;
dir = (slot==idx) ? '=' : (slot>idx) ? '<': '>';
fprintf(stderr, "[%4x] %c %4x: %4x %c %10u->%3u\n"
, idx, dir, 0xffff & slot
, 0xffff & table[idx].link
, table[idx].is_linked ? '*' : '.'
, table[idx].key,table[idx].value
);
}
}
/* For testing: print the hashchains, construct a histogram of chainlengths,
** and calculate the "total cost of retrieval".
*/
void tiny_count(void)
{
unsigned idx, cnt, len, tothops, slot;
unsigned histogram[THE_SIZE];
memset(histogram, 0, sizeof histogram);
cnt=tothops=0;
for (slot =0; slot < THE_SIZE; slot++ ) {
idx = tiny_hash(table[slot].key) % THE_SIZE;
if (slot!=idx) continue; /* this is not the start of a chain */
for (len=0 ; idx != LINK_DEAD; idx = table[idx].link) {
if (!table[idx].is_linked) continue;
if (len==0) fprintf(stderr, "[%u]:", slot);
fprintf(stderr, " %u", table[idx].key);
len++;
}
fprintf(stderr, "(=%u)\n", len);
cnt += len;
histogram[len] += 1;
tothops += (((len+1) *len)/2);
}
fprintf(stderr, "Histogram of chainlengths:\n");
for (len=0; len < THE_SIZE; len++) {
if (!histogram[len]) continue;
fprintf(stderr, "[%u]: %u\n", len, histogram[len]);
}
fprintf(stderr, "tothops=%u/%u (%f hops per node)\n"
, tothops, cnt, (double)tothops/cnt);
}
Результат: (хорошо: часть этого)
....
[978]: 1794172570(=1)
[980]: 642121828(=1)
[983]: 2674104091(=1)
[985]: 547527125(=1)
[986]: 2383911594(=1)
[988]: 4254837348(=1)
[989]: 1860851825 1990214465 1766290905(=3)
[990]: 3793608270 469685686(=2)
[992]: 1189958296 872917240(=2)
[994]: 1999781290 1501026482(=2)
[995]: 520334159 211600319(=2)
[997]: 177583921(=1)
[998]: 1173163646 1013572158(=2)
[999]: 1705614211 3460318251(=2)
Histogram of chainlengths:
[1]: 369
[2]: 190
[3]: 57
[4]: 15
[5]: 4
tothops=1491/1000 (1.491000 hops per node)
Примечание: из-за сортировки при инициализации хеш-таблицы записи находятся очень близко к месту, где они ожидаются. Это увеличивает местность ссылки.
Вы пробовали массивы Джуди? Может быть именно то, что вам нужно.
Я расширил gperf и nbperf для целочисленных наборов ключей.
Я заранее знаю набор ключей, и я хотел бы использовать это для получения преимущества в производительности/размере.
Если это означает то, что я думаю, это означает (вы знаете наборы ключей (и значений) заранее, как и во время компиляции), вы также можете создать функцию поиска из своих данных. Иногда это имеет смысл, например, во встроенных системах, где у вас много ПЗУ и мало ОЗУ.
Вот идея:
- С отсортированным набором пар ключ-значение (отсортированным по ключу) вы можете построить функцию, которая реализует дерево с потоком управления, проверяя биты от наиболее значащих до наименее значимых. Таким образом, при не более чем 32 (32-битных ключа) сравнениях в худшем случае вы найдете значение, принадлежащее вашему ключу. В среднем гораздо меньше (не берусь предположить, 32/2 ли это, потому что уже поздно).
Никто не хотел бы писать такую тяжелую функцию if-then-else вручную, но эй, если код сгенерирован, это половина боли (и двойное удовольствие от написания генератора). Кроме того, этот подход не нуждается ни в куче, ни в указателях, ни в сложных структурах данных, поэтому совершенно тривиально показано, что он «безвреден». Опять же, иногда это именно то, что вам нужно в некоторых (критических) встроенных системах.
Опять же, жизнеспособность этого варианта также зависит от процессора. Встроенные процессоры редко имеют длинные конвейеры и модули прогнозирования ветвлений и все то современное, что мы часто принимаем как должное в настольных средах AMD/INTEL. Таким образом, это может не так сильно влиять на производительность этих более примитивных процессоров, как может показаться на первый взгляд.
Давайте намочим пальцы, написав функцию, которая генерирует наш «известный заранее» список пар ключ-значение.
(defun random-value ()
"Returns a random byte (0..255)"
(random 256))
(defun random-key-value-mapping (&optional (nkeys 1000))
"Generates 'nkeys pairs of unique random 32 bit integers with random values."
(let ((max-value (ash 1 32))
(ht (make-hash-table :size nkeys)))
(loop
with n = 0
while (< n nkeys)
for key = (random max-value)
when (null (nth-value 1 (gethash key ht)))
do (setf (gethash key ht) (random-value))
(incf n))
(sort
(loop
for k being the hash-keys of ht
for v = (gethash k ht)
collecting (cons k v))
#'<
:key #'first)))
Эта функция возвращает довольно скучный список пар:
CL-USER> (defparameter *kvs* (random-key-value-mapping 10))
CL-USER> *kvs*
((609397212 . 141) (676943009 . 17) (1196140740 . 26) (2084672536 . 89)
(2348838239 . 16) (3437178460 . 59) (4111000746 . 82) (4112460519 . 228)
(4144164697 . 250) (4168664243 . 55))
;;;; looks in binary like this:
CL-USER> (loop for (k . v) in *kvs* do (format t "~32,'0b ~8,'0b~%" k v))
00100100010100101010100111011100 10001101
00101000010110010101010010100001 00010001
01000111010010111010100011000100 00011010
01111100010000011001010000011000 01011001
10001100000000000110110101011111 00010000
11001100110111110010111001011100 00111011
11110101000010001110010010101010 01010010
11110101000111110010101011100111 11100100
11110111000000101110111101011001 11111010
11111000011110001100010010110011 00110111
С приведенным выше бинарным дампом уже легко увидеть, к чему все идет. Просто взглянув на MSB (старший значащий бит), наше (двоичное) дерево разбивает набор на 4 элемента, у которых есть 0, и 6 элементов, у которых есть 1.
Впоследствии мы делаем это снова с этими подмножествами, со следующим битом (от MSB к LSB). Функция, делающая это, я назвал
(defun prefix-tree (kmsb kvs)
(if (< kmsb 0)
(list :leaf (mapcar #'rest kvs))
(let* ((mask (ash 1 kmsb))
(split
(multiple-value-list
(loop
for kv in kvs
if (/= 0 (logand (first kv) mask))
collecting kv into ups
else
collecting kv into downs
finally (return (values ups downs))))))
(list
:node
mask
:pos
kmsb
:ups
(when (first split)
(let ((n (length (first split))))
(if (= 1 n)
(list :leaf (list (rest (first (first split)))))
(prefix-tree (- kmsb 1) (first split)))))
:downs
(when (second split)
(let ((n (length (second split))))
(if (= 1 n)
(list :leaf (list (rest (first (second split)))))
(prefix-tree (- kmsb 1) (second split)))))))))
Первый дополнительный аргумент уже есть, так что рекурсия работает. Как это выглядит, когда мы запускаем это в нашем списке ключей-значений?
CL-USER> (prefix-tree 31 *kvs*)
(:NODE 2147483648 :POS 31 :UPS
(:NODE 1073741824 :POS 30 :UPS
(:NODE 536870912 :POS 29 :UPS
(:NODE 268435456 :POS 28 :UPS
(:NODE 134217728 :POS 27 :UPS (:LEAF (55)) :DOWNS
(:NODE 67108864 :POS 26 :UPS
(:NODE 33554432 :POS 25 :UPS (:LEAF (250)) :DOWNS
(:NODE 16777216 :POS 24 :UPS
(:NODE 8388608 :POS 23 :UPS NIL :DOWNS
(:NODE 4194304 :POS 22 :UPS NIL :DOWNS
(:NODE 2097152 :POS 21 :UPS NIL :DOWNS
(:NODE 1048576 :POS 20 :UPS (:LEAF (228)) :DOWNS (:LEAF (82))))))
:DOWNS NIL))
:DOWNS NIL))
:DOWNS NIL)
:DOWNS (:LEAF (59)))
:DOWNS (:LEAF (16)))
:DOWNS
(:NODE 1073741824 :POS 30 :UPS
(:NODE 536870912 :POS 29 :UPS (:LEAF (89)) :DOWNS (:LEAF (26))) :DOWNS
(:NODE 536870912 :POS 29 :UPS
(:NODE 268435456 :POS 28 :UPS NIL :DOWNS
(:NODE 134217728 :POS 27 :UPS (:LEAF (17)) :DOWNS (:LEAF (141))))
:DOWNS NIL)))
Если вы посмотрите на это дерево под прямым углом, оно уже почти похоже на C-код, не так ли? Структура if-then-else в результирующем коде уже видна.
Теперь осталось сделать скучную часть. Создайте код из этой древовидной структуры. Я не буду подробно останавливаться на этом. Просто код.
(defvar *indent* 0)
(defvar *spacing* 2)
(defvar *cout* t)
(defun indent ()
(incf *indent*))
(defun outdent ()
(decf *indent*))
(defun iformat (format-string &rest args)
(apply
#'format
(append (list *cout*
(format nil "~~&~~~D,0t~A" (* *indent* *spacing*) format-string))
args)))
(defun if-else-forest (pt path)
(cond
((null pt)
(iformat "return false;"))
((eq :leaf (first pt))
(iformat "*pv = ~D;" (first (second pt)))
(iformat "return true;"))
((eq :node (first pt))
(let ((mask (getf pt :node))
(ups (getf pt :ups))
(downs (getf pt :downs)))
(when ups
(let ((new-path (logior path mask)))
(iformat "if (0x~X == (k & 0x~X)) {" new-path new-path)
(indent)
(if-else-forest ups new-path)
(outdent)
(iformat "}")))
(when downs
(iformat "if (0x~X == (k & 0x~X)) {" path path)
(indent)
(if-else-forest downs path)
(outdent)
(iformat "}"))))))
(defun print-kvp (stream kvp &optional colon-p at-sign-p)
(declare (ignore colon-p at-sign-p))
(let ((*cout* stream))
(iformat "{~D, ~D}" (first kvp) (rest kvp))))
(defun create-test-code (pt kvs)
(declare (ignorable pt))
(iformat "typedef struct KVP_tag { uint32_t key; uint8_t value; } KVP_t;")
(iformat "#define N_KVP ((size_t)~D)" (length kvs))
(iformat "static const KVP_t s_kvp[N_KVP] = {")
(indent)
(iformat "~{~/print-kvp/~^, ~}" kvs)
(outdent)
(iformat "};")
(iformat "int main (int argc, const char* argv[]) {")
(indent)
(iformat "size_t fail_count = 0;")
(iformat "for (size_t i = 0; i < N_KVP; i++) {")
(indent)
(iformat "uint32_t key = s_kvp[i].key;")
(iformat "uint8_t expected_value = s_kvp[i].value;")
(iformat "uint8_t found_value;")
(iformat "if (lookup_key(key, &found_value)) {")
(indent)
(iformat "if (found_value != expected_value) {")
(indent)
(iformat "fail_count++;")
(iformat "printf(\"ERROR: for key %d (expected: %d) %d was found.\\n\", key, expected_value, found_value);")
(outdent)
(iformat "}")
(outdent)
(iformat "} else {")
(indent)
(iformat "fail_count++;")
(iformat "printf(\"lookup_key(%x) failed.\", key);")
(outdent)
(iformat "}")
(outdent)
(iformat "}")
(iformat "printf(\"%zu out of %zu tests failed.\\n\", fail_count, N_KVP);")
(outdent)
(iformat "}"))
(defun c-code-from-prefix-tree (pt &optional (stream t) include-test-code)
(declare (ignorable pt))
(let ((*indent* 0)
(*spacing* 2)
(*cout* stream))
(iformat "#include <stdbool.h>~%")
(iformat "#include <stdint.h>~%")
(iformat "#include <stddef.h>")
(when include-test-code
(iformat "#include <stdio.h>"))
(iformat "bool lookup_key(uint32_t k, uint8_t * pv) {~%")
(indent)
(iformat "if (NULL == pv) return false;~%")
(if-else-forest pt 0)
(iformat "return false; ~%")
(outdent)
(iformat "}~%")
(when include-test-code
(create-test-code pt include-test-code))))
Функция
Давайте позвоним!
CL-USER> (with-open-file (stream "pseudo-ht.c" :direction :output :if-exists :supersede)
(c-code-from-prefix-tree (prefix-tree 31 *kvs*) stream *kvs*))
И вот, что мы получили - наш C-код, названный "pseudo-ht.c".
#include <stdbool.h>
#include <stdint.h>
#include <stddef.h>
#include <stdio.h>
bool lookup_key(uint32_t k, uint8_t * pv) {
if (NULL == pv) return false;
if (0x80000000 == (k & 0x80000000)) {
if (0xC0000000 == (k & 0xC0000000)) {
if (0xE0000000 == (k & 0xE0000000)) {
if (0xF0000000 == (k & 0xF0000000)) {
if (0xF8000000 == (k & 0xF8000000)) {
*pv = 55;
return true;
}
if (0xF0000000 == (k & 0xF0000000)) {
if (0xF4000000 == (k & 0xF4000000)) {
if (0xF6000000 == (k & 0xF6000000)) {
*pv = 250;
return true;
}
if (0xF4000000 == (k & 0xF4000000)) {
if (0xF5000000 == (k & 0xF5000000)) {
if (0xF5000000 == (k & 0xF5000000)) {
if (0xF5000000 == (k & 0xF5000000)) {
if (0xF5000000 == (k & 0xF5000000)) {
if (0xF5100000 == (k & 0xF5100000)) {
*pv = 228;
return true;
}
if (0xF5000000 == (k & 0xF5000000)) {
*pv = 82;
return true;
}
}
}
}
}
}
}
}
}
}
if (0xC0000000 == (k & 0xC0000000)) {
*pv = 59;
return true;
}
}
if (0x80000000 == (k & 0x80000000)) {
*pv = 16;
return true;
}
}
if (0x0 == (k & 0x0)) {
if (0x40000000 == (k & 0x40000000)) {
if (0x60000000 == (k & 0x60000000)) {
*pv = 89;
return true;
}
if (0x40000000 == (k & 0x40000000)) {
*pv = 26;
return true;
}
}
if (0x0 == (k & 0x0)) {
if (0x20000000 == (k & 0x20000000)) {
if (0x20000000 == (k & 0x20000000)) {
if (0x28000000 == (k & 0x28000000)) {
*pv = 17;
return true;
}
if (0x20000000 == (k & 0x20000000)) {
*pv = 141;
return true;
}
}
}
}
}
return false;
}
typedef struct KVP_tag { uint32_t key; uint8_t value; } KVP_t;
#define N_KVP ((size_t)10)
static const KVP_t s_kvp[N_KVP] = {
{609397212, 141},
{676943009, 17},
{1196140740, 26},
{2084672536, 89},
{2348838239, 16},
{3437178460, 59},
{4111000746, 82},
{4112460519, 228},
{4144164697, 250},
{4168664243, 55}
};
int main (int argc, const char* argv[]) {
size_t fail_count = 0;
for (size_t i = 0; i < N_KVP; i++) {
uint32_t key = s_kvp[i].key;
uint8_t expected_value = s_kvp[i].value;
uint8_t found_value;
if (lookup_key(key, &found_value)) {
if (found_value != expected_value) {
fail_count++;
printf("ERROR: for key %d (expected: %d) %d was found.\n", key, expected_value, found_value);
}
} else {
fail_count++;
printf("lookup_key(%x) failed.", key);
}
}
printf("%zu out of %zu tests failed.\n", fail_count, N_KVP);
}
И, к моему удивлению, он заработал прямо из коробки. Чего я (пока) не делал, так это сравнивал это с 1000 ключей и сравнивал с другими методами.
me@mymachine:~/dev/cl$ clang-13 -Wall -o pseudo-ht pseudo-ht.c
me@mymachine:~/dev/cl$ ./pseudo-ht
0 out of 10 tests failed.
И вот оно. Готов к доработке и усовершенствованию. В зависимости от конкретного набора пар ключ-значение порядок действий MSB->LSB просто произволен и может быть улучшен путем выбора другого порядка, который лучше разбивает дерево. Много места для большего количества идей. Например, префиксы (биты, общие для подмножества) в настоящее время имеют длину всего 1 бит, но могут быть и длиннее.
Ориентиры
Я удосужился добавить тесты и сравнение с бинарным поиском. А вот как результат выглядит на моей штуковине AMD Ryzen 3 (скомпилирован с
./pseudo-ht-10000 из 1000 тестов не пройдены.
поисковых запросов в секунду: 1,23287e+08
поисковых запросов в секунду (двоичный поиск): 6,47126e+07
По крайней мере, немного быстрее, чем бинарный поиск.