[Haskell-cafe] Re: Performance question

Achim Schneider barsoap at web.de
Fri Mar 19 03:21:28 EDT 2010

Arnoldo Muller <arnoldomuller at gmail.com> wrote:

> Right now, the bottleneck of my program is in binarySearch', the
> function must be called a few billion times.
> Do you have any ideas on how to improve the performance of this
> function?
The fastest way to do a binary search is to reify it into code using
TH, in Van Emde Boas layout if it's a big enough search (so that you
get less cache misses)

This might of course get tricky if your tree isn't compile-time static,
but if you're really doing gazillions of lookups, occasionally
compiling+dynamically linking code might well be worth it.

(c) this sig last receiving data processing entity. Inspect headers
for copyright history. All rights reserved. Copying, hiring, renting,
performance and/or quoting of this signature prohibited.

More information about the Haskell-Cafe mailing list