* Re: argv subscript range uses too many memory [not found] ` <121110065709.ZM4781@torch.brasslantern.com> @ 2012-11-10 21:16 ` Peter Stephenson [not found] ` <20121120130457.GD2500@localhost.localdomain> 1 sibling, 0 replies; 11+ messages in thread From: Peter Stephenson @ 2012-11-10 21:16 UTC (permalink / raw) To: Zsh Hackers' List 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/ ^ permalink raw reply [flat|nested] 11+ messages in thread
[parent not found: <20121120130457.GD2500@localhost.localdomain>]
[parent not found: <121120090300.ZM5552@torch.brasslantern.com>]
* Re: argv subscript range uses too many memory [not found] ` <121120090300.ZM5552@torch.brasslantern.com> @ 2012-11-20 17:44 ` Bart Schaefer 2012-11-20 18:24 ` Bart Schaefer 2012-11-20 21:05 ` Peter Stephenson 0 siblings, 2 replies; 11+ messages in thread From: Bart Schaefer @ 2012-11-20 17:44 UTC (permalink / raw) To: zsh-workers; +Cc: Han Pingtian [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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: argv subscript range uses too many memory 2012-11-20 17:44 ` Bart Schaefer @ 2012-11-20 18:24 ` Bart Schaefer 2012-11-22 9:28 ` Han Pingtian 2012-11-20 21:05 ` Peter Stephenson 1 sibling, 1 reply; 11+ messages in thread From: Bart Schaefer @ 2012-11-20 18:24 UTC (permalink / raw) To: zsh-workers; +Cc: Han Pingtian 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: argv subscript range uses too many memory 2012-11-20 18:24 ` Bart Schaefer @ 2012-11-22 9:28 ` Han Pingtian 2012-11-22 18:29 ` Bart Schaefer 0 siblings, 1 reply; 11+ messages in thread From: Han Pingtian @ 2012-11-22 9:28 UTC (permalink / raw) To: zsh-workers 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. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: argv subscript range uses too many memory 2012-11-22 9:28 ` Han Pingtian @ 2012-11-22 18:29 ` Bart Schaefer 2012-11-25 8:11 ` Han Pingtian 0 siblings, 1 reply; 11+ messages in thread From: Bart Schaefer @ 2012-11-22 18:29 UTC (permalink / raw) To: zsh-workers 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? ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: argv subscript range uses too many memory 2012-11-22 18:29 ` Bart Schaefer @ 2012-11-25 8:11 ` Han Pingtian 2012-11-25 19:03 ` Bart Schaefer 0 siblings, 1 reply; 11+ messages in thread From: Han Pingtian @ 2012-11-25 8:11 UTC (permalink / raw) To: zsh-workers 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. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: argv subscript range uses too many memory 2012-11-25 8:11 ` Han Pingtian @ 2012-11-25 19:03 ` Bart Schaefer 2012-11-29 23:37 ` Han Pingtian 0 siblings, 1 reply; 11+ messages in thread From: Bart Schaefer @ 2012-11-25 19:03 UTC (permalink / raw) To: zsh-workers 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. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: argv subscript range uses too many memory 2012-11-25 19:03 ` Bart Schaefer @ 2012-11-29 23:37 ` Han Pingtian 0 siblings, 0 replies; 11+ messages in thread From: Han Pingtian @ 2012-11-29 23:37 UTC (permalink / raw) To: zsh-workers 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: argv subscript range uses too many memory 2012-11-20 17:44 ` Bart Schaefer 2012-11-20 18:24 ` Bart Schaefer @ 2012-11-20 21:05 ` Peter Stephenson 2012-11-20 23:22 ` Bart Schaefer 1 sibling, 1 reply; 11+ messages in thread From: Peter Stephenson @ 2012-11-20 21:05 UTC (permalink / raw) To: zsh-workers; +Cc: Han Pingtian 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/ ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: argv subscript range uses too many memory 2012-11-20 21:05 ` Peter Stephenson @ 2012-11-20 23:22 ` Bart Schaefer 2012-11-22 22:33 ` Han Pingtian 0 siblings, 1 reply; 11+ messages in thread From: Bart Schaefer @ 2012-11-20 23:22 UTC (permalink / raw) To: zsh-workers; +Cc: Han Pingtian 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. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: argv subscript range uses too many memory 2012-11-20 23:22 ` Bart Schaefer @ 2012-11-22 22:33 ` Han Pingtian 0 siblings, 0 replies; 11+ messages in thread From: Han Pingtian @ 2012-11-22 22:33 UTC (permalink / raw) To: zsh-workers 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(); } ^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2012-11-29 23:47 UTC | newest] Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- [not found] <20121108084001.GA7594@localhost.localdomain> [not found] ` <20121108100226.575b0788@pwslap01u.europe.root.pri> [not found] ` <20121110105811.GA7136@localhost.localdomain> [not found] ` <121110065709.ZM4781@torch.brasslantern.com> 2012-11-10 21:16 ` argv subscript range uses too many memory Peter Stephenson [not found] ` <20121120130457.GD2500@localhost.localdomain> [not found] ` <121120090300.ZM5552@torch.brasslantern.com> 2012-11-20 17:44 ` Bart Schaefer 2012-11-20 18:24 ` Bart Schaefer 2012-11-22 9:28 ` Han Pingtian 2012-11-22 18:29 ` Bart Schaefer 2012-11-25 8:11 ` Han Pingtian 2012-11-25 19:03 ` Bart Schaefer 2012-11-29 23:37 ` Han Pingtian 2012-11-20 21:05 ` Peter Stephenson 2012-11-20 23:22 ` Bart Schaefer 2012-11-22 22:33 ` Han Pingtian
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).