9front - general discussion about 9front
 help / color / mirror / Atom feed
* [9front] git/query: improve LCA results
@ 2021-08-29  2:04 ori
  2021-08-29  2:33 ` ori
  0 siblings, 1 reply; 4+ messages in thread
From: ori @ 2021-08-29  2:04 UTC (permalink / raw)
  To: 9front

Currently, git/pull can request you to do spurious
merges.

We actually ran into this once in the 9front repo:
commit 185fe31de404b67441248d91e6321645278ba92a will
request a supurious merge if you pull from it.

This is because when faced with a commit graph like
this:

  ---a---b---c---d---e
      \             /
       +-----f----+

and we want to find the least common ancestor of
commits 'b' and 'e', we will return commit 'a'.  This
is technically the correct answer: we can get to 'a'
with 1 step from 'e', and 2 from 'e', for a total of 3
steps, which is shorter than the number of steps to
get from 'e' to 'b' directly

However, for every practical purpose of the LCA
algorithm, if a node is an ancestor of another, we
want to return that ancestor, rather than the node
which can be reached from all parents in the
smallest number of steps.

This means that we need to keep scanning until we've
visited all potential ancestors between the two nodes,
and picking the shortest distance between nodes
reachable from 'e' and the nodes reachable from 'b'.

We already have code that almost does this, in our
findtwixt() code, painting backwards from a set of
'head' and 'tail' nodes in parallel until there are
no more nodes reachable from 'head' without crossing
over 'tail'.

Since we paint until all nodes reachable from head
are painted, we're guaranted to encounter the ancestor
we want to return if it's present.

This change takes findtwixt() and refactors it into
a paint function which, when passed 'ancestor=1',
will return the lca rather than the full set of
covered nodes.

Along with these changes are a few refactors to prevent
exponential blowups in time when repainting a graph of
mostly-done nodes, by bailing out early: this made
pulling git (commits a5fa49ff0 => c4203212e36) take
tens of seconnds instead of more than tens of minutes.

As a bonus, we delete some code by doing this refactor.

Since bugs here can lead to issues sysupdating, I'd
like some extra eyeballs, testing, and review on this
before I commit.

diff e6f0abc25e4e237fff97ef9bdd1dc98ee519def8 uncommitted
--- a/sys/src/cmd/git/ref.c
+++ b/sys/src/cmd/git/ref.c
@@ -22,17 +22,11 @@
 	int	stksz;
 };
 
-struct XObject {
-	Object	*obj;
-	Object	*mark;
-	XObject	*queue;
-	XObject	*next;
-};
-
 struct Objq {
 	Objq	*next;
 	Object	*o;
 	int	color;
+	int	dist;
 };
 
 static Object zcommit = {
@@ -128,110 +122,6 @@
 	return 1;
 }
 
-XObject*
-hnode(XObject *ht[], Object *o)
-{
-	XObject *h;
-	int	hh;
-
-	hh = o->hash.h[0] & 0xff;
-	for(h = ht[hh]; h; h = h->next)
-		if(hasheq(&o->hash, &h->obj->hash))
-			return h;
-
-	h = emalloc(sizeof(*h));
-	h->obj = o;
-	h->mark = nil;
-	h->queue = nil;
-	h->next = ht[hh];
-	ht[hh] = h;
-	return h;
-}
-
-Object*
-ancestor(Object *a, Object *b)
-{
-	Object *o, *p, *r;
-	XObject *ht[256];
-	XObject *h, *q, *q1, *q2;
-	int i;
-
-	if(a == b)
-		return a;
-	if(a == nil || b == nil)
-		return nil;
-	r = nil;
-	memset(ht, 0, sizeof(ht));
-	q1 = nil;
-
-	h = hnode(ht, a);
-	h->mark = a;
-	h->queue = q1;
-	q1 = h;
-
-	h = hnode(ht, b);
-	h->mark = b;
-	h->queue = q1;
-	q1 = h;
-
-	while(1){
-		q2 = nil;
-		while(q = q1){
-			q1 = q->queue;
-			q->queue = nil;
-			o = q->obj;
-			for(i = 0; i < o->commit->nparent; i++){
-				p = readobject(o->commit->parent[i]);
-				if(p == nil)
-					goto err;
-				h = hnode(ht, p);
-				if(h->mark != nil){
-					if(h->mark != q->mark){
-						r = h->obj;
-						goto done;
-					}
-				} else {
-					h->mark = q->mark;
-					h->queue = q2;
-					q2 = h;
-				}
-			}
-		}
-		if(q2 == nil){
-err:
-			werrstr("no common ancestor");
-			break;
-		}
-		q1 = q2;
-	}
-done:
-	for(i=0; i<nelem(ht); i++){
-		while(h = ht[i]){
-			ht[i] = h->next;
-			free(h);
-		}
-	}
-	return r;
-}
-
-int
-lca(Eval *ev)
-{
-	Object *a, *b, *o;
-
-	if(ev->nstk < 2){
-		werrstr("ancestor needs 2 objects");
-		return -1;
-	}
-	a = pop(ev);
-	b = pop(ev);
-	o = ancestor(a, b);
-	if(o == nil)
-		return -1;
-	push(ev, o);
-	return 0;
-}
-
 static int
 repaint(Objset *keep, Objset *drop, Object *o)
 {
@@ -249,29 +139,57 @@
 	for(i = 0; i < o->commit->nparent; i++){
 		if((p = readobject(o->commit->parent[i])) == nil)
 			return -1;
+		if(oshas(drop, p->hash))
+			goto next;
 		if(repaint(keep, drop, p) == -1)
 			return -1;
+next:
 		unref(p);
 	}
 	return 0;
 }
 
-int
-findtwixt(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres)
+static int
+haskeep(Objq *q)
 {
+	for(; q != nil; q = q->next)
+		if(q->color == Keep)
+			return 1;
+	return 0;
+}
+
+static int
+bestpick(Hash *head, int nhead, Hash *tail, int ntail, Objq *q, int dist)
+{
+	int i;
+
+	if(q->dist < dist)
+		return 1;
+	for(i = 0; i < nhead; i++)
+		if(hasheq(&head[i], &q->o->hash))
+			return 1;
+	for(i = 0; i < ntail; i++)
+		if(hasheq(&tail[i], &q->o->hash))
+			return 1;
+	return 0;
+}
+
+static int
+paint(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres, int ancestor)
+{
 	Objq *q, *e, *n, **p;
 	Objset keep, drop;
-	Object *o, *c;
-	int i, ncolor;
+	Object *o, *c, *best;
+	int i, dist, ncolor;
 
 	e = nil;
 	q = nil;
 	p = &q;
+	best = nil;
+	dist = 1<<30;
 	osinit(&keep);
 	osinit(&drop);
 	for(i = 0; i < nhead; i++){
-		if(hasheq(&head[i], &Zhash))
-			continue;
 		if((o = readobject(head[i])) == nil){
 			fprint(2, "warning: %H does not point at commit\n", o->hash);
 			werrstr("read head %H: %r", head[i]);
@@ -286,13 +204,12 @@
 		e = emalloc(sizeof(Objq));
 		e->o = o;
 		e->color = Keep;
+		e->dist = 0;
 		*p = e;
 		p = &e->next;
 		unref(o);
 	}		
 	for(i = 0; i < ntail; i++){
-		if(hasheq(&tail[i], &Zhash))
-			continue;
 		if((o = readobject(tail[i])) == nil){
 			werrstr("read tail %H: %r", tail[i]);
 			return -1;
@@ -306,6 +223,7 @@
 		e = emalloc(sizeof(Objq));
 		e->o = o;
 		e->color = Drop;
+		e->dist = 0;
 		*p = e;
 		p = &e->next;
 		unref(o);
@@ -312,7 +230,7 @@
 	}
 
 	dprint(1, "finding twixt commits\n");
-	while(q != nil){
+	while(haskeep(q)){
 		if(oshas(&drop, q->o->hash))
 			ncolor = Drop;
 		else if(oshas(&keep, q->o->hash))
@@ -319,18 +237,36 @@
 			ncolor = Keep;
 		else
 			ncolor = Blank;
-		if(ncolor == Drop || ncolor == Keep && q->color == Keep)
+		dprint(2, "visit: ncolor=%s, qcolor=%s %H\n",
+			ncolor == Keep ? "keep" : "drop",
+			q->color == Keep ? "keep" : "drop",
+			q->o->hash);
+		if(ncolor == Keep && q->color == Keep){
 			goto next;
-		if(ncolor == Keep && q->color == Drop){
+		}else if(ncolor == Drop){
+			dprint(2, "consider: best %H => %H (dist: %d => %d)\n", best ? best->hash : Zhash, q->o->hash, dist, q->dist);
+			if(q->color == Keep && bestpick(head, nhead, tail, ntail, q, dist)){
+				dprint(2, "ancestor: best %H => %H (dist: %d => %d)\n", best ? best->hash : Zhash, q->o->hash, dist, q->dist);
+				best = q->o;
+				dist = q->dist;
+			}
+		}else if(ncolor == Keep && q->color == Drop){
+			dprint(2, "consider: best %H => %H (dist: %d => %d)\n", best ? best->hash : Zhash, q->o->hash, dist, q->dist);
+			if(bestpick(head, nhead, tail, ntail, q, dist)){
+		//q->dist < dist || hasheq(head, &q->o->hash)){
+				dprint(2, "ancestor: best %H => %H (dist: %d => %d)\n", best->hash, q->o->hash, dist, q->dist);
+				best = q->o;
+				dist = q->dist;
+			}
 			if(repaint(&keep, &drop, q->o) == -1)
 				goto error;
 		}else if (ncolor == Blank) {
-			dprint(2, "visit: %s %H\n", q->color == Keep ? "keep" : "drop", q->o->hash);
 			if(q->color == Keep)
 				osadd(&keep, q->o);
 			else
 				osadd(&drop, q->o);
-			for(i = 0; i < q->o->commit->nparent; i++){
+			o = readobject(q->o->hash);
+			for(i = 0; i < o->commit->nparent; i++){
 				if((c = readobject(q->o->commit->parent[i])) == nil)
 					goto error;
 				if(c->type != GCommit){
@@ -341,6 +277,7 @@
 				dprint(2, "enqueue: %s %H\n", q->color == Keep ? "keep" : "drop", c->hash);
 				n = emalloc(sizeof(Objq));
 				n->color = q->color;
+				n->dist = q->dist + 1;
 				n->next = nil;
 				n->o = c;
 				e->next = n;
@@ -347,8 +284,9 @@
 				e = n;
 				unref(c);
 			}
+			unref(o);
 		}else{
-			sysfatal("oops");
+			sysfatal("oops: ncolor==%d && qcolor==%d", ncolor, q->color);
 		}
 next:
 		n = q->next;
@@ -355,13 +293,24 @@
 		free(q);
 		q = n;
 	}
-	*res = eamalloc(keep.nobj, sizeof(Object*));
-	*nres = 0;
-	for(i = 0; i < keep.sz; i++){
-		if(keep.obj[i] != nil && !oshas(&drop, keep.obj[i]->hash)){
-			(*res)[*nres] = keep.obj[i];
-			(*nres)++;
+	if(ancestor){
+		if(best == nil){
+			*nres = 0;
+			*res = nil;
+		}else{
+			*nres = 1;
+			*res = eamalloc(1, sizeof(Object*));
+			(*res)[0] = best;
 		}
+	}else{
+		*res = eamalloc(keep.nobj, sizeof(Object*));
+		*nres = 0;
+		for(i = 0; i < keep.sz; i++){
+			if(keep.obj[i] != nil && !oshas(&drop, keep.obj[i]->hash)){
+				(*res)[*nres] = keep.obj[i];
+				(*nres)++;
+			}
+		}
 	}
 	osclear(&keep);
 	osclear(&drop);
@@ -372,6 +321,46 @@
 		free(q);
 	}
 	return -1;
+}
+
+int
+findtwixt(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres)
+{
+	return paint(head, nhead, tail, ntail, res, nres, 0);
+}
+
+Object*
+ancestor(Object *a, Object *b)
+{
+	Object **o, *r;
+	int n;
+
+	if(paint(&a->hash, 1, &b->hash, 1, &o, &n, 1) == -1 || n == 0)
+		return nil;
+	r = o[0];
+	free(o);
+	return r;
+}
+
+int
+lca(Eval *ev)
+{
+	Object *a, *b, **o;
+	int n;
+
+	if(ev->nstk < 2){
+		werrstr("ancestor needs 2 objects");
+		return -1;
+	}
+	n = 0;
+	a = pop(ev);
+	b = pop(ev);
+	paint(&a->hash, 1, &b->hash, 1, &o, &n, 1);
+	if(n == 0)
+		return -1;
+	push(ev, *o);
+	free(o);
+	return 0;
 }
 
 static int


^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [9front] git/query: improve LCA results
  2021-08-29  2:04 [9front] git/query: improve LCA results ori
@ 2021-08-29  2:33 ` ori
  2021-08-29  7:45   ` hiro
  0 siblings, 1 reply; 4+ messages in thread
From: ori @ 2021-08-29  2:33 UTC (permalink / raw)
  To: 9front

Quoth ori@eigenstate.org:
> Since bugs here can lead to issues sysupdating, I'd
> like some extra eyeballs, testing, and review on this
> before I commit.

A slightly improved version. The `haskeep()` optimization
to break out early could cause us to leave before we'd
found the best node.

diff e6f0abc25e4e237fff97ef9bdd1dc98ee519def8 uncommitted
--- a/sys/src/cmd/git/ref.c
+++ b/sys/src/cmd/git/ref.c
@@ -22,19 +22,19 @@
 	int	stksz;
 };
 
-struct XObject {
-	Object	*obj;
-	Object	*mark;
-	XObject	*queue;
-	XObject	*next;
-};
-
 struct Objq {
 	Objq	*next;
 	Object	*o;
 	int	color;
+	int	dist;
 };
 
+static char *colors[] = {
+[Keep] "keep",
+[Drop] "drop",
+[Blank] "blank",
+};
+
 static Object zcommit = {
 	.type=GCommit
 };
@@ -128,110 +128,6 @@
 	return 1;
 }
 
-XObject*
-hnode(XObject *ht[], Object *o)
-{
-	XObject *h;
-	int	hh;
-
-	hh = o->hash.h[0] & 0xff;
-	for(h = ht[hh]; h; h = h->next)
-		if(hasheq(&o->hash, &h->obj->hash))
-			return h;
-
-	h = emalloc(sizeof(*h));
-	h->obj = o;
-	h->mark = nil;
-	h->queue = nil;
-	h->next = ht[hh];
-	ht[hh] = h;
-	return h;
-}
-
-Object*
-ancestor(Object *a, Object *b)
-{
-	Object *o, *p, *r;
-	XObject *ht[256];
-	XObject *h, *q, *q1, *q2;
-	int i;
-
-	if(a == b)
-		return a;
-	if(a == nil || b == nil)
-		return nil;
-	r = nil;
-	memset(ht, 0, sizeof(ht));
-	q1 = nil;
-
-	h = hnode(ht, a);
-	h->mark = a;
-	h->queue = q1;
-	q1 = h;
-
-	h = hnode(ht, b);
-	h->mark = b;
-	h->queue = q1;
-	q1 = h;
-
-	while(1){
-		q2 = nil;
-		while(q = q1){
-			q1 = q->queue;
-			q->queue = nil;
-			o = q->obj;
-			for(i = 0; i < o->commit->nparent; i++){
-				p = readobject(o->commit->parent[i]);
-				if(p == nil)
-					goto err;
-				h = hnode(ht, p);
-				if(h->mark != nil){
-					if(h->mark != q->mark){
-						r = h->obj;
-						goto done;
-					}
-				} else {
-					h->mark = q->mark;
-					h->queue = q2;
-					q2 = h;
-				}
-			}
-		}
-		if(q2 == nil){
-err:
-			werrstr("no common ancestor");
-			break;
-		}
-		q1 = q2;
-	}
-done:
-	for(i=0; i<nelem(ht); i++){
-		while(h = ht[i]){
-			ht[i] = h->next;
-			free(h);
-		}
-	}
-	return r;
-}
-
-int
-lca(Eval *ev)
-{
-	Object *a, *b, *o;
-
-	if(ev->nstk < 2){
-		werrstr("ancestor needs 2 objects");
-		return -1;
-	}
-	a = pop(ev);
-	b = pop(ev);
-	o = ancestor(a, b);
-	if(o == nil)
-		return -1;
-	push(ev, o);
-	return 0;
-}
-
 static int
 repaint(Objset *keep, Objset *drop, Object *o)
 {
@@ -249,29 +145,48 @@
 	for(i = 0; i < o->commit->nparent; i++){
 		if((p = readobject(o->commit->parent[i])) == nil)
 			return -1;
+		if(oshas(drop, p->hash))
+			goto next;
 		if(repaint(keep, drop, p) == -1)
 			return -1;
+next:
 		unref(p);
 	}
 	return 0;
 }
 
-int
-findtwixt(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres)
+static int
+bestpick(Hash *head, int nhead, Hash *tail, int ntail, Objq *q, int dist)
 {
+	int i;
+
+	if(q->dist < dist)
+		return 1;
+	for(i = 0; i < nhead; i++)
+		if(hasheq(&head[i], &q->o->hash))
+			return 1;
+	for(i = 0; i < ntail; i++)
+		if(hasheq(&tail[i], &q->o->hash))
+			return 1;
+	return 0;
+}
+
+static int
+paint(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres, int ancestor)
+{
 	Objq *q, *e, *n, **p;
 	Objset keep, drop;
-	Object *o, *c;
-	int i, ncolor;
+	Object *o, *c, *best;
+	int i, dist, ncolor;
 
 	e = nil;
 	q = nil;
 	p = &q;
+	best = nil;
+	dist = 1<<30;
 	osinit(&keep);
 	osinit(&drop);
 	for(i = 0; i < nhead; i++){
-		if(hasheq(&head[i], &Zhash))
-			continue;
 		if((o = readobject(head[i])) == nil){
 			fprint(2, "warning: %H does not point at commit\n", o->hash);
 			werrstr("read head %H: %r", head[i]);
@@ -282,17 +197,16 @@
 			unref(o);
 			continue;
 		}
-		dprint(1, "twixt init: keep %H\n", o->hash);
+		dprint(1, "init: keep %H\n", o->hash);
 		e = emalloc(sizeof(Objq));
 		e->o = o;
 		e->color = Keep;
+		e->dist = 0;
 		*p = e;
 		p = &e->next;
 		unref(o);
 	}		
 	for(i = 0; i < ntail; i++){
-		if(hasheq(&tail[i], &Zhash))
-			continue;
 		if((o = readobject(tail[i])) == nil){
 			werrstr("read tail %H: %r", tail[i]);
 			return -1;
@@ -306,6 +220,7 @@
 		e = emalloc(sizeof(Objq));
 		e->o = o;
 		e->color = Drop;
+		e->dist = 0;
 		*p = e;
 		p = &e->next;
 		unref(o);
@@ -319,18 +234,37 @@
 			ncolor = Keep;
 		else
 			ncolor = Blank;
-		if(ncolor == Drop || ncolor == Keep && q->color == Keep)
+		dprint(2, "visit: ncolor=%s, qcolor=%s %H\n",
+			colors[ncolor], colors[q->color], q->o->hash);
+		if(ncolor == Keep && q->color == Keep){
 			goto next;
-		if(ncolor == Keep && q->color == Drop){
+		}else if(ncolor == Drop){
+			dprint(2, "consider: best %H => %H (dist: %d => %d)\n",
+				best ? best->hash : Zhash, q->o->hash,
+				dist, q->dist);
+			if(q->color == Keep && bestpick(head, nhead, tail, ntail, q, dist)){
+				dprint(2, "ancestor: best %H => %H (dist: %d => %d)\n",
+					best ? best->hash : Zhash, q->o->hash,
+					dist, q->dist);
+				best = q->o;
+				dist = q->dist;
+			}
+		}else if(ncolor == Keep && q->color == Drop){
+			dprint(2, "consider: best %H => %H (dist: %d => %d)\n", best ? best->hash : Zhash, q->o->hash, dist, q->dist);
+			if(bestpick(head, nhead, tail, ntail, q, dist)){
+				dprint(2, "ancestor: best %H => %H (dist: %d => %d)\n", best ? best->hash : Zhash, q->o->hash, dist, q->dist);
+				best = q->o;
+				dist = q->dist;
+			}
 			if(repaint(&keep, &drop, q->o) == -1)
 				goto error;
 		}else if (ncolor == Blank) {
-			dprint(2, "visit: %s %H\n", q->color == Keep ? "keep" : "drop", q->o->hash);
 			if(q->color == Keep)
 				osadd(&keep, q->o);
 			else
 				osadd(&drop, q->o);
-			for(i = 0; i < q->o->commit->nparent; i++){
+			o = readobject(q->o->hash);
+			for(i = 0; i < o->commit->nparent; i++){
 				if((c = readobject(q->o->commit->parent[i])) == nil)
 					goto error;
 				if(c->type != GCommit){
@@ -338,9 +272,10 @@
 					unref(c);
 					continue;
 				}
-				dprint(2, "enqueue: %s %H\n", q->color == Keep ? "keep" : "drop", c->hash);
+				dprint(2, "enqueue: %s %H\n", colors[q->color], c->hash);
 				n = emalloc(sizeof(Objq));
 				n->color = q->color;
+				n->dist = q->dist + 1;
 				n->next = nil;
 				n->o = c;
 				e->next = n;
@@ -347,8 +282,9 @@
 				e = n;
 				unref(c);
 			}
+			unref(o);
 		}else{
-			sysfatal("oops");
+			sysfatal("oops: ncolor==%d && qcolor==%d", ncolor, q->color);
 		}
 next:
 		n = q->next;
@@ -355,13 +291,24 @@
 		free(q);
 		q = n;
 	}
-	*res = eamalloc(keep.nobj, sizeof(Object*));
-	*nres = 0;
-	for(i = 0; i < keep.sz; i++){
-		if(keep.obj[i] != nil && !oshas(&drop, keep.obj[i]->hash)){
-			(*res)[*nres] = keep.obj[i];
-			(*nres)++;
+	if(ancestor){
+		if(best == nil){
+			*nres = 0;
+			*res = nil;
+		}else{
+			*nres = 1;
+			*res = eamalloc(1, sizeof(Object*));
+			(*res)[0] = best;
 		}
+	}else{
+		*res = eamalloc(keep.nobj, sizeof(Object*));
+		*nres = 0;
+		for(i = 0; i < keep.sz; i++){
+			if(keep.obj[i] != nil && !oshas(&drop, keep.obj[i]->hash)){
+				(*res)[*nres] = keep.obj[i];
+				(*nres)++;
+			}
+		}
 	}
 	osclear(&keep);
 	osclear(&drop);
@@ -372,6 +319,46 @@
 		free(q);
 	}
 	return -1;
+}
+
+int
+findtwixt(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres)
+{
+	return paint(head, nhead, tail, ntail, res, nres, 0);
+}
+
+Object*
+ancestor(Object *a, Object *b)
+{
+	Object **o, *r;
+	int n;
+
+	if(paint(&a->hash, 1, &b->hash, 1, &o, &n, 1) == -1 || n == 0)
+		return nil;
+	r = o[0];
+	free(o);
+	return r;
+}
+
+int
+lca(Eval *ev)
+{
+	Object *a, *b, **o;
+	int n;
+
+	if(ev->nstk < 2){
+		werrstr("ancestor needs 2 objects");
+		return -1;
+	}
+	n = 0;
+	a = pop(ev);
+	b = pop(ev);
+	paint(&a->hash, 1, &b->hash, 1, &o, &n, 1);
+	if(n == 0)
+		return -1;
+	push(ev, *o);
+	free(o);
+	return 0;
 }
 
 static int


^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [9front] git/query: improve LCA results
  2021-08-29  2:33 ` ori
@ 2021-08-29  7:45   ` hiro
  2021-08-29 15:28     ` ori
  0 siblings, 1 reply; 4+ messages in thread
From: hiro @ 2021-08-29  7:45 UTC (permalink / raw)
  To: 9front

> and we want to find the least common ancestor of
commits 'b' and 'e', we will return commit 'a'.

whether it's least or most common (no idea what that means), it's the
only ancestor in your example anyway...

> This is technically the correct answer: we can get to 'a'
with 1 step from 'e', and 2 from 'e'

I count differently, either it's 2 hops (e-f-a) or 4 hops

> for a total of 3

so you mean 6 ?

> steps, which is shorter than the number of steps to
get from 'e' to 'b' directly

3 < 3 ?

^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [9front] git/query: improve LCA results
  2021-08-29  7:45   ` hiro
@ 2021-08-29 15:28     ` ori
  0 siblings, 0 replies; 4+ messages in thread
From: ori @ 2021-08-29 15:28 UTC (permalink / raw)
  To: 9front

Quoth hiro <23hiro@gmail.com>:
> > for a total of 3
> 
> so you mean 6 ?
> 
> > steps, which is shorter than the number of steps to
> get from 'e' to 'b' directly
> 
> 3 < 3 ?

Miscounted -- though, if they're equal, we'd
return whichever node happened to be first in
the queue.


^ permalink raw reply	[flat|nested] 4+ messages in thread

end of thread, other threads:[~2021-08-29 17:30 UTC | newest]

Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-08-29  2:04 [9front] git/query: improve LCA results ori
2021-08-29  2:33 ` ori
2021-08-29  7:45   ` hiro
2021-08-29 15:28     ` ori

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).