Re: [RFC PATCH 2/5] Add delta-islands.{c,h}

On Tue, Jul 24, 2018 at 09:47:29AM -0700, Junio C Hamano wrote:

Hmm, maybe. The tricky thing about this bitmap (and this touches on your "why another bitmap" question below) is that we have a _ton_ of them (one per object). So we want to do what we can to keep memory usage down. So there are two weird things:

 - these bitmaps do not know their own size. They are all exactly the
   same size (one bit per island), and we store the size only once in
   the whole program.

 - they are copy-on-write. This helps because there's a lot of
   locality to the maps within the object graph. But it also means
   sometimes we initialize empty, and sometimes from another array.

So I think it might work to do:

  if (old) {
	/* copy bits from existing bitmap */
	FLEX_ALLOC_MEM(b, bits, old->bits, st_mult(island_bitmap_size, 4));
  } else {
	/* start with all-zero bits courtesy of xcalloc */
	FLEX_ALLOC_MEM(b, bits, NULL, 0);
  }

That'd still waste an extra byte per struct (or 4, I guess, due to padding), since we unconditionally NUL-terminate the flex-struct (since they were really designed around string storage).

Mostly it's about memory savings, as I discussed above. We _could_ use ewah bitmaps instead of naive ones here. Those are bad for random access to bits, but I think most of the operations are "is this bitmap a subset of this other one" which can be done by walking them linearly.

I doubt the compression would be all that significant, though. They do best when there's a lot of locality in the bitmap. Here our bits are the islands, grouped and ordered by some subset of the refname. I don't think there's any reason to think that refs/heads/a and refs/heads/b would be correlated. OTOH, if most objects are in most islands (e.g., because the islands represent a bunch of forks of some "base" history), then you might get a big run of 1's for those objects.

I don't think we really experimented with it. To be honest, I don't recall how much measuring we did for the refcounted bitmaps, either. So I'm not sure how much the copy-on-write saves (though my vague recollection is that it was worth doing if you have a lot of islands).

The tree depth is set when we actually walk the graph collecting objects, and we use the max depth at which we've seen it. That said, this happens in show_object(), which I think we'd avoid entering twice for the same object (due to list-objects setting the SEEN flag).

So I suspect that yes, you could have a case where a tree has multiple depths, and we'd visit them topologically out of order. And that could lead to objects reachable from that tree missing some of their islands. Something like:

  - refs/remotes/123/master points to commit C which points to tree X,
    which points to blob B

  - refs/remotes/456/master points to commit D which points to tree Y,
    which points to tree X, which points to blob B

We mark C with island "123" and D with island "456", and ditto for their root trees X and Y. Then we sort the trees by depth, with the intent that Y would come before its child X. But due to the bogus depth, X may come first. We propagate the mark for 123 down to children of X, including B. When we get to Y, we propagate the mark for 456 down to tree X. But we don't ever visit X again, because we assume we're going in topological order through the list.

And we might decide not to allow a delta that we otherwise would (because B really is in both 123 and 456, but is only marked for one).

I don't think so. They're really local to the single pack-objects operation, so they're no worse than all the other file-local static globals.

-Peff