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.