I'll only look at the memory vs. speed trade-off.
Suppose that M is the key size we want to look up, and N is the number of words in the dictionary. If we start with a sorted dictionary, then the prefix can be found with binary search, so that is O(M * log N) lookup cost in terms of the dictionary size. A prefix tree has a lookup cost of O(M). But the "work" done to actually look things up is trivial, i.e. on modern CPUs there's no cost to doing the character comparisons and such, especially that you could use SIMD intrinsics to speed that up by a lot. The entire cost is in cacheline accesses.
To speak in concrete terms, let's use the alphanumeric word dictionary from https://github.com/dwyl/english-words, on x86-64 (i.e. 8-byte pointer size). Let's also assume that we're wishing to optimize for lookup efficiency (broadly defined).
First, some general statistics of this dictionary:
- 3,494,697 letters
- 370,103 words
- 1,027,815 nodes in a prefix tree
- 3 child nodes average branching factor.
- 9 letters median word length (also the average), 31 letters maximum word length
- branching factors (for successive letters looked up):
1-26, 2-22, 3-8.6, 4-5.1, 5-2.7, 6-1.7, 7-1.1, 8-0.9, 9-0.8
So, if we stored the dictionary as a simple concatenation of null-terminated C strings, with no other optimizations, it'd take around 4MB of memory. This fits comfortably in the 6MB L3 cache of the CPU I'm trying this on (that cache can hold ~100k cachelines of 64 bytes each, in best case).
On the other hand, the question's implementation of the prefix tree takes ~220MB of RAM because the nodes are huge: 216 bytes. We'd have hoped that the prefix tree would have "compressed" our data, but instead it expands it by a factor of 55x. Each node fits in 4 cache lines (3.3 really).
Tree traversal using Node needs to pull up to two cachelines per Node (maybe 1.5 on average): one for the child node pointer, another for the value and the child pointer. Some of those cachelines will have to be misses, since the tree doesn't fit in the cache.
The L3 cache can fit around 30k nodes. Let's somewhat arbitrarily assume that about 10k of them will be "long lived hot nodes". The product of the first 5 branching factors is ~25k, so we can estimate that about 4 first characters of each word will be nodes that fit in L3. With average word being 9 letters long, we will miss 4-5 additional nodes, or 8-10 additional cachelines. That'd be the real cost of this implementation on this particular data set.
Now let's say our benchmark will be as follows: take a "lookup string" of all words in random order, concatenated into a long string of zero-terminated words. Iterating such a string is very fast, since the CPU will prefetch everything, so other than some cache pressure, the overhead of using such permuted word stream is very low. We use words from that string as lookup keys, and copy them to an output string as we perform each lookup. An exemplary benchmark takes about 120ms to look up all the 370k words in random order from the prefix tree, constructing the "output string". The function being timed is below, the assert is a no-op in release mode, and the nodes were all allocated from a contiguous memory block.
I wrote the examples below in C++, to make life a bit easier, but they could all be written in C without any loss of performance.
auto doLookup(Node *root, const std::string &lookupStream)
{
std::string result, word;
Node *node = root;
result.clear();
result.reserve(lookupStream.size());
for (char ch : lookupStream) {
if (ch) {
node = node->children[ch - 'a'];
word.push_back(ch);
} else {
node = root;
result.append(word);
result.push_back('\0');
word.clear();
}
}
assert(result == lookupStream);
return std::make_pair(std::move(result), node);
}
Given this "standard" to compare with, let's do the "next most stupid thing": an equivalent lookup using just the dictionary, with zero-delimited words in ascending order, using a binary search, where each time we "throw a dart" in the dictionary, we have to scan back to find the beginning of the word.
The function being timed is below. It isn't particularly pretty but it does the job.
auto doLookup2(const std::string &dictionary, const std::string &lookupStream)
{
assert(dictionary.front() == '\0');
assert(dictionary.back() == '\0');
assert(lookupStream.back() == '\0');
std::string result, word;
result.reserve(lookupStream.size());
for (char ch : lookupStream) {
if (ch)
word.push_back(ch);
else {
const char *begin = &dictionary.front(), *end = &dictionary.back();
const char *prevP = nullptr;
for (;;) { // binary search
const char *p = begin + (end - begin) / 2;
const char *const p0 = p;
assert(p0 != prevP); // otherwise we didn't find the word
while (*p)
--p; // find start of the word
p ++;
int const cmp = strcmp(word.data(), p);
if (cmp == 0) {
assert(word == p);
result.append(word);
result.push_back('\0');
word.clear();
break;
}
if (cmp < 0 /* word < p */) {
end = p0;
} else { /* word > p */
begin = p0;
}
prevP = p0;
}
}
}
assert(result == lookupStream);
return result;
}
This function takes about 170ms (vs. the tree's 120ms), and trades off 50% longer execution for 55x smaller memory use, although it doesn't find the first word with a given prefix, just some word - then one has to iterate backward. Doing that in the most rudimentary way adds some 10ms to the runtime (I'm not showing it above).
This trade-off may be acceptable as-is. But either approach could be micro-optimized. Cutting the tree size in half by replacing the node pointers with indices of nodes in the pool cuts about 10ms off the runtime - we don't expect a huge improvement, since the tree still doesn't fit in the cache.
But the tree approach seems promising, so let's try to reduce memory consumption further. Instead of allocating 26 child node pointers in each node, let's allocate only one, and double the pointer array size whenever we run out of space. There isn't a direct index-to-pointer mapping for child pointers anymore, but instead we can store a bit flag for each character, indicating whether the pointer is present or absent in the array. Furthermore, the leaf nodes can all be stored as stock nodes, since they are identical. The node looks as follows:
struct TreeNode
{
uint32_t activeChildren;
struct TreeNode *children[1]; // this is a dynamically sized array
} typedef TreeNode;
The activeChildren member also stores the end-of-word flag - access is provided via accessors.
This approach reduces the allocated memory size to 15MB, and the lookup benchmark takes about 140ms - only 20ms worse than the "reference" implementation. Only 750k nodes are individually allocated, the remaining 250k are all leaf nodes collected as the single stockLeafNode.
Retrieval of a child node looks as follows:
TreeNode **getChildNode(TreeNode *node, char ch)
{
ch -= NODE_LOWEST_VALUE;
uint32_t childrenBits = node->activeChildren;
if (!bitIsSet(childrenBits, ch))
return NULL;
return node->children + numberOfSetBitsBelow(childrenBits, ch);
}
numberOfSetBitsBelow(bits, bit) returns the count of set bits ("1") in the bits paramer, but only the bits in positions lower than bit number bit. E.g. numberOfSetBitsBelow(0xFE, 3) == 2, because below bit 3 only bits 2 and 1 are set.
Using getChildNode, we have the following prefix lookup:
TreeNode *findNode(TreeNode *node, const char *word)
{
for (char ch = *word++; ch; ch = *word++) {
TreeNode *nextNode = *getChildNode(node, ch);
if (!nextNode)
break;
node = nextNode;
}
return node;
}
Complete project is at https://github.com/KubaO/stackoverflown/tree/master/questions/cr-prefix-tree-252512
