[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: rewrite O(n^2) algorithm in Grob::common_refpoint algorithm

From: dak
Subject: Re: rewrite O(n^2) algorithm in Grob::common_refpoint algorithm to O(n) (issue 5371050)
Date: Thu, 10 Nov 2011 17:26:35 +0000

Reviewers: joeneeman, md5i,
File lily/ (right):
lily/ c = c->dim_cache_[a].parent_;
On 2011/11/10 16:41:54, joeneeman wrote:
After this loop, balance will be 0, right?

Only if it was't negative before.
So the next loop won't do anything...

Depending on the sign of balance, either one or both loops will do
nothing.  The compiler is smart enough to know that after exiting the
first loop body it will not need to recheck the balance, so there is
little point in uglifying the code.
lily/ while (c != d) {
On 2011/11/10 16:41:54, joeneeman wrote:
The old version would return 0 if there was no common refpoint (which
possible if the grob hierarchy hasn't been fully built yet). I'd
suggest a
"while (c && c != d)" to keep the old behavior.

I suggest we leave everything as it is.  If there is no common refpoint,
both c and d will become 0 at the same time, and the loop will exit
without any extra conditions.

The code passed the regtests first time through (after I changed
<const_cast> to a normal cast.  Surprised that g++ 4.6 does not know

I like it in this style and symmetry which captures the underlying idea
pretty nicely.

Description: rewrite O(n^2) algorithm in Grob::common_refpoint algorithm to

Please review this at

Affected files:
  M lily/

Index: lily/
diff --git a/lily/ b/lily/
index 7f90971803c90c599e1489e875d92add202df864..253736dcadd87aae844250396bec539b489de2c1 100644
--- a/lily/
+++ b/lily/
@@ -513,15 +513,38 @@ Grob::less (Grob *g1, Grob *g2)
 Grob *
 Grob::common_refpoint (Grob const *s, Axis a) const
-  /* I don't like the quadratic aspect of this code, but I see no
-     other way.  The largest chain of parents might be 10 high or so,
-     so it shouldn't be a real issue.  */
-  for (Grob const *c = this; c; c = c->dim_cache_[a].parent_)
-    for (Grob const *d = s; d; d = d->dim_cache_[a].parent_)
-      if (d == c)
-        return (Grob *) d;

-  return 0;
+  /* Catching the trivial cases is likely costlier than just running
+     through: one can't avoid going to the respective chain ends
+     anyway.  We might save the second run through when the chain ends
+     differ, but keeping track of the ends makes the loop more costly.
+  */
+  int balance = 0;
+  Grob const *c;
+  Grob const *d;
+  for (c = this; c; ++balance)
+    c = c->dim_cache_[a].parent_;
+  for (d = s; d; --balance)
+    d = d->dim_cache_[a].parent_;
+  /* Cut down ancestry to same size */
+  for (c = this; balance > 0; --balance)
+    c = c->dim_cache_[a].parent_;
+  for (d = s; balance < 0; ++balance)
+    d = d->dim_cache_[a].parent_;
+  /* Now find point where our lineages converge */
+  while (c != d) {
+    c = c->dim_cache_[a].parent_;
+    d = d->dim_cache_[a].parent_;
+  }
+  return (Grob *) c;


reply via email to

[Prev in Thread] Current Thread [Next in Thread]