Generated JS for blur algorithm is too slow #2845

DartBot · 2012-05-01T05:55:13Z

This issue was originally filed by @bp74

Hello

I know you are early in the process and a lot of optimizations will come in the future, but please let me show you a small sample what could be done:

I wrote an image blur algorithm in Dart and here are the most important parts of the code:

  List<int> buffer = new List<int>(1024);
  ...
  if (y >= 0) dif += 6 * buffer[y & 1023] + buffer[(y - ry2) & 1023] - 4 * (buffer[(y - ry1) & 1023] + buffer[(y + ry1) & 1023]);
  else if (y + ry1 >= 0) dif += 6 * buffer[y & 1023] - 4 * (buffer[(y - ry1) & 1023] + buffer[(y + ry1) & 1023]);
  else if (y + ry2 >= 0) dif += 6 * buffer[y & 1023] - 4 * (buffer[(y + ry1) & 1023]);
  else if (y + ry3 >= 0) dif -= 4 * buffer[(y + ry1) & 1023];
  ...
  destinationData[offsetY] = (sum / weight).toInt();

Full sourcecode is here: http://code.google.com/p/dartflash/source/browse/trunk/library/filters/BlurFilter.dart

Here are the benchmarks (3 runs), thumbs up for Chrome!!

Chrome: 106ms 83ms 82ms
IE9: 1329ms 555ms 554ms
Firefox: 694ms 741ms 748ms

Now a take a look at the generated javascript, and i see this:

  var buffer = new Array((1024));
  ...
  if (y >= (0)) dif += ($add$($mul$((6), buffer.$index(y & (1023))), buffer.$index((y - ry2) & (1023))) - $mul$((4), ($add$(buffer.$index((y - ry1) & (1023)), buffer.$index((y + ry1) & (1023))))));
  else if (y + ry1 >= (0)) dif += ($mul$((6), buffer.$index(y & (1023))) - $mul$((4), ($add$(buffer.$index((y - ry1) & (1023)), buffer.$index((y + ry1) & (1023))))));
  else if (y + ry2 >= (0)) dif += ($mul$((6), buffer.$index(y & (1023))) - $mul$((4), (buffer.$index((y + ry1) & (1023)))));
  else if (y + ry3 >= (0)) dif -= ($mul$((4), buffer.$index((y + ry1) & (1023))));
  ...
  destinationData.$setindex(offsetY, (sum / weightY).toInt());

Well, that looks like you have replaced the index-setters to "$index" methods, which makes it very hard for the javascript-VM to make it really fast.

Now i "optimized" the JavaScript with 3 simple changes:

* i replaced the index-setters with real indexer.
* i replaced $add$ and $mul$ with "+" and "".
i replace the "num.toInt()" method with an inline version "num | 0".

Please look at the new benchmarks:

Chrome: 26ms, 15ms, 15ms
IE9: 278ms, 58ms, 58ms
Firefox: 236ms, 231ms, 231ms

That's a factor of 5 to 10 (firefox only 3). With only a very small change to the generated code.

As said in the beginning, i know that optimization is not a top priority right now and a lot of things will come in the future. I only want to show and remind how much impact such small code changes can have.

Thank you very much for your good work an Dart.

kasperl · 2012-05-01T06:41:54Z

Thanks for the information. We're actively working on propagating type information so that we can generate better JavaScript code. Our new Dart-to-JavaScript compiler (dart2js) does try to use real indexers and raw JS primitives for + and * when we can tell it is safe to do so.

If you could put a small benchmark that you care about somewhere and make it easy to run (maybe just a small version of what you've already posted), we'd be happy to try it out as part of tuning our compiler.

Thanks again!

Added Area-Dart2JS, Accepted labels.

DartBot · 2012-05-01T07:15:20Z

This comment was originally written by @bp74

Thank you very much for your reply, i'm happy to provide the benchmark.

Here is the URL:
http://www.dartflash.com/test/Benchmark1/Benchmark1.html

It contains the dart-file, as well as the dart.js-file.

kasperl · 2012-05-02T10:13:46Z

Thanks, Bernhard! This is very useful.

kasperl · 2012-05-15T15:00:22Z

Changed the title to: "Generated JS for blur algorithm is too slow".

DartBot · 2012-06-14T19:16:52Z

This comment was originally written by @bp74

Updated numbers of the benchmark for Dart Build 8641:
http://www.dartflash.com/test/Benchmark1-8641/Benchmark1.html

Chrome: 616ms, 571ms, 571ms
IE9: 2924ms, 1349ms, 1358ms

Firefox 13: failed because of issue #2535

Well, i keep my faith in the Dart team to make in faaaaaast in the future :)

kasperl · 2012-06-15T05:23:49Z

cc @madsager.

kasperl · 2012-06-15T10:25:09Z

If we make our Uint8ClampedArray implement JavaScriptIndexingBehavior the numbers do improve a lot. It is still too slow, but at least we avoid using the blurFilter$bailout variant.

--- a/lib/html/frog/html_frog.dart
+++ b/lib/html/frog/html_frog.dart
@@ -15156,7 +15156,7 @@ class _Uint8ArrayImpl extends _ArrayBufferViewImpl implements Uint8Array, List<i
   _Uint8ArrayImpl subarray(int start, [int end = null]) native;
}

-class _Uint8ClampedArrayImpl extends _Uint8ArrayImpl implements Uint8ClampedArray native "*Uint8ClampedArray" {
+class _Uint8ClampedArrayImpl extends _Uint8ArrayImpl implements Uint8ClampedArray, JavaScriptIndexingBehavior native "*Uint8ClampedArray" {

   // Use implementation from Uint8Array.
   // final int length;

cc @rakudrama.

kasperl · 2012-06-20T07:42:59Z

Stephen landed his change (r8882) to make your benchmark not get stuck in the slow bailout version (basically allowing us to use [] on the Uint8ClampedArray). This should help a bit, but we still have more work ahead of us.

DartBot · 2012-06-20T17:10:11Z

This comment was originally written by @bp74

Thank you very much for the update. Yes this change makes a huge difference:

Chrome : 157ms, 95ms, 95ms
IE9 : 1856ms, 704ms, 704ms

The code looks better too - most operations are native JS operations now, except the binary AND. Let me clarify that this issue is not about this particular function, it's just an example of code that does a lot of number crunching. Another example i have is a 2D-Matrix class which is frequently used in my graphics engine. Believe it or not, the "copyFromAndConcat" method below has 26(!!) type checkes for bailout code (if i write the code in a different way i can bring it down to 12 type checks). For a function that should be stupidly fast this is a high burden. Personally, i think the dart2js compiler should use type annotations much more to make good JS-code. Kasper gave a short response on Google+ about this topic and i know there are good reasons for not using the type annotations. Maybe in the end we will have a compiler switch to enable unsafe but fast JS-code!?

class Matrix {
  num _a, _b, _c, _d, _tx, _ty;

  Matrix(num a, num b, num c, num d, num tx, num ty) :
    _a = a, _b = b, _c = c, _d = d, _tx = tx, _ty = ty;

  void copyFromAndConcat(Matrix copyMatrix, Matrix concatMatrix) {
    _a = copyMatrix._a * concatMatrix._a + copyMatrix._b * concatMatrix._c;
    _b = copyMatrix._a * concatMatrix._b + copyMatrix._b * concatMatrix._d;
    _c = copyMatrix._c * concatMatrix._a + copyMatrix._d * concatMatrix._c;
    _d = copyMatrix._c * concatMatrix._b + copyMatrix._d * concatMatrix._d;
    _tx = copyMatrix._tx * concatMatrix._a + copyMatrix._ty * concatMatrix._c + concatMatrix._tx;
    _ty = copyMatrix._tx * concatMatrix._b + copyMatrix._ty * concatMatrix._d + concatMatrix._ty;
  }
}

BTW: the JS-code uses "getters" to access the fields of "copyMatrix" and "concatMatrix". Maybe the dart2js compiler can access the fields directly and not using a getter implementation in the future.

PS: Sorry for being annoying, but JS-speed is the most important point for me. And don't get me wrong, i know you all do great work to make it better day after day.

kasperl · 2012-06-20T17:55:10Z

Thanks for the update, Bernhard! We will continue to try to improve the performance of the dart2js output and we really value your input. I'm sure we will be able to get rid of most of the 26 checks you mention.

FWIW, I expect us to fix the binary AND issue tomorrow.

kasperl · 2012-09-03T11:31:21Z

Set owner to @kasperl.
Added this to the M1 milestone.

kasperl · 2012-09-04T10:16:22Z

It looks like we did manage to fix the AND issue. Next steps involve more type propagation and type inferencing (a few things have already landed). What's the current status seen from your side, Bernhard?

It is a bit wrong to mark this as fixed (because it certainly still is work in progress), but we'll try to file more actionable issue going forward.

Thanks again for the bug report, Bernhard.

Added Fixed label.

DartBot · 2012-09-04T12:42:53Z

This comment was originally written by @bp74

Thanks Kasper, it's okay to close this issue. I know there is a lot of work going on with type propagation and type inferencing.

Sure there is still a lot of room for improvements. In Chrome the code runs almost as fast as before when compiled with frog. In IE9 and Firefox the code is almost twice as fast with dart2js (very strange)!

DartBot · 2012-09-28T08:22:47Z

This comment was originally written by [email protected]

FWIW, Nicolas just landed a change that may improve this even further (by getting rid of some bounds checks through value range propagation).

DartBot · 2012-09-28T13:26:59Z

This comment was originally written by @bp74

Thanks Kasper for the notice, i did a test with Build 13015 and the JavaScript code looks much(!) better now. All range checks are gone, only a few type checks remain.

If i have a List<int> and all i do is write ints to the list, after a read from the list the type is still check if it is really a number. But i don't want to complain, it's great to see this fantastic progress in dart2js. Thanks to you and your team!

DartBot · 2012-10-04T16:43:33Z

This comment was originally written by @bp74

Wow, i'm speechless! With the latest build of Dart, the benchmark is more than twice as fast as before. You guys are geniuses :) I compared the previous version to the current version and only one small thing has changed - the fixed length of the Uint8ClampedArray [canvas.context2D.getImageData().data] is stored in a temporary variable in front of the loop! This is an awesome optimization.

http://code.google.com/p/dart/source/detail?r=13224

First three runs:
Chrome : 75ms, 37ms, 37ms
IE9 : 750ms, 243ms, 243ms
Firefox : 200ms, 191ms, 191ms

Included commits: ``` git log --format="%C(auto) %h %s" 0402c467547daa5886352cb315338ae54552d21c..0e657414a472e74ca5dd76ae0db50cc060251dec 0e657414 Show outdated and discontinued in listing in get (#2844) f842ae22 Include a deprecation notice in .packages (#2845) ``` Change-Id: Iaf03c5ea0380c16332ce65f2c4b3bf935873d30c Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/180841 Reviewed-by: Jonas Jensen <[email protected]> Commit-Queue: Sigurd Meldgaard <[email protected]>

DartBot added Type-Defect web-dart2js labels Oct 4, 2012

DartBot assigned kasperl Oct 4, 2012

DartBot added this to the M1 milestone Oct 4, 2012

This issue was closed.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Generated JS for blur algorithm is too slow #2845

Generated JS for blur algorithm is too slow #2845

DartBot commented May 1, 2012

kasperl commented May 1, 2012

Uh oh!

DartBot commented May 1, 2012

Uh oh!

kasperl commented May 2, 2012

Uh oh!

kasperl commented May 15, 2012

Uh oh!

DartBot commented Jun 14, 2012

Uh oh!

kasperl commented Jun 15, 2012

Uh oh!

kasperl commented Jun 15, 2012

Uh oh!

kasperl commented Jun 20, 2012

Uh oh!

DartBot commented Jun 20, 2012

Uh oh!

kasperl commented Jun 20, 2012

Uh oh!

kasperl commented Sep 3, 2012

Uh oh!

kasperl commented Sep 4, 2012

Uh oh!

DartBot commented Sep 4, 2012

Uh oh!

DartBot commented Sep 28, 2012

Uh oh!

DartBot commented Sep 28, 2012

Uh oh!

DartBot commented Oct 4, 2012

Uh oh!

Generated JS for blur algorithm is too slow #2845

Generated JS for blur algorithm is too slow #2845

Comments

DartBot commented May 1, 2012

kasperl commented May 1, 2012

Uh oh!

DartBot commented May 1, 2012

Uh oh!

kasperl commented May 2, 2012

Uh oh!

kasperl commented May 15, 2012

Uh oh!

DartBot commented Jun 14, 2012

Uh oh!

kasperl commented Jun 15, 2012

Uh oh!

kasperl commented Jun 15, 2012

Uh oh!

kasperl commented Jun 20, 2012

Uh oh!

DartBot commented Jun 20, 2012

Uh oh!

kasperl commented Jun 20, 2012

Uh oh!

kasperl commented Sep 3, 2012

Uh oh!

kasperl commented Sep 4, 2012

Uh oh!

DartBot commented Sep 4, 2012

Uh oh!

DartBot commented Sep 28, 2012

Uh oh!

DartBot commented Sep 28, 2012

Uh oh!

DartBot commented Oct 4, 2012

Uh oh!