small pgms using big data?

[cs.utexas.edu!uwm.edu!ux1.cso.uiuc.edu!ux1.cso.uiuc.edu!uicbert.eecs.uic.edu!lam@yale-zoo.arpa]

I'm looking for scheme programs to test different aspects of garbage 
collectors.  For now, I'm looking for *small* programs that operate
on *large* amounts of data.  Programs that have some sort of size
parameter, to scale the problem size and data usage, would be ideal.

One such program (which we already have) is an n queens program,
where we can scale the problem size by setting n to different values.
(Don't offer us that one, though -- we've already got it.)


Other good programs would be things like chess programs with alpha-
beta pruning, which we could scale by setting the number of lookahead
moves.

Branch-and-bound and transitive closure kinds of things would
be interesting, especially if the inputs are in a fairly simple
format.  (E.g., the dataflow phase of a compiler would be good,
if it wouldn't be hard to isolate and port to a very vanilla
Scheme, and we could just read representative inputs from
a file or something.)


Our main desiderata are:

  1) that the programs be fairly easily ported (in particular, to
     a Scheme with very few extensions, and in which #F and '()
     are two distinct objects.)

  2) scalability via either a simple parameter or choice of
     input problem

  3) representativeness of some important class of algorithms --
     e.g., things that explore state spaces in something like
     a depth-first way, where only the representations on
     the current path are live, and those that keep around
     representations of things already reached, like branch-
     and-bound.

(I don't mean to overstress AI-type algorithms -- these are just
examples.  We just want small programs whose overall processing
patterns resemble those of more serious programs, and which scale.)


Ultimately, we want to put together a set of benchmark programs
that can be used to stress different aspects of a garbage
collector over a range of problem sizes.

Please reply via email.  If there's interest, I'll summarize
to the net.

    -- Mike Lam

Software Systems Laboratory          lam@bert.eecs.uic.edu
EECS Dept. (m/c 154)
University of Illinois at Chicago
Box 4348 Chicago IL 60680