Re: [PATCH v1 0/3] [RFC] Speeding up checkout (and merge, rebase, etc)

> On Wed, Jul 18, 2018 at 08:45:14PM +0000, Ben Peart wrote:
> 
>> When working directories get big, checkout times start to suffer.  Even with
>> GVFS virtualization (which limits git to only having to update those files
>> that have been changed locally) we�re seeing P50 times for checkout of 31
>> seconds and the P80 time is 43 seconds.
> 
> Funny aside: all of your apostrophes look like the unicode question
> mark. Looking at raw bytes of your mail, they're actually u+fffd
> (unicode "replacement character"). Your headers correctly claim to be
> utf8. So presumably they got munged by whatever converted to unicode and
> didn't have the original character in its translation table. I wonder if
> this was send-email (so really perl's encode module), or if your smtp
> server tried to do an on-the-fly conversion (I know many servers will
> switch the content-transfer-encoding, but I haven't seen a charset
> conversion before).
> 

> Anyway, on to the actual discussion:
> 
>> Here is a checkout command with tracing turned on to demonstrate where the
>> time is spent.  Note, this is somewhat of a �best case� as I�m simply
>> checking out the current commit:
>>
>> benpeart@gvfs-perf MINGW64 /f/os/src (official/rs_es_debug_dev)
>> $ /usr/src/git/git.exe checkout
>> 12:31:50.419016 read-cache.c:2006       performance: 1.180966800 s: read cache .git/index
>> 12:31:51.184636 name-hash.c:605         performance: 0.664575200 s: initialize name hash
>> 12:31:51.200280 preload-index.c:111     performance: 0.019811600 s: preload index
>> 12:31:51.294012 read-cache.c:1543       performance: 0.094515600 s: refresh index
>> 12:32:29.731344 unpack-trees.c:1358     performance: 33.889840200 s: traverse_trees
>> 12:32:37.512555 read-cache.c:2541       performance: 1.564438300 s: write index, changed mask = 28
>> 12:32:44.918730 unpack-trees.c:1358     performance: 7.243155600 s: traverse_trees
>> 12:32:44.965611 diff-lib.c:527          performance: 7.374729200 s: diff-index
>> Waiting for GVFS to parse index and update placeholder files...Succeeded
>> 12:32:46.824986 trace.c:420             performance: 57.715656000 s: git command: 'C:\git-sdk-64\usr\src\git\git.exe' checkout
> 
> What's the current state of the index before this checkout? 

> I don't
> recall offhand how aggressively we prune the tree walk based on the diff
> between the index and the tree we're loading. If we're starting from > scratch, then obviously we do have to walk the whole thing. But in most
> cases we should be able to avoid walking into sub-trees where the index
> has a matching cache_tree record.
> 
> If we're not doing that, it seems like that's going to be the big
> obvious win, because it reduces the number of trees we have to consider
> in the first place.
> 

>> ODB cache
>> =========
>> Since traverse_trees() hits the ODB for each tree object (of which there are
>> over 500K in this repo) I wrote and tested having an in-memory ODB cache
>> that cached all tree objects.  This resulted in a > 50% hit ratio (largely
>> due to the fact we traverse the tree twice during checkout) but resulted in
>> only a minimal savings (1.3 seconds).
> 
> In my experience, one major cost of object access is decompression, both
> delta and zlib. Trees in particular tend to delta very well across
> versions. We have a cache to try to reuse intermediate delta results,
> but the default size is probably woefully undersized for your repository
> (I know from past tests it's undersized a bit even for the linux
> kernel).
> 
> Try bumping core.deltaBaseCacheLimit to see if that has any impact. It's
> 96MB by default.
> 
> There may also be some possible work in making it more aggressive about
> storing the intermediate results. I seem to recall from past
> explorations that it doesn't keep everything, and I don't know if its
> heuristics have ever been proven sane.
> 
> For zlib compression, I don't have numbers handy, but previous
> experiments showed that trees don't actually benefit all that much from
> zlib (presumably because they're mostly random-looking hashes). So one
> option would be to try repacking _just_ the trees with
> "pack.compression" set to 0, and see how the result behaves. I suspect
> that will be pretty painful with your giant multi-pack repo.
> 
> It might be slightly easier if we had an option to set the compression
> level on a per-type basis (both to experiment, and then of course if it
> works to actually tune your repo).
> 
> The numbers above aren't specific enough to know how much time was spent
> doing zlib stuff, though. And even with more specific probes, it's
> generally still hard to tell the difference between what's specific to
> the compression level, and what's a result of the fact that zlib is
> essentially copying all the bytes from the filesystem into memory.
> Still, my timings with zstd[1] showed something like 10-20% improvement
> on object access, so we should be able to get something at least as good
> by moving to no compression.
> 
> [1] https://public-inbox.org/git/20161023080552.lma2v6zxmyaiiqz5@sigill.intra.peff.net/
> 

>> Multi-threading unpack_trees()
>> ==============================
>> The current model of unpack_trees() is that a single thread recursively
>> traverses each tree object as it comes across it.  One thought I had was to
>> multi-thread the traversal so that each tree object could be processed in
>> parallel.  To test this idea out, I wrote an unbounded
>> Multi-Product-Multi-Consumer queue and then wrote a
>> traverse_trees_parallel() function that would add any new tree objects into
>> the queue where they can be processed by a pool of worker threads.  Each
>> thread will wake up when there is work in the queue, remove a tree object,
>> process it adding any additional tree objects it finds.
> 
> I'm generally terrified of multi-threading anything in the core parts of
> Git. There are so many latent bits of non-reentrant or racy code.
> 
> I think your queue suggestion may be the sanest approach, though,
> because it makes it keeps the responsibilities of the worker threads
> pretty clear.
> 

>> When I brought up this idea with some other git contributors they mentioned
>> that multi threading unpack_trees() had been discussed a few years ago on
>> the list but that the idea was discarded.  They couldn�t remember exactly
>> why it was discarded and none of us have been able to find the email threads
>> from that earlier discussion. As a result, I decided to write up this RFC
>> and see if the greater git community has ideas, suggestions, or more
>> background/history on whether this is a reasonable path to pursue or if
>> there are other/better ideas on how to speed up checkout especially on large
>> repos.
> 
> I don't remember any specific discussion, and didn't dig anything up
> after a few minutes. But I'd be willing to bet that the primary reason
> it would not be pursued is the general lack of thread safety in the
> current codebase.
> 
> -Peff
>