495499 - [FIX]Speed up putImageData if the image data contains doubles

Status: RESOLVED FIXED

(Core :: Graphics: Canvas2D, defect)

Description

[Boris Zbarsky [:bzbarsky]]

Attachment: Fix

It seems that a number of image processing algorithms produce image data values that are doubles.  Pending the point when we implement the HTML5 thing and stop using a JS array here, we should try to handle this case faster (without JS_GetElement!).

The patch also removes unused code, per jorendorff's request.  If we do want to reinstate it, we should just template on the desired type instead of copy/pasting, I think.

The patch also gets us a little closer to the HTML5 spec behavior for values that are out of range (clamp instead of wrapping).

This patch is a pretty noticeable perf win (20% or so) on Ben Galbraith's image filter testcase.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Attachment: JPEG file for the performance testcase

Comment 2

[Boris Zbarsky [:bzbarsky]]

Attachment: HTML testcase

Comment 3

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

Comment on attachment 380487 [details] [diff] [review]
Fix

I was hoping to avoid having to do the clamping, but I guess it's really better that we do -- I figured undefined behaviour if you pass something out of range was ok (ints outside of 0..255).  But yeah, doing the coercion inside js is much better.

Comment 4

[Boris Zbarsky [:bzbarsky]]

fwiw, the current HTML5 draft requires clamping, requires rounding of floats to ints (using a particular IEEE rounding mode at that), not just truncation, and requires that all of these happen on set in the image data, not on put....

If you have comments on all that, please send to hixie!

Comment 5

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

I'm pretty sure we've sent it to Hixie, to no avail.

Comment 6

[Jason Orendorff [:jorendorff]]

Re #4, I think all that is a good thing. Clamping and rounding make sense for the use cases here. Given that, it is only sane for that stuff to happen on set.  Using an Array for this, storing extra precision on the heap and so forth until we're ready to coerce everything to 8-bit integers, is yeah fairly crazy.

The problem is that SM has no sane way to support simple array-like int indexing; what we do for strings is slow, and what we do for arrays is a lot of work.  So, a bug for that might be a good idea.

There is one thing I dislike about the HTML5 API: it allows you to do

  pixelData[0] = "zgxymvrk"; // sets pixelData[0] to 0

This is arguably the language we've got, but would it kill us to recognize an obvious error and throw an exception every once in a while, I ask you.

Comment 7

[Jason Orendorff [:jorendorff]]

I think this friend API should have the word Canvas in its name.  There's no sense in pretending this isn't a one-off, special-purpose hack.  It is.  And that's OK.

It's pretty easy to go ahead and round: 
            *dp++ = (JSUint8) (vd + 0.5);
That is only slow if the user is actually using noninteger values (i.e. actually needs rounding), right?  This still isn't entirely compliant, thanks to the following howler in the spec:

> If the number is not an integer, it should be rounded to the nearest integer
> using the IEEE 754r convertToIntegerTiesToEven rounding mode.

but if rounding makes sense, we might as well implement it now.

r+ with the name change.

Comment 8

[Boris Zbarsky [:bzbarsky]]

>            *dp++ = (JSUint8) (vd + 0.5);

Ah, yes.  I can do that.  Not a bad idea.

I think we should push back on the rounding mode thing in the spec, honestly, especially since that's not the default rounding behavior elsewhere in ECMAScript nor is it in at least some system libraries....

I'm fine with the name change if brendan is.

Comment 9

[Brendan Eich [:brendan]]

FWIW, Scott Furman added JS_ValueToInt32, which calls js_ValueToInt32, which has

    return (int32) floor(d + 0.5);  /* Round to nearest */

way back in '96, when Netscape was adding <layers>. Graphics use-cases want APIs to round to nearest. It's ok to have such APIs.

Why does Hixie want ties rounding to even? Is that really necessary?

The only issue was that those API names didn't say g-r-a-p-h-i-c-s or "canvas", and ES1 standardized truncating conversions, wherefore JS_ValueToECMAInt32 etc.

I like jorendorff's suggestion for a concrete name. Also agree on setter throwing when you try to store a non-number.

/be

Comment 10

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

(In reply to comment #4)
> fwiw, the current HTML5 draft requires clamping, requires rounding of floats to
> ints (using a particular IEEE rounding mode at that), not just truncation, and
> requires that all of these happen on set in the image data, not on put....
> 
> If you have comments on all that, please send to hixie!

Yeah, the clamping and the like is probably fine, though it's a perf hit no matter how you do it -- doing all that on set isn't something we're going to do any time soon though, and I made that comment when the spec got changed.  Rounding and the like does seem better than requiring authors to write Math.floor() or whatnot in their own code.

Comment 11

[Boris Zbarsky [:bzbarsky]]

> Also agree on setter throwing when you try to store a non-number.

That's basically our current behavior; for the spec-specified behavior, take it up with hixie?

Comment 12

[Boris Zbarsky [:bzbarsky]]

Attachment: OK, let's try this

Changes in this patch from the previous one:

1) Renamed the function.
2) Added rounding using the "add 0.5" approach.
3) Added ties-to-even using something that looks reasonably likely to be fast
   to me.  I looked at the code gcc generates for it, and that takes about 5
   extra instructions (have to load the integer back into an xmm register, do
   the compare, then actually adjust the return value as needed).  Makes the
   ToUint8 function about 20% slower in my testing; makes the overall testcase
   maybe 1-2% slower.  Sad, but if people are going to be doing computations on
   using the imagedata to store intermediate results we'll really want the
   round-to-even behavior to prevent drift.  It's not really an issue for us
   for now, since we only round on put, when we have bigger issues anyway due
   to premultiplied alpha, so maybe I shouldn't worry about this.  Either way.
4) Added a test to exercise both codepaths.

Comment 13

[Jason Orendorff [:jorendorff]]

Comment on attachment 380763 [details] [diff] [review]
OK, let's try this

This looks good.  There is still a comment in there that says:

> * range.  Double values are converted to integers in this range by
> * truncation, not the rounding that the current HTML5 spec calls for,
> * where Canvas is concerned.  But maybe that spec will change!

r+ with that fixed.

Comment 14

[Brendan Eich [:brendan]]

Comment on attachment 380763 [details] [diff] [review]
OK, let's try this

>+static inline PRUint8 ToUint8(PRInt32 aInput)
>+{
>+    if (aInput < 0)
>+        return 0;
>+    if (aInput > 255)
>+        return 255;

Maybe GCC will do this, MSVC probably does, but why not optimize the common case (I hope) to

    if (PRUint32(aInput) > 255)
        return (aInput < 0) ? 0 : 255;

>+    return (PRUint8)aInput;

C++-style casts are prettier IMHO -- YMMV.

>+    // XXXbz it'd be awfully nice if we could prevent such modification of
>+    // imageData objects, since it's likely the spec won't allow it anyway.

Is this an XXXbz to be fixed in our code, tracked by a bug on file? If so, FIXME: bug nnnnnn. If it can't be fixed in our code, is it a request for a JS API? If so, would ES5's Object.freeze help? If not, maybe some other standard? Best to be specific and file a bug if you can.

> JS_FRIEND_API(JSBool)
>-js_ArrayToJSUint8Buffer(JSContext *cx, JSObject *obj, jsuint offset, jsuint count,
>-                        JSUint8 *dest)
>+js_CoerceArrayToCanvasImageData(JSContext *cx, JSObject *obj, jsuint offset,
>+                                jsuint count, JSUint8 *dest)

Don't pass cx if it is not needed -- if it becomes needed, we can rev this FRIEND API. Passing it and having a boolean return type suggests this is a fallible API, meaning false return implies OOM or a thrown exception. But false means can't-optimize. Best to lose cx now. Alternative: put cx last, not first, in the parameter list.

/be

Comment 15

[Boris Zbarsky [:bzbarsky]]

> but why not optimize the common case (I hope) to

Yeah, I can do that.

> C++-style casts are prettier IMHO -- YMMV.

Sure.  I keep forgetting this is C++-land now.  ;)

> Is this an XXXbz to be fixed in our code, tracked by a bug on file?

Will file and fix comment.

> Don't pass cx if it is not needed

I believe OBJ_IS_DENSE_ARRAY() needs it.  Or at least claims to.  I guess I'll move it to the end of the arg list.

Comment 16

[Brendan Eich [:brendan]]

Fooey -- some have taken to passing BOGUS_CX for such an unused cx parameter. But since you are hacking on jsarray.{h,cpp}, you could just add a static JS_INLINE helper to the .h file with signature bool js_IsDenseArray(JSObject *obj). Seems worth doing even if we find a struct or invent a class to move it into later.

/be

Comment 17

[Brendan Eich [:brendan]]

And of course change OBJ_IS_DENSE_ARRAY to call js_IsDenseArray. Thanks,

/be

Comment 18

[Boris Zbarsky [:bzbarsky]]

Yeah, I can do that.  I'll get up a patch with those changes tomorrow.

Comment 19

[Boris Zbarsky [:bzbarsky]]

Attachment: With those changes

Comment 20

[Brendan Eich [:brendan]]

Comment on attachment 382304 [details] [diff] [review]
With those changes

>+    JSBool ok =
>+        js_CoerceArrayToCanvasImageData(dataArray, 0, w*h*4, imageBuffer);
>+
>+    // no fast path? go slow.  We sadly need this for now, instead of just
>+    // throwing, because dataArray might not be dense in case someone stuck
>+    // their own array on the imageData.
>+    // FIXME: it'd be awfully nice if we could prevent such modification of
>+    // imageData objects, since it's likely the spec won't allow it anyway.
>+    // Bug 497110 covers this.
>     if (!ok) {

Final nit: We use ok to mean success, with failure implying OOM or pending exception. Could you rename ok to fast or fastpath here? r=me with that.

/be

Comment 21

[Brendan Eich [:brendan]]

Comment on attachment 382304 [details] [diff] [review]
With those changes

>     jsval v;
>     jsint vi;
>+    jsdouble vd;
>+    jsdouble toTruncate;
>+    JSUint8 val;

Oops, missed interdiff hunks somehow (bug in bugzilla interdiff, maybe). Nits again:

C++ style favors declare and initialize at latet dominating opportunity, so some if not all of these should move down.

>+                val = JSUint8(toTruncate);
>+                /* now val is rounded to nearest, ties rounded up.  We want
>+                   rounded to nearest ties to even, so check whether we had a
>+                   tie. */

Major comment style is

/*
 *
 */

with a blank line before the first comment-line unless preceded at end of previous line by a left brace.

>+                if (val == toTruncate) {
>+                  /* It was a tie (since adding 0.5 gave us the exact integer
>+                     we want).  Since we rounded up, we either already have an
>+                     even number or we have an odd number but the number we
>+                     want is one less.  So just unconditionally masking out the
>+                     ones bit should do the trick to get us the value we
>+                     want. */

So this just wants major comment style.

/be

Comment 22

[Boris Zbarsky [:bzbarsky]]

Made those changes locally, as well as the rename from comment 20.

Comment 23

[Boris Zbarsky [:bzbarsky]]

Pushed http://hg.mozilla.org/mozilla-central/rev/f7f8e22b0425

Comment 24

[Boris Zbarsky [:bzbarsky]]

This is a very safe performance improvement; I wonder whether it's worth taking on the 1.9.1 branch at some point....  I'm not sure it is, but worth a thought.

Comment 25

[Brendan Eich [:brendan]]

I'm in favor. The code is memory-safe AFAICT. It adds loads but only from extant array dslots, which build on the same assumptions as the rest of the dense array code. The rest is clamping and rounding and stuff.

/be

Comment 26

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

> The patch also removes unused code, per jorendorff's request.  If we do want to
> reinstate it, we should just template on the desired type instead of
> copy/pasting, I think.

Crap, I didn't see this earlier -- that code wasn't unused, canvas 3d needs it. =/  I'll look into reinstating it, perhaps in a way that can then remain compatible with dense arrays.

Or we can just get dense arrays done sooner...

Comment 27

[Boris Zbarsky [:bzbarsky]]

> that code wasn't unused, canvas 3d needs it.

Doh.  :(  mxr has its limitations after all.  :(

I think for unsigned integer types we should just be able to template on the type and reuse the code I wrote here, at least assuming we want the same clamping/rounding semantics...

Comment 28

[Boris Zbarsky [:bzbarsky]]

And also, if that consumer knows ahead of time what type it'll want out of the array, we should try to just have a template for the eager-converting array canvas wants.