Re: Slowdown around 5.0.5-dev-0

[Bart Schaefer <schaefer@brasslantern.com>]

On Oct 10,  8:32pm, Sebastian Gniazdowski wrote:
}
} As for the code, it's interesting that it is just existence of large
} array that slows down things.

To the best of my understanding (not having written the original code),
the zsh heap works like this:

The "heaps" and "fheap" pointers start out NULL.

The first zhalloc() creates a block of memory either of the "arena size"
or the size requested, whichever is larger.  This block has a header
that contains a pointer to another block (initially NULL), and a counter
of the amount of allocated space in the current block.

On subsequent zhalloc(), either a pointer to the end of allocated
space in the existing block is returned (if sufficient space), or a
new block is allocated and linked through the pointer in in the header
of the existing block.  Thus a linked list of partially-filled blocks
may be built up.

Every zhalloc() therefore looks for space in the first block it can
find that has enough.  As an optimization, the "fheap" pointer is left
pointed at the earliest block that has any free space, so full blocks
can be skipped by the search at allocation time.  However, if the only
block with available space is the last (most recently allocated) one,
fheap becomes invalid when that block is freed.

On pushheap(), a linked list of free space positions (struct heapstack)
is created for each existing block in the heap.  The effect is that
every block is its own stack of heaps; there isn't a single global
stack of heaps.  On popheap() or freeheap(), the list of free space
positions is traversed and the free pointer in each heap block is
reset to its position at the time it was pushed onto the stack.

It is this reset traversal that causes the slowdown.  If all the existing
heap blocks are completely filled before the pushheap() occurs, fheap is
invalidated on every free, and then we spend a lot of time uselessly
resetting the free space pointers in those existing blocks.

(We also invalidate fheap any time we temporarily switch to a new heap,
which currently happens in completion, so completion operations will
invoke additional scans for arenas with free space.)

} The large 89k array "sleeps" waiting for change

Yes, so it fills the top of the heap and occupies it forever, thereby
causing the heap blocks it occupies to be uselessly traversed seeking
available space every time the smaller array is manipulated.

This suggests a couple of possible fixes, but I've run out of time to
experiment right now.

-- 
Barton E. Schaefer