6

Gperf consistently underperforms a Judy array in my environment, and I'm wondering if there is another perfect hash library out there built specifically for integer keys. I know the set of keys beforehand, and I would like to leverage that into a performance/size advantage.

There are ~1000 keys, and retrievals are not in sequential order. Key pairs are both integers. Keys are 32-bit, and retrieved values are 8-bit. Size is the most important factor.

If there is a way to tweak Gperf for integer keys, or just another approach in general, I'm all ears, too. :)

(Sidenote: ...While typing out this question, I realized a binary search probably takes the cake and I've just over-thought the problem. I'd still like to hear any thoughts you may have for the sake of learning, though!)

Edit: Keys are not evenly distributed. Most are randomly clustered throughout the entire possible range.

Edit 2: Worst-case binary searches were too slow for my taste, so I ended up playing with the keys until I found 8 bits to use from each to make 256 well-distributed buckets. I held the min & max of each bucket (24 bits for each bucket entry), and made one big struct array for the key-pairs. On-par/faster and smaller than everything else I tested with for my particular case, so I guess I'm going with that for now. :)

6
  • You could use Lua as a hash table library. But for 1000 entries, you'd probably be better off searching a sorted array, as you mentioned.
    – lhf
    Nov 9, 2011 at 2:37
  • Do you need inserts / deletes too, or is it a static lookup table? Nov 10, 2011 at 0:23
  • @wildplasser Static table. :)
    – user962158
    Nov 10, 2011 at 19:27
  • If you can afford a table of 2 * 1000 integers, a hashtable is possibly feasible. Might need some bit-tweaking, combining the payload and the overflow-pointers. (maybe an in_use-bit, too) Nov 10, 2011 at 19:56
  • The hash table works fine, using 2*N ints of space and the characteristic ~1.5 probes per operation. This is about the best you can get without a perfect hash (which is nearly impossible for 1000 entries) Nov 11, 2011 at 15:44

5 Answers 5

4

Keep your keys sorted, and use an M-tree to retrieve any key.

An M-tree has M entry per node, instead of 2 for binaries. It will help tremendously for performance. Use a cache line size as the basis of your node size, hence 64 Bytes. You can store 16 32bits values in this size.

Since you have 1000 values, 3 levels will be enough to retrieve the right key (as opposed to 10 levels for a binary tree).

Another idea would be to hash your keys into a small hash-table, such as 12-bits one (4K entries), and solve the potential collisions with a simple chain. You are very likely to get most of your keys in a single search.

1
  • Accepting this. Thanks for the great explanation. I'll tinker with that idea. :)
    – user962158
    Nov 10, 2011 at 19:33
3
/*
** 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://stackoverflow.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);
}

The result: (well: some of it)

....
[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)

Note: because of the sorting while initialising the hashtable, entries are very close to the place where they are expected. This increases the locality of reference.

2

Have you tried judy arrays? Might be exactly what you need.

1
  • 1
    Unfortunately, Judy arrays were what I was trying to beat with a static table! I didn't need insertions/deletions, so I wanted to get rid of whatever overhead that entailed. :(
    – user962158
    Nov 10, 2011 at 19:38
1

I extended gperf and nbperf for integer key sets.

2
  • How would you use it for integers? Is there an example somewhere?
    – nowox
    Nov 15, 2023 at 11:36
  • See the docs. Normally the app should detect that the keys are all integers, if it's dense or sparse and how many bits you need. nbperf -I
    – rurban
    Nov 16, 2023 at 8:29
0

I know the set of keys beforehand, and I would like to leverage that into a performance/size advantage.

If that means, what I think it means (you know the sets of keys (and values) beforehand, as in at compile time), you can as well generate a lookup function from your data. This sometimes makes sense, e.g. in embedded systems, where you have lots of ROM and only little RAM.

Here is the idea:

  • With the sorted set of key-value pairs (sorted by key), you can construct a function, which implements the tree with control flow, checking the bits from most significant down to least significant. So, with at most 32 (32 bit key) comparisons worst case, you find the value, belonging to your key. On average, it is much less (I dare not guess if it is 32/2, because it is late already).

No one would want to write such an if-then-else heavy function manually, but hey - if the code gets generated, it is half the pain (and double the fun writing the generator). Plus, this approach needs no heap, no pointers, no complex data structures and so it is quite trivially shown to be "harmless". Again, sometimes this is just what you want in some (critical) embedded systems.

Again, whether this is a viable option also depends on the CPU. Embedded CPUs rarely have long pipelines and branch prediction units and all that modern stuff we often take for granted in AMD/INTEL desktop environments. So, it just might not affect performance as much on those more primitive CPUs as one might first think.

Lets get our fingers wet, by writing a function, which generates our "known beforehand" list of key-value pairs.

(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)))

This function returns some rather boring- looking list of pairs:

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

With the binary dump above, it is already easy to see, where this is heading. Just looking at the MSB (most significant bit), our (binary) tree splits the set into 4 entries, which have a 0 and 6 entries, which have 1.

Subsequently, we do that with those subsets again, with the next bit (from MSB towards LSB). The function, doing that, I called prefix-tree.

(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)))))))))

The first, extra argument is just there, so the recursion works. How does it look like, when we run this on our key-value-list?

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)))

If you look at that tree in the right angle, this already nearly looks like C-code, does it not? The if-then-else structure in the resulting code is already visible. :node parts have an if-else output and :leaf parts just return the byte value, we are looking for.

What is now left to do is the boring part. Generate code from that tree structure. I will not elaborate on that. Just the code.

(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))))

The function if-else-forest does the crucial job. It got its name, before I understood, that else parts would make it actually more complicated. Also, next to the function lookup_key() itself, the code optionally generates a main(), which tests if we find the right values.

Let's call it!

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*))

And here is, what we get - our C-code, named "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);
}

And to my surprise, it worked right out of the box. What I did not do (yet) is benchmark this with 1000 keys and compare it to other methods.

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.

And there we have it. Ready to be refined and improved upon. Depending on the concrete set of key-value-pairs, the MSB->LSB order of doing things is just arbitrary and could be enhanced by picking a different order, which splits the tree better. Lots of room for more ideas. E.g. prefixes (bits, a subset has in common) are currently only 1 bit long - but could be longer.

Benchmarks

I got around to add benchmarks and a comparison to binary search. And here is how the output looks like on my AMD Ryzen 3 thingy (compiled with -O3 and with 1000 key-value-pairs):

./pseudo-ht-1000 0 out of 1000 tests failed.
lookups per second: 1.23287e+08
lookups per second (binary-search): 6.47126e+07

A bit faster than binary search at least.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.