From: Jeff King Date: Wed, 27 May 2026 10:04:06 GMT Subject: Re: [PATCH 6/8] pack-bitmap: sort bitmaps before XORing Message-ID: <20260527100406.GG981444@coredump.intra.peff.net> In-Reply-To: On Tue, May 19, 2026 at 12:12:50PM -0400, Taylor Blau wrote: > Reachability bitmaps may be stored as XORs against nearby bitmaps, up to > 10 away. However, when callers provide selected commits in an arbitrary > order, the writer may miss good ancestor/descendant pairs and produce > much larger bitmap files without changing query coverage. > > Sort the selected bitmaps in date order (from oldest to newest) before > computing XOR offsets, leaving pseudo-merge bitmaps alone (which we will > deal with separately in following commits). That order certainly makes the most sense. I'd have thought we ended up there incidentally because of the order in which we consider the commits, but perhaps not. I wonder if this got much worse when we re-wrote the bitmap generation code a few years ago. That was in v2.31.0, I think. Repacking linux.git with bitmaps, though, I couldn't find any difference in size between v2.30 and v2.31. They're both ~67M. But that also didn't shrink with this patch, either. If you have some spare CPU cycles to burn, I would be interested in a comparison of the bitmap size of your test repo using v2.30.0, v2.31.1, and this patch. > On our same testing repository from previous commits, this change shrunk > our selection of 1,261 bitmaps from ~635.46 MiB to 176.4 MiB for a > ~72.24% reduction in the on-disk size of our *.bitmap file. The time to > generate the smaller bitmap file decreased by ~3.69 seconds, though this > is likely mostly noise. Certainly good numbers. The obvious follow-up question is: how does the reading side fare? I'd expect it to be a little better, if only because there are fewer bytes to consider when XOR-ing. But if there's some hidden assumption we're missing, then it could get wildly worse. It would be good to confirm that that didn't happen. ;) > static void compute_xor_offsets(struct bitmap_writer *writer) > { > static const int MAX_XOR_OFFSET_SEARCH = 10; > > int i, next = 0; > + int nr = bitmap_writer_nr_selected_commits(writer); > + > + if (nr > 1) { > + QSORT(writer->selected, nr, bitmapped_commit_date_cmp); > + > + for (i = 0; i < nr; i++) { > + struct bitmapped_commit *stored = &writer->selected[i]; > + khiter_t hash_pos = kh_get_oid_map(writer->bitmaps, > + stored->commit->object.oid); > + > + if (hash_pos == kh_end(writer->bitmaps)) > + BUG("selected commit missing from bitmap map: %s", > + oid_to_hex(&stored->commit->object.oid)); > + > + kh_value(writer->bitmaps, hash_pos) = stored; > + } > + } OK. It took me a minute to wrap my head around this. The real work is done by QSORT(). But because we maintain a hash pointing into that array, we have to go through each hash entry and fix up its pointer. Looks correct. -Peff