Concurrent Skip List issues

A commenter on my code sample for a concurrent skiplist correctly pointed out two errors in the program. I attempted to fix both, but further testing revealed another problem in Release mode (optimized, no debug). One of the thread would suddenly stop. After much screwing around, I discovered that the program was stuck in a spin wait: “while (!goAhead) ;”. I added a volatile declaration to that variable and then the program worked. It turns out the loop keeps reusing the value in the register, rather than reloading the variable when another thread says it’s OK to go.

I’ve put the code in Launchpad and removed it from the other post. You can download it like this using the Bazaar VC tool:

bzr branch lp:~suranap/+junk/

There’s still a problem with the program. When I run 2 threads, it is really quick. When I run 4 threads, there is so much contention that the “add” method has to retry a zillion times. Of course, my test case is probably extreme. I’ll compare the performance with Java’s implementation to see if it’s in the same league.


One comment

  1. Pingback: Concurrent Skip List woes « Handwaving

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s