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 \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.
- 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):
- 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);
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;
}