Consider copying MultiChildRenderObjectWidget.children

[rakudrama]

One of the problems with the Flutter model is that developers can accidentally or intentionally mutate the Widget tree via mutating MultiChildRenderObjectWidget.children. See dart-lang/sdk#27755.

I think there might be a performance reason to copy the children. It depends on how often the framework walks the children.

List is an interface that has many implementations.
The VM has _List for fixed-length lists and _GrowableList for 'regular' lists, and another implementation (I don't recall the name) for unmodifiable and const Lists.

In a small Flutter app, all the children are likely from List literals or to calls to .toList(), so the children field is likely to have just two or three implementation classes. The JITing VM and AOT try to discover this, and the three implementation classes are carefully crafted to be as alike as possible. This makes it possible to compile children[i] to some indexing code.

It is possible that in a large Flutter app that there are other implementations of List that are passed in as the children, meaning it is no longer possible to compile children[i] to indexing code since some of the implementations have custom indexers and .length getters that must be called.

My hypothesis is that as the inner loop in the framework becomes more polymorphic, the performance of this code shared by all multi-child widgets degrades.

One could test this hypothesis by taking a benchmark that is where walking the children is 'hot'. I expect the benchmark would walk the 'the same' a large Widget tree over and over, with no actual appearance change. Alter one of the constructors to pass in an UnmodifiableListView([....]) instead of [....]. This will cause the walking of children[i] to become less efficient. Does this show up in the benchmark?

If you decide to protect the performance by copying (which ensures there is only one kind of List), I would suggest copying with List<Widget>.unmodifiable(input).
A small fixed-length or unmodifiable list can be is half the size of a growable list or less. If the growable input is no longer referenced, it can be GC-ed. The copy will do more allocation, but have a smaller size post-GC. This may be a reasonable tradeoff.

Making the children unmodifiable will prevent users from modifying the trees they create which will help them avoid a class of bugs.
It will break the problematic pattern of widget.children.add(w).
Even if the above hypothesis does not pan out, copying the list to an unmodifiable list in debug mode would help developers avoid bugs.

[Hixie]

This bug is just about executing an experiment, it's not really the place for debating language design choices. :-)

[Hixie]

I think you misunderstood this issue. There's no proposed solution here, it's only a description of an experiment to run.

[icatalud]

The experiment is not clear then, what is it trying to achieve?

There is an implementation that affects users, for example at the end:

Even if the above hypothesis does not pan out, copying the list to an unmodifiable list in debug mode would help developers avoid bugs.

This is something that affects the users, there is an attempt to copy the list of children to an immutable List in debug mode. It would be wrong to do that as it would hide a problem that would show up in release.

[Hixie]

@icatalud The experiment is to determine whether copying child lists will improve or hurt performance. We had previously assumed it would hurt performance (because memory copying is expensive) but @rakudrama observed that it's conceivable that it would have other benefits that would actually outweigh the copying, and we should measure it to see.

[icatalud]

@Hixie, if you or @rakudrama can explain me a bit of this code points or provide some references to learn, a fellow developer would greatly appreciate it. I’m trying to learn how the VM works.

[icatalud]

Off-topic message

With a complete understanding of the internals it would be possible to predict the results of the experiment. It is technically challenging to me, I’m hoping someday I will be able to understand the concepts behind it.

I leave my deductions just for fun a read in case someone has some spare time and would enjoy evaluating it. There is no relevant content.

List is an interface that has many implementations. … The JITing VM and AOT try to discover this,... This makes it possible to compile children[i] to some indexing code

that there are other implementations of List that are passed in as the children, meaning it is no longer possible to compile children[i] to indexing code since some of the implementations have custom indexers and .length getters that must be called.

I suspect that the indexing code part is implying that the compiled code optimizes the default list implementations to retrieve the data directly from the underlying data array. To do so, functions that use lists store the internal data pointer in a separate variable and whenever list[i] is accessed it is replaced by a data[i]. But it must be checked if the index is in range (.length), otherwise it is unsafe. It mentions that .length getters are necessary for the indexers of certain implementations of List, which suggests that some internal implementations might be splitting the data in several internal arrays. I find that far fetched, at least that is not the case for growable array. Custom implementations of list could not be compiled to an indexer, since the method could be anything, which means the compiled code would need to perform a conditional check where either it retrieves the data directly from a data[i] or it invokes the method from the custom list.

I tested compiling Dart overriding the native entry List_getIndexed and it only gets invoked when there is an out of range index, which would be what was mentioned to me as a fall-through the normal function body. I didn’t find the intrinsified version of the method, which means this is something done when compiling the instructions.

One could test this hypothesis by taking a benchmark that is where walking the children is 'hot'. I expect the benchmark would walk the 'the same' a large Widget tree over and over, with no actual appearance change.

The ‘hot’ part is implying that functions could be specially optimized for invariant parameters, because it mentions walking the same tree over and over, but it seems unrealistic to optimize per parameters, but there must be some special optimizations in hot, which would explain why JIT can sometimes be more efficient than AOT.

Alter one of the constructors to pass in an UnmodifiableListView([....]) instead of [....]. This will cause the walking of children[i] to become less efficient.

Assuming there is no inlining of Dart code, the getter of a ListView would be a method invocation, but this requires jumping to the getter code, passing the index and retrieving the underlying data pointer every time a value is retrieved from the list, which is certainly more inefficient. However if there is inlining, because view.list is final, the compiler could interpret every invocation of view.list[i] as the underlying data of view.list, making it equivalent.

The copy will do more allocation, but have a smaller size post-GC. This may be a reasonable tradeoff.

I think it is, but only when the array is passed as literal.

[Hixie]

@icatalud Please stop posting off-topic messages. I was hoping you might take the fact that all your previous comments here have been marked as off-topic as a hint, but apparently that has not worked so let me be more explicit: please don't post off-topic comments on bugs. It just generates noise and isn't helpful. Thanks.

[icatalud]

@Hixie, I was asking for some input to learn about the internals of the VM. It’s generally common that developers ask for stuff and get technical explanations about technologies on these forums. The culture of developers is usually that to help each other, I definitely didn’t take the off-topic as hint that I shouldn’t ask curiosity questions, but rather than the comment had been addressed and hidden to not create confusion. Sometimes devs have some spare time and enjoy explaining things, there are plenty of issues that are full of these kind of conversations. It is definitely always the right thing to be as explicit as possible about everything. If other Flutter devs have the mood to help me understand this, it would be greatly appreciated.

I find understanding the root of the technical considerations relevant to the topic though, because this experiment could be deduced without even running it.

The use of severe tag calls for attention, but in reality this has a small impact, which is confusing. But taking a look at the issues in the forum it seems to be common to flag things as severe (for externals devs is confusing). I think it’s unrealistic to think this solution will take less memory, because many times the children are passed as references in which cases it always takes more memory, but it could be beneficial to copy in debug mode. Alternatively children can be stored as they are in a private field and expose children as ListView. I don't think an experiment is necessary.

[Hixie]

@icatalud I applaud your enthusiasm but you continue to use the wrong fora for discussions. Please desist.