Mutating Data Organization: Practical?

Thread View: comp.lang.misc

2 messages

[T] Back to Threads [V] Tree View [G] Group Articles

2 total messages Started by Glassy Tue, 01 Sep 1992 14:26

#1097

Author: Glassy
Date: Tue, 01 Sep 1992 14:26

47 lines
2525 bytes

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

Re: Mutating Data Organization: Practical?

#1098

Author: Barry Margolin
Date: Tue, 01 Sep 1992 18:29

39 lines
2390 bytes

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

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads