speed of hashing

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

speed of hashing

Dennis Raddle
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: 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


On Tue, Jul 4, 2017 at 5:09 AM, Dennis Raddle <[hidden email]> 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.


_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: speed of hashing

Dennis Raddle
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 tip.
D


On Mon, Jul 3, 2017 at 7:22 PM, Michael Snoyman <[hidden email]> 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[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


On Tue, Jul 4, 2017 at 5:09 AM, Dennis Raddle <[hidden email]> 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.



_______________________________________________
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.
Loading...