From: Pit Capitain <pit@...>
Date: 2005-09-07T01:22:39+09:00
Subject: Re: Sorted arrays

Ara.T.Howard schrieb:
> 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 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.

Interesting. What types of keys and values did you use?

Regards,
Pit