I was curious about the performance of a trie so did a few tests to satisfy myself. First two problems with your original code:
You don't check for EOF in your inner for loop meaning your code will run forever unless the file ends exactly with a
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.
Another issue is the mixing of
fopen(..., "r") with
fseek() depending on if your word file contains
\r\n line terminations. Using mode
\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):
- 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.
- Removing the
fseek() call reduces this to 1060ms.
- Loading the file all at once (only 1.5MB) and parsing the string using
strtok() has a very small performance increase to 1000 ms.
- Replacing the
strtok() with manual parsing logic has no visible effect.
- 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....
- 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)
bool loadfaster(const char* dictionary)
// 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);
// Read entire file: should check for read error here
char* pBuffer = malloc(Size + 1);
fread(pBuffer, 1, Size, dict);
// File data will not be nul terminated when read
pBuffer[Size] = '\0';
root = pNextFreeNode++;
node* current = NULL;
int c = 0;
char* pParse = pBuffer;
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;
if (*pParse == '\n') ++pParse;
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
Which should be negligible in general (not visible in my simple time tests).