[Haskell-cafe] speed of hashing
dennis.raddle at gmail.com
Tue Jul 4 09:21:38 UTC 2017
Thanks, I suspect you are right that caching wouldn't help. However, there
are several places that unboxed vectors might help me, so thanks for that
On Mon, Jul 3, 2017 at 7:22 PM, Michael Snoyman <michael at snoyman.com> wrote:
> 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 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 :)
>  https://www.stackage.org/haddock/lts-8.21/vector-0.11.
> On Tue, Jul 4, 2017 at 5:09 AM, Dennis Raddle <dennis.raddle at gmail.com>
>> 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?
>> Haskell-Cafe mailing list
>> To (un)subscribe, modify options or view archives go to:
>> Only members subscribed via the mailman list are allowed to post.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe