COW-stacks

COW-stacks

Why

Klink (as Tinyscheme) has two representations of its stack:

• As a list.
  • Pro: It allows reusable continuations
  • Con: It's very inefficient.
• As a resizable array
  • Pro: It's much more efficient
  • Con: It does not allow reusable continuations.

Neither choice is very appealing.

The answer

Thinking about the problem, I invented what I call a copy-on-write stack. It's really a set of arbitrarily many stacks. The multiple stacks can share their deeper elements, while cheaply pushing and popping their shallow elements.

I'm not actually going to add COW-stacks to Klink any time soon, but I thought about how they would work and I wrote it down. Stray references below to Klink and continuations are due to the context in which I was thinking about COW-stacks.

How: COW stacks

Entities, briefly:

SE

Stack element

LS

Linear section (of stack elements)

Slider

The part that's visible from outside; the stack as a container.

Operations, briefly:

• push
• pop
• capture a continuation
• finalize a continuation

Overall idea

We hold a tree of linear sections of stack elements. The sliders, representing states of execution, can move along the tree, and can be cloned for continuation capture. These is to work as if each continuation capture had copied the entire stack.

Desired properties

• The most common operations go very fast. In particular, when there's only one slider, this should do almost nothing that an ordinary stack would not do
• Allow arbitrarily many partly-shared stacks.
• Minimize copying the stack.
• Each stack works as if the entire stack had been copied

Entities in detail

Stack element

• Essentially as a dump stack element now
• Parts:
  • Next instruction (ie, to be continued to)
  • Arguments
  • Possibly data
    • Rethinking data function types: "data" may just a special argument that it passes to itself, that our special data-function type gets from its car. Do we ever need to actually store that?
  • List of dynamic bindings
    • Could cache the identity of the next SE, if it never moves in memory.

Linear sections

• A linear section of the tree. Generally associated to one or more sliders. It keeps a list of these sliders roughly in order from shallowest to deepest. Ie, highest index to lowest.
• Parts:
  • Reference to its parent linear section
    • For the root, this is NULL
  • Index into its parent linear section
  • A growable array of stack elements
  • Length of that array
  • Pointer to a slider, understood as the head of a list.
    • Can be NULL (for an empty list) if this linear section has become unoccupied.

Slider

• The object representing a state of execution.
• Owners:
  • Captured continuations
  • The interpreter
• Parts:
  • Reference to PO
  • Index into the PO's array of stack elements.
  • Reference to the "next" slider, understood to be used as a cell in a list.
    • For the last element, this is NULL
    • Would be nice for this to be a weak reference, since it shouldn't keep sliders alive.
  • States:

    surely-shallowest

    This element is the head of the list

    maybe-shallowest

    This element, while not the head of the list, may well be equally as shallow. It's not guarantee to be, since we mostly don't conform marks when we move other sliders.

    deeper-than-this

    This element has been moved deeper than its "proper" position in the list. It can remain out of position indefinitely.

    dead

    This node represents an unreferenced slider and can safely be removed at any time. That's just if we choose strategy (2) for removing sliders.

    normal

    This node is none of the above.

Two strategies for removing a slider

• Traverse the list and when we find it, perform list surgery.
• Mark it dead and when it's encountered, discard it.

I have no strong opinion on which is better.

Operations in detail

• pop
  • These are the possible situations:
    • Decrement within linear section
      • When: index > 0
      • Action:
        • Decrement the index.
        • If state is:

          surely-shallowest

          Make new list of sliders, keeping this slider on list.

          (other states)

          Set it deeper-than-this.

          dead

          Shouldn't happen.

    • Decrement out of linear section to previous LS.
      • When: index == 0 and LS has a parent
      • If state is:

        surely-shallowest

        Make new list of sliders, removing this slider from the list.

        (other states)

        Do nothing special for this step.

        dead

        Shouldn't happen.

      • Remove it from the list
        • Clone a new slider and mark this one dead?
        • Extract it from the list?
      • Add it to the parent LS
        • Index is the index that the child LS had into its parent.
        • State: maybe-shallowest
    • Decrement out of root linear section
      • When: index == 0 and LS has no parent
      • Stack is empty. Interpreter is done.
• push
  • These are the possible situations:
    • State is surely-shallowest
      • Remarks: This state does nothing special
    • State is maybe-shallowest
      • Compare to the actual head's index. If this slider is:
        • As deep (or deeper):
          • Mark that one maybe-shallowest
          • Remove ours from the list.
          • Mark ours (or its clone) surely-shallowest
          • Place ours (or its clone) at the beginning of the list.
          • Continue as surely-shallowest.
        • Not as deep
          • (We needn't mark ours normal because we're about to remove it)
          • Proceed as for normal.
    • State is normal or deeper-than-this
      • Make a new LS
        • Its parent is the old LS
        • Its index into parent is our old index
      • Remove this slider from the list.
  • In each case, having made sure we are safe, we add another SE:
    • If the array isn't large enough, enlarge it.
    • Write an element to PO at our index
    • Increment our index by 1
• capture a continuation
  • Make a new slider. Insert it behind the old slider, same index.
    • Index: Same as old one
    • State
      • If old slider is surely-shallowest, make the new one maybe-shallowest.
      • Otherwise give the new one the same state as the old one.
• finalize a continuation
  • Remove its slider from the list
• Initialization
  • Make one linear section
    • Initialize its array of SEs.
  • Make one slider, surely-shallowest, index 0, pointing at that linear section.

Supporting operations

Conform sliders

Conform a first element that moved or was removed.

• Remarks
  • This was just intended for when the first element moves. Other elements mostly stay in place, and are only reconsidered if first element happens to see them while it's rebuilding a list.
  • We'll examine the next elements, collecting a new list that we'll give to the LS. We'll also conform the portion of the list that we see, and we'll make sure that that portion extends as far as the next-shallowest index.
• Action:
  • (Simple case, for comparison) If there's no next element, we're done. New list is this element or nothing.
  • If an element is this slider itself, ignore it. We'll insert it when we have surely decided its position.
  • If there is one and its state is:

    surely-shallowest

    This shouldn't ever happen.

    dead

    Ignore this slider. It won't be part of the new list.

    (other)

    We'll put in rough order in the collected list.

    Possibilities of its index relative to our slider:

    • Its index is shallower (presumably only by 1)
      • Set our slider's state normal since we can rule out the other states.
      • Do we know a definite head yet?
        • No:
          • This is now the definite head.
          • Mark it surely-shallowest
          • Record min-index
          • Record reference to its cdr, the tail cdr.
        • Yes:
          • Leave it in its place in the list
          • If it's index is:
            • Same as min-index
              • Mark it maybe-shallowest
            • Larger than min-index
              • Mark it normal
            • Smaller than min-index
              • This shouldn't ever happen
          • Record reference to its cdr, the new tail cdr.
    • Its index is the same as our slider's.
      • Remarks: We may or may not want to also mark other nodes, since they may tie for shallowest.
      • Construct an intermediate list consisting of:
        • Our slider, if we're leaving it on the list
        • The new slider
        • Append the deeper-than-this list, if any.
        • Append the new slider's tail.
      • Remark: If there's no deeper-than-this list, this construction amounts to consing our slider to the new slider.
      • Do we know a definite head yet?
        • No:
          • Mark our slider surely-shallowest
          • Mark the other slider maybe-shallowest
          • Return the intermediate list
        • Yes:
          • Add it as the tail of the collected list
          • Return the collected list
    • Its index is larger than our sliders:
      • If other node is deeper-than-this:
        • Queue it to a deeper-than-this list
          • We'll add that list when we construct an intermediate list just before returning.
          • It's a queue so nodes stay in order.
        • Continue (ie, examine next node)
        • Remarks:
          • There's no point try to remark it.
            • It won't match min-index
            • It won't match our slider's index.
      • Otherwise:
        • Same as for same index.

  • If there's none (general this time),
    • Construct an intermediate list consisting of:
      • Our slider, if we're leaving it on the list
      • Append the deeper-than-this list, if any.
      • No tail
    • Treat it as in maybe-shallowest, same index.