[ruby-talk:19002] How to optimize a Ruby program?

I've come up with my first Ruby program (below). Actually, it's a
library module that implements the Hunt/McIlroy "diff" algorithm. It was
pretty fast to write (I more or less translated it from my Perl CPAN
module), but it may not have  been a great choice. (I'm going to post it
to RAA, so I'll have more questions about the right way to package it).

I'm a bit frustrated with the speed. On a pair of 4000 line arrays of
text, it runs on my machine in 35 seconds. My Perl code, on the other
hand, does the same job in 25 seconds. Of course, it's fast enough on
smaller arrays.

I've looked at it quite a bit, and even wrote a line profiler, but can't
manage to make it much faster.

The single biggest chunk of time is spent in the binary search routine
in replaceNextLargerWith(). I found that I could make it a tiny bit
faster by doing a single <=> and then using equal? to compare with
literal -1 and 1.

Anyway, I'd appreciate it if someone could give me some advice as to how
to make it more competitive with Perl's speed. I'd rather keep it pure
Ruby, instead of making a C extension.

Another question is the API. Note that there is a keyGen and a compare
method (that call hash() and eql?() respectively by default); I'd expect
people using this module with specialized data types  to override these
if necessary.

But in traverseSequences, there are up to 5 callbacks so that user code
can be called at the right times. Should this require inheritance or
overriding, or is the Ruby Way to pass in multiple Method or Proc
instances?

Thanks,
-- 
Ned Konz
currently: Stanwood, WA
email:     [e-mail]
homepage:  http://bike-nomad.com