[Haskell-cafe] Re: Data.HashTable

[gwern0 at gmail.com]

On 2008.03.06 22:43:53 +0100, Johannes Waldmann <waldmann at imn.htwk-leipzig.de> scribbled 1.4K characters:
> > In practice, Data.Map outperforms it in essentially all cases
> > (Data.HashTable stops working beyond a certain size and so any
> > asymptotic benefits, if they exist at all, don't have time to kick
> > in).
>
> What!
>
> I learned at school, and I teach my students,
> * balanced binary tree: costs are log(size)
> * hashtable: cost are essentially constant
> therefore, hashtable should be preferred in almost all cases
> (if you know a reasonable hash function
> and except where you need persistency, of course)
>
> the difference should be visible even for moderate sizes
> (e.g. 1000). With a reasonable implementation  I expect
> log(1000) = 10 comparisons (and dereferencings) for the tree;
> while the hashtable should have the computation of the hash value
> (ideally, in registers), one memory access, and one comparison.
>
> ... but indeed some experiments with Data.Map and Data.Hashtable
> support the point you made. That's either good for Data.Map
> or bad for Data.Hashtable.
>
> PS: I did not manage to compile HsJudy-1.0 with ghc-6.8.2
> (some hsc file missing - perhaps that should be auto-generated? how?)
>
> Best regards, Johannes.

Oh... I'm terribly sorry about that. It was I who uploaded HsJudy.

The problem was, it's maintained by the Pugs project for some reason. The directory structure looks like:

pugs/
      thirdparty/
                 HsJudy/
                 hsregex/
                 HsSyck/
                 installed/
                 judy/
                        Judy-1.0.3/

Here Judy-1.0.3/ contains the actual C library Judy itself. So what the Cabalized package residing in HsJudy/ was doing was literally linking against stuff like '../judy/Judy-1.0.3/src/JudyL/*.o'.

At the time I was packaging, Cabal didn't yet warn about problems like ../, so it would build and install just fine when I ran it with no problems; but I forgot that obviously all the ../ stuff would totally break in an sdist tarball.

I think I've fixed it: <http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HsJudy-0.1.1>.

--
gwern
Air eavesdropping pipe-bomb TSCM Centro ^X JIC TWA USACIL Protection
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20080307/248c8f7a/attachment.bin