🚀 go-pugleaf

In article <1992Sep1.142643.3061@coe.montana.edu> oususalg@cs.montana.edu (Glassy) writes:
>Suppose the machine representation of one's data could transparently
>mutate in response to the way one uses it.

I've seen data structures that mutate in response to the contents, but not
to the references.  For instance, different hash table designs are
appropriate for different sizes of hash tables.  The Symbolics
implementation of Common Lisp hash tables uses different strategies for
different sizes.

>i mentioned that i'd like to do this mutation 'transparently', because
>as a user of the data, i don't care what its internal representation
>is, as long as i can efficiently monkey with the data right *now* :-).

I don't think it is reasonable to expect good performance in response to a
heuristic determination of access patterns, as you suggest.  By the time
the heuristic recognizes a pattern and mutates the data structure, the
pattern may be mostly done and it's too late.  For instance, if it takes 10
accesses to establish a recognizable pattern, and the application typically
does 11 accesses of a particular type in a row, the data structure is going
to mutate just before the last access, which is going to be pessimal.  And
one or two unusual accesses in the middle of a pattern are likely to
confuse the heuristics.

However, I agree with you that the user shouldn't be concerned with the
representation, either.  However, providing higher-level access hints is
not the same thing as requesting a particular implementation.  Thus, one
might write:

access_mode(data_structure, MODE_SEQUENTIAL);

to indicate that upcoming access to the structure will be sequential.  It's
up to the implementation of the data structure to translate that into
whatever representational strategy is appropriate.
-- 
Barry Margolin
System Manager, Thinking Machines Corp.

barmar@think.com          {uunet,harvard}!think!barmar