home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / mitsch75.zip / scheme-7_5_17-src.zip / scheme-7.5.17 / src / wabbit / headhunt.text next >
INI File  |  1994-02-08  |  6KB  |  101 lines
  1. [File ~ziggy/Thesis/PhD/BreakPoint/headhunt.text]
  2. -----
  3. Goal: Find all Scheme objects that point to any element of a target vector of
  4.       objects, returning the result in a specified buffer. If there are more
  5.       pointing objects than slots in the buffer, return a status flag
  6.       indicating that there may be more pointing objects (so the caller can
  7.       frob the pointers already found then call findptrs again).
  8.  
  9. ----------
  10. Interface:
  11.  
  12.   Given: TARGET-VECTOR  - a vector of target objects, and 
  13.          POINTER-BUFFER - a buffer for accumulating objects that point to
  14.                             elements of the TARGET-VECTOR
  15.          [RTN-AGG-VECT? - optional flag requesting ptr to vector of all
  16.                             aggregates live after GC]
  17.  
  18.   Effect: Fills POINTER-BUFFER with objects that point to elements of
  19.                 TARGET-VECTOR.
  20.  
  21.   Returns: Three values
  22.              - A flag indicates whether all pointers to TARGET-VECTOR elements
  23.                could fit in POINTER-BUFFER.
  24.          - A flag indicating if more pointers to TARGET-VECTOR elements may
  25.                exist but could not be isolated in this GC pass.  Next pass may
  26.                succeed in isolating them all (? compression after-effect) or it
  27.                may always fail into more objects are released.
  28.              - Either false when RTN-AGG-VECT? is false (i.e., not requested)
  29.                otherwise it is a vector of all aggregates or false if the
  30.                vector was too big to fit in available memory.
  31. -------------
  32. Idea [Jinx's]
  33.  
  34. Embed hack in a copying GC-like memory sweep as follows:
  35.  
  36.    FROM SPACE: .-----------------------------.
  37.                |                             | FROM TOP (hi addr)
  38.                `-----------------------------'
  39.  
  40.      TO SPACE: .-----------------------------.
  41.                |                             |   TO TOP (hi addr)
  42.                `-----------------------------'
  43.                  ^      ^                ^
  44.                  | ->   | ->          <- |
  45.                  |      |                |
  46.                 Scan   Free             Heads
  47.  
  48.  Scan and Free move as w/ a normal copying GC.
  49.  Each aggregate datum [e.g., pair, vector, cell, code block, closure, etc] that
  50.   is encountered has a pointer to its head copied into Heads.  Whenever one of
  51.   the elements in the TARGET-VECTOR is encountered, some object whose head is
  52.   right of Heads must have pointed to it. Scan through head space to find it.
  53.  NB: This Scan through head space can be conducted as a binary search since the
  54.   pointers to aggregate heads (in TO space) are in order R->L monotonically
  55.   increasing (because they are copied as Free drifts to the right). When
  56.   a target datum is sighted, the aggregate pointing to that target has To-space
  57.   address that is the lesser of the two consecutive entries in head space which
  58.   straddle the Scan pointer.
  59.  If Free collides w/ Heads, continue the copying GC as normal, abandonning any
  60.   further findptr hackery, but set the ALL-FIT-IN-PTR-BUFF flag to false (to
  61.   return).
  62.  Extra boon: if the GC completes w/o encrouchment then Heads points to
  63.   the first element of a L->R consecutive array containing ptrs to all
  64.   aggregate objects in TO space. By plopping down a VECTOR header left of Head
  65.   (if there is a free slot to the left of Heads), this array can be instantly
  66.   reified into a Scheme vector. Free cells are then those between Free and
  67.   Heads (or the Heads vector could be btblt'd left into the Free cells. Such a
  68.   vector handle may be useful for various statistics and bookkeeping frobs, so
  69.   it could be returned to the user if a handle on this vector is requested
  70.   (otherwise, the array can just be abandonned in TO space and treated as free
  71.   cells). Naturally, such a vector should not be retained long, however, since
  72.   it stands to consume a fair fraction of space in TO space. If not desired,
  73.   Heads can be set to TO-space TOP when the GC completes, and again the free
  74.   cells are those between Free and Heads.
  75.  
  76.  --*--
  77.  
  78.  Ziggy observation 1: actually, even after Free has encroached on Heads, we can
  79.   still keep an eye out for TARGET-VECTOR elts and scan from right of Free
  80.   into remaining heads. If we find the head we seek, we win and keep going. We
  81.   need set the MAYBE-MORE flag only if/when we scan through all heads and
  82.   fail to find the appropriate head. If we are moby lucky, we may just win when
  83.   we might otherwise have wimped out... though it may be hard to anticipate or
  84.   otherwise characterize under what conditions this extension may pay off.
  85.   Nevertheless, it somewhat simplifies the algorithm: if Free encroaches Heads
  86.   then scan right of Free to end; otherwise scan right of Heads to end. Never
  87.   give up the hunt.
  88.  
  89.  Ziggy observation 2: even when Free is about to encrouch on Heads, we may be
  90.   able to safely shift all Heads entries to the right (dropping rightmost head
  91.   space elements) as follows: binary search for the head space object left of
  92.   the Scan straddle. The next smaller head space entry is already fully scanned
  93.   so it cannot possibly be needed any longer to locate pointing aggr heads.
  94.   Thus every elt to the right of the lesser Scan straddle head are no longer
  95.   needed in head space so head space elts can be shifted right to truncate head
  96.   space. This hack, however, obliterates head space as a potential reified
  97.   vector of ALL-AGGS-VECT, but then again if the encroachment were not avoided
  98.   then the obliteration already occurs by virtue of the Free/Heads encroachment
  99.   anyway, so nothing is lost. Upshot: always do the right shift truncation so
  100.   we don't lose potential pointing obj isolations due to head space overflow.
  101.