Data.* collections maintenance

[Sebastian Sylvan]

On 10/24/05, Simon Marlow <simonmar at microsoft.com> wrote:
> On 22 October 2005 11:58, Adrian Hey wrote:
>
> > 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.
>
> It's not just benchmark code - in GHC we use Int-based maps all over the
> place for speed.  Given your promising results for polymorphic AVL
> trees, it's a fair bet that you could beat Data.IntMap with a
> specialised Int version.  If you did, we would be forced to use
> Data.Tree.AVL in GHC :)

Wouldn't an Array (or DiffArray) based HashMap be even better?

/S

--
Sebastian Sylvan
+46(0)736-818655
UIN: 44640862