title: Is Android layout really exponentially hard?
body: <p>Some commonly used android layouts such as
  RelativeLayout and LinearLayout (when weights are nonzero)
  have onMeasure() implementations that measure their children
  twice, resulting in exponential running time when nested.
  This is easily verifiable by emitting Log entries
  from a leaf View's onMeasure()... it gets called 2<sup>depth</sup>
  times.</p>
  <p>Can someone give a clear and specific description as to why this is?
  Most importantly, is this exponential behavior due to an important part
  of the overall contract, or is it just an implementation detail
  that might be optimized away?  If it is believed to be unavoidable,
  please give an example that requires it.</p>
  <p>Such an example would greatly help me and others
  who are grumbling that the &quot;keep your layouts shallow&quot;
  mandate is burdensome and who are wondering
  whether this is being driven simply by
  not-yet-optimal algorithms in the core libraries,
  or whether there really is a fundamental difficulty
  blocking a fix.</p>
  <p>Perhaps a minimal example would consist
  of a Button inside a LinearLayout inside another LinearLayout
  (with match_parent and weight=1 everywhere, to trigger
  the full exponential behavior),
  with some additional parameters or circumstances
  making it clear that all four of the calls
  to Button.onMeasure() are indeed meaningful and necessary.</p>
  <p>My first guess would be that only two linear-time
  traversals are really needed-- the first traversal to gather everyone's
  preferred sizes, the second traversal to distribute slack
  and/or shrinkage.
  Other layout engines in the world, such as those for Tex and Swing and HTML,
  seem to be able to routinely handle very deep hierarchies
  having lots of alignment constraints and stretches,
  without any exponential blowup, and I imagine that's how they work.</p>
  <p>Please note, I don't want answers explaining <em>how</em>
  the exponential blow-up occurs-- I understand that,
  and there have been several posts already where that has been
  asked and answered:</p>
  <ul>
  <li><a href="https://stackoverflow.com/questions/9430764/why-are-nested-weights-bad-for-performance-alternatives/">Why are nested weights bad for performance? Alternatives?</a></li>
  <li><a href="https://stackoverflow.com/questions/13850509/android-layout-measuring-time-doubles-with-each-step-up-the-hierarchy/">Android layout measuring time doubles with each step up the hierarchy</a></li>
  <li><a href="https://stackoverflow.com/questions/14722538/layout-weight-warning-nested-weight-bad-performance/">Layout Weight warning Nested weight bad performance</a></li>
  <li><a href="https://stackoverflow.com/questions/8672647/efficiency-of-android-layout-hierarchy/">Efficiency of Android Layout hierarchy</a></li>
  <li><a href="http://android-developers.blogspot.com/2009/02/android-layout-tricks-1.html" rel="nofollow noreferrer">http://android-developers.blogspot.com/2009/02/android-layout-tricks-1.html</a></li>
  </ul>
  <p>My question is whether the recursive double-measuring is
  fundamentally necessary/justified,
  and if so, I'd like a clear explanation/example showing why.</p>
  <p>Edit 2013/8/22: I think maybe my question is still not getting across.
  I'll try to clarify and explain my motivation, more boldly this time.</p>
  <p>Layout is not an exponentially hard problem,
  as evidenced by efficient layout engines in the world, such as those for Tex and Swing and HTML.</p>
  <p>So, what happened with LinearLayout,
  and how should the android developer community proceed in response?
  I am asking not in the spirit of laying blame,
  but rather to understand and decide how to best move forward.</p>
  <p>I can think of 4 possibilities:</p>
  <ol>
  <li>Fix the performance bug in the core library, without changing any contracts</li>
  <li>Change contracts as needed, and fix the performance bug in the
  core library</li>
  <li>Write an alternative to LinearLayout, that has its essential
  features (namely distributing extra space among children in specified proportions) but without the performance bug, and use it for new apps</li>
  <li>Continue to micromanage our layouts to work around the
  performance bug for the rest of our android development careers.</li>
  </ol>
  <p>(4) isn't a serious option for me personally.
  Furthermore it seems clear to me that
  changing the behavior of LinearLayout at this point is impractical,
  so I don't believe (2) is a serious option either.</p>
  <p>That leaves (1) and (3).
  I'm capable and willing to do either of those personally, but which one?
  Obviously (1) is far preferable if it's possible-- so, is it possible?
  That seems to be the crucial blocking question that needs to be answered
  in order to determine how to move forward.</p>
  <p>I have spent some time in the core code
  and the doc and it's not becoming clear,
  so that is why I'm asking the question here.</p>