benchmarking data structures (was: How lazy is DData.Seq?)

Malcolm Wallace Malcolm.Wallace at
Thu May 20 12:43:21 EDT 2004

ajb at writes:

> The best implementation is the one that matches the characteristics
> of your application/data the closest.
> Of course, it's usually not obvious what those characteristics are
> in advance.

There is a data-structure benchmarking kit called "auburn"
sadly no longer actively maintained.

One of the things it can do is to generate "datatype usage graphs"
(dugs) for any given abstract datatype.  These record information like
the relative proportions of appends,reads,writes, etc. in a particular
usage scenario.  A series of competing implementations of the abstract
datatype can be benchmarked against a series of randomly generated
dugs.  Furthermore, auburn has an automated decision procedure for
deciding which implementation would be best for your application,
based on the previous benchmarking.


More information about the Libraries mailing list