16 lines
3.6 KiB
Plaintext
16 lines
3.6 KiB
Plaintext
Black magic and the Great Beast
|
|
<p>Something of significance to the design discussion for the Great Beast occurred today.</p>
|
|
<p>I have finally – <em>finally!</em> – achieved significant insight into the core merge code, the “black magic” section of cvs-fast-export. If you look in <a href="https://gitorious.org/cvs-fast-export/cvs-fast-export/source/acdeb17616339846f106fae7334fa34b6893c880:merge.c">merge.c in the repo head version</a> you’ll see a bunch of detailed comments that weren’t there before. I feel rather as Speke and Burton must have when after weeks of hacking their way through the torrid jungles of darkest Africa they finally glimpsed the source of the Nile…</p>
|
|
<p><span id="more-6406"></span></p>
|
|
<p>(And yes, that code has moved. It used to be in the revlist.c file, but that now contains revision-list utility code used by both stages 1 and 2. The black magic has moved to merge.c and is now somewhat better isolated from the rest of the code.)</p>
|
|
<p>I don’t grok all of it yet – there’s some pretty hairy and frightening stuff happening around branch joins, and my comprehension of edge cases is incomplete. But I have figured out enough of it to have a much better feel than I did even a few days ago for how it scales up.</p>
|
|
<p>In particular I’m now pretty sure that the NetBSD attempt did <em>not</em> fail due to an O(n**2)/O(n**3) blowup in time or space. I think it was just what it looked like, straight-up memory exhaustion because the generated gitspace commits wouldn’t fit in 4GB. Overall scaling for computational part (as opposed to I/O) looks to me like it’s roughly:</p>
|
|
<p>* O(m**2) in time, with m more related to maximum revisions per CVS master and number of branches than total repo or metadata volume.</p>
|
|
<p>* O(n) in space, where in is total metadata volume. The thing is, n is much larger than m! </p>
|
|
<p>This has implications for the design of the Great Beast. To match the implied job load, yes, serial computation speed is important, but the power to rapidly modify data structures of more than 4GB extent even more so. I think this supports the camp that’s been arguing hard for prioritizing RAM and cache performance over clock speed. (I was leaning that way anyway.) </p>
|
|
<p>My estimate of O(n) spatial scaling also makes me relatively optimistic about the utility of throwing a metric buttload of RAM at the problem. I think one of the next things I’m going to do is write an option that returns stats on memory usage after stages 1 and 2, run it on several repos, and see if I can curve-fit a formula that predicts the stage 2 figure given Stage 1 usage.</p>
|
|
<p>Even without that, I think we can be pretty confident that the NetBSD conversion won’t break 32GB; the entire repo content is 11GB, so the metadata has to be significantly smaller than that. If I understand the algorithms correctly (and I think I do, now, to the required degree) we basically have to be able to hold the equivalent of two copies of the metadata in memory.</p>
|
|
<p>(In case it’s not obvious, I’m using NetBSD as a torture test because I believe it represents a near worst case in complexity.)</p>
|
|
<p>I’m also going to continue working on shrinking the memory footprint. I’ve implemented a kind of slab allocation for the three most numerous object classes, cutting malloc overhead. More may be possible in that direction.</p>
|
|
<p>So, where this comes out is I’m now favoring a design sketch around 1.35V ECC RAM and whichever of the Xeons has the best expected RAM cache performance, even if that means sacrificing some clock speed.</p>
|