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]

Advertisements

4 comments

  1. Pingback: Complexity Matters « Handwaving
  2. D Meatte

    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.

    • Pinku

      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.

  3. Pingback: Concurrent Skip List issues « 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