Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Performance difference with [] on typed arrays vs. typed array views #9596

Closed
fsc8000 opened this issue Apr 2, 2013 · 14 comments
Closed

Performance difference with [] on typed arrays vs. typed array views #9596

fsc8000 opened this issue Apr 2, 2013 · 14 comments
Assignees
Labels
area-vm type-bug Incorrect behavior (everything from a crash to more subtle misbehavior)

Comments

@fsc8000
Copy link
Contributor

fsc8000 commented Apr 2, 2013

The attached example shows a performance degradation when using an array view.

In the view case, the optimizer is not able to eliminate the if-statement for the range check from the inlined body of Uint8ArrayView.[]:

    if (index < 0 || index >= length) {
      _throwRangeError(index, length);
    }


Attachment:
uint8listview.dart (616 Bytes)

@ghost
Copy link

ghost commented Apr 2, 2013

We probably need to optimize at the operator level ([], []=) instead of only at the level of the native.

@DartBot
Copy link

DartBot commented Apr 2, 2013

This comment was originally written by @tatumizer


"View" is very powerful concept. Simplifies programming tremendously. Please make it perform exactly as array, whatever it takes. Probably, doing this on operator level is the only choice.

@fsc8000
Copy link
Contributor Author

fsc8000 commented Apr 2, 2013

Yes, doing it at the operator level would work.

Before doing that I'll look into improving constant propagation and range analysis to eliminate the if-statement completely.

If that works out nicely and covers all interesting cases, we could avoid special-casing for the [] and []= operators on views.


Added Started label.

@sethladd
Copy link
Contributor

sethladd commented Apr 3, 2013

cc @johnmccutchan.

@fsc8000
Copy link
Contributor Author

fsc8000 commented Apr 4, 2013

https://code.google.com/p/dart/source/detail?r=20914 improves typed array view performance by eliminating more range checks. Of course, it is not always possible to eliminate the range check, but it should help in the reported example.

There may be still a performance difference due to the start offset that needs to be added when loading from a view.

@fsc8000
Copy link
Contributor Author

fsc8000 commented May 1, 2013

Added Fixed label.

@DartBot
Copy link

DartBot commented May 10, 2013

This comment was originally written by @tatumizer


Performance of subscript for uint8 view is much slower than subscript for underlying typed array. (6.1 ns/byte vs 2.3 ns/byte) In other words, it doesn't look optimized at all.
Please run it with and without view to verify my claim.
testListSubscriptView8(size, iterations) {
  var _list=new Uint8List(size);
  
  var list=new Uint8List.view(_list.buffer);
  int x=0;
  for (int i=0; i<iterations; i++) {
    for (int j=0; j<size; j++)
      x|=list[j];
  }
  return x;
}

@ghost
Copy link

ghost commented May 10, 2013

Set owner to @sgmitrovic.
Added Accepted label.

@ghost
Copy link

ghost commented May 10, 2013

The main performance drop is still caused by not being able to eliminate explicit range checks and by some register allocation issues. Example program below.

import 'dart:typed_data';

main() {
  var size = 10000000;
  var _list = new Uint8List(size);
  var list = new Uint8List.view(_list.buffer);
  foo(list, size, 1);
  for (int i = 0; i < 10; i++) {
    var sw = new Stopwatch()..start();
    foo(list, size, 100);
    sw.stop();
    print(sw.elapsedMilliseconds);
  }
}

foo(list, size, iterations) {
  int x=0;
  for (int i=0; i<iterations; i++) {
    for (int j=0; j<size; j++) {
      x|=list[j];
    }
  }
  return x;
}

@fsc8000
Copy link
Contributor Author

fsc8000 commented May 13, 2013

The reason we can't eliminate the range check in this example is that the compiler can't deduce the connection between 'size' and 'list.length' inside function foo.

If you replace

for (int j=0; j<size; j++) {

with

for (int j=0; j<list.length; j++) {

the performance difference should go away.

Optimizing the example as shown would still be possible if the compiler could optimistically hoist the range check out of the loop. The current implementation of bounds-check elimination is not able to do that.

@iposva-google
Copy link
Contributor

Removed Priority-Medium label.
Added Priority-Unassigned label.

@fsc8000 fsc8000 assigned ghost Jun 5, 2013
@kevmoo kevmoo added type-bug Incorrect behavior (everything from a crash to more subtle misbehavior) and removed priority-unassigned labels Feb 29, 2016
@iposva-google iposva-google assigned fsc8000 and unassigned ghost May 19, 2016
@iposva-google
Copy link
Contributor

@fsc8000 Is this still an issue?

@fsc8000
Copy link
Contributor Author

fsc8000 commented May 20, 2016

Yes, there is still a difference, but t is much smaller now though. I see around 30% depending on inlining/OSR instead of the original ~3x slowdown.

@fsc8000
Copy link
Contributor Author

fsc8000 commented Oct 7, 2016

Closing as the original large slow-down seems fixed.

@fsc8000 fsc8000 closed this as completed Oct 7, 2016
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
area-vm type-bug Incorrect behavior (everything from a crash to more subtle misbehavior)
Projects
None yet
Development

No branches or pull requests

5 participants