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.

Concurrent Skip List woes

[ed: I've removed the code. Look here for an explanation and the updated code.]

Java has a very fast, very complex ConcurrentSkipListMap, but .NET does not. I implemented a simpler concurrent skip list algorithm (pdf) in C#. I ran 2 threads to add/remove entries with high contention. It runs quickly for a short time and then suddenly slows to a crawl. I haven’t figured out the problem yet. I’m not even sure how to debug it. Code after the jump. [fixed it, explanation here]

Numbers everyone should know

Jeff Dean, a brilliant engineer at Google, gave a talk a while ago listing the numbers every engineer should know. I copied these from here.

• L1 cache reference 0.5 ns
• Branch mispredict 5 ns
• L2 cache reference 7 ns
• Mutex lock/unlock 100 ns
• Main memory reference 100 ns
• Compress 1K bytes with Zippy 10,000 ns
• Send 2K bytes over 1 Gbps network 20,000 ns
• Read 1 MB sequentially from memory 250,000 ns
• Round trip within same datacenter 500,000 ns
• Disk seek 10,000,000 ns
• Read 1 MB sequentially from network 10,000,000 ns
• Read 1 MB sequentially from disk 30,000,000 ns
• Send packet CA->Netherlands->CA 150,000,000 ns