Re: [PATCH v2 23/24] pack-bitmap-write: relax unique rewalk condition
- From
- Jonathan Tan <jonathantanmy@google.com>
- Date
- Dec 2, 2020, 07:44 UTC
- Message-ID
- <20201202074439.3478090-1-jonathantanmy@google.com>
- In-Reply-To
- <1da4fa0fb85fe848aa86987e767b33d296f8f878.1605649533.git.me@ttaylorr.com>
Show 6 quoted lines
> However, there was a (significant) drawback: wide histories with many > refs had an explosion of memory costs to compute the commit bitmasks > during the exploration that discovers these intermediate commits. Since > these wide histories are unlikely to repeat walking objects, the benefit > of walking objects multiple times was not expensive before. But now, the > commit walk *before computing bitmaps* is incredibly expensive.
Do you have numbers of how large the commit bitmasks are?
Show 6 quoted lines
> In an effort to discover a happy medium, this change reduces the walk > for intermediate commits to only the first-parent history. This focuses > the walk on how the histories converge, which still has significant > reduction in repeat object walks. It is still possible to create > quadratic behavior in this version, but it is probably less likely in > realistic data shapes.
Would this work? I agree that the width of the commit bitmasks would go down (and there would also be fewer commit bitmasks generated, further increasing the memory savings). But intuitively, if there is a commit that is selected and only accessible through non-1st-parent links, then any bitmaps generated for it cannot be contributed to its descendants (since there was no descendant-to-ancestor walk that could reach it in order to form the reverse edge).
Show 10 quoted lines
> Here is some data taken on a fresh clone of the kernel: > > | runtime (sec) | peak heap (GB) | > | | | > | from | with | from | with | > | scratch | existing | scratch | existing | > -----------+---------+----------+---------+----------- > original | 64.044 | 83.241 | 2.088 | 2.194 | > last patch | 44.811 | 27.828 | 2.289 | 2.358 | > this patch | 100.641 | 35.560 | 2.152 | 2.224 |
Hmm...the jump from 44 to 100 seems rather large.