Complexity Matters

In my previous post, I complained that the performance of my concurrent skiplist was outrageously slow. I ran it with a profiler, but all operations were slow. By accident I narrowed it down to the randomLevel function. Then I realized that I had limited the height of the skiplist to 6 when I was testing it. This is fine for a small collection of 2^6 (=64) items. In my performance testing, I was using a list of 200K items. That means the bottom row contains a singly-linked list of ~3000 items which must be searched linearly. That is very very slooow. The morals of the story are that (1) complexity effects performance enormously and (2) it’s hard to find those bottlenecks by just profiling and staring at code.

The solution is to remove the call to Math.Min in line 37. It runs fine after that.

Advertisements

One comment

  1. Pingback: Concurrent Skip List woes « Handwaving

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