🚀 go-pugleaf

A small idea yesterday:

Suppose the machine representation of one's data could transparently
mutate in response to the way one uses it.

For example, say I start out with a mythical data structure called a
'u-list' (universal list?).  I append a lot of data, one element at a
time, to it.  So at first I'd like the u-list simply to have a
singly-linked list representation in the machine.

Then for a while, I do a bunch of random accesses.  Now I'd like the
u-list to turn into an array.

Then I access the data with another (say, clumpy) pattern, like a[1],
a[21], a[2], a[22]... Now I'd like the data to somehow change its
organization to maximize locality of reference (wrt the specific
machine I'm on).

How often would the data's organization have to mutate?  Say, once
every few runs of the program.  Data on reference/use patterns would be
stored for each run, accumulated, analyzed, and possibly a new
organization applied every so often (e.g., once every 5 runs?).

Is this nuts?  Has it been done?  If so, in what contexts?

It may be tempting to reply:  well, just use a XYZ representation,
where XYZ is one of:
   skip-list, avl-tree, threaded-splay-tree, etc., etc.

but I think this misses the point.  (I think.)  There is no single
existing data structure that does *everything* well, i.e. use minimal
storage, and perform sequential access, random access, prepend, append,
arbitrary insertions, etc, all in constant order.  (at least, I haven't
run across such a data structure yet!)  so:  if my use of the data has
a pattern to it that changes (relatively) slowly over time (e.g.  over
a 5-run period), then having the data change its internal
representation to best suit what i seem to be doing with it *now*,
might make sense.

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* :-).

thoughts?

-- 
Lou Glassy (oususalg@cs.montana.edu)                  C Delenda Est