home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / lang / misc / 2848 < prev    next >
Encoding:
Internet Message Format  |  1992-09-01  |  2.3 KB
  1. Path: sparky!uunet!stanford.edu!ames!think.com!barmar
  2. From: barmar@think.com (Barry Margolin)
  3. Newsgroups: comp.lang.misc
  4. Subject: Re: Mutating Data Organization:  Practical?
  5. Date: 1 Sep 1992 18:29:25 GMT
  6. Organization: Thinking Machines Corporation, Cambridge MA, USA
  7. Lines: 39
  8. Message-ID: <180cq5INNf0t@early-bird.think.com>
  9. References: <1992Sep1.142643.3061@coe.montana.edu>
  10. NNTP-Posting-Host: telecaster.think.com
  11.  
  12. In article <1992Sep1.142643.3061@coe.montana.edu> oususalg@cs.montana.edu (Glassy) writes:
  13. >Suppose the machine representation of one's data could transparently
  14. >mutate in response to the way one uses it.
  15.  
  16. I've seen data structures that mutate in response to the contents, but not
  17. to the references.  For instance, different hash table designs are
  18. appropriate for different sizes of hash tables.  The Symbolics
  19. implementation of Common Lisp hash tables uses different strategies for
  20. different sizes.
  21.  
  22. >i mentioned that i'd like to do this mutation 'transparently', because
  23. >as a user of the data, i don't care what its internal representation
  24. >is, as long as i can efficiently monkey with the data right *now* :-).
  25.  
  26. I don't think it is reasonable to expect good performance in response to a
  27. heuristic determination of access patterns, as you suggest.  By the time
  28. the heuristic recognizes a pattern and mutates the data structure, the
  29. pattern may be mostly done and it's too late.  For instance, if it takes 10
  30. accesses to establish a recognizable pattern, and the application typically
  31. does 11 accesses of a particular type in a row, the data structure is going
  32. to mutate just before the last access, which is going to be pessimal.  And
  33. one or two unusual accesses in the middle of a pattern are likely to
  34. confuse the heuristics.
  35.  
  36. However, I agree with you that the user shouldn't be concerned with the
  37. representation, either.  However, providing higher-level access hints is
  38. not the same thing as requesting a particular implementation.  Thus, one
  39. might write:
  40.  
  41. access_mode(data_structure, MODE_SEQUENTIAL);
  42.  
  43. to indicate that upcoming access to the structure will be sequential.  It's
  44. up to the implementation of the data structure to translate that into
  45. whatever representational strategy is appropriate.
  46. -- 
  47. Barry Margolin
  48. System Manager, Thinking Machines Corp.
  49.  
  50. barmar@think.com          {uunet,harvard}!think!barmar
  51.