On Mon, Nov 23, 2020 at 11:49:49AM -0500, Taylor Blau wrote: > On Sun, Nov 22, 2020 at 12:32:01PM -0800, Junio C Hamano wrote: > > Taylor Blau <me@xxxxxxxxxxxx> writes: > > > > > - a geometric increase in existing size; we'll switch to 3/2 instead of > > > 2 here. That's less aggressive and may help avoid fragmenting memory > > > (N + 3N/2 > 9N/4, so old chunks can be reused as we scale up). > > > > I am sure this is something obvious to bitmap folks, but where does > > 9N/4 come from (I get that the left-hand-side of the comparison is > > the memory necessary to hold both the old and the new copy while > > reallocating the words[] array)? > > I thought that I was in the group of "bitmap folks", but since it's not > obvious to me either, I guess I'll have to hand in my bitmap folks > membership card ;). > > Peff: where does 9N/4 come from? it is not a bitmap thing at all. We are growing a buffer, so if we continually multiply it by 3/2, then our sequence of sizes is: - before growth: N - after 1 growth: 3N/2 - after 2 growths: 9N/4 Meaning we can fit the third chunk into the memory vacated by the second two. Whereas with a factor of, say 2: - before growth: N - after 1 growth: 2N - after 2 growth: 4N which does not fit, and fragments your memory. There's a slight lie there, which is that you'll typically still hold the growth G-1 while doing growth G (after all, that is where you will copy the data from). But it still works out that you eventually get to use old chunks. The breakeven point is actually the golden ratio, but a) it's irrational and b) it probably makes sense to give some slop for malloc chunk overhead. 1.6 would probably be fine, too, though. :) > On a similar note: we could certainly > use ALLOC_GROW here, too, but it would change the behavior slightly (by > using alloc_nr()'s "add-16-first" behavior). Maybe we should be using > it, but I'll defer to your judgement. That would be OK, modulo the measurement question I asked in the other (wrong) part of the thread. -Peff
