Another lesson in performance: NIO

Remember when I wondered how slow it is to copy data around in memory?

This time, I needed to load a 2MB file from disk and examine it for certain patterns.

The original from jazzy spell checker worked like this: It did a binary search in the file for a code. The code would be at the start of each line and be separated from the correct word by an asterisk:

    AT*wide
    AT*widow
    AT*width
    AT*wight
    AT*wit

The search algorithm would seek somewhere in the file, skip the current line, read the next one, compare the code against the one we look for. If our code was smaller, we would seek backward; if it was larger, we would seek forward. Standard binary search.

Only it didn’t work. The test took 4 seconds to load the file without finding anything. Debugging recursive algorithms isn’t as nice as looking at them …

So I considered a different approach: I would load the whole file, character by character, and remember the lines with the same code in an index. A good time to have a look at NIO, especially the grep example.

Question: If it takes 4 seconds to seek ten times in a RandomAccessFile and read about 2000 bytes from it, how long would it take to read it character by character, examine each line, build an index and then load whole chunks (say, 1KB each) from the file when a word needs to be looked up? Plus the additional work of removing the code pattern from the chunk to produce a list of words …

Answer: 0.3 seconds. That’s more than ten times faster. And I could probably optimize the code some more.

Conclusion: When it comes to performance, measurement beats superstition.

And the new code is easy to understand, and to test, too! ^_^

One Response to Another lesson in performance: NIO

  1. […] The original from jazzy spell checker worked like this: It did a binary search in the file for a… [full post] digulla Dark Views softwarejavanioperformance 0 0 0 0 […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s