Concurrent stack implementations in Ruby (relative performance of mutexes/CAS?)
I took the latest source code from the github and have started review of this project. Here are my benchmarks results:

# Intel(R) Core(TM)2 Duo CPU     P7570  @ 2.26GHz
# ruby 1.9.2p290 (2011-07-09 revision 32553) [i686-linux]
Testing ThreadSafeStack with 1 thread, iterating 1000000x each
  2.250000   0.000000   2.250000 (  2.254392)
Garbage collector ran 0 times
Testing ThreadSafeStack with 5 threads, iterating 200000x each
  2.350000   0.020000   2.370000 (  2.533645)
Garbage collector ran 0 times
Testing ThreadSafeStack with 25 threads, iterating 40000x each
  2.890000   0.780000   3.670000 (  3.170657)
Garbage collector ran 0 times
Testing ConcurrentStack with 1 thread, iterating 1000000x each
  2.840000   0.000000   2.840000 (  2.836545)
Garbage collector ran 54 times
Testing ConcurrentStack with 5 threads, iterating 200000x each
  2.850000   0.010000   2.860000 (  2.871540)
Garbage collector ran 54 times
Testing ConcurrentStack with 25 threads, iterating 40000x each
  2.880000   0.000000   2.880000 (  2.881745)
Garbage collector ran 56 times
Testing RecyclingConcurrentStack with 1 thread, iterating 1000000x each
  3.910000   0.000000   3.910000 (  3.906049)
Garbage collector ran 0 times
Testing RecyclingConcurrentStack with 5 threads, iterating 200000x each
  3.900000   0.000000   3.900000 (  3.910919)
Garbage collector ran 0 times
Testing RecyclingConcurrentStack with 25 threads, iterating 40000x each
  3.960000   0.000000   3.960000 (  4.024026)
Garbage collector ran 0 times


With jruby 1.6.5 (ruby-1.8.7-p330) I encountered a deadlock. With JRruby it is reproduced each time I ran the benchmark, but with MRI I've seed it only once so far. I will try to find the cause and post an update here.



UPDATE

I reviewed the implementation of concurrent stacks and did not found anything that may cause deadlocks or other issues. Looks like deadlock is caused by benchmarking code. With JRuby it just hangs (very frequently). With MRI I received 'deadlock detected' exceptions:

Testing ConcurrentStack with 25 threads, iterating 40000x each
/home/alex/Projects/read-write-lock/concurrent-stack.rb:143:in `join': deadlock detected (fatal)
    from /home/alex/Projects/read-write-lock/concurrent-stack.rb:143:in `block (2 levels) in test_with_threads'
    from /home/alex/Projects/read-write-lock/concurrent-stack.rb:143:in `each'
    from /home/alex/Projects/read-write-lock/concurrent-stack.rb:143:in `block in test_with_threads'
    from /usr/share/ruby-rvm/rubies/ruby-1.9.2-p290/lib/ruby/1.9.1/benchmark.rb:295:in `measure'
    from /home/alex/Projects/read-write-lock/concurrent-stack.rb:141:in `test_with_threads'
    from /home/alex/Projects/read-write-lock/concurrent-stack.rb:120:in `test'
    from /home/alex/Projects/read-write-lock/concurrent-stack.rb:150:in `&lt;top (required)&gt;'
    from -e:1:in `load'
    from -e:1:in `&lt;main&gt;'


And

/home/alex/Projects/read-write-lock/concurrent-stack.rb:143:in `join': deadlock detected (fatal)
    from /home/alex/Projects/read-write-lock/concurrent-stack.rb:143:in `block (2 levels) in test_with_threads'
    from /home/alex/Projects/read-write-lock/concurrent-stack.rb:143:in `each'
    from /home/alex/Projects/read-write-lock/concurrent-stack.rb:143:in `block in test_with_threads'
Testing RecyclingConcurrentStack with 1 thread, iterating 1000000x each
    from /usr/share/ruby-rvm/rubies/ruby-1.9.2-p290/lib/ruby/1.9.1/benchmark.rb:295:in `measure'
    from /home/alex/Projects/read-write-lock/concurrent-stack.rb:141:in `test_with_threads'
    from /home/alex/Projects/read-write-lock/concurrent-stack.rb:118:in `test'
    from /home/alex/Projects/read-write-lock/concurrent-stack.rb:152:in `block in &lt;top (required)&gt;'
    from /home/alex/Projects/read-write-lock/concurrent-stack.rb:151:in `loop'
    from /home/alex/Projects/read-write-lock/concurrent-stack.rb:151:in `&lt;top (required)&gt;'
    from -e:1:in `load'
    from -e:1:in `&lt;main&gt;'


As far as I can see, the only thing that may cause deadlock is situation when main thread does QUEUE.broadcast and then does Thread#join on the thread but this thread did not executed QUEUE.wait yet. Then main thread infinitely waits for this thread and MRI may detect such deadlock situation.

When I increased sleep time from 0.001 to 0.01 and more it seemed that deadlock has gone. Looks like this issue is caused by long thread initialization time - sometimes it cannot start block execution for all threads before QUEUE.broadcast call.

Also, as a small improvement, the following code may be extracted into private function like cache_node to improve pop method readability:

FREE_LIST.update do |current|
  node.next = current
  node
end


Stack implementation looks correct and clear, I did not found other issues.



With sleep == 0.05 benchmarks for JRuby are these:

# jruby 1.6.5 (ruby-1.8.7-p330) (2011-10-25 9dcd388) (Java HotSpot(TM) Server VM 1.6.0_26) [linux-i386-java]
Testing ThreadSafeStack with 1 thread, iterating 1000000x each
  2.881000   0.000000   2.881000 (  2.881000)
Testing ThreadSafeStack with 5 threads, iterating 200000x each
  2.658000   0.000000   2.658000 (  2.658000)
Testing ThreadSafeStack with 25 threads, iterating 40000x each
  2.885000   0.000000   2.885000 (  2.885000)
Testing ConcurrentStack with 1 thread, iterating 1000000x each
  2.142000   0.000000   2.142000 (  2.142000)
Testing ConcurrentStack with 5 threads, iterating 200000x each
  1.084000   0.000000   1.084000 (  1.084000)
Testing ConcurrentStack with 25 threads, iterating 40000x each
  0.969000   0.000000   0.969000 (  0.970000)
Testing RecyclingConcurrentStack with 1 thread, iterating 1000000x each
  2.628000   0.000000   2.628000 (  2.628000)
Testing RecyclingConcurrentStack with 5 threads, iterating 200000x each
  1.436000   0.000000   1.436000 (  1.436000)
Testing RecyclingConcurrentStack with 25 threads, iterating 40000x each
  1.473000   0.000000   1.473000 (  1.473000)