Optimizing DictionaryReader

Warning: I'm talking about computer science here.

In the last days, I noticed increased activity in the DictionaryReader project, mostly caused by Yen-Ju working off the remaining bugs. Amongst others, he fixed bug 8497, which annoyed me for quite some time back when I programmed on DictionaryReader. The fix is particularly cool, so I want to share it with you.

Let's first have a look at the application: DictionaryReader is an application that allows you to look up words in local and online dictionaries. The format used for locally stored dictionaries is a seemingly undocumented format which is also used by the Dict.org server. The Dict.org server is the de-facto standard for online dictionary services. In this format, each dictionary consists of two files:

When the dict.org server program starts up, it can read in the index files and store the description positions in RAM for fast access. This is exactly what DictionaryReader does as well, but there's a small difference: Where the dict.org server is already running when the user requests a word lookup, DictionaryReader is possibly just starting up then and still needs to read in the index files. And this was terribly slow until Yen-Ju reduced the time to scan an index file by about 30%-40%.

The index file consists of lines of the following format:

term/word TAB startposition-coded-as-Base64 TAB length-coded-as-Base64

The original version of DictionaryReader's algorithm to read in the index file read in the line part-by-part, parsing the Base64-coded integers, and creating an instance of the specially crafted BigRange class. Creating this class was an ugly hack that was necessary because the Cocoa/GNUstep NSRange datatype is unfortunately a C struct and thus can't be stored in the NSDictionary-hashmap, which maps dictionary entries (words, terms) to the position of their description.

Yen-Ju's clever solution is actually quite obvious: Don't parse the Base64-coded integers directly, but store the two unparsed integers directly in the hashmap. This results in higher memory usage per term, but it frees us from allocating BigRange objects in addition to the strings, which are possibly allocated anyway internally. As allocations are expensive, the speed improvement is quite good. A cool hack, and Yen-Ju even got rid of the ugly BigRange-class. :-)

I think it's amazing. :-) Look at the patch here.