Re: grob.cc: rewrite O(n^2) algorithm in Grob::common_refpoint algorithm to O(n) (issue 5371050)

[dak]

Reviewers: joeneeman, md5i,


http://codereview.appspot.com/5371050/diff/1/lily/grob.cc
File lily/grob.cc (right):

http://codereview.appspot.com/5371050/diff/1/lily/grob.cc#newcode536
lily/grob.cc:536: 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.

http://codereview.appspot.com/5371050/diff/1/lily/grob.cc#newcode542
lily/grob.cc:542: 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
is
> 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
it).

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

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

Please review this at http://codereview.appspot.com/5371050/

Affected files:
  M lily/grob.cc


Index: lily/grob.cc
diff --git a/lily/grob.cc b/lily/grob.cc
index  
7f90971803c90c599e1489e875d92add202df864..253736dcadd87aae844250396bec539b489de2c1  
100644
--- a/lily/grob.cc
+++ b/lily/grob.cc
@@ -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;
 }

 void