Mutating Data Organization: Practical? 
Author Message
 Mutating Data Organization: Practical?

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?

--



Sat, 18 Feb 1995 22:26:43 GMT  
 Mutating Data Organization: Practical?

Quote:

>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.

Quote:
>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.




Sun, 19 Feb 1995 02:29:25 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. Practical solutions for dealing with null/missing value data

2. CFP: The Practical Application of Knowledge Discovery and Data Mining (PADD98)

3. Bug: Mutating a ListView

4. Dolphin (All Versions) Mutate View Issue (and maybe a fix)

5. Dolphin 98 Mutate View Bug?

6. Why can't I mutate Object in Visual Smalltalk

7. Why can't I mutate Object in Visual Smalltalk

8. return value of mutating methods

9. mutating python VM opcodes

10. Mutate an immutable?

11. mutating params passed by ref

12. Detecting mutating viruses

 

 
Powered by phpBB® Forum Software