Re: It's time for 5.0.1

[Bart Schaefer <schaefer@xxxxxxxxxxxxxxxx>]

On Dec 9,  7:10pm, Peter Stephenson wrote:
} Subject: Re: It's time for 5.0.1
}
} On Sat, 08 Dec 2012 11:54:16 -0800
} Bart Schaefer <schaefer@xxxxxxxxxxxxxxxx> wrote:
} > The only other
} > thing we might want to consider is [tweaked slightly] workers/30818.
} > The trouble is that as noted in 30826, it doesn't entirely solve the
} > underlying problem.  On the other hand, it might improve common cases
} > enough to be worth applying while we think about optimizing freeheap().
} 
} Yes, I'd say it's worth committing, although I don't know where we go next.

In workers/29175 I wrote this comment:

     * When pushheap() is called, it sweeps over the entire heaps list of       
     * arenas and marks every one of them with the amount of free space in      
     * that arena at that moment.  zhalloc() is then allowed to grab bits       
     * out of any of those arenas that have free space.                         

I'm now pretty sure that's completely wrong.  Does anyone recall what is
really supposed to be going on in pushheap() ?

On further examination the flow looks to me to go something like this:

1. We start out with heaps = NULL. zhalloc() is called, allocates a Heap
   struct, and points heaps at it.

2. Until the memory represented by that Heap struct is insufficient,
   zhalloc() carves slices off it.  So far so good.

3. When more memory is needed, zhalloc() allocates another Heap struct
   and chains it off the first one's next pointer.  Repeat as neeeded.

4. Now pushheap() is called.  For each Heap in the linked list, a new
   Heapstack is allocated and pushed into the Heap structs sp list.
   Each Heap object has some amount (possibly zero) of free space
   "above" the already used space in its arena.  The Heapstack tracks
   the starting position of this free space.

5. See steps 2 and 3.

6. Eventually freeheap() is called.  It walks through the Heapstack and
   resets the free space position in each corresponding Heap arena.

7. At last popheap() is called.  It both resets the free space like
   freeheap() and also discards the top Heapstack in each sp list.

If the above is all correct, then what pushheap()/freeheap()/popheap()
are designed to do is maximize re-use of the existing Heap arenas for
nested scopes; attempt to avoid allocating new Heap objects at the cost
of tracking/resetting the free space in every existing Heap arena.  This
puts conservation of space at a large premium over speed of operation.
(Which, given how profligate things like parameter expansion are with
their use of space, is maybe not entirely out of line.)

The problem with this is that the better zhalloc() is at filling up the
Heap arenas, the harder freeheap() has to work -- because it ends up
managing a Heapstack for each of a bunch of useless [that is, full] Heap
arenas.  At that point it'd be much better if it just pushed the entire
heaps list and started over from scratch.