Re: argv subscript range uses too many memory

Re: argv subscript range uses too many memory

[Peter Stephenson]

On Sat, 10 Nov 2012 06:57:09 -0800
Bart Schaefer <schaefer@brasslantern.com> wrote:
> Further discussion probably should be re-routed to zsh-workers.

I've done that.
 
> In a loop, the heap allocations are not popped until the loop is done,
> IIRC, so you'll end up with a large number of copies of the original
> array in the heap with slice results pointing into different parts of
> each copy.  Maybe there's a narrower scope in which a pushheap/popheap
> could be inserted.

What's puzzling me is that loops, including the "while" involved here,
execute freeheap() at the end of each iteration.  That should restore the pristine state of the loop when it was pushed each time around, shouldn't it?  Maybe I'm missing some subtlety of freeheap().

I'm a little bit worried there might be some pathology with permanent,
i.e. non-heap, allocation, in particular with zsh's own implementation
of malloc() (though I don't think anyone's compared between system and
zsh versions).  That would be something along the lines of: each time
around the loop we create an array that is just a little bit bigger than
the one we created last time, so doesn't fit in the memory we freed, so
we allocate yet another chunk of memory.  That's probably nonsense
because (i) if we allocated another chunk, the combination of the that
with the previous one would be order twice as large as the original, so
we shouldn't see pathological behaviour unless something was doubling
each time, and there's nothing obviously like that in this case (ii)
indeed we're looking at arrays getting smaller each time.  Still, I
can't quite get this out of my head.  That's probably because my head's
a funny shape inside.

-- 
Peter Stephenson <p.w.stephenson@ntlworld.com>
Web page now at http://homepage.ntlworld.com/p.w.stephenson/

Re: argv subscript range uses too many memory

[Bart Schaefer]

[Moved to zsh-workers; Han Pingtian Cc'd in case he's only on -users]

On Nov 20,  9:03am, Bart Schaefer wrote:
}
} Unfortunately as far as I can tell these two issues (the speed problem
} in last year's "the source of slow large for loops" thread and the space
} problem in this thread) are directly in conflict with one another.  The
} speed problem requires that the heap not be fully garbage collected on
} every loop pass, but the space problem requires that it be collected at
} some point before the loop is done.
} 
} Maybe there's a hybrid where freeheap() can examine the difference in
} position (fheaps - heaps) and do a full garbage collect only when the
} heap has become "too full".

On a moment's reflection that doesn't work directly because both heaps
and fheaps are pointers into a linked list, so they can't be differenced
that easily.  Theoretically fheaps must always either be NULL or have a
value greater than or equal to heaps, but beyond that nothing forces
heap blocks to be in sequential pointer order, they could be returned by
malloc() in any arbritrary order.

So what we need is a fast way to estimate how much uncollected garbage
is in the heap -- or, conversely, a fast way to estimate how close we
are to running out of memory -- so that garbage collection can be put
off until it's necessary.

Or, as I said before, find a scope in which to pushheap/popheap ...

-- 
Barton E. Schaefer

Re: argv subscript range uses too many memory

[Bart Schaefer]

On Nov 20,  9:44am, Bart Schaefer wrote:
}
} So what we need is a fast way to estimate how much uncollected garbage
} is in the heap -- or, conversely, a fast way to estimate how close we
} are to running out of memory -- so that garbage collection can be put
} off until it's necessary.

On a bit more examination, I think perhaps the "bug" is in zhalloc()
itself.

The fheaps pointer should always point to the first arena that has any
free space.  Instead zhalloc() leaves it pointing to the first arena
that has enough space for the requested allocation, or to the most-
recently-allocated arena if no arena has enough space for the request.

So what about the following?  This is still probably incomplete because
(ARENA_SIZEOF(fheap) >= (size + fheap->used)) seems like the wrong test
for whether to begin the search at fheap, but I'm curious whether this
improves the garbage collection behavior.

Index: Src/mem.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/mem.c,v
retrieving revision 1.20
diff -u -r1.20 mem.c
--- Src/mem.c   14 May 2011 17:23:23 -0000      1.20
+++ Src/mem.c   20 Nov 2012 18:12:41 -0000
@@ -507,9 +507,11 @@
 
     /* find a heap with enough free space */
 
-    for (h = ((fheap && ARENA_SIZEOF(fheap) >= (size + fheap->used))
-             ? fheap : heaps);
-        h; h = h->next) {
+    h = (fheap && ARENA_SIZEOF(fheap) >= (size + fheap->used)) ? fheap : heaps;
+    for (fheap = NULL; h; h = h->next) {
+       /* track the first heap with free space in fheap */
+       if (!fheap && h->used < ARENA_SIZEOF(h))
+           fheap = h;
        if (ARENA_SIZEOF(h) >= (n = size + h->used)) {
            void *ret;
 
@@ -566,7 +568,8 @@
            hp->next = h;
        else
            heaps = h;
-       fheap = h;
+       if (!fheap)
+           fheap = h;
 
        unqueue_signals();
 #ifdef ZSH_HEAP_DEBUG

Re: argv subscript range uses too many memory

[Han Pingtian]

On Tue, Nov 20, 2012 at 10:24:15AM -0800, Bart Schaefer wrote:
> So what about the following?  This is still probably incomplete because
> (ARENA_SIZEOF(fheap) >= (size + fheap->used)) seems like the wrong test
> for whether to begin the search at fheap, but I'm curious whether this
> improves the garbage collection behavior.
> 
> Index: Src/mem.c
> ===================================================================
> RCS file: /cvsroot/zsh/zsh/Src/mem.c,v
> retrieving revision 1.20
> diff -u -r1.20 mem.c
> --- Src/mem.c   14 May 2011 17:23:23 -0000      1.20
> +++ Src/mem.c   20 Nov 2012 18:12:41 -0000
> @@ -507,9 +507,11 @@
> 
>      /* find a heap with enough free space */
> 
> -    for (h = ((fheap && ARENA_SIZEOF(fheap) >= (size + fheap->used))
> -             ? fheap : heaps);
> -        h; h = h->next) {
> +    h = (fheap && ARENA_SIZEOF(fheap) >= (size + fheap->used)) ? fheap : heaps;
> +    for (fheap = NULL; h; h = h->next) {
> +       /* track the first heap with free space in fheap */
> +       if (!fheap && h->used < ARENA_SIZEOF(h))
> +           fheap = h;
>         if (ARENA_SIZEOF(h) >= (n = size + h->used)) {
>             void *ret;
> 
> @@ -566,7 +568,8 @@
>             hp->next = h;
>         else
>             heaps = h;
> -       fheap = h;
> +       if (!fheap)
> +           fheap = h;
> 
>         unqueue_signals();
>  #ifdef ZSH_HEAP_DEBUG

I have tried this patch. Looks like with this patch on 5.0, both 

for i in {1..700000}; do true; done

and 

set -- ~/**/*
while ((ARGC>=3))
do
  print -- "${argv[1,3]}"
  shift 3
done

will run very slow, but the memory problem is solved at the
sametime.

Re: argv subscript range uses too many memory

[Bart Schaefer]

On Nov 22,  5:28pm, Han Pingtian wrote:
}
} I have tried this patch. Looks like with this patch on 5.0, [loops]
} will run very slow, but the memory problem is solved at the
} sametime.

If you would not mind, try removing both that patch and the one you
previously removed for 29175, but increase HEAPSIZE to

#define HEAPSIZE (163840 - H_ISIZE)

and see if that makes any noticeable difference in the "run very slow"
condition?

Re: argv subscript range uses too many memory

[Han Pingtian]

On Thu, Nov 22, 2012 at 10:29:27AM -0800, Bart Schaefer wrote:
> On Nov 22,  5:28pm, Han Pingtian wrote:
> }
> } I have tried this patch. Looks like with this patch on 5.0, [loops]
> } will run very slow, but the memory problem is solved at the
> } sametime.
> 
> If you would not mind, try removing both that patch and the one you
> previously removed for 29175, but increase HEAPSIZE to
> 
> #define HEAPSIZE (163840 - H_ISIZE)
> 
> and see if that makes any noticeable difference in the "run very slow"
> condition?

I have tried this. It works just fine. Both problems lools like has been
fixed. Do you think it is the right solution?

Thanks.

Re: argv subscript range uses too many memory

[Bart Schaefer]

On Nov 25,  4:11pm, Han Pingtian wrote:
} Subject: Re: argv subscript range uses too many memory
}
} On Thu, Nov 22, 2012 at 10:29:27AM -0800, Bart Schaefer wrote:
} > 
} > If you would not mind, try removing both that patch and the one you
} > previously removed for 29175, but increase HEAPSIZE
} 
} I have tried this. It works just fine. Both problems lools like has been
} fixed. Do you think it is the right solution?

It's a large step in the right direction.  The questions remaining are:

What is the right value for HEAPSIZE?   Mmultiplying it by 10 is was just
a quick way to test; it might be better to multiply by 8 or 16 to keep a
size that's a power of 2 for efficient byte alignment of arena blocks.
It depends on the underlying malloc implementation.

Has this really addressed the problem from 29175?  Larger blocks will
mean it takes longer for the arena list to grow, but a loop that uses
enough memory can still become pathologically slow.

Re: argv subscript range uses too many memory

[Han Pingtian]

On Sun, Nov 25, 2012 at 11:03:36AM -0800, Bart Schaefer wrote:
> 
> Has this really addressed the problem from 29175?  Larger blocks will
> mean it takes longer for the arena list to grow, but a loop that uses
> enough memory can still become pathologically slow.

It looks like this loop is really quick with the patch applied:

% time zsh -fc  'for i in {1..700000}; do true; done'
zsh -fc 'for i in {1..700000}; do true; done'  3.24s user 0.22s system 99% cpu 3.466 total

But this 10 times larger loop is still really slow:

% time zsh -fc  'for i in {1..7000000}; do true; done'
zsh -fc 'for i in {1..7000000}; do true; done'  1136.44s user 4.39s system 99% cpu 19:05.28 total

Re: argv subscript range uses too many memory

[Peter Stephenson]

On Tue, 20 Nov 2012 09:44:42 -0800
Bart Schaefer <schaefer@brasslantern.com> wrote:
> So what we need is a fast way to estimate how much uncollected garbage
> is in the heap -- or, conversely, a fast way to estimate how close we
> are to running out of memory -- so that garbage collection can be put
> off until it's necessary.
> 
> Or, as I said before, find a scope in which to pushheap/popheap ...

Instead of optimising freeheap for the case where the are lots of
heaps, could we just increase HEAPSIZE?  It's only 16384 (minus a
header), which seems pretty small to me.

Or could we make it a variable, so the more memory you acquire the
larger it is?  Then if you need a lot of memory you're not constantly
allocating it in small chunks.

-- 
Peter Stephenson <p.w.stephenson@ntlworld.com>
Web page now at http://homepage.ntlworld.com/p.w.stephenson/

Re: argv subscript range uses too many memory

[Bart Schaefer]

On Nov 20,  9:05pm, Peter Stephenson wrote:
}
} Instead of optimising freeheap for the case where the are lots of
} heaps, could we just increase HEAPSIZE?  It's only 16384 (minus a
} header), which seems pretty small to me.

Note that HEAPSIZE is only the lower limit on the size of an arena.
The actual size will depend on the largest contiguous chunk requested
of zhalloc().  Which is a bit strange because all calls to zfree()
use the HEAPSIZE or HEAPFREE constants instead of h->size or perhaps
ARENA_SIZEOF(h).  It must really not matter to zfree().

In any case workers/29175 isn't really optimizing just for a lot of
heaps or even for a lot of allocated memory; it's optimizing for a
lot of calls to freeheap(), most of which don't really have anything
useful to do.  It's just that in Han Pingtian's example there IS
something useful to do, but the optimization skips doing it because
fheap has been advanced [by zhalloc()] to point only at the most
recently allocated block.

If you think of the heaps linked-list as proceeding left to right,
then with 29175 freeheap assumes fheap points somwhere in the middle
of the list, but zhalloc tends to move it too far to the right.  It
remains to be seen whether 30809 moves it too far back to the left
(that is, effectively reverses 29175).

Or ... I may have completely misinterpreted how freeheap is supposed
to do its work, and there's an entirely different optimization that
should be done in place of 29175.

Re: argv subscript range uses too many memory

[Han Pingtian]

Hi Bart,

I have tried your suggestion. Looks like this patch on 5.0 resolve both
problem. The for loop of 29175 run about 5 seconds on my loptop and the
while loop only used ~180M memory on my loptop, it does't trigger
oom-killer any more.


diff --git a/Src/mem.c b/Src/mem.c
index 5275c6c..0e4d258 100644
--- a/Src/mem.c
+++ b/Src/mem.c
@@ -106,7 +106,7 @@ union mem_align {
 };
 
 #define H_ISIZE  sizeof(union mem_align)
-#define HEAPSIZE (16384 - H_ISIZE)
+#define HEAPSIZE (163840 - H_ISIZE)
 /* Memory available for user data in default arena size */
 #define HEAP_ARENA_SIZE (HEAPSIZE - sizeof(struct heap))
 #define HEAPFREE (16384 - H_ISIZE)
@@ -319,28 +319,8 @@ freeheap(void)
     h_free++;
 #endif
 
-    /* At this point we used to do:
     fheap = NULL;
-     *
-     * 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.
-     *
-     * With the above reset of fheap, the loop below sweeps back over the
-     * entire heap list again, resetting the free space in every arena to
-     * the amount stashed by pushheap() and finding the first arena with
-     * free space to optimize zhalloc()'s next search.  When there's a lot
-     * of stuff already on the heap, this is an enormous amount of work,
-     * and performance goes to hell.
-     *
-     * However, there doesn't seem to be any reason to reset fheap before
-     * beginning this loop.  Either it's already correct, or it has never
-     * been set and this loop will do it, or it'll be reset from scratch
-     * on the next popheap().  So all that's needed here is to pick up
-     * the scan wherever the last pass [or the last popheap()] left off.
-     */
-    for (h = (fheap ? fheap : heaps); h; h = hn) {
+    for (h = heaps; h; h = hn) {
 	hn = h->next;
 	if (h->sp) {
 #ifdef ZSH_MEM_DEBUG
@@ -377,7 +357,7 @@ freeheap(void)
     if (hl)
 	hl->next = NULL;
     else
-	heaps = fheap = NULL;
+	heaps = NULL;
 
     unqueue_signals();
 }