Eric Wong <normalperson / yhbt.net> wrote:
> Tried a singly linked list, but object allocation overhead sucks :<

Btw, it's in the "ll-queue" branch of git://bogomips.org/ruby
(http://bogomips.org/ruby.git/commit/?h=ll-queue) against trunk.

Performance sucks, but at least it appears to be linear as it grows:

$ for i in 1000 10000 100000; do ./trunk/ruby -I lib /tmp/zzz.rb $i; done
n = 100000
utime = 0.27999999999999997
n = 1000000
utime = 6.08
in = 10000000
utime = 57.82

(/tmp/zzz.rb is Joel's original script without Thread.pass)

> Maybe keeping the array small, swapping Thread#wakeup for Thread#run
> and calling Thread#run outside of the Mutex#synchronize block
> will be better...

Nope...  Throwing Thread.pass/Thread#run in various places didn't seem
to significantly improve over the Ruby linked list implementation.

Maybe this is worth revisiting: http://bugs.ruby-lang.org/issues/3620