[Haskell-cafe] speed of hashing

[Michael Snoyman]

The real answer here is to benchmark; there's no way to know for certain
what will be faster in the abstract, especially without seeing your
implementation. That said: in order for a caching algorithm to work, you're
going to have to traverse your entire input list to perform a lookup.
Meaning: I'd be surprised if caching sped up this case. But again, that's
just a guess, benchmarking would be the only true answer.

Algorithms like this can often be significantly faster if you used an
unboxed vector[1] to hold the Ints instead of a list, so if you're
benchmarking, I'd recommend throwing that into the mix as well.

Finally: what were you considering using as a data structure to hold the
cache? I would imagine that using a HashMap would sort of defeat the
purpose in this case :)

Michael

[1]
https://www.stackage.org/haddock/lts-8.21/vector-0.11.0.0/Data-Vector-Unboxed.html

On Tue, Jul 4, 2017 at 5:09 AM, Dennis Raddle <dennis.raddle at gmail.com>
wrote:

> Hello, I have an application which could benefit from caching certain
> computations. For instance, I might have a function:
>
> listToWord :: [Int] -> Word16
>
> which takes an integer X in the input as referring to bit X in the output
> word, and sets the bits.
>
> I have to run this computation many times within the inner loop. So I
> thought I could cache it. The only trouble is that it may not be any less
> expensive to convert the [Int] into a hash value, or use it as a key to
> look up a binary Map.
>
> What do you think? Does Haskell hashing use some kind of optimized
> computation that's faster than me writing a loop by hand?
>
> D
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20170704/be61cbb6/attachment.html>