[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]
January 18, 2009 at 11:05 pm |
[...] Handwaving “glossing over detail for the sake of time or clarity” « Concurrent Skip List woes [...]
June 10, 2009 at 3:04 pm |
Thanks for posting this source. This was the only thread safe C# skip list I could find and it was a lot easier to adapt this than to make my own from one of Pugh’s papers.
I found what I think are two bugs in the posted source.
The first is on line 37. You’re follow up post says it isn’t needed, but I found if the randomLevel wasn’t capped, I would get a level for my new node greater than the max height used to declare a new node’s next lists.
The second is on line 59. I’m fairly sure the ‘lFound.HasValue’ in ‘if (lFound.HasValue && v.CompareTo(curr.key) == 0)’ should be ‘!lFound.HasValue’ otherwise there’s no opportunity for that function to ever initialize the variable and succeed in the find.
August 25, 2009 at 4:53 pm |
You are right about both bugs. On the first, I changed it so it doesn’t ask for a MaxHeight anymore. On the second, I failed to copy the code from the paper correctly. Your fix is correct.
August 26, 2009 at 3:52 pm |
[...] Skip List issues By Pinku A commenter on my code sample for a concurrent skiplist correctly pointed out two errors in the program. I [...]