Indices passed to FilteredElementList public functions should consistently refer to element indices

Please refer to https://code.google.com/p/dart/issues/detail?id=23418 for the bug reportincluding a WebStorm project which demonstrates the problem.

This proposal includes a fix to ensure that indices passed to the public functions defined in class FilteredElementList of the dart:html package consistently refer to element indices (not element indices sometimes, and node indices other times). Without this change, it is not possible to reliably insert elements relative to other elements. This can be problematic as the order of HTML elements must be guaranteed to ensure elements appear where expected in a normal page flow.

This proposal also address the TODO in file sdk/lib/html/html_common/filtered_element_list.dart to avoid excessively creating/allocating a filtered list of elements from nodes whenever calling [], every, any, length, etc. The implementation is less concise but should result in much reduced memory allocation and speed improvements.

R=alanknight@google.com

Committed: https://github.com/dart-lang/sdk/commit/3b125d3bc9cc4d0f6f6a3ad2e0f6c8367128d8b8

[Alan Knight, 2015-05-13 22:08:14]

alanknight@google.com changed reviewers:
+ alanknight@google.com

[Alan Knight, 2015-05-13 22:08:15]

Thanks. A definite bug, which needs fixing. A few questions though, particularly
on the performance optimization. Do we have any benchmarks or other evidence of
what this is saving?

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
File sdk/lib/html/html_common/filtered_element_list.dart (right):

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
sdk/lib/html/html_common/filtered_element_list.dart:12: implements
NodeListWrapper{
Indentation.

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
sdk/lib/html/html_common/filtered_element_list.dart:86:
RangeError.checkValidRange(start, end, this.length);
this.length iterates the _iterable. That probably negates any performance gains.

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
sdk/lib/html/html_common/filtered_element_list.dart:88: for (int i =
_childNodes.length - 1; i >= 0; i--) {
I don't think this is correct. See
https://dartpad.dartlang.org/0503db0694c22429e0e3

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
sdk/lib/html/html_common/filtered_element_list.dart:120: int nodeElementIndex =
0;
What is this gaining us versus having insert as 
    var element =_iterable[index];
    value.insertBefore(element.nextSibling);
?

This seems like we're manually inlining browser operations which I suspect can
be very fast. And the ultimate implementation of this is going to be in terms of
insertBefore anyway.

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
sdk/lib/html/html_common/filtered_element_list.dart:128:
RangeError.checkValueInInterval(elementIndex, 0, nodeElementIndex + 1, "index");
Line length

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
sdk/lib/html/html_common/filtered_element_list.dart:132: void insert(int index,
T value) {
Don't assign to input parameters. It's confusing.

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
sdk/lib/html/html_common/filtered_element_list.dart:135: _childNodes.add(value);
I don't think this checking is necessary. If you look at the generated JS the
compiler does this anyway, so just calling insert/insertAll should achieve the
same thing.

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
sdk/lib/html/html_common/filtered_element_list.dart:167: if (nodeToRemove !=
null) {
Why the extra step here?

[almstrand, 2015-05-14 06:34:45]

Thanks, I have not benchmarked the proposed implementation. Considering the
potentially large number of List allocations in the current implementation it
seems reasonable that there should be significant improvements. As an example,
both the [] operator and length getter allocate a new List each time called. If
done in a loop, that could be very costly. Not being familiar with he review
process, I am not clear on the next steps though would be happy to push a commit
that attempts to address much of these comments as well as writing simple
benchmarks to compare before/after.

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
File sdk/lib/html/html_common/filtered_element_list.dart (right):

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
sdk/lib/html/html_common/filtered_element_list.dart:12: implements
NodeListWrapper{
On 2015/05/13 22:08:14, Alan Knight wrote:
> Indentation.

Acknowledged.

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
sdk/lib/html/html_common/filtered_element_list.dart:86:
RangeError.checkValidRange(start, end, this.length);
On 2015/05/13 22:08:14, Alan Knight wrote:
> this.length iterates the _iterable. That probably negates any performance
gains.

Would it be acceptable to check the range *after* attempting to remove the
elements? In that case we can get away with iterating the node elements just
once, and calculating the length of the element array along the way.

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
sdk/lib/html/html_common/filtered_element_list.dart:88: for (int i =
_childNodes.length - 1; i >= 0; i--) {
On 2015/05/13 22:08:14, Alan Knight wrote:
> I don't think this is correct. See
> https://dartpad.dartlang.org/0503db0694c22429e0e3

You are correct, the array must not be iterated in reverse here. I confirmed
(see: https://dartpad.dartlang.org/0ea27032e18a6dd97350) that this can be
corrected by changing the order. Aside from the performance issue commented on
above re: iterating _iterable, and pending any benchmarking, the proposed change
does avoid the allocation of a new _filtered list in the original
implementation, and the additional List allocation in sublist(...). The proposed
implementation requires no allocation and has a time complexity of < O(n).

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
sdk/lib/html/html_common/filtered_element_list.dart:120: int nodeElementIndex =
0;
On 2015/05/13 22:08:14, Alan Knight wrote:
> What is this gaining us versus having insert as 
>     var element =_iterable[index];
>     value.insertBefore(element.nextSibling);
> ?
> 
> This seems like we're manually inlining browser operations which I suspect can
> be very fast. And the ultimate implementation of this is going to be in terms
of
> insertBefore anyway.

I agree. That is a much more concise and likely more performant implementation.
It would be great if insertAll() could be implemented a similar way, but it
seems insertBefore(...) takes a single element as input. Because of that we
would be forced to call _iterable[] and insertBefore(...) repeatedly, which will
iterate _iterable for each insertion. Perhaps in that case the proposed
implementation would still perform better?

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
sdk/lib/html/html_common/filtered_element_list.dart:128:
RangeError.checkValueInInterval(elementIndex, 0, nodeElementIndex + 1, "index");
On 2015/05/13 22:08:15, Alan Knight wrote:
> Line length

Acknowledged.

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
sdk/lib/html/html_common/filtered_element_list.dart:132: void insert(int index,
T value) {
On 2015/05/13 22:08:14, Alan Knight wrote:
> Don't assign to input parameters. It's confusing.

Acknowledged.

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
sdk/lib/html/html_common/filtered_element_list.dart:135: _childNodes.add(value);
On 2015/05/13 22:08:14, Alan Knight wrote:
> I don't think this checking is necessary. If you look at the generated JS the
> compiler does this anyway, so just calling insert/insertAll should achieve the
> same thing.

The conditional add(...) was borrowed from List.dart (referencing
https://github.com/dart-lang/bleeding_edge/blob/master/dart/sdk/lib/collectio...).
I wonder if there is any reason it is done that way in List.dart. If none,
perhaps that implementation can also be improved.

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
sdk/lib/html/html_common/filtered_element_list.dart:167: if (nodeToRemove !=
null) {
On 2015/05/13 22:08:14, Alan Knight wrote:
> Why the extra step here?

Acknowledged.

[Alan Knight, 2015-05-15 19:30:57]

General commentary, haven't had a chance to go over the specific items yet.

The way the reviews normally work is that the author can make changes to the
code based on review feedback and do "git cl upload" again, which makes a new
patch set, until it converges to LGTM. Having tests is important. We obviously
don't have tests that exercise this properly or we wouldn't have the bug. But we
should fix that. 

We tend to be pretty data-driven on performance optimizations. There are a
number of benchmarks that always get run, and we watch for regressions or that
things that make the code more complex in the name of performance actually
improve it. For web stuff in particular we're probably most interested in the
performance when compiled to JS. The dart2js compiler is pretty clever, and the
JS runtimes are too, so intuitive ideas of what's faster don't always work out.
And improvements in real programs are better than in contrived benchmarks.

You did have an example in the bug report which is real usage. That's good,
although it does occur to me that looking up the index is unnecessary. At the
DOM level the APIs are done in terms of nodes (append, insertBefore), so it's
presumably faster not to do it with the index. And those are in terms of
individual nodes, so anything that has multiples will end up needing to iterate.
The API should work regardless, but it's not the best way to do it for
performance.

I'm not really a performance expert, but Stephen (sra) is, so copied him. The
bug is definitely real and important. I'd be tempted to try to separate the core
fix from performance stuff unless it's very directly related.

[almstrand, 2015-05-15 21:26:09]

Thanks for the feedback and for taking time to clarify the process.

I agree with the approach of focusing on resolving the bug first, and can upload
a patch set shortly which does only that.

Once reviewed/modified/accepted, perhaps we can create another issue that
focuses on addressing the TODO to improve performance.

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
File sdk/lib/html/html_common/filtered_element_list.dart (right):

https://codereview.chromium.org/1129333002/diff/1/sdk/lib/html/html_common/fi...
sdk/lib/html/html_common/filtered_element_list.dart:120: int nodeElementIndex =
0;
On 2015/05/14 06:34:45, almstrand wrote:
> On 2015/05/13 22:08:14, Alan Knight wrote:
> > What is this gaining us versus having insert as 
> >     var element =_iterable[index];
> >     value.insertBefore(element.nextSibling);
> > ?
> > 
> > This seems like we're manually inlining browser operations which I suspect
can
> > be very fast. And the ultimate implementation of this is going to be in
terms
> of
> > insertBefore anyway.
> 
> I agree. That is a much more concise and likely more performant
implementation.
> It would be great if insertAll() could be implemented a similar way, but it
> seems insertBefore(...) takes a single element as input. Because of that we
> would be forced to call _iterable[] and insertBefore(...) repeatedly, which
will
> iterate _iterable for each insertion. Perhaps in that case the proposed
> implementation would still perform better?

insertAll(...) can be implemented similarly to your suggestion using
insertAllBefore(...), e.g.:

  void insertAll(int index, Iterable<T> iterable) {
    Element element =_iterable.elementAt(index);
    element.parentNode.insertAllBefore(iterable, element);
  }

[Alan Knight, 2015-07-14 21:46:24]

lgtm

Sorry for the delay in review, I've been away. I also ran the formatter over the
code, as we're trying to do now, and changed the typed local Element to var to
match the style guide in two methods. It won't let me upload, because I don't
own the issue. I'll see if I can commit it.

[Alan Knight, 2015-07-14 21:50:47]

Committed patchset #2 (id:20001) manually as
3b125d3bc9cc4d0f6f6a3ad2e0f6c8367128d8b8 (presubmit successful).