Map for FGL

[Adrian Hey]

Hello,

On Monday 09 Jan 2006 1:11 pm, Christian Maeder wrote:
> Hi,
>
> I wonder how well
>
> http://www.haskell.org/ghc/docs/latest/html/libraries/fgl/Data-Graph-Induct
>ive-Internal-FiniteMap.html
>
> performs wrt. other Map implementations.
>
> It may be worth replacing this implementation, too.

I suspect it doesn't compare too well with Data.Tree.AVL, though I've
never measured it to be honest. It's based on "AVL trees" (or rather
trees where left and right sub-tree heights differ by at most 1), but
doesn't seem to use the AVL algorithm itself. IIRC it stores (boxed!)
height in each tree node, not "balance factor". As well as requiring
an extra field (same as Adams) this also causes other inefficiencies.
Insertion requires inspection of nodes which aren't on the insertion
path to determine the balance factor, which has gotta slow things down.

That said, it should still do a pretty good job of balancing and the
balancing mechanism itself and node size will have little impact on
look up times (for example).

It'd be worth a look at to see what functions this provides that
weren't provided by the old FiniteMap implementation, and whether or
not these are still absent from Data.Map (I believe this was the
original motivation for FGL having it's own private implementation in
the first place).

Regards
--
Adrian Hey