Thursday, May 8, 2008

Surprising findings using Ruby Arrays as Queues

I'm working on an Aho-Corasick implementation in Ruby, and found something interesting about Ruby. Well, something interesting to a relative newbie, I suppose... Arrays are the Ruby object that people use for Queues in Ruby. Which is a little odd, because the performance of Ruby arrays as queues is pretty poor. Worse, in fact, than inserts into a Hash. This is probably due to the fact that pushing objects into an array requires growing the array. Furthermore, I found that the performance of Array#+ is better than Array#push and Array#<<, even though all three methods ostensibly do the same thing. It turns out that Ruby does have a Queue object that performs well. It's intended for producer/consumer operations across multiple threads, but nonetheless it performs much better as a Queue than arrays do. Here it is, the Queue class in all its glory.