1001653 - Return earlier from ResolveFlexibleLengths if all of our flex items are frozen

Status: RESOLVED FIXED

(Core :: Layout, defect, P4)

Description

[Daniel Holbert [:dholbert]]

Per end of bug 985304 comment 10 & second-to-last chunk in bug 985304 comment 13, we should perhaps make FlexLine::ResolveFlexibleLengths() return early for cases where all flex items have "flex:none".

The most efficient way to do this is perhaps to give FlexLine a member-variable that indicates whether any of its flex items started out un-frozen.

Comment 1

[Mats Palmgren (inactive)]

It might also be worth keeping track of how many unfrozen items there still
are and bail out of the loops that only deals with unfrozen items when we
have seen that many, something like this:

auto cnt = remainingFrozenItems;
for (FlexItem* item = mItems.getFirst(); cnt; item = item->getNext()) {
  if (!item->IsFrozen()) {
    --cnt;

Slightly more complicated, so maybe not worth it: maintain a sentinel after
the last frozen item so you could do:

auto cnt = remainingFrozenItems;
for (FlexItem* item = firstMaybeUnfrozenItem; cnt; item = item->getNext()) {
  if (!item->IsFrozen()) {
    --cnt;

and then when you freeze an item just set it to getNext().
I'm not sure it would pay off to actually go look for the next
unfrozen item there (unless the code is already iterating items).

Comment 2

[Daniel Holbert [:dholbert]]

(In reply to Mats Palmgren (:mats) from comment #1)
> It might also be worth keeping track of how many unfrozen items there still
> are and bail out of the loops that only deals with unfrozen items when we
> have seen that many, something like this:

I'm opting to go with something like this first proposal. The firstMaybeUnfrozenItem part (second suggestion in comment 1) may be worth it, but it's a bit messier in terms of maintaining state, so I'm going to hold off on that part for now.

Comment 3

[Daniel Holbert [:dholbert]]

Attachment: fix v1

Comment 4

[Daniel Holbert [:dholbert]]

Attachment: fix v1, "diff -w" version

Comment 5

[Daniel Holbert [:dholbert]]

Attachment: fix v2

This version adds this optimization to one more loop.

Comment 6

[Daniel Holbert [:dholbert]]

Attachment: fix v2, "diff -w" version

Comment 7

[Daniel Holbert [:dholbert]]

Attachment: fix v3

Comment 8

[Daniel Holbert [:dholbert]]

Attachment: fix v3 "diff -w" version

Notes on the patch:
 * FlexLine now keeps track of its count of frozen items: "mNumFrozenItems"
 * This value is incremented in two spots:
   - when FlexItems are added (if they're already frozen)
   - when FlexItems are frozen in FreezeOrRestoreEachFlexibleSize())
   So, the count remains up-to-date.
 * Eventually, it becomes equal to mNumItems, when we've resolved all flexible sizes. If they're already equal when we enter ResolveFlexibleLengths, we can return immediately. (This is a generalization of the existing "IsEmpty()" early-return.)
 * Given mNumItems and mNumFrozenItems, we can easily compute the number of *unfrozen* items, which lets us bail out of loops early (after we iterate through that many unfrozen items).

ALSO:
 - Previously, I hadn't bothered with an !IsFrozen() check in the second loop touched by this patch (where we compute "weightSum" & a few other things) -- instead, I just made frozen items return 0 from GetWeight(). BUT, now that I'm guarding that loop's contents with !IsFrozen(), we can assert about frozenness inside of GetWeight()/GetFlexFactor(). (That's the topmost change in the patch.)
 - Also, this patch adjusts the scope of the FreezeOrRestoreEachFlexibleSize() assertion for "Can have either min or max violation", to now be inside of an !IsFrozen() check. This is because *only* unfrozen items can have min/max-size violations.  (which can be seen by the fact that our SetHadMinViolation/SetHadMaxViolation calls are inside of an !IsFrozen() check, combined with the fact that we clear violations after freezing items.)

Comment 9

[Daniel Holbert [:dholbert]]

(Might also be worth asserting that remainingUnfrozenItems is 0 at the end of each of these loops, too.  I'll add that before landing, if you don't object.)

Comment 10

[Mats Palmgren (inactive)]

Comment on attachment 8416575 [details] [diff] [review]
fix v3 "diff -w" version

>+  // Since this loop only operates on unfrozen flex items, we can break as
>+  // soon as we know there are no unfrozen items remaining.
>+  uint32_t remainingUnfrozenItems = mNumItems - mNumFrozenItems;
>+  for (FlexItem* item = mItems.getFirst();
>+       item && remainingUnfrozenItems > 0; item = item->getNext()) {
>+    if (!item->IsFrozen()) {
>+      remainingUnfrozenItems--;

I'm a little worried that the code comment might lead a casual reader
to misunderstand what these loops are actually doing.
The two "mNumFrozenItems++" which are both in conditional branches,
so there might still be some !IsFrozen() items after the loop.
This is fine, but I think it contradicts the "no unfrozen items
remaining".  The name 'remainingUnfrozenItems' is slightly ambiguous
as well, since it could be misunderstood as "remaining unfrozen items
*in the list*", and that this loop freezes all the items.
So I would suggest changing the "remaining" part of the comment/name
to something different to avoid that. (It's probably my fault since
I suggested it in comment 1, sorry!)

Perhaps this is a better wording:
 // Since this loop only operates on unfrozen flex items, we can break as
 // soon as we have seen all of them.

I'm not sure about the loop variable name... perhaps 'itemsToProcess'?
or a bland name, like 'count', 'num', 'i'?

Also, the 'item' null checks seems redundant - we must have at least
that many items (assuming these loops don't manipulate the list).

Other than that, the code looks good!
r=mats with the nits addressed as you see fit

Comment 11

[Mats Palmgren (inactive)]

(In reply to Daniel Holbert [:dholbert] from comment #9)
> (Might also be worth asserting that remainingUnfrozenItems is 0 at the end
> of each of these loops, too.  I'll add that before landing, if you don't
> object.)

That'd be fine, except perhaps if the loops fit within one page, it might
not be necessary if we drop the 'item' null-check.  It's rather obvious
if it becomes:
        for (FlexItem* item = mItems.getFirst();
             remainingUnfrozenItems > 0; item = item->getNext()) {
          ...
        }
        MOZ_ASSERT(remainingUnfrozenItems == 0);

Comment 12

[Daniel Holbert [:dholbert]]

(In reply to Mats Palmgren (:mats) from comment #10)
> The name 'remainingUnfrozenItems' is slightly ambiguous
> as well, since it could be misunderstood as "remaining unfrozen items
> *in the list*",

Ah, I see what you mean.

> I'm not sure about the loop variable name... perhaps 'itemsToProcess'?
> or a bland name, like 'count', 'num', 'i'?

I'd prefer something indicating "unfrozen", but I agree "remaining" may be vague since (as you said) it may imply a broader scope beyond this loop.

I'm leaning towards "unfrozenItemsToBeSeen". That's more clearly loop-scoped.

> Perhaps this is a better wording:
>  // Since this loop only operates on unfrozen flex items, we can break as
>  // soon as we have seen all of them.

WFM.

> Also, the 'item' null checks seems redundant - we must have at least
> that many items (assuming these loops don't manipulate the list).

Yeah, I left that in there as a sanity-check I suppose (and as a remnant of the traditional iterator loop structure).  We can move it to an assertion instead of an official loop check, though.

> > (Might also be worth asserting that remainingUnfrozenItems is 0 at the end
> > of each of these loops, too.  I'll add that before landing, if you don't
> > object.)
> 
> That'd be fine, except perhaps if the loops fit within one page, it might
> not be necessary if we drop the 'item' null-check.

Yup, never mind about this part. I'll demote the item null-check to an assertion (as noted above), which makes unnecessary the count assertion that I was suggesting.

Comment 13

[Daniel Holbert [:dholbert]]

Attachment: fix v4, for landing

Here's the patch w/ review comments addressed.

I ended up naming the variable "numUnfrozenItemsToBeSeen", which is a bit long, but it at least uses a similar naming-scheme to the variables that we derive it from (mNumItems, mNumFrozenItems), with the "ToBeSeen" suffix indicating that it's a just-for-now tally of remaining items to walk through.

I'll give this a Try run, and then land if that goes well.

Comment 14

[Daniel Holbert [:dholbert]]

Attachment: fix v4a, for landing (now with 8 lines of context)

Comment 15

[Daniel Holbert [:dholbert]]

Try run: https://tbpl.mozilla.org/?tree=Try&rev=ff90923f843e

Comment 16

[Daniel Holbert [:dholbert]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/5304021e5104

Comment 17

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/5304021e5104