Re: [PATCH] [RFC] Making use of bitmaps for thin objects

On Sun, Dec 22, 2013 at 11:47:34AM -0800, Ben Maurer wrote:

Sorry for the slow reply; I've been on vacation.

First off, I'm excited that you're looking into using bitmaps. We've been using them for a while at GitHub, but more testing is definitely appreciated. :)

When you build your bitmaps, do you set the pack.writeBitmapHashCache option? We found that it makes a significant difference during the compression phase, as otherwise git attempts deltas between random files based on size. Here are some numbers for a simulated fetch from torvalds/linux, representing about 7 weeks of history. Running:

  from=2d3c627502f2a9b0a7de06a5a2df2365542a72c9
  to=f0a679afefc0b6288310f88606b4bb1f243f1aa9
  run() {
    (echo $to && echo ^$from) |
    git pack-objects --stdout --all-progress --revs >/dev/null
  }

  echo "==> no hash cache"
  git repack -adb 2>/dev/null
  time run

  echo "==> with hash cache"
  git -c pack.writebitmaphashcache=1 repack -adb 2>/dev/null
  time run

produces:

  ==> no hash cache
  Counting objects: 20661, done.
  Delta compression using up to 8 threads.
  Compressing objects: 100% (7700/7700), done.
  Writing objects: 100% (20661/20661), 23.23 MiB | 11.13 MiB/s, done.
  Total 20661 (delta 13884), reused 16638 (delta 12940)

  real    0m3.626s
  user    0m10.760s
  sys     0m0.060s

  ==> with hash cache
  Counting objects: 20661, done.
  Delta compression using up to 8 threads.
  Compressing objects: 100% (7700/7700), done.
  Writing objects: 100% (20661/20661), 22.64 MiB | 10.82 MiB/s, done.
  Total 20661 (delta 14038), reused 16638 (delta 12940)

  real    0m3.072s
  user    0m6.168s
  sys     0m0.100s

So our resulting pack shrinks a little because we find better deltas, but note that we save a fair bit of CPU time (the wall clock time ends up not all that different, because the single-threaded writing phase represents a big chunk of that).

I'm not too surprised. The long-time strategy for a fetch has been to walk down the "haves" and "wants" to their merge base. That boundary commit is marked as a "preferred base", meaning we won't send it, but it's a good base for other objects, since we know the client has it.

Technically _all_ of the history reachable from that merge base could be marked as a preferred base, but we don't do so for efficiency reasons:

  1. It's expensive to walk the full object graph for a small fetch, and

  2. You would clog the delta-search algorithm if you had a very large
     number of preferred-base objects.

With bitmaps, though, the history walk is free (we just check each object against our "have" bitmap), so (1) is a non-issue. For (2), we probably don't want to stick each object into the preferred-base list, but we do want to reuse on-disk deltas we have, if we know the other side has the base.

I don't know if you went through the same line of thinking, but that matches your proposed solution. :)

Even without a linear history, it mostly works. If you are fetching all of the branches from the other side, then you will end up with all of the objects that the remote has. Which means that either you already have the base, or the remote is about to send it to you.

It will break down, though, whenever the other side has something you're not fetching. For that you really need to do the "have" bitmap check.

You might try with "--all-progress" (or pipe to "wc -c"), as this should be reducing the output size, too.

Here's my same torvalds/linux test, run with the patch I'm including below:

  Counting objects: 20661, done.
  Delta compression using up to 8 threads.
  Compressing objects: 100% (3677/3677), done.
  Writing objects: 100% (20661/20661), 5.17 MiB | 0 bytes/s, done.
  Total 20661 (delta 16963), reused 20661 (delta 16963)

  real    0m0.355s
  user    0m0.312s
  sys     0m0.044s

We dropped an order of magnitude in time, but we also shrunk the packfile from 22MiB to 5MiB! That's good enough to make me assume there's a bug in my code. :)

It's definitely a valid approach. I'm not sure if JGit is doing this optimization itself already, but it was something we were already considering for C git.

Having been confused by it myself before, I think the magic keyword is "preferred base". Once you know that, the code makes more sense. :)

Yes. Your approach writes the thin-sha1 into a special field in the object_entry. This has two downsides:

  1. It bloats the object_entry by 20 bytes. Given that a full repack of
     the kernel has over 4 million of these, that's 80MB.

  2. You have to special-case many sites which are expecting to find
     delta information in entry->delta.

We can solve both by storing the information in entry->delta. Usually that field points to another object_entry in the main "to-pack" list, either for an object we are sending or for a preferred base. But since we don't want to clog the list, we can just allocate a one-off object_entry to use as the base.

I came up with the patch below. We _may_ need to allocate the "fake" object_entry bases in a separate list, and actually connect them correctly via the delta_child/delta_sibling pointers, but I haven't looked carefully yet at how those fields are used (I think it is mostly for write order, but we don't care here since the base objects aren't being written at all).

Let me know how this patch does for you. My testing has been fairly limited so far.

---