Skip to main content
add notes on unload
Source Link
uesp
  • 171
  • 2

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
 void unloadfaster()
 {
      free(pNodeBucket);
 }

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

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
 void unloadfaster()
 {
      free(pNodeBucket);
 }

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

Source Link
uesp
  • 171
  • 2

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.

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