Sorry for the delay in getting the results out. There is a really funny story behind it with me running 7 hours of tests in debug mode then aggregating results and getting it all ready before I realized what I had done :-/

You can find the original contest here http://codebetter.com/blogs/gregyoung/archive/2006/07/27/147736.aspx.

Order is Important!

One of the key optimizations for the tokenizer is realizing that the order of processing is extremely important. If we know any information about the domain our code will run in we can often make domain specific optimizations by changing the ordering of our statements.

In the English language for instance characters appear on an order of magnitude more frequently than punctuation. In order to optimize for this case we should check our most often circumstances first. This is better shown with a simple example. The following two functions are both doing the exact same thing but the second example is much faster than the first.

Run across the string "This is some normal english text. Occasionally you will also get a number such as 2" (concat’ed 10000) times the second version is almost twice the speed of the first. In our most often case in the first example (a lower case letter) we have to fail through all of the other conditions where as in the second example it ius our first condition. The goal should be to check the mutually exclusive conditions in an order that is correct when you statistically analyze the data.

ToCharArray() ?!

I saw many submissions calling Data.ToCharArray() to get a character array representing the data so they could read it. There is another method on the string object that does a similar job, which although hidden to you is much faster than ToCharArray(). Consider the following test.

In debug mode they have nearly identical performance but in release the ORCharsSameArray function is about 3 times faster. When you use a foreach on a string (or if you use an index) a special method get_Chars is called (you can’t call this on your own). We can see this occurring by looking at the IL in question.

This method lets you view the data inside of the string as if it were an array of chars.  Since the data is only being read there is no need to generate an array. The reason that they are roughly the same speed in debug is that the method does not get inlined, in release mode the method is inlined and it is nearly as efficient as unsafe code.

Threading (The Red Herring?)

A few tried threaded solutions only one did it efficiently. Garmon got the algorithm right.

The problem with threading is locking … In order to maintain a hash properly between two threads one needs to setup critical sections around the hash. The big problem comes in that on every probe to the hash one has to worry about a resize of the hash by the other thread. In order to get around this one has to create a hash per thread, since each thread has its own hash they can operate on their own hash without locking as the other thread will not touch the hash.

Once the two threads are complete one then must merge the two hashes. This will always be a O(n) operation at best generally O(hashsize) which is why threading was not much of an issue here unless you get absolutely huge data sets with lots of repetition. It takes a lot to make up for the O(n) operation on the copy, the creation of the second hash, the delay to actually start the thread, and the additional memory overhead caused by having two hashes.

The key to threads being successful is a high rate of repetition in the data!

Use a Map

All of the submissions used if conditionals to tokenize the data.  There were cases such as

Could we pre-generate this information into a table and simply do a table lookup?

Note that this code is doing any transformations that we may want and is also storing some additional information in the high bits of the int16(we only use 8 bits for the char). In particular it is storing a bit that tells us if what was read is a word terminator or not and it tells us whether or not we should add to the current position of the output buffer. This code will produce output similar to the following

Now that we have this map saved off we can write an extremely elegant tokenizer that is also faster than our prior incarnations which used conditionals.

Clean, compact, and efficient … what more can you ask for?

A Side Challenge

I gave myself a side challenge yesterday, could I tokenize the string two chars at a time with only a single branch in my loop? It took me a little while to come up with an answer to this problem but it did exist. Here is the code.

In order to really look at this code you will also need to look at the code that generates a 64k map that it references (no I will not post the 64k map hereJ). The complete code and the map can be found in the MappedWordCounter.cs file. If people would like I can explain further just how it works but basically it sets high bits in the map to define how much to move forward both the buffer and the output pointers (it also stores a bit flag as to whether or not the 2 chars contained a word terminator as did the previous tokenizing example). There is however one odd case which is worth discussion.

If you read two characters and the first is an ignored or termination character. In the case of an ignored character you don’t want to end up with a “hole” in your array as such you have to not move the output buffer.  In this case one is added to the buffer making it on an odd letter and you add zero to the output as you don’t want to include the character. This means that in this case you read and write the second character twice. A further special case can be seen when you have two ignored or termination characters except the buffer moves two while the output moves zero positions.

Initial Hash Table Size

In the tests where a new object is created for every call the hash table size becomes extremely important. If the table is too big it will be allocating useless memory and will need to clear that memory. If the table is too small it will have to go through numerous growth operations which are a fairly big hit. I have yet to find a “good” way of initializing the table except for using domain information such as “every 9 letters or so will on average produce a new word”.

In general it is best to error a bit on the side of caution and allocate slightly more memory to your hash table than to error the other direction and to force a growth of your table.

I made YoungCompressed use a 150000 entry table for every entry, check out the performance characteristics compared to the other entries which were using a text.length / 7 sized table.

The Default Equality Comparison is SLOW

No submissions used this but it can quickly speed up many of them.  I am going to pick on Brandon Grossutti’s submission here but the optimization applies to all of them that use a dictionary<>. By simply changing Brandon’s code from

Dictionary<string, int> MyWords = new Dictionary<string, int>();

To

Dictionary<string, int> MyWords = new Dictionary<string, int> (1, StringComparer.Ordinal);

Took about 7% off the total running time of the submission. This is an important one to remember.

Write a Custom Hash Table

It is well known that code which is designed to be generic will often be less efficient than code tailor made for the job at hand (in other words generality comes at a loss of performance). The .NET dictionary and hash classes are both very generic. By writing your own version of these classes there is a performance gain to be had. I wrote a few varying forms of my hash table that are included with the code.

The first version of the table works in a very similar fashion to the standard table. It stores  the string keys as char * and uses a modulus based system for finding the next available slot (i.e. slot = (slot + 1) % tablesize). This method is quite fast but there are a few optimizations which can be made.

One of these optimizations is to get rid of the modulus which is a slow operation on most machines (and it is used extremely often, every probe). In order to get rid of the modulus we need to make some special requirements on the hash table. To be exact you need to control the size of the hash table to only be a power of two (this can be seen in "bithash" and is in my overall submission).

If the table is a power of two you can use a bit mask instead of a modulus to insure that your current value is within the realm of your hash. Once the hash is assured to be a power of two one can calculate the bitmask for the hash table as hashsize – 1. All that is then required is the mask which can be seen here.

uint slot = (uint)(Hash & m_HashMask);

The bit mask is significantly faster on most architectures, this change yielded nearly a 10% gain for the algorithm on my machine.

Buffer?

Since I am using char* in my hash table, I do not need to initialize a specific string for it (and I can deal with as a unit32* when I need to do things like comparisons). The big problem you will run into here is that you need to keep the memory that the string is in pinned. This can either be done explicitly or by holding a GCHandle for the object (such as I do with the actual data in the hash table). If you do not do this you can end up with seemingly random bugs that occur when the GC compacts the heap (the string you were pointing to has moved).

In order to get around the nightmare of trying to maintain GCHandles my tokenizer puts the data into a big output buffer. This output buffer is unsafe and it is pinned for the duration of the operation (so we know it won’t move).

This methodology is not very general but it does help prevent a lot of other overhead.

Equality Compare (Custom Hash)

One of the slowest items in the code is the equality compare of an entry in the hash table.  Consider the following code

This code goes through character by character comparing our string in our hash to the string we wish to use (keep in mind that this gets called at least once for every probe to the hash). A better way of doing this would be unroll the loop a bit by using a (uint32*) to perform our comparison, as such we could compare two characters every iteration of the loop instead of just one (remember that a character is 16 bits).

We will however run into a problem comparing two characters at a time. What happens if we have a string with an odd number of characters? We only really have two choices about what to do here.  The first option is to loop 1 character short and then check the last character, this is a generally good solution but it can be optimized further if you can control the data coming in.

Since there is only one client for this hash we can definitely control the data coming in. Imagine the words cat, dog, and “the” in memory as shown below.

In this case we would need to use the above method (where we special case the last character and read it separately). Since we control the memory layout however we can avoid this by “aligning” the memory as follows.