git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH v3] fetch-pack: always allow fetching of literal SHA1s

From
Jeff King <peff@peff.net>
Date
May 11, 2017, 20:52 UTC
Message-ID
<20170511205214.ofwkqogksohs6s4b@sigill.intra.peff.net>
In-Reply-To
<695d833e-9ef1-4d74-265e-f5e3af8a54cd@google.com>
On Thu, May 11, 2017 at 10:51:37AM -0700, Jonathan Tan wrote:
Show 14 quoted lines
> > This is inside the nr_sought loop. So if I were to do:
> > 
> >   git fetch origin $(git ls-remote origin | awk '{print $1}')
> > 
> > we're back to being quadratic. I realize that's probably a silly thing
> > to do, but in the general case, you're O(m*n), where "n" is number of
> > unmatched remote refs and "m" is the number of SHA-1s you're looking
> > for.
> 
> The original patch was quadratic regardless of whether we're fetching names
> or SHA-1s, which can be said to be bad since it is a regression in an
> existing and common use case (and I agree). This one is O(m*n), as you said
> - the "quadratic-ness" only kicks in if you fetch SHA-1s, which before this
> patch is impossible.

Yeah, no question this is an improvement over the original. I think this still "regresses" a certain request performance-wise, but it's a request that could never have succeeded in the original. Mostly I'd just rather not leave a hidden quadratic loop that will blow up in somebody's face a year or two down the road.

Show 8 quoted lines
> Having a sha1_array or oidset would require allocation (O(n log n) time, I
> think, in addition to O(n) space) and this cost would be incurred regardless
> of how many SHA-1s were actually fetched (if m is an order of magnitude less
> than log n, for example, having a sha1_array might be actually worse). Also,
> presumably we don't want to incur this cost if we are fetching zero SHA-1s,
> so we would need to do some sort of pre-check. I'm inclined to leave it the
> way it is and consider this only if the use case of fetching many SHA1-s
> comes up.

An oidset should be O(n) in both time and space. Which we're already spending in the earlier loop (and in general, when we allocate O(n) ref structs in the first place). I don't think we need to care too much about micro-optimizing bumps to the constant-factor here; we just need to make sure we don't end up in an algorithmic explosion.

And if we initialize the oidset lazily, then we incur that cost only when we would be doing the linear walk in your patch anyway. See the patch below.

Show 8 quoted lines
> > AIUI, you could also avoid creating the unmatched list entirely when the
> > server advertises tip/reachable sha1s. That's a small optimization, but
> > I think it may actually make the logic clearer.
> 
> If you mean adding an "if" block at the point where we add the unmatched ref
> to the unmatched list (that either adds it to the list or immediately frees
> it), I think it makes the logic slightly more complicated. Or maybe you had
> something else in mind?

I was just thinking that it does not leave a case where we create a data structure (the unmatched list) even though we know right then that it will not ever be used. So it's an extra line of logic there, but the overall function may be clearer. I dunno, it's probably not a big deal either way.

-Peff
---
diff --git a/fetch-pack.c b/fetch-pack.c
index 5cace7458..a660331e6 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -15,6 +15,7 @@
 #include "version.h"
 #include "prio-queue.h"
 #include "sha1-array.h"
+#include "oidset.h"
 
 static int transfer_unpack_limit = -1;
 static int fetch_unpack_limit = -1;
@@ -592,6 +593,12 @@ static void mark_recent_complete_commits(struct fetch_pack_args *args,
 	}
 }
 
+static void add_refs_to_oidset(struct oidset *oids, const struct ref *refs)
+{
+	for (; refs; refs = refs->next)
+		oidset_insert(oids, &refs->old_oid);
+}
+
 static void filter_refs(struct fetch_pack_args *args,
 			struct ref **refs,
 			struct ref **sought, int nr_sought)
@@ -600,6 +607,8 @@ static void filter_refs(struct fetch_pack_args *args,
 	struct ref **newtail = &newlist;
 	struct ref *unmatched = NULL;
 	struct ref *ref, *next;
+	struct oidset tip_oids = OIDSET_INIT;
+	int tip_oids_initialized = 0;
 	int i;
 
 	i = 0;
@@ -654,22 +663,15 @@ static void filter_refs(struct fetch_pack_args *args,
 		    (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1))) {
 			can_append = 1;
 		} else {
-			struct ref *u;
-			/* Check all refs, including those already matched */
-			for (u = unmatched; u; u = u->next) {
-				if (!oidcmp(&ref->old_oid, &u->old_oid)) {
-					can_append = 1;
-					goto can_append;
-				}
-			}
-			for (u = newlist; u; u = u->next) {
-				if (!oidcmp(&ref->old_oid, &u->old_oid)) {
-					can_append = 1;
-					break;
-				}
+			if (!tip_oids_initialized) {
+				/* Check all refs, including those already matched */
+				add_refs_to_oidset(&tip_oids, unmatched);
+				add_refs_to_oidset(&tip_oids, newlist);
+				tip_oids_initialized = 1;
 			}
+			can_append = oidset_contains(&tip_oids, &ref->old_oid);
 		}
-can_append:
+
 		if (can_append) {
 			ref->match_status = REF_MATCHED;
 			*newtail = copy_ref(ref);
@@ -680,6 +682,7 @@ static void filter_refs(struct fetch_pack_args *args,
 	}
 	*refs = newlist;
 
+	oidset_clear(&tip_oids);
 	for (ref = unmatched; ref; ref = next) {
 		next = ref->next;
 		free(ref);
Previous: Jonathan TanNext: Jeff King
Message 22 of 47 in “fetch-pack: always allow fetching of literal SHA1s”
  1. fetch-pack: always allow fetching of literal SHA1sJonathan Tan, May 9, 2017
  2. Jeff KingMay 9, 2017
  3. Shawn PearceMay 10, 2017
  4. Jeff KingMay 10, 2017
  5. Shawn PearceMay 10, 2017
  6. Mike HommeyMay 10, 2017
  7. Ævar Arnfjörð BjarmasonMay 10, 2017
  8. Jonathan NiederMay 10, 2017
  9. Martin FickMay 10, 2017
  10. Jonathan NiederMay 10, 2017
  11. Jonathan NiederMay 10, 2017
  12. Sebastian SchuberthMay 10, 2017
  13. Jeff KingMay 11, 2017
  14. Jonathan NiederMay 11, 2017
  15. Jeff KingMay 11, 2017
  16. fetch-pack: always allow fetching of literal SHA1sJonathan Tan, May 10, 2017
  17. Jonathan NiederMay 10, 2017
  18. fetch-pack: always allow fetching of literal SHA1sJonathan Tan, May 10, 2017
  19. Jonathan NiederMay 10, 2017
  20. Jeff KingMay 11, 2017
  21. Jonathan TanMay 11, 2017
  22. Jeff KingMay 11, 2017
  23. Jeff KingMay 11, 2017
  24. Brandon WilliamsMay 11, 2017
  25. Jeff KingMay 13, 2017
  26. fetch-pack: always allow fetching of literal SHA1sJonathan Tan, May 11, 2017
  27. Jonathan NiederMay 11, 2017
  28. Jeff KingMay 11, 2017
  29. fetch-pack: always allow fetching of literal SHA1sJonathan Tan, May 11, 2017
  30. Jonathan NiederMay 11, 2017
  31. Jeff KingMay 12, 2017
  32. Junio C HamanoMay 12, 2017
  33. Jeff KingMay 12, 2017
  34. Jonathan TanMay 12, 2017
  35. Jonathan NiederMay 12, 2017
  36. Jeff KingMay 12, 2017
  37. Jonathan TanMay 12, 2017
  38. Jeff KingMay 13, 2017
  39. Jeff KingMay 12, 2017
  40. fetch-pack: always allow fetching of literal SHA1sJonathan Tan, May 12, 2017
  41. fetch-pack: always allow fetching of literal SHA1sJonathan Tan, May 12, 2017
  42. Jonathan NiederMay 12, 2017
  43. Jeff KingMay 13, 2017
  44. Junio C HamanoMay 15, 2017
  45. fetch-pack: always allow fetching of literal SHA1sJonathan Tan, May 15, 2017
  46. Jonathan NiederMay 15, 2017
  47. Jeff KingMay 15, 2017

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.