# Loading dictionary using trie in C very slow with large data set

The code below works for very small dictionary files I used to test (two words). However when I run this using a more typical dictionary file, my machine slows to the point of near crash. I would like a review of what the potential bottleneck may be which I believe to be in the load() function. Of course, general comments are also welcomed if they may help with optimization and overall performance.

typedef struct node

{
bool is_word;
struct node* children[27];
}
node;

node* root;

int nwords = 0;

/**
* Returns true if word is in dictionary else false.
*/

bool check(const char* word)
{
node* current = root;

int i = 0;

while(word[i] != '\0')
{
int letter = tolower(word[i]);

if (letter == '\'')
{
return false;
}

if (current->children[letter-'a'] != NULL)
{
current = current->children[letter-'a'];
i++;
}

else
{
return false;
}
}

if (current->is_word == true)
{
return true;

}

return false;
}

/**
* Loads dictionary into memory.  Returns true if successful else false.
*/

{

FILE* dict = fopen(dictionary, "r");

if(dict == false)
{
return false;
}

//initialize nodes

root = calloc(27,sizeof(node));
node* current = NULL;

int c = 0;

while(fgetc(dict) != EOF)
{
fseek(dict, -1, SEEK_CUR); //go back one byte to beginning of word
current = root; //set index to root

for(c = fgetc(dict); c != '\n'; c = fgetc(dict)) //iterate through word
{
if(current->children[c-'a'] == NULL)
{
current->children[c-'a'] = calloc(27,sizeof(node));
current = current->children[c-'a'];
}
else
{
current = current->children[c-'a'];
}
}
current->is_word = true; //once line break reached end the word
nwords++;
}

fclose(dict);
return true;
}

/**
* Returns number of words in dictionary if loaded else 0 if not yet loaded.
*/

unsigned int size(void)
{
return nwords;
}

/**
* Unloads dictionary from memory.  Returns true if successful else false.
*/

void freeNode(node* current)
{
for (int i = 0; i < 27; i++)
{
if(current->children[i] != NULL)
{
freeNode(current->children[i]);
}
}
free(current);
}

{
freeNode(root);
return true;
}

-
It would be a whole lot easier to profile your code for the bottleneck if you included everything and not just this little bit. –  syb0rg Jul 31 at 22:44
Notice that you calloc(27,sizeof(node)) to add a tree element, which allocates 27*sizeof(node), so each node takes 27x as much space as you need. try calloc(1,sizeof(node)) instead. –  ChuckCottrill Aug 1 at 3:11

A few notes:

• typedef struct names are commonly written in PascalCase today.

Node* current = NULL;

• Initialize your variables on the lowest scope as possible. Therefore, declare your variables within your for loops. (C99)

for(int c = fgetc(dict); c != '\n'; c = fgetc(dict)) //iterate through word


Also, I feel as if you should be checking c for EOF, and then check for \n within the for loop.

• The statements inside of your for loop look fishy to me:

if(current->children[c-'a'] == NULL)
{
current->children[c-'a'] = calloc(27,sizeof(node))
current = current->children[c-'a'];
}
else
{
current = current->children[c-'a'];
}


No matter what, you are going to set children equal to current->children[c-'a'], so you can move that statement out of both branches of the conditional (DRY). Also, you should not be allocating 27 elements for every single Node. Here is how I would write it:

if (!current->children[c-'a']) current->children[c-'a'] = calloc(1, sizeof(node));
current = current->children[c-'a'];

• You can remove the != NULL part in your if conditional statements.

• Avoid global variables: root and nwords.

• Avoid magic numbers.

for (int i = 0; i < 27; i++)


Use a #define instead at the top of your code.

#define NUM_NODES 27


But where does the number 27 even come from? Documentation would go a long way here to help developers understand what it is.

• Set your Node values to NULL after you free them. This is so that you do not try to access the data again after it has been freed.

-
thanks. I replace the if statement with your and it blazes through now. Can you please elaborate on why I did not need the else portion (i.e., if the node is null)? Also I think the apostrophe escaping was correct. There are other bugs in the check function I need to sort out though. –  Andy Aug 1 at 1:25
@Andy I edited in an explanation, though I am surprised that one replacement made it so much more efficient. Did you have compiler optimizations disabled? –  syb0rg Aug 1 at 1:59
Thanks for the edit. Yes, I first took out the fseek which got the program to stop crashing but average load time of 1400K word dictionary was 4 seconds and with your if/else edit time is 0.03 seconds. Oddly, and I need to investigate, with your edit the unload time fell considerably. Perhaps what I was doing earlier was creating superfluous nodes. In any event, thanks. –  Andy Aug 1 at 2:12
@Andy No, by not setting the Node values to NULL, you were performing excessive recursive calls on the children to free them. –  syb0rg Aug 1 at 2:22
You probably should check isalpha(letter) rather than the apostrophe check, to avoid any non-letter (as you rely on that for the array index/offset anyway. –  ChuckCottrill Aug 1 at 3:13

IO is most likely your problem. The fseek(dict, -1, ...) is performing unnecessary IO. If you restructure your loop to be more efficient, it will help...

Consider this loop:

int c = 0;

// note, store the c on this read....
while((c = fgetc(dict)) != EOF)
{
if (c == '\n')
{
// end of word, save it....
if (!current->is_word)
{
//in case of duplicates.
current->is_word = true; //once line break reached end the word
nwords++;
}
// reset the pointers.
current = root;
} else {
if(current->children[c-'a'] == NULL)
{
current->children[c-'a'] = calloc(27,sizeof(node));
}
current = current->children[c-'a'];
}
}
if (current!= root && !current->is_word)
{
//in case of duplicates, and an unterminated last line.
current->is_word = true; //once line break reached end the word
nwords++;
}


Doing it this way ensures a forward-only scan through the file.

-
I removed the fseek and now it at least runs to completion although I think check may have a bug I need to sort out. Interestingly the slowest part of program is the recursive unload() function. Of 3.75 seconds of run time, 2.73 are in unload. –  Andy Aug 1 at 0:50
fgets and read a whole line/word, chomp the newline, and add a word at a time. –  ChuckCottrill Aug 1 at 3:14

You are allocating a lot of space (and much of it is wasted). Grabbing memory affects performance in various ways, most important being a cache performance. And with the links pointing all over the memory space, cache misses incur serious cost over tree traversal.

Bottomline is, do not expect a good performance from a tree with high branghing factor. Take a look at a PATRICIA (or radix) tree for a correct implementation of your idea.

PS: My two cents in addition to @syb0rg analysis: using fseek restricts you from the streaming files, and strictly speaking it is not necessary at all:

while((c = fgetc(dict)) != EOF) {
current = root; //set index to root

for(; c != '\n'; c = fgetc(dict)) //iterate through word
{
...
}

-
-

I was curious about the performance of a trie so did a few tests to satisfy myself. First two problems with your original code:

1. You don't check for EOF in your inner for loop meaning your code will run forever unless the file ends exactly with a \n.

for(c = fgetc(); c != '\n' && c != EOF; c = fgetc(dict)) //iterate through word


Always check return codes when reading data from files. I suspect this may be the issue with your code "crashing" as even with loading 150k words your code only takes 1.5 seconds with the fix.

2. Another issue is the mixing of fopen(..., "r") with fseek() depending on if your word file contains \n or \r\n line terminations. Using mode r with \n will probably result in incorrect parsing when seeking...at least it did with me using VS2010 on Windows7 causing considerable head scratching. Changing the mode to rb fixed the seek issue but eliminating the seek altogether is a better fix and then the file mode doesn't matter.

The other answers go over a variety of good optimizations and code improvements but I wanted to look specifically at how each one impacts the performance of the loading code (Note: please take the times below with a grain of salt...do your own benchmarks if performance really matters):

1. Your original code (with the two fixes mentioned above) takes 1500ms to load/parse 150k english words. Not necessarily bad. It results in 388k allocations of new nodes.
2. Removing the fseek() call reduces this to 1060ms.
3. Loading the file all at once (only 1.5MB) and parsing the string using strtok() has a very small performance increase to 1000 ms.
4. Replacing the strtok() with manual parsing logic has no visible effect.
5. At this point the only obvious thing left is to optimize the individual allocations with one block allocation (see code at the end). This has a huge effect on performance reducing the loading time to only 15 ms. Hopefully that is fast enough for you....
6. At this point there isn't anything obvious left to optimize. You could try saving and loading the completely parsed trie but the I'm not sure if you'd gain much with the larger read size involved. Profiling would be your best bet to see what, if anything, could be optimized.

Note that the code below is missing some error handling/checking code for simplicity and the node allocation size is hard coded for the same reason. Look up "block/bucket/arena allocators" for more details on this type of optimization.

         // Loads 150k word dictionary in 15ms (x100 faster than original implementation)
{
// Size is hard coded for this example code (388k allocations used)
// You'd also want to be able to free() the memory some how
node* pNodeBucket = calloc(400000, sizeof(node));
node* pNextFreeNode = pNodeBucket;

FILE* dict = fopen(dictionary, "rb");  // "b" mode is important here
if(dict == false) return false;

// Get size of file: should check for error codes here
fseek(dict, 0, SEEK_END);
long Size = ftell(dict);
fseek(dict, 0, SEEK_SET);

char* pBuffer = malloc(Size + 1);
fclose(dict);

// File data will not be nul terminated when read
pBuffer[Size] = '\0';

root = pNextFreeNode++;
node* current = NULL;

int c = 0;
char* pParse = pBuffer;

while (*pParse)
{
current = root;

for(; *pParse != '\n' && *pParse; ++pParse)
{
if(current->children[*pParse-'a'] == NULL)
{
current->children[*pParse-'a'] = pNextFreeNode++;
}

current = current->children[*pParse-'a'];
}

current->is_word = true;
nwords++;

if (*pParse == '\n') ++pParse;
}

free(pBuffer);
return true;
}


Update on unload(): I missed that your were also looking at the performance of the unload() function. Unfortunately, if you keep the original allocation scheme there isn't very much you can do. Memory allocation/deallocation can be slow and with not always consistent (it can take longer or shorter depending on the state of the allocator).

For example, in my sample test of 150k words unload() has to check 10.5 million pointers and deallocate 388k of them taking 7 seconds to do so (would be faster if not running under VS). If you change the allocator to a single bucket as in my example then your deallocation is simply:

          // Make pNodeBucket global for this to work
{
free(pNodeBucket);
}


Which should be negligible in general (not visible in my simple time tests).

-
this is great analysis. Am going to try this as well. And yes, 15ms is fast enough, lol. I originally did this in PHP and it took like 20 seconds! –  Andy Aug 1 at 14:32

ChuckCottril and vnp are way right. Furthermore, below the first 2-3 layers of the trie, nearly every node is 26/27 full of NULL pointers, so that's another factor of 27 wasted storage. (27*27 = 729x wasted storage.)

What I would do is:

1. Put the words in a long ordered array. (The size of this is a tiny fraction of an equivalent trie.)

2. Only use the trie for sufficient levels to be an index into that array. The way to build it is to recursively walk the ordered array, building the trie on the way out.

In terms of performance, memory allocation is a huge killer.

ADDED: uesp also has a good idea, which is to do only one calloc rather than many. The way to do this is to walk the ordered word list twice. First you walk it to see how much storage you need (this is very fast). Then you calloc the storage. Finally you walk it again, building the trie by personally allocating nodes out of the block you got with calloc.

-
For some reason I thought when I create a new node that new node has to have a spot for every letter in alphabet. But I guess that is done in the struct's definition. Might explain why unload was so brutally slow. –  Andy Aug 1 at 14:21
@Andy: right, but the "spot" is a pointer to a node, not a whole node, as ChuckCottril pointed out. Plus, below the first 2-3 levels, very few nodes contain >1 pointer, because most words contain many more letters than are needed to disambiguate them. Look at any dictionary and see how many initial letters are in common between adjacent words. Or type something into Google and see how quickly it guesses what you wanted. –  Mike Dunlavey Aug 1 at 14:26