Darcs-git pulling from the Linux repo: a Linux VM question

Hi,

If you are one of the few initiated who can tune the Linux VM, please skip to the end of this mail and give me some advice. If you are one of the even fewer initiated who understand Darcs' memory usage, read the whole of this message and send me a patch. Otherwise, press D.

Now that I've got a Darcs that groks Git repos, I can play with a fairly large tree -- the Linux 2.6 one. All the experiments described below were done on a 1.4 MHz Pentium-M with 640 MB of memory, running Linux 2.6.9 (Debian branded) over Reiserfs.

All the commands that don't need to actually read the underlying blobs are instantaneous; for example, ``darcs changes'' takes 0.4s. Commands that require reading the blobs but allow discarding them straight away are reasonable enough -- ``darcs changes -s'' on all but the initial import takes a very reasonable 15s, ``darcs changes -s'' including the initial import takes 2m30s real time, (50s CPU time).

The trouble, of course, is with commands that need to read a full tree and keep it in memory. This is, unfortunately, the case with pull of the initial commit, which is over 200MB in size. Darcs behaviour when pulling this initial commit is as follows.

As I'm currently reading the git repository eagerly, Darcs starts by reading the whole of the initial tree into memory; this takes roughly 2 minutes of real time (at less than 10% CPU), reads 18987 Git files (blobs and trees), of which 18512 are unique (meaning that less than 500 were read two times or more -- yes, I should be keeping track of the blobs I've already read). When that is done, Darcs' VMEM usage is beneath 300MB.

At that point, Darcs stops doing I/O, and starts trying to interpret the data. It runs between 80% and 100% of CPU, and grows steadily until its VMEM reaches 550MB. At that point, the system starts swapping very lightly (no more than 200kB/s or so), and Darcs' VMEM usage grows up to 720MB after 5 minutes CPU, 8 minutes real time.

When Darcs has grokked the fullness of the Linux kernel, it decides to write out a patch. So it starts touching all of its memory while simultaneously writing out data to a patch file at a fairly sustained rate. It gets pretty close to the end -- over 200MB of patch are written --, when suddenly the system appears to freeze for a second, then the OOM killer triggers and kills the Darcs process.

Now obviously there is a problem with Darcs -- it shouldn't be needing 720MB of virtual memory just to grok a 250 MB import --, but there's also a problem with the VM. A 720 MB process should be reasonable on a machine with 640 MB, and there's no apparent reason why the kernel couldn't go more heavily into swap. My completely uninformed guess would be that the heavy I/O activity generated by Darcs in the final stage causes a shortage of some resource (probably buffers) that is essential for the VM to perform the swapping, and that the only way the kernel sees to get itself out of the tight spot is to invoke the OOM killer on the process that's causing the I/O activity.

So yes, in the longer term we need to fix Darcs. For now, does anyone know how I can tune the Linux VM to get a 720 MB process to run reliably in 640 MB of main memory? Obviously, adding swap or tuning the overcommit policy doesn't help (the issue is precisely that the VM refuses to dig into the swap early enough). I don't understand what ``swappinness'' is, but it doesn't appear to help. The ``min_free_kbytes'' and ``dirty_*'' knobs look promising, but nobody seems to know what they mean.

So what was it you said about self-tuning VM systems?

                                        Juliusz

On Wed, 27 Apr 2005, Juliusz Chroboczek wrote:

I really think you're screwed. The only way you have even a _chance_ of getting it to work well is that if you have very nice access patterns to that 720MB, but my guess is that that simply isn't the case. You probably read most of it in once (and write out changes once, but I hope you at least notice the case of "nothing changed" so that probably is the smaller of your problems), and the fact is, you're going to have absolutely _horrible_ access patterns, since you'll end up not just with a 720MB process that doesn't have much locality, you'll end up with another 720MB that you needed to have in the page cache for the IO.

The only way I can see to fix it short-term is to try to use "mmap()" instead of "read()" to read the file data, and then try to avoid touching the mapping unless you _have_ to. In other words: if you actually need to _compare_ the data (which obviously reads from the mapping), you're screwed.

Using mmap() will at least mean that the system can re-use the page cache pages, though, so it should improve memory pressure a bit.

The kernel tries to tune itself in the sense that it automatically allocates the memory to user processes vs caching (page cache, directory caching etc) and tunes itself quite well that way.

But there's no way to tune for crappy access patterns and working sets bigger than the amount of RAM. Sorry. You really need to fix darcs.

You _really_ shouldn't read in files that you don't absolutely need. That's really the biggest point of git: using the sha1 for naming the objects is really all about "descrive the contents using 20 bytes instead of by reading the contents". Because reading the content _will_ be expensive. Even if you have 2GB of memory and you can keep it all cached, it will be horribly expensive.

		Linus

Thanks, that's what I needed to know.

Ahem... you don't expect me to embark on hacking Git without at least understanding that, do you?

Here we're speaking about the initial import. Committed on 17 April 2005 by Linus Torvalds, with the comment ``Let it rip''. 220 MB of changed files in a single commit. 2 minutes real time just to read all the files, never mind doing anything useful with them.

To put it mildly, Darcs is not optimised for that sort of usage.

That's exactly why we're so interested in your repository.

                                        Juliusz

On Wed, 27 Apr 2005, Juliusz Chroboczek wrote:

I think you may well want to consider the initial commit special. In many ways it is - it has no parents etc, so even apart from the fact that the initial commit obviously tends to be a lot bigger than any other commit, it actually fundamnetally is _technically_ different too.

It shouldn't be. Make the initial one a special case, and import things file-by-file for that one special case.

Afterwards, you should be able to handle other commits as "diffs", and then it's entirely reasonable to have the difference all in memory. If somebody really does end up having a 220MB diff, and darcs sucks at it, then at that point I don't think it's darcs' problem any more, it's the project that you're trying to track that is doing something wrong..

So if you _just_ consider the initial git commit special (and it's easy to notice by just looking at the lack of parents), then you may not need to change darcs in the other cases.

And almost all SCM's consider the initial state a special case anyway. The fact that GIT doesn't is just a result of the strange way of representing data, which doesn't care. I don't think you should emulate git in that respect.

		Linus

On Wed, Apr 27, 2005 at 09:16:03AM -0700, Linus Torvalds wrote:

This has been discussed, and while I'm not opposed to special-casing the initial commit, mostly we've taken the stance so far of not special-casing. It's much nicer if we can make darcs efficient enough to perform the initial commit without a special case, which has the nice side-effect of also improving other cases.

When we're desperate, we'll special-case the initial commit, but currently I'm sure we can pretty easily adjust things by making the git-tree-reading lazy, which should pretty well address both the memory and speed concerns--and also improve performance of other commands. Perhaps more to the point, it will also ensure that the same optimizations that work for working with darcs repos will help when dealing with git repos.

Just to make it clear: reading the git tree is lazy. The problem is somewhere in the higher layers, probably in pull_cmd.

There's also another problem: reading the git tree takes 220MB. Then Darcs allocates a further 500MB without calling my code at all. (Some of it is doubtless due to linesPS, that should be more than a handful of megabytes.)

                                        Juliusz

On Thu, Apr 28, 2005 at 05:36:01PM +0200, Juliusz Chroboczek wrote:

I guess really that's the issue. Get itself is a special case that we've already optimized for the initial get. You'll also run into trouble using pull to grab an entire plain old darcs repository with a large initial commit. We can (and should) also optimize pull, but it's not going to ever be as efficient as a get is, for the case where you start with an empty repository.

The output of linesPS actually does take a huge amount of space.