Is Android layout really exponentially hard?

Question

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^depth times.

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.

Such an example would greatly help me and others who are grumbling that the "keep your layouts shallow" 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.

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.

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.

Please note, I don't want answers explaining how the exponential blow-up occurs-- I understand that, and there have been several posts already where that has been asked and answered:

• Why are nested weights bad for performance? Alternatives?
• Android layout measuring time doubles with each step up the hierarchy
• Layout Weight warning Nested weight bad performance
• Efficiency of Android Layout hierarchy
• http://android-developers.blogspot.com/2009/02/android-layout-tricks-1.html

My question is whether the recursive double-measuring is fundamentally necessary/justified, and if so, I'd like a clear explanation/example showing why.

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.

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.

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.

I can think of 4 possibilities:

1. Fix the performance bug in the core library, without changing any contracts
2. Change contracts as needed, and fix the performance bug in the core library
3. 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
4. Continue to micromanage our layouts to work around the performance bug for the rest of our android development careers.

(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.

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.

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.

Answer 1

In terms of measuring children twice, it's my understanding that this is what happens with LinearLayouts particularly when weights are involved. The best explanation I've found for this comes from RomainGuy in one of his presentations.

He has a slide about this and briefly speaks to it at 17:45. Feel free to rewind to get a bit of context though. You can find the video I'm referencing here: Devoxx'10 - Dive Into Android

Basically what he says is that on the first pass they calculate the total width or height depending on orientation of the LinearLayout, add the weights of the children, and find out how much space is left over, then on the second pass with that information they are able to properly divvy out all the remaining space to all the children. Simple enough.

I'd also like to point out though that yes, while it's very true that shallow layout hierarchies have less of a performance hit, if you are adding just 1 or 2 extra layers, you probably aren't going to see a big performance impact for the user. Once it's laid out, it's done. Even in ListView's if you properly use the given "convertView", and set up ViewHolder's, you're going to get good performance.

I'd encourage you to use DDMS and do a layout dump of some of Google's apps. They are very complex, and often times surprisingly deep, but they still get good performance. Don't be stupid with your layouts, but if it saves you time, adding an extra layout isn't the end of the world.