zsh-workers
 help / color / mirror / code / Atom feed
From: Bart Schaefer <schaefer@brasslantern.com>
To: zsh-workers@zsh.org
Subject: Re: Slowdown around 5.0.5-dev-0
Date: Sat, 10 Oct 2015 17:06:22 -0700	[thread overview]
Message-ID: <151010170623.ZM16166@torch.brasslantern.com> (raw)
In-Reply-To: <CAKc7PVBBP0NfNwn9AVxqKQyRUcKfSPVC4C-Y2mjEsTo5JHSZyw@mail.gmail.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


  reply	other threads:[~2015-10-11  0:06 UTC|newest]

Thread overview: 61+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2015-10-10 10:54 Sebastian Gniazdowski
2015-10-10 17:58 ` Bart Schaefer
2015-10-10 18:11   ` Sebastian Gniazdowski
2015-10-10 18:32     ` Sebastian Gniazdowski
2015-10-11  0:06       ` Bart Schaefer [this message]
2015-10-11  6:20         ` Bart Schaefer
2015-10-11  8:39           ` Sebastian Gniazdowski
2015-10-11 16:17             ` Bart Schaefer
2015-10-11 16:48               ` Sebastian Gniazdowski
2015-10-11 17:31                 ` Bart Schaefer
2015-10-11 18:05                   ` Sebastian Gniazdowski
2015-10-11 21:22                     ` Bart Schaefer
2015-10-12  8:21                       ` Sebastian Gniazdowski
2015-10-12 14:01                         ` Bart Schaefer
2015-10-12 16:50                           ` Sebastian Gniazdowski
2015-10-13  0:33                             ` Bart Schaefer
2015-10-13  8:21                               ` Sebastian Gniazdowski
2015-10-13 15:52                                 ` Bart Schaefer
2015-10-14  6:50                                   ` Sebastian Gniazdowski
2015-10-14 13:27                                   ` Peter Stephenson
2015-10-14 16:25                                     ` Bart Schaefer
2015-10-14 16:50                                       ` Bart Schaefer
2015-10-15  4:32                                         ` Bart Schaefer
2015-10-15 13:03                                           ` Sebastian Gniazdowski
2015-10-16  0:35                                             ` Bart Schaefer
2015-10-17  9:12                                               ` Sebastian Gniazdowski
2015-10-17  9:24                                                 ` Sebastian Gniazdowski
2015-10-18 16:19                                                 ` Bart Schaefer
2015-10-18 20:40                                                   ` Sebastian Gniazdowski
2015-10-18 21:07                                                     ` Bart Schaefer
2015-10-18 21:31                                                       ` Sebastian Gniazdowski
2015-10-19 17:21                                                         ` Bart Schaefer
2015-10-22 12:49                                                           ` Sebastian Gniazdowski
2015-10-22 15:00                                                             ` Bart Schaefer
2015-10-22 16:28                                                               ` Sebastian Gniazdowski
2015-10-22 16:33                                                                 ` Sebastian Gniazdowski
2015-10-23 15:40                                                               ` Sebastian Gniazdowski
2015-10-23 15:57                                                                 ` Sebastian Gniazdowski
2015-10-23 19:26                                                                   ` Bart Schaefer
2015-10-23 23:50                                                                     ` Bart Schaefer
2015-10-24  6:09                                                                       ` Sebastian Gniazdowski
2015-10-24  7:37                                                                         ` Sebastian Gniazdowski
2015-10-24  8:04                                                                           ` Sebastian Gniazdowski
2015-10-24 19:39                                                                           ` Bart Schaefer
2015-10-25  7:35                                                                             ` Sebastian Gniazdowski
2015-10-25 17:23                                                                               ` Bart Schaefer
2015-10-25 20:56                                                                                 ` Sebastian Gniazdowski
2015-10-26  0:49                                                                                   ` Bart Schaefer
2015-10-26  7:41                                                                                     ` Sebastian Gniazdowski
2015-10-26  7:47                                                                                       ` Sebastian Gniazdowski
2015-10-24  6:27                                                                       ` Sebastian Gniazdowski
2015-10-24 10:54                                                                       ` Sebastian Gniazdowski
2015-10-24 11:25                                                                         ` Sebastian Gniazdowski
2015-10-24 16:31                                                                         ` Bart Schaefer
2015-10-24 16:41                                                                           ` Bart Schaefer
2015-10-23  6:32                                                             ` Sebastian Gniazdowski
2015-10-16  0:37                                             ` Bart Schaefer
2015-10-13 13:07                         ` Sebastian Gniazdowski
2015-10-13 13:31                           ` Sebastian Gniazdowski
2015-10-12 12:05                       ` Sebastian Gniazdowski
2015-10-12 15:13                         ` Bart Schaefer

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=151010170623.ZM16166@torch.brasslantern.com \
    --to=schaefer@brasslantern.com \
    --cc=zsh-workers@zsh.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://git.vuxu.org/mirror/zsh/

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).