Hashtables: 'Basic' hashtables performance quirks on Win64

[Gregory Collins]

Can you isolate which of the hash table instances is slow? The basic hash
table uses linear probing and may perform badly if the hash function has
poor clustering behavior. Some versions of "hashable" set "hash = id" for
Int, which may not help matters.

The benchmarks I have, as you suggest, say that it performs well -- but
they are incomplete. I can't optimize what I don't test: if you can isolate
a minimal example where it performs much worse than it should, I would
appreciate that.

As far as Windows goes, I don't use it and don't have access to such a
machine, I would need help to debug and fix this.

G



On Sat, Jan 18, 2014 at 10:38 AM, kyra <kyrab at mail.ru> wrote:

> Having built Agda on 64-bit GHC 7.6.3 on Windows I've stumbled on Agda
> being unbearable slow (I tried it on Penryn and Sandy Bridge computers).
> The culprit turned out to be Agda uses 'BasicHashTable' in
> src/full/Agda/TypeChecking/Serialise.hs (line 98).
>
> Switching either to Cuckoo or Linear immediately cures the problem.
>
> The problem does not manifest itself on 32-bit Windows build or any Linux
> build.
>
> Also 'Basic' hashtable perform better than Cuckoo and Linear in standard
> benchmarks on Win64. And at the same time in Agda scenario it's performance
> degrades by a *couple of orders of magnitude*!
>
> Thus, *all* things are important here: 64-bit, Windows, Agda use case.
>
> I wonder what stands behind this behaviour? What are specifics of 'Basic'
> hashtable implementation and how to fix this or should this be fixed at all?
>
> Regards,
> Kyra
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>



-- 
Gregory Collins <greg at gregorycollins.net>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20140118/507fdd8b/attachment.html>