From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: X-Spam-Status: No, score=-3.9 required=3.0 tests=AWL,BAYES_00, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI, SPF_HELO_NONE,SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.6 Received: from out1.vger.email (out1.vger.email [IPv6:2620:137:e000::1:20]) by dcvr.yhbt.net (Postfix) with ESMTP id 1D5871F428 for ; Wed, 15 Mar 2023 17:50:58 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231983AbjCORta (ORCPT ); Wed, 15 Mar 2023 13:49:30 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36544 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229546AbjCORt2 (ORCPT ); Wed, 15 Mar 2023 13:49:28 -0400 Received: from cloud.peff.net (cloud.peff.net [104.130.231.41]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 849EE7BA0D for ; Wed, 15 Mar 2023 10:49:06 -0700 (PDT) Received: (qmail 18607 invoked by uid 109); 15 Mar 2023 17:49:05 -0000 Received: from Unknown (HELO peff.net) (10.0.1.2) by cloud.peff.net (qpsmtpd/0.94) with ESMTP; Wed, 15 Mar 2023 17:49:05 +0000 Authentication-Results: cloud.peff.net; auth=none Received: (qmail 2623 invoked by uid 111); 15 Mar 2023 17:49:05 -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; Wed, 15 Mar 2023 13:49:05 -0400 Authentication-Results: peff.net; auth=none Date: Wed, 15 Mar 2023 13:49:05 -0400 From: Jeff King To: Derrick Stolee via GitGitGadget Cc: git@vger.kernel.org, gitster@pobox.com, me@ttaylorr.com, vdye@github.com, Derrick Stolee Subject: Re: [PATCH v2 1/8] for-each-ref: add --stdin option Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org On Fri, Mar 10, 2023 at 05:20:56PM +0000, Derrick Stolee via GitGitGadget wrote: > When a user wishes to input a large list of patterns to 'git > for-each-ref' (likely a long list of exact refs) there are frequently > system limits on the number of command-line arguments. > > Add a new --stdin option to instead read the patterns from standard > input. Add tests that check that any unrecognized arguments are > considered an error when --stdin is provided. Also, an empty pattern > list is interpreted as the complete ref set. > > When reading from stdin, we populate the filter.name_patterns array > dynamically as opposed to pointing to the 'argv' array directly. This > requires a careful cast while freeing the individual strings, > conditioned on the --stdin option. This is a nice feature to have, but I suspect like other pattern features in Git (e.g., pathspecs), the matching is linear, and thus pre-expanding the set of refs you're interested in becomes accidentally quadratic. And that seems to be the case here. If I have N refs and feed the whole set as patterns via --stdin: -- >8 -- for i in 4000 8000 16000 32000; do rm -rf repo git init -q repo ( cd repo git commit --allow-empty -qm foo perl -e ' my ($oid, $n) = @ARGV; print "create refs/heads/branch$_ $oid\n" for (1..$n); ' $(git rev-parse HEAD) $i | git update-ref --stdin git for-each-ref --format='%(refname)' >refs echo -n "$i: " command time -f %U \ git.compile for-each-ref --stdin &1 >/dev/null ) done -- 8< -- then the result quadruples for every doubling of the refs. 4000: 0.32 8000: 1.33 16000: 5.10 32000: 20.90 That may or may not be a show-stopper for your use case, and if not, I don't think it's something we need to address immediately. But we may want some kind of "literal" mode, that takes in a list of refs rather than a list of patterns, and does a sorted-merge with the list of available refs (or uses a hash table, I guess, but for-each-ref also tries to avoid even being linear in the total number of refs, so you'd still want to find the lowest/highest to bound the iteration). -Peff