Switched `Element.renderObject` to iterative implementation. by gaaclarke · Pull Request #112885 · flutter/flutter

gaaclarke · 2022-10-04T21:59:25Z

The iterative implementation is 30% faster in local testing on x86_64 AOT where Element is RenderObjectElement. (97% faster with JIT).

Benchmark:

// @dart=2.12
import 'dart:collection';

enum _ElementLifecycle {
  other,
  defunct,
}

class RenderObject {
  int count = 0;
}

class Element {
  _ElementLifecycle _lifecycleState = _ElementLifecycle.other;

  RenderObject? get renderObject {
    RenderObject? result;
    final Queue<Element> elements = Queue<Element>();
    elements.addFirst(this);
    void adder(Element x) => elements.addLast(x);
    while (elements.isNotEmpty) {
      final Element current = elements.removeFirst();
      if (current._lifecycleState == _ElementLifecycle.defunct) {
        break;
      } else if (current is RenderObjectElement) {
        result = current.renderObject;
        break;
      } else {
        current.visitChildren(adder);
      }
    }
    return result;
  }

  RenderObject? get renderObject2 {
    RenderObject? result;
    void visit(Element element) {
      if (element._lifecycleState == _ElementLifecycle.defunct) {
        return;
      } else if (element is RenderObjectElement) {
        result = element.renderObject;
      } else {
        element.visitChildren(visit);
      }
    }
    visit(this);
    return result;
  }

  void visitChildren(void Function(Element) func) {}
}

class RenderObjectElement extends Element {
  final RenderObject? _renderObject = RenderObject();

  @override
  RenderObject? get renderObject => _renderObject;
}

void main() {
  RenderObjectElement foo = RenderObjectElement();
  int numIterations = 1000000000;
  int count = 0;
  {
    Stopwatch stopWatch = Stopwatch();
    stopWatch.start();
    for (int i = 0; i < numIterations; ++i) {
      count += foo.renderObject!.count;
    }
    stopWatch.stop();
    print('$count renderObject ${stopWatch.elapsedMicroseconds / numIterations.toDouble()} µs');
  }
  {
    Stopwatch stopWatch = Stopwatch();
    stopWatch.start();
    for (int i = 0; i < numIterations; ++i) {
      count += foo.renderObject2!.count;
    }
    stopWatch.stop();
    print('$count renderObject2 ${stopWatch.elapsedMicroseconds / numIterations.toDouble()} µs');
  }
}

ouput

0 renderObject 0.000530598 µs
0 renderObject2 0.000766342 µs

Pre-launch Checklist

I read the Contributor Guide and followed the process outlined there for submitting PRs.
I read the Tree Hygiene wiki page, which explains my responsibilities.
I read and followed the Flutter Style Guide, including Features we expect every widget to implement.
I signed the CLA.
I listed at least one issue that this PR fixes in the description above.
I updated/added relevant documentation (doc comments with ///).
I added new tests to check the change I am making, or this PR is test-exempt.
All existing and new tests are passing.

If you need help, consider asking for advice on the #hackers-new channel on Discord.

flutter-dashboard · 2022-10-04T21:59:28Z

It looks like this pull request may not have tests. Please make sure to add tests before merging. If you need an exemption to this rule, contact Hixie on the #hackers channel in Chat (don't just cc him here, he won't see it! He's on Discord!).

If you are not sure if you need tests, consider this rule of thumb: the purpose of a test is to make sure someone doesn't accidentally revert the fix. Ask yourself, is there anything in your PR that you feel it is important we not accidentally revert back to how it was before your fix?

Reviewers: Read the Tree Hygiene page and make sure this patch meets those guidelines before LGTMing.

gaaclarke · 2022-10-04T22:06:42Z

@goderbauer I was just curious and started looking at these micro-optimizations for the framework. I'm not sure how heavy we want to be about building tests around these micro-optimizations. If you gave me the go ahead I could crank out tons of these for framework.dart and object.dart in a short amount of time. They are pretty easy to spot.

packages/flutter/lib/src/widgets/framework.dart

jonahwilliams · 2022-10-04T22:15:46Z

packages/flutter/lib/src/widgets/framework.dart

-        return;
-      } else if (element is RenderObjectElement) {
-        result = element.renderObject;
+    final Queue<Element> elements = Queue<Element>();


I've generally found that data structures besides list/map/set are not particularly fast in Dart. I'm curious if you tried with just a plain List

I couldn't use a List because "removeFirst" would be O(n). In order to use a List directly I'd have to do something like a RingBuffer, but then there is the risk of overflow.

Fair enough, I just checked and the default Queue in dart is a ListQueue with a resizing ring buffer. No need to re-implement.

gaaclarke · 2022-10-04T22:29:03Z

packages/flutter/lib/src/widgets/framework.dart

+      if (current._lifecycleState == _ElementLifecycle.defunct) {
+        break;
+      } else if (current is RenderObjectElement) {
+        result = current.renderObject;


FYI there is a slight change here that may not be a problem. The old version, if you have multiple children that are RenderObjectElement, the last one visited will be returned. This implementation stops execution at the first one found.

I'm surprised by the old behavior. I wonder if that was intentional or not?

It's hard for me to believe it was intentional, the documentation states that the order of visitChildren is undefined so it can't be meaningful that the last one get precedence.

Is there really a functional change here? The old code contained this assert: assert(result == null); which was enforcing that there can only ever be one child. If there's only ever one child, then it doesn't matter whether you return the first one or last one. It's the same one?

In fact, we should keep that assert around, adapted to the new code. It is invalid to call this if the Element has multiple children. An assert should warn you about this instead of just silently returning a "random" child.

Also, since there's only going to be one child, you probably don't even need the Queue?

@goderbauer good call, I removed the assert when I was writing the benchmark to make sure it didn't mess up the results and missed it's purpose. I made the change, it is surprisingly only slightly faster than the one that allocates the queue.

jonahwilliams

LGTM

goderbauer · 2022-10-05T00:03:48Z

packages/flutter/lib/src/widgets/framework.dart

+      if (current._lifecycleState == _ElementLifecycle.defunct) {
+        break;
+      } else if (current is RenderObjectElement) {
+        result = current.renderObject;


Is there really a functional change here? The old code contained this assert: assert(result == null); which was enforcing that there can only ever be one child. If there's only ever one child, then it doesn't matter whether you return the first one or last one. It's the same one?

packages/flutter/lib/src/widgets/framework.dart

goderbauer · 2022-10-05T00:12:46Z

packages/flutter/lib/src/widgets/framework.dart

+      if (current._lifecycleState == _ElementLifecycle.defunct) {
+        break;
+      } else if (current is RenderObjectElement) {
+        result = current.renderObject;


In fact, we should keep that assert around, adapted to the new code. It is invalid to call this if the Element has multiple children. An assert should warn you about this instead of just silently returning a "random" child.

goderbauer · 2022-10-05T00:19:53Z

packages/flutter/lib/src/widgets/framework.dart

+      if (current._lifecycleState == _ElementLifecycle.defunct) {
+        break;
+      } else if (current is RenderObjectElement) {
+        result = current.renderObject;


Also, since there's only going to be one child, you probably don't even need the Queue?

goderbauer

LGTM

…lutter/flutter#112885)

Switched Element.renderObject to iterative implementation.

9041a96

flutter-dashboard bot added the framework flutter/packages/flutter repository. See also f: labels. label Oct 4, 2022

gaaclarke changed the title ~~Switched Element.renderObject to iterative implementation.~~ Switched Element.renderObject to iterative implementation. Oct 4, 2022

gaaclarke requested a review from goderbauer October 4, 2022 22:04

gaaclarke mentioned this pull request Oct 4, 2022

Remove recursion from the framework's trees #112888

Closed

jonahwilliams reviewed Oct 4, 2022

View reviewed changes

packages/flutter/lib/src/widgets/framework.dart Outdated Show resolved Hide resolved

jonahwilliams reviewed Oct 4, 2022

View reviewed changes

jonahs suggestion

ddf4cb3

gaaclarke commented Oct 4, 2022

View reviewed changes

jonahwilliams approved these changes Oct 5, 2022

View reviewed changes

goderbauer reviewed Oct 5, 2022

View reviewed changes

goderbauer requested changes Oct 5, 2022

View reviewed changes

gaaclarke added 2 commits October 5, 2022 09:43

goderbauer1

64bbd3c

goderbauer2

ce37b4a

gaaclarke requested a review from goderbauer October 5, 2022 16:56

goderbauer approved these changes Oct 5, 2022

View reviewed changes

gaaclarke added the autosubmit Merge PR when tree becomes green via auto submit App label Oct 5, 2022

auto-submit bot merged commit 69fc4fb into flutter:master Oct 5, 2022

This was referenced Oct 6, 2022

Roll Flutter from d554fcb36a6e to 98c04987963b (18 revisions) flutter/packages#2682

Merged

Roll Flutter from d554fcb36a6e to 98c04987963b (18 revisions) flutter/plugins#6543

Closed

engine-flutter-autoroll added a commit to engine-flutter-autoroll/packages that referenced this pull request Oct 6, 2022

69fc4fb Switched Element.renderObject to iterative implementation. (f…

4296a5f

…lutter/flutter#112885)

engine-flutter-autoroll added a commit to engine-flutter-autoroll/plugins that referenced this pull request Oct 6, 2022

69fc4fb Switched Element.renderObject to iterative implementation. (f…

8349e0f

…lutter/flutter#112885)

engine-flutter-autoroll mentioned this pull request Oct 6, 2022

Roll Flutter from d554fcb36a6e to 61f61c44b422 (20 revisions) flutter/plugins#6545

Closed

engine-flutter-autoroll added a commit to engine-flutter-autoroll/plugins that referenced this pull request Oct 6, 2022

69fc4fb Switched Element.renderObject to iterative implementation. (f…

e166435

…lutter/flutter#112885)

engine-flutter-autoroll mentioned this pull request Oct 6, 2022

Roll Flutter from d554fcb36a6e to be86a916548a (22 revisions) flutter/plugins#6548

Merged

engine-flutter-autoroll added a commit to engine-flutter-autoroll/plugins that referenced this pull request Oct 6, 2022

69fc4fb Switched Element.renderObject to iterative implementation. (f…

67c2623

…lutter/flutter#112885)

Conversation

gaaclarke commented Oct 4, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pre-launch Checklist

Uh oh!

flutter-dashboard bot commented Oct 4, 2022

Uh oh!

gaaclarke commented Oct 4, 2022

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jonahwilliams left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

goderbauer left a comment

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

gaaclarke commented Oct 4, 2022 •

edited

Loading