From: Hugh Sasse <hgs@...>
Date: 2005-09-07T01:32:38+09:00
Subject: Re: Sorted arrays

On Wed, 7 Sep 2005, Ara.T.Howard wrote:

> On Wed, 7 Sep 2005, Hugh Sasse wrote:
>
>> Other speed tips I've been gathering are at:
>> 
>> http://www.eng.cse.dmu.ac.uk/~hgs/ruby/performance/
>> 
>> you'll see I was trying to solve a similar problem....
>
> what did you end up doing?  i forgot you were working with csv data - did you
> consider using sqlite, loading everything into an in-memory table, and going
> from there?  could be very fast and quick to code...

I found that the real time-killer was the CSV library itself.  This
is fair enough: it takes account of all sorts of things like if the
strings contain quotes and commas.   For the input I've been given
this never happens, so it was much faster to use split to separate
the fields -- by which I mean that several hours dropped to about 5
minutes.  This was sufficient speedup for my purposes.
>
> on a related note, i did some research into lookups in c using hahses verses
> sorted arrays/bsearch; much to my suprise (as a computer scientist) i found
> that, with the exception of HUGE (millions) of entries lookup by bsearch was
> and order of magnitude faster than any hashing mechanism i could find.  my

I'm not too surprised (with this hindsight :-)) because the address
calculations are probably cheaper than the full hashing
we'd-have-to-cope-with-a-whole-bunch-of-hashable-things function.

> test looked at cdb, hsearch, glib hashing functions, gperf and, for bsearch,
> the c library bsearch.  profiling the different programs showed that the
> reason the bsearch was faster was speedy was due to lack of function calls
> and this is easy to imagine - flipping a pointer around memory with only one
> stack frame is about as lightweight as one can get...  anyhow, my tests were
> very specific to my application but interesting nonetheless - thought you'd 
> be
> interested.

Yes, and I do wonder (as someone who has not looked at the code to
this extent) how much more speed we could wring out of the ruby
implementations.
>
> cheers.
>
> -a

         Thank you,
         Hugh