5
\$\begingroup\$

Deferred allocation is a memory optimizing trick of using the Node** as Node* when there is only one item in the "bucket". Thus "item" member holds either the index of such lonely item, or a negative value if the bucket is fully allocated.

Cache-awareness here is merely adding a compiler's __builtin_prefetch() in the right place to allow about 30% speed up.

trie4d.h

#ifndef TRIE4D_H

#include <stdlib.h>
#include <sys/types.h>
#include <string.h>

/* define your own value type if needed */
#define VALUE_TYPE int

struct Node {
    struct Node **N;
    VALUE_TYPE value;
    char item;
};

struct Node* newNode();
int addNode(struct Node *C, void *key, int count, VALUE_TYPE value);
struct Node* findNode(struct Node * C, void *key, int count);
void freeNode(struct Node* C);

#endif // TRIE4D_H

trie4d.c

#include "trie4d.h"

struct Node* newNode() {
    struct Node *node;
    node = malloc(sizeof (struct Node));
    node->value = -1;
    node->item = -1;
    return node;
}

int addNode(struct Node *C, void *key, int count, VALUE_TYPE value) {
    int pos = 0;
    struct Node* tmp;
    while (1) {
        char u;
        int bpos = pos >> 1;
        if (bpos >= count) {
            if (C->value == -1) {
                C->value = value;
                return 1; /* value added */
            }
            C->value = value;
            return 0; /* value replaced */
        }
        unsigned char b = ((unsigned char*)key)[bpos];
        if (pos++ & 1) u = (b >>= 4);
        else u = b & 0xf;
        if (C->item == -1) {
            C->item = u;
            C->N = (struct Node**)newNode();
            C = (struct Node*) C->N;
        }
        else if (C->item >= 0) {
            if (C->item == u) {
                C = (struct Node*)C->N;
            }
            else {
                tmp = (struct Node*) C->N;
                C->N = malloc(sizeof (void*) * 16);
                memset(C->N, 0, sizeof(void*) << 4);
                C->N[C->item] = tmp;
                C->item = -2;
                C = C->N[u] = newNode();
            }
        } else {
            if (C->N[u])
                C = C->N[u];
            else 
                C = C->N[u] = newNode();
        }
    }
}

struct Node* findNode(struct Node * C, void *key, int count) {
    int pos = 0;
    while (1) {
        char u;
        int bpos = pos >> 1;
        if (bpos >= count) return C;
        unsigned char b = ((unsigned char*)key)[bpos];
        if (pos++ & 1) u = (b >>= 4);
        else u = b & 0xf;

        if (C->item == -1) return 0;
        else if (C->item >= 0) {
            if (u == C->item) C = (struct Node*)C->N;
            else return 0;
        } else {
            __builtin_prefetch(C->N[u]);
            C = C->N[u];
            if (C == 0) return 0;
        }
    }
}

#ifdef DEBUG
/* this will count upon destruction, how much memory was used */
int mem_count = 0;
#endif

void freeNode(struct Node* C) {
    int i;
    if (C->item == -2) {
        for (i = 0; i < 16; i++) {
            if (C->N[i]) freeNode(C->N[i]);
        }
        free(C->N);
        #ifdef DEBUG
        mem_count += 16 * sizeof(struct Node);
        #endif
    }
    else if (C->item >= 0) {
        freeNode((struct Node*)C->N);
    }
    free(C);
    #ifdef DEBUG
    mem_count += sizeof(struct Node);
    #endif
}

This trie was made mostly as very fast key/value dictionary (competing with hash tables), so you will not find a common for tries function "traverse down from node" (useful for "auto-complete" style implementations).

Although this implementation uses more memory than hash tables, it is almost as fast and extremely simple, only 100 LOC. Making it a good candidate to port to low level languages (like assembly or Forth).

The goal was to make an extremely fast dictionary, with O(K) lookup time, where K is a length of key. The problem is that modern CPU is very slow at pointer dereferencea and a nature of tree is to do a pointer dereference on each step, thus a cache should be reloaded.

\$\endgroup\$
1
\$\begingroup\$

General comments

Overall I found your code to be quite reasonable. You are using each 4 bits of a variable length key as a "character" of a "trie".

  1. I think you should have defined these constants instead of using magic numbers:

    #define ITEM_EMPTY       -1
    #define ITEM_ALLOCATED   -2
    #define VALUE_UNSET      -1
    
  2. When you allocate a new node, you set node->item to -1, but you do not initialize node->N to anything. This works because there is an implicit assumption in your code that if node->item == -1, then node->N is unusable. But just for your own sanity when debugging, I suggest that you set node->N = NULL anyways.
  3. In these two lines of code:

               C->N = malloc(sizeof (void*) * 16);
               memset(C->N, 0, sizeof(void*) << 4);
    

    First of all, you are inconsistent in that you use * 16 one place and << 4 in the next place. But really, you should just replace that code with:

                 C->N = calloc(16, sizeof(void *));
    
  4. Your if/else style and braces are inconsistent. Compare:

            if (C->item == u) {
                C = (struct Node*)C->N;
            }
            else {
    

    with:

            if (C->item == -1) return 0;
            else if (C->item >= 0) {
                if (u == C->item) C = (struct Node*)C->N;
                else return 0;
            } else {
    
  5. Your variable names are a bit cryptic. I eventually figured out that bpos was "byte position" and pos was "nibble position". I still don't know what C or u stand for, though. I think count should be renamed keyLength.

Loading each byte twice

In both your addNode() and findNode() functions, you load a byte from the key and either use its upper or lower half (4 bits per trie depth). So you end up loading the byte from the key twice (once for each half). You might be able to do better by saving the value of that byte and on each 2nd iteration, you can use the saved value to get the upper half instead of reloading that byte from memory.

Prefetch

As written, I don't think your __builtin_prefetch() call will do anything. You put that prefetch call right before you are about to dereference the pointer, so even if the compiler inserted a prefetch instruction there, it wouldn't help speed anything up. I compiled your program with and without that line and both versions generated the same assembly code (with no prefetch instruction). The way to get benefit out of builtin_prefetch() is to call it some amount of time before you are going to actually use that address. For example, at the top of the while loop, you can do:

if (C->item != -1)
    __builtin_prefetch(C->N);

I'm not sure that you will get much of a benefit from this though. You'll have to run some tests to see whether this actually helps or hurts.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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