Gitoxide use significantly more memory than git when cloning semisynthetic repos

[0xdeafbeef]

Duplicates

• I have searched the existing issues

Current behavior 😯

Regular git uses 5gb of ram for indexation and spends 55m47s on clone:

/usr/bin/time -vv  git clone https://github.com/fz139/vigruzki.git vigruzki2
Cloning into 'vigruzki2'...
remote: Enumerating objects: 570224, done.
remote: Counting objects: 100% (8218/8218), done.
remote: Compressing objects: 100% (4097/4097), done.
remote: Total 570224 (delta 4128), reused 8211 (delta 4121), pack-reused 562006
Receiving objects: 100% (570224/570224), 5.74 GiB | 14.37 MiB/s, done.
Resolving deltas: 100% (240329/240329), done.
        Command being timed: "git clone https://github.com/fz139/vigruzki.git vigruzki2"
        User time (seconds): 12655.67
        System time (seconds): 3815.96
        Percent of CPU this job got: 492%
        Elapsed (wall clock) time (h:mm:ss or m:ss): 55:47.09
        Average shared text size (kbytes): 0
        Average unshared data size (kbytes): 0
        Average stack size (kbytes): 0
        Average total size (kbytes): 0
        Maximum resident set size (kbytes): 5335480
        Average resident set size (kbytes): 0
        Major (requiring I/O) page faults: 7
        Minor (reclaiming a frame) page faults: 2987959137
        Voluntary context switches: 6497363
        Involuntary context switches: 2048852
        Swaps: 0
        File system inputs: 0
        File system outputs: 0
        Socket messages sent: 0
        Socket messages received: 0
        Signals delivered: 0
        Page size (bytes): 4096
        Exit status: 0

gix uses 28gb of ram for indexation and spends 1h31m on clone:

 /usr/bin/time -vv gix clone https://github.com/fz139/vigruzki.git
 20:27:37 read pack done 6.2GB in 437.75s (14.1MB/s)
 20:27:37  indexing done 570.2k objects in 428.24s (1.3k objects/s)
 20:27:37 decompressing done 13.6GB in 428.24s (31.8MB/s)
 21:51:31     Resolving done 570.2k objects in 5033.41s (113.0 objects/s)
 21:51:31      Decoding done 7.0TB in 5033.41s (1.4GB/s)
 21:51:31 writing index file done 19.4MB in 0.03s (626.6MB/s)
 21:51:31  create index file done 570.2k objects in 5461.80s (104.0 objects/s)
 21:51:31           checkout done 5.0 files in 0.35s (14.0 files/s)
 21:51:31            writing done 245.2MB in 0.35s (705.7MB/s)
HEAD:refs/remotes/origin/HEAD (implicit)
        1b49858194dc61cb0349a14a6d81a6061dde23b7 HEAD symref-target:refs/heads/main -> refs/remotes/origin/HEAD [new]
+refs/heads/*:refs/remotes/origin/*
        1b49858194dc61cb0349a14a6d81a6061dde23b7 refs/heads/main -> refs/remotes/origin/main [new]
        Command being timed: "gix clone https://github.com/fz139/vigruzki.git"
        User time (seconds): 7947.84
        System time (seconds): 929.27
        Percent of CPU this job got: 162%
        Elapsed (wall clock) time (h:mm:ss or m:ss): 1:31:12
        Average shared text size (kbytes): 0
        Average unshared data size (kbytes): 0
        Average stack size (kbytes): 0
        Average total size (kbytes): 0
        Maximum resident set size (kbytes): 27360768
        Average resident set size (kbytes): 0
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 468633190
        Voluntary context switches: 3885411
        Involuntary context switches: 1039556
        Swaps: 0
        File system inputs: 56
        File system outputs: 0
        Socket messages sent: 0
        Socket messages received: 0
        Signals delivered: 0
        Page size (bytes): 4096
        Exit status: 0

All tests were done on tmpfs in RAM

git version 2.40.1

gix --version
gix-plumbing 0.25.0

Kernel: 6.2.11-300.fc38.x86_64
CPU: AMD Ryzen 9 7950X (32) @ 4.500GHz

Memory: 127923MiB

Expected behavior 🤔

No response

Steps to reproduce 🕹

1. gix clone https://github.com/fz139/vigruzki.git

[Byron]

Thanks a lot for reporting this incredibly interesting case!

My hypothesis for what's happening here is the following: there are three big files with 100MB each and nearly 110k commits which update at least one, if not all, data dumps each commit. Maybe it's a log-like append-only file format which means delta compression will have a good time building very long chains.

Indexing 540k objects will not use 28GB of RAM, and 10m objects aren't a problem either. However, gitoxide parallelizes over all 32 cores and traverses the delta-chains. Per thread, it keeps at least one base in memory, applies a delta, to generate the next base. Depending on the delta-trees topology, it may have to keep multiple bases in memory at the same time, and all that per thread. In the best case, each thread will have a buffer for the base object, along with a buffer for the undeltified destination that will be the new base. With 32 cores that's 210032 = 6.4GB of memory. It's easy to imagine how due to topology this working set got larger, or we see the effects of memory fragmentation. The latter shouldn't happen as buffers are reused, but I could imagine that this is related to re-alloc as the buffers might be subtly growing.

Something else I noticed is that the performance was degrading over time as more and more cores stopped getting any data. This is expected to happen on imbalanced delta-trees where one root node (i.e. the first base) has a lot of deltas on top of it. That's how the first 1.5TB of objects would be decompressed with about 12GB/s using all cores, but at 3TB there was only 1 core left to process the remaining 4TB at only 1.8GB/s - 2.1GB/s.

When looking at the profile it's interesting to see that the delta-application and decompression of pack entries takes insignificant time. Instead, it is really, really busy computing SHA1s of the objects.

When looking at the output while only one core is left for processing, we see that there is nearly 50k objects left for one core, which means there indeed is a single base that has ~50k deltas on top of it.

Unfortunately, over time, memory usage rose and at 6.7TB of decompressed objects in, it was at 7GB. This is probably due to branching bases so it had to keep much more than one base in memory at a time. Fortunately shortly after it went down to ~5GB again.

Here is the final result of the clone invocation.

❯ /usr/bin/time -lp gix clone https://github.com/fz139/vigruzki.git
 08:28:54 read pack done 6.2GB in 706.56s (8.7MB/s)
 08:28:54  indexing done 570.4k objects in 684.49s (833.0 objects/s)
 08:28:54 decompressing done 13.6GB in 684.49s (19.9MB/s)
 09:11:46     Resolving done 570.4k objects in 2572.62s (221.0 objects/s)
 09:11:46      Decoding done 7.0TB in 2572.62s (2.7GB/s)
 09:11:47 writing index file done 19.4MB in 0.03s (751.0MB/s)
 09:11:47  create index file done 570.4k objects in 3257.24s (175.0 objects/s)
 09:11:47           checkout done 5.0 files in 0.50s (10.0 files/s)
 09:11:47            writing done 245.3MB in 0.50s (493.2MB/s)
HEAD:refs/remotes/origin/HEAD (implicit)
        b3685dccd158bade1a7fe149a7d5f5e43204348f HEAD symref-target:refs/heads/main -> refs/remotes/origin/HEAD [new]
+refs/heads/*:refs/remotes/origin/*
        b3685dccd158bade1a7fe149a7d5f5e43204348f refs/heads/main -> refs/remotes/origin/main [new]
real 3280.63
user 3872.36
sys 307.70
          8123875328  maximum resident set size
                   0  average shared memory size
                   0  average unshared data size
                   0  average unshared stack size
            20173971  page reclaims
              348743  page faults
                   0  swaps
                   0  block input operations
                   0  block output operations
                 757  messages sent
             9082910  messages received
                   2  signals received
              164472  voluntary context switches
             8884492  involuntary context switches
      17280558917972  instructions retired
      12706987488513  cycles elapsed
         15496447232  peak memory footprint

git ( master) [?] via 🐍 took 54m40s

In terms of memory usage, we see that it peaked at 8GB of allocated memory when using 10 cores, while the full set of memory usage (including virtual memory) is 8GB + 7GB (the memory mapped pack).

It's interesting that in terms of time taken, gitoxide is still competitive despite being hampered in its concurrency, even though it comes at the cost of higher memory usage. However, on my CPU the average decompression rate was nearly twice as high as on the Ryzen 9. Can it be that the sha1 implementation is worse on that platform, or that gitoxide wasn't compiled with the max settings?

Any kind of remedy would try to bring the maximum resident size down.

Workarounds

Bringing down memory usage

The measured memory usage is peak memory and I'd expect that to be much lower as mean. However, one way to reduce it is to limit the amount of cores used.

gix -t10 clone https://github.com/fz139/vigruzki.git for example should bring peak usage down to ~5GB peak, this is what I tested by merit of only having 8 fast cores and 2 slower ones.

Use shallow clones

Depending on the usecase, not having the full history might be sufficient.

gix clone --depth 1 https://github.com/fz139/vigruzki.git would definitely not show any issue, and future fetches wouldn't either unless they are so far apart that it would once again fetch a pack with incredibly long delta chains.

Future solutions

This will still have to be implemented

Use a different resolution algorithm

Use a the 'less-memory' algorithm which will parallelize per object and use a couple of caches to speed up pack access similar to what git does. It should be much faster in this particular case as it can keep the cores busy.

gix no-repo pack verify -a less-memory .git/objects/pack/pack-20b60ba716f8fca721e463d06cdf056e78b4ba02.idx pretty much immediately goes out of memory causing instant swapping as by default, it uses a 64-slot pack delta cache, one per thread. Thus each thread very quickly fills up 6.4GB of RAM just to operate. There is an alternative cache backend that measures memory instead of units, but it's too slow to be general purpose. Maybe the current slot-cache could be updated to track memory as well?

Work-stealing

Ideally, the existing standard algorithm would be able to deal with such a case gracefully and instead find a way to feed other threads. With the current data structure, that's not possible as each thread owns a single base in the tree, and only the owner can safely traverse it. I could imagine that each thread operating on a base checks if there are unused threads and if so, spawns its own threads to help finishing the work. If the data structure can support that I would definitely be tempted to implement that.

Special handling for large objects (out of scope)

In theory, there could be heuristics that could apply special handling to large objects. This could be done by memory mapping them right away, or by unloading them at opportune moments and reloading those objects before use (at the cost of having to traverse a possibly large delta chain). Note that this itself might be prohibitive unless a proper delta-cache is used as 200GB/s of memory bandwidth would just be good for 2000 deltas/s in this scenario.
However, big-file support is probably its very own topic, and this issue can be solved by limiting the amount of threads and increasing parallelism.