Data.* collections maintenance

[Adrian Hey]

Hello Christian

On Friday 21 Oct 2005 3:41 pm, Christian Maeder wrote:
> (It would also be handy if your modules could be passed to the same
> properties and performance checker if we had those.)

Yes, definining a common API which useable in actual applications
seems rather difficult, but even if we just agreed a common simple
API for correctness testing and benchmarking that would be useful
(these could be made much more thorough if they didn't have to
be re-written for each new implementation).

> A different performance profile is of course fine (and desirable if
> there is a big gain in certain or even most cases).

AVL seems to gain in two ways.

1- It does a better job of balancing in pathological cases like growing
   a tree from a sorted list (where the tree is not known to be sorted).

2- The Hedge algorithm seems to be a bit of a problem IMO. The actual
   benchmark times for AVL union and Data.Set union aren't
   significantly different for sets of Ints (AVL seemed marginally
   faster, but nothing to get excited about).
   But if you count the number of comparisons actually performed
   Data.Set (Hedge algorithm) is doing about 3..5 times as many
   comparisons. Presumably this would be reflected in measured
   execution times in cases where set element comparison was less
   trivial than comparing Ints.

Also, you'd expect the additional indirection overhead of using
an AVL tree of association pairs (vs. specialised Data.Map) to
slow down lookup somewhat. But it doesn't seem to significantly
IIRC, even with Ints. Not sure why. Maybe better balancing is
giving shorter search paths, or maybe use of Ord dictionary
passing (vs. HOFs) is more expensive.

One problem with AVL is the complexity of most of the code means
producing specialised unboxed implementations manually is not an
attractive proposition. Hopefully compilers will do this sort of
thing for us one day.

But in reality I expect this sort of thing to be more of an issue
for benchmark style code using Ints. For more complex keys and
comparisons the indirection cost will be relatively insignificant
I think. For polymorpic implementations counting the actual number
of comparisons required by some function is just as important IMO.

> So far, the problem always was to agree on an accepted interface (that I
> didn't want to be a class but leave to the discipline of library writers.)
>
> How about something like Data.Set.Tree.AVL (and Data.Set.Seq.Ordered)
> or Data.SetByAVLTree (and Data.SetByOrderedSeq)?

Dunno. At one time I did have something like Data.Tree.AVL.Clone.Data.Set
and Data.Tree.AVL.Clone.Data.Map, but I never actually posted the
implementations. (I wish I had now because it seems I've lost them.)

Regards
--
Adrian Hey