Concurrent stack implementations in Ruby (relative performance of mutexes/CAS?) This code is very simple, but it is intended as an experiment in the relative performance of mutexes/CAS on different platforms. The latest version can always be found at:

https://github.com/alexdowad/showcase/blob/master/ruby-threads/concurrent_stack.rb

It comes with a built-in benchmarking script. Please try running and post the results, along with your OS, version of Ruby, and CPU. Please also post if you can find any way to improve style or performance.

For convenience the first version of the code is reproduced below:

# 3 thread-safe stack implementations
# Written by Alex Dowad

# Usage:
# stack.push(1)
# stack.peek    =&gt; 1 (1 is not removed from stack)
# stack.pop     =&gt; 1 (now 1 is removed from stack)

require 'rubygems' # for compatibility with MRI 1.8, JRuby
require 'thread'
require 'atomic'   # atomic gem must be installed

# The easy one first
class ThreadSafeStack
  def initialize
    @s,@m = [],Mutex.new
  end
  def push(value)
    @m.synchronize { @s.push(value) }
  end
  def pop
    @m.synchronize { @s.pop }
  end
  def peek
    @m.synchronize { @s.last }
  end
end

# a non-locking version which uses compare-and-swap to update stack
class ConcurrentStack
  Node = Struct.new(:value,:next)

  def initialize
    @top = Atomic.new(nil)
  end
  def push(value)
    node = Node.new(value,nil)
    @top.update { |current| node.next = current; node }
  end
  def pop
    node = nil
    @top.update do |current|
      node = current
      return if node.nil?
      node.next
    end
    node.value
  end
  def peek
    node = @top.value
    return if node.nil?
    node.value
  end
end

# same as ConcurrentStack, but additionally recycles popped nodes
# (to reduce load on GC)
# a global free list is used, and is also updated using CAS,
#   in exactly the same way as the stacks themselves
class RecyclingConcurrentStack
  Node      = Struct.new(:value,:next)
  FREE_LIST = Atomic.new(nil)

  def initialize
    @top = Atomic.new(nil)
  end
  def push(value)
    node = get_node(value)
    @top.update { |current| node.next = current; node }
  end
  def pop
    node = nil
    @top.update do |current|
      return if (node = current).nil?
      node.next
    end
    result = node.value
    FREE_LIST.update do |current|
      node.next = current
      node
    end
    result
  end
  def peek
    node = @top.value
    return if node.nil?
    node.value
  end

  private
  def get_node(val)
    # if contention causes the CAS to fail, just allocate a new node
    node = FREE_LIST.value
    if node &amp;&amp; FREE_LIST.compare_and_swap(node,node.next)
      node.value = val
      node
    else
      Node.new(val,nil)
    end
  end
end

# Test driver
if __FILE__ == $0
  require 'benchmark'
  ITERATIONS_PER_TEST = 1000000
  QUEUE,MUTEX = ConditionVariable.new,Mutex.new

  def wait_for_signal
    MUTEX.synchronize { QUEUE.wait(MUTEX) }
  end
  def send_signal
    MUTEX.synchronize { QUEUE.broadcast }
  end

  def test(klass)
    test_with_threads(klass,1)
    test_with_threads(klass,5)
    test_with_threads(klass,25)
  end

  def test_with_threads(klass,n_threads)
    stack = klass.new
    iterations = ITERATIONS_PER_TEST / n_threads
    puts "Testing #{klass} with #{n_threads} thread#{'s' if n_threads&gt;1}, iterating #{iterations}x each"

    threads = n_threads.times.collect do
                Thread.new do
                  wait_for_signal
                  iterations.times do
                    stack.push(rand(100))
                    stack.peek
                    stack.pop
                  end
                end
              end
    n_gc = GC.count
    sleep(0.001)

    result = Benchmark.measure do
      send_signal
      threads.each { |t| t.join }
    end
    puts result
    puts "Garbage collector ran #{GC.count - n_gc} times"
  end

  test(ThreadSafeStack)
  test(ConcurrentStack)
  test(RecyclingConcurrentStack)
end
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)