From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.8 required=3.0 tests=BAYES_00, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE, SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id EE207C433DB for ; Fri, 22 Jan 2021 22:55:29 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 97E0B23AC0 for ; Fri, 22 Jan 2021 22:55:29 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728573AbhAVWzV (ORCPT ); Fri, 22 Jan 2021 17:55:21 -0500 Received: from cloud.peff.net ([104.130.231.41]:35970 "EHLO cloud.peff.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728526AbhAVWzI (ORCPT ); Fri, 22 Jan 2021 17:55:08 -0500 Received: (qmail 15061 invoked by uid 109); 22 Jan 2021 22:54:19 -0000 Received: from Unknown (HELO peff.net) (10.0.1.2) by cloud.peff.net (qpsmtpd/0.94) with ESMTP; Fri, 22 Jan 2021 22:54:19 +0000 Authentication-Results: cloud.peff.net; auth=none Received: (qmail 20065 invoked by uid 111); 22 Jan 2021 22:54:20 -0000 Received: from coredump.intra.peff.net (HELO sigill.intra.peff.net) (10.0.0.2) by peff.net (qpsmtpd/0.94) with (TLS_AES_256_GCM_SHA384 encrypted) ESMTPS; Fri, 22 Jan 2021 17:54:20 -0500 Authentication-Results: peff.net; auth=none Date: Fri, 22 Jan 2021 17:54:18 -0500 From: Jeff King To: Taylor Blau Cc: git@vger.kernel.org, dstolee@microsoft.com, gitster@pobox.com, jrnieder@gmail.com Subject: Re: [PATCH v2 1/8] packfile: prepare for the existence of '*.rev' files Message-ID: References: <6742c15c84bafbcc1c06e2633de51dcda63e3314.1610576805.git.me@ttaylorr.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <6742c15c84bafbcc1c06e2633de51dcda63e3314.1610576805.git.me@ttaylorr.com> Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org On Wed, Jan 13, 2021 at 05:28:06PM -0500, Taylor Blau wrote: > (Numbers taken in the kernel after cheating and using the next patch to > generate a reverse index). There are a couple of approaches to improve > cold cache performance not pursued here: > > - We could include the object offsets in the reverse index format. > Predictably, this does result in fewer page faults, but it triples > the size of the file, while simultaneously duplicating a ton of data > already available in the .idx file. (This was the original way I > implemented the format, and it did show > `--batch-check='%(objectsize:disk)'` winning out against `--batch`.) > > On the other hand, this increase in size also results in a large > block-cache footprint, which could potentially hurt other workloads. > > - We could store the mapping from pack to index position in more > cache-friendly way, like constructing a binary search tree from the > table and writing the values in breadth-first order. This would > result in much better locality, but the price you pay is trading > O(1) lookup in 'pack_pos_to_index()' for an O(log n) one (since you > can no longer directly index the table). > > So, neither of these approaches are taken here. (Thankfully, the format > is versioned, so we are free to pursue these in the future.) But, cold > cache performance likely isn't interesting outside of one-off cases like > asking for the size of an object directly. In real-world usage, Git is > often performing many operations in the revindex, I think you've nicely covered the arguments for and against the extra offset here. This final paragraph ends in a comma, which makes me wonder if you wanted to say something more. I'd guess it is along the lines that most commands will be looking up more than one object, so that cold-cache effort is amortized. Or another way of thinking about it: 17ms versus 25ms in the cold-cache for a _single_ object is not that big a deal, because the extra 8ms does not scale as we ask about more objects. Here's an actual argument in numbers (test repo is linux.git after building a .rev file using your series): For a single object, the extra cold-cache costs give --batch a slight edge: $ git rev-parse HEAD >obj $ hyperfine -p 'echo 3 | sudo tee /proc/sys/vm/drop_caches' \ 'git cat-file --buffer --batch-check="%(objectsize:disk)" obj-1000 $ hyperfine -p 'echo 3 | sudo tee /proc/sys/vm/drop_caches' \ 'git cat-file --buffer --batch-check="%(objectsize:disk)" Documentation/technical/pack-format.txt | 17 ++++ > builtin/repack.c | 1 + > object-store.h | 3 + > pack-revindex.c | 112 +++++++++++++++++++++--- > pack-revindex.h | 7 +- > packfile.c | 13 ++- > packfile.h | 1 + > tmp-objdir.c | 4 +- > 8 files changed, 145 insertions(+), 13 deletions(-) Oh, there's a patch here, too. :) It mostly looks good to me. I agree with Junio that "compute" is a better verb than "load" for generating the in-memory revindex. > +static int load_pack_revindex_from_disk(struct packed_git *p) > +{ > + char *revindex_name; > + int ret; > + if (open_pack_index(p)) > + return -1; > + > + revindex_name = pack_revindex_filename(p); > + > + ret = load_revindex_from_disk(revindex_name, > + p->num_objects, > + &p->revindex_map, > + &p->revindex_size); > + if (ret) > + goto cleanup; > + > + p->revindex_data = (char *)p->revindex_map + 12; Junio mentioned once spot where we lose constness through a cast. This is another. I wonder if revindex_map should just be a "char *" to make pointer arithmetic easier without having to cast. But also... > + if (p->revindex) > + return p->revindex[pos].nr; > + else > + return get_be32((char *)p->revindex_data + (pos * sizeof(uint32_t))); If p->revindex_data were "const uint32_t *", then this line would just be: return get_be32(p->revindex_data + pos); Not a huge deal either way since the whole point is to abstract this behind a function where it only has to be written once. I don't think there is any downside from the compiler's view (and we already use this trick for the bitmap name-hash cache). > diff --git a/packfile.c b/packfile.c > index 7bb1750934..b04eac9286 100644 > --- a/packfile.c > +++ b/packfile.c > @@ -324,11 +324,21 @@ void close_pack_index(struct packed_git *p) > } > } > > +void close_pack_revindex(struct packed_git *p) { > + if (!p->revindex_map) > + return; > + > + munmap((void *)p->revindex_map, p->revindex_size); > + p->revindex_map = NULL; > + p->revindex_data = NULL; > +} > + > void close_pack(struct packed_git *p) > { > close_pack_windows(p); > close_pack_fd(p); > close_pack_index(p); > + close_pack_revindex(p); > } Thinking out loud a bit: a .rev file means we're spending an extra map per pack (but not a descriptor, since we close after mmap). And like the .idx files (but unlike .pack file maps), we don't keep track of these and try to close them when under memory pressure. I think that's probably OK in terms of bytes. It may mean running up against operating system number-of-mmap limits more quickly when you have a very large number of packs, as mentioned in: https://lore.kernel.org/git/20200601044511.GA2529317@coredump.intra.peff.net/ But this is probably bumping the number of problematic packs from 30k to 20k. Both are sufficiently ridiculous that I don't think it matters in practice. > diff --git a/tmp-objdir.c b/tmp-objdir.c > index 42ed4db5d3..da414df14f 100644 > --- a/tmp-objdir.c > +++ b/tmp-objdir.c > @@ -187,7 +187,9 @@ static int pack_copy_priority(const char *name) > return 2; > if (ends_with(name, ".idx")) > return 3; > - return 4; > + if (ends_with(name, ".rev")) > + return 4; > + return 5; > } Probably not super important, but: should the .idx file still come last here? Simultaneous readers won't start using the pack until the .idx file is present. We'd probably prefer they see the whole thing atomically, than see a .idx missing its .rev (they won't ever produce a wrong answer, but they'll generate the in-core revindex on the fly when they don't need to). I guess one could argue that .bitmap files should get similar treatment, but we'd not generally see those in the quarantine objdir anyway, so nobody ever gave it much thought. -Peff