497794 - Need a way to initialize an array without copying

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Boris Zbarsky [:bzbarsky]]

GetImageData() or CreateImageData() on a canvas frirst builds up a jsval[] vector, then creates a JS array to wrap it... and the array creation memcpys the vector.  For the image in bug 497458, which is 2560x1600px, that would be a memcpy of 2560*1600*4*4 == 65,536,000 bytes.  Which of course Takes Time.

If we keep using arrays for image data, we need to either have a way to allocate here and stick it into the JS array without copying, or have a way to have the array do the allocation (since it fuses length and dslots into a single allocation) and then tell us where to put our image data, or _something_.

Or we could stop using a JS array here, of course.... roc suggests that having a bytearray type that jstracer knows about might be the right way to go.

Comment 1

[Mike Shaver (:shaver emeritus)]

Easiest thing to do for now is expose EnsureSize and an accessor for &dslots[0] to js_*-using friends.  Then the canvas can just be building into the right place.

Comment 2

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Note that Webkit has a ByteArray thing that SFX knows about.

Comment 3

[Mike Shaver (:shaver emeritus)]

Yeah, it's been requested in a few places.  Would take longer to do than my hack, though. :)

Comment 4

[Boris Zbarsky [:bzbarsky]]

The hack could be done; I'm worried about it playing nice with type-specialized arrays, though...  Rob, should I just do this, and you'll adapt accordingly?  Ideally, we'd start of imagedata as an int-specialized array, as long as it's an array.

I filed bug 497795 on a ByteArray type.

Comment 5

[Rob Arnold [:robarnold]]

(In reply to comment #4)
> The hack could be done; I'm worried about it playing nice with type-specialized
> arrays, though...  Rob, should I just do this, and you'll adapt accordingly? 

Yeah, I can adapt; this doesn't look like a terribly large change. We'll want something better when we have type specialized arrays (I know there is a push to have them only be contiguous arrays for faster canvasing).

For what it's worth, I don't think the ByteArray solution is that hard since most of the work was already done for type specialized arrays (C++ templates are nice sometimes).

Comment 6

[Robert O'Callahan (:roc) (email my personal email if necessary)]

We've got months of 1.9.2 ahead of us, can't we for once do something the right way instead of with a hack?

Comment 7

[Rob Arnold [:robarnold]]

(In reply to comment #6)
> We've got months of 1.9.2 ahead of us, can't we for once do something the right
> way instead of with a hack?

As a general rule, I am in favor of removing rather than introducing hacks. I think we will have enough time to do this a right way.

Comment 8

[Mike Shaver (:shaver emeritus)]

(In reply to comment #6)
> We've got months of 1.9.2 ahead of us, can't we for once do something the right
> way instead of with a hack?

For once, indeed.  I don't think that the change I propose (allowing external code to ask for an array of a given size, and then get access to its raw storage) is at all incompatible with that array being specialized for byte-width data, or the tracer being taught about it.  It's an interim step that lets us get a big gain quickly, but if it will interfere with someone doing ByteArray work then sure, let's not do it.

I am all for us solving problems in a systematic way, if they are systematic problems.  So far we have seen a single use case for this: canvas pixel-blasting.  What other use cases should inform this more general solution?

Comment 9

[Boris Zbarsky [:bzbarsky]]

I don't think we have any use cases here other than canvas yet....

I suspect that when we have the ByteArray type, we'll still need the friend API to fill in the buffer; it's just that the filling-in code will change slighly to put in PRUint8 instead of jsval.  So I'll just go ahead and do that.  Rob can merge with specialized arrays as needed.

Is there a way we can add this pixastic test to something we run on tbox?  It'd be good to have a test on there that's sensitive to canvas imagedata performance...

Comment 10

[Robert O'Callahan (:roc) (email my personal email if necessary)]

I don't have another specific use-case right now. I expect that the emerging APIs for File and Blob data would benefit from efficient access to the data as a byte array.

But I think it's worth doing just for ImageData --- 1/4 the memory and spec compliance.

Comment 11

[Boris Zbarsky [:bzbarsky]]

Attachment: Possible patch against trunk (should apply to 1.9.1 too)

Some numbers.... on the pixtastic testcase in question, on my machine, without this patch over 4 trials I see a mean of 995ms and sttdev of 16ms.  With the patch, over 4 trials, I see a mean of 860ms and sttdev of 8ms.

The win is bigger than expected because I was not looking at hypervisor stacks.  While memcpy was in fact only 5% of total time in _our_ code, memory faults were 30% of overall testcase time.  With the patch, memory faults are 25% of the (smaller) overall testcase time.  That plus the lack of memcpy explains the 14% overall difference.

So I think roc is right that making the array 4x smaller would help a good bit here.

Comment 12

[Mike Shaver (:shaver emeritus)]

roc is very rarely wrong about such things; I don't mean to indicate that we shouldn't do byte-specialized arrays, because I think they would be awesome.  I just think that adding these hooks is an easy first thing to do, and shouldn't be seen as exclusive to ByteArray or otherwise conflicting with it.

Comment 13

[Boris Zbarsky [:bzbarsky]]

Attachment: 1.9.2 version

Comment 14

[Boris Zbarsky [:bzbarsky]]

Attachment: m-c version (same as 1.9.2 except for some jsarray context)

The 1.9.2 patch would just apply to m-c if it were -u4 instead of -u8.

Comment 15

[Boris Zbarsky [:bzbarsky]]

This is a significant perf win for canvas, so requesting blocking....

Comment 16

[Rob Arnold [:robarnold]]

Comment on attachment 407325 [details] [diff] [review]
1.9.2 version

Looks good to me though it would be nice to have a JS peer take a look at it too (perhaps Waldo?).

Comment 17

[Jeff Walden [:Waldo]]

Comment on attachment 407325 [details] [diff] [review]
1.9.2 version

>diff --git a/js/src/jsarray.cpp b/js/src/jsarray.cpp

> static JSBool
>-ResizeSlots(JSContext *cx, JSObject *obj, uint32 oldlen, uint32 newlen)
>+ResizeSlots(JSContext *cx, JSObject *obj, uint32 oldlen, uint32 newlen,
>+            JSBool initializeAllSlots = JS_TRUE)

These days in JS-land we use bool except in JSAPI (or friend, I guess) interfaces, so initializeAllSlots should be bool.


> static JSBool
>-EnsureCapacity(JSContext *cx, JSObject *obj, uint32 newcap)
>+EnsureCapacity(JSContext *cx, JSObject *obj, uint32 newcap,
>+               JSBool initializeAllSlots = JS_TRUE)

Likewise for initializeAllSlots here.


>@@ -370,22 +374,33 @@ EnsureCapacity(JSContext *cx, JSObject *
>          * example, (oldcap * 2 + 1) produces the sequence 7, 15, 31, 63, ...
>          * which makes the total allocation size (with dslots[-1]) a power
>          * of two.
>          */
>         uint32 nextsize = (oldcap <= CAPACITY_DOUBLING_MAX)
>                           ? oldcap * 2 + 1
>                           : oldcap + (oldcap >> 3);
> 
>-        newcap = JS_MAX(newcap, nextsize);
>-        if (newcap >= CAPACITY_CHUNK)
>-            newcap = JS_ROUNDUP(newcap + 1, CAPACITY_CHUNK) - 1; /* -1 for dslots[-1] */
>-        else if (newcap < ARRAY_CAPACITY_MIN)
>-            newcap = ARRAY_CAPACITY_MIN;
>-        return ResizeSlots(cx, obj, oldcap, newcap);
>+        uint32 newCapacity = JS_MAX(newcap, nextsize);
>+        if (newCapacity >= CAPACITY_CHUNK)
>+            newCapacity = JS_ROUNDUP(newCapacity + 1, CAPACITY_CHUNK) - 1; /* -1 for dslots[-1] */
>+        else if (newCapacity < ARRAY_CAPACITY_MIN)
>+            newCapacity = ARRAY_CAPACITY_MIN;
>+        if (!ResizeSlots(cx, obj, oldcap, newCapacity, initializeAllSlots))
>+            return JS_FALSE;
>+        if (!initializeAllSlots) {
>+            /*
>+             * Initialize the slots caller didn't actually ask for.
>+             */
>+            for (jsval *slots = obj->dslots + newcap;
>+                 slots < obj->dslots + newCapacity;
>+                 slots++)
>+                *slots = JSVAL_HOLE;
>+        }

newcap and newCapacity is a little confusing; actualCapacity instead please?


>+        // Fall through to return JS_TRUE
>     }
>     return JS_TRUE;

Comment not necessary here.


>+JS_FRIEND_API(JSObject *)
>+js_NewArrayObjectWithCapacity(JSContext *cx, jsuint capacity, jsval **vector)
>+{
>+    JSObject *obj = JS_NewArrayObject(cx, capacity, NULL);

js_NewArrayObject please.


>+    JSTempValueRooter tvr;
>+    JS_PUSH_TEMP_ROOT_OBJECT(cx, obj, &tvr);

JSAutoTempValueRooter tvr(cx, obj) please.

Comment 18

[Brendan Eich [:brendan]]

(In reply to comment #17)
> (From update of attachment 407325 [details] [diff] [review])
> >diff --git a/js/src/jsarray.cpp b/js/src/jsarray.cpp
> 
> > static JSBool
> >-ResizeSlots(JSContext *cx, JSObject *obj, uint32 oldlen, uint32 newlen)
> >+ResizeSlots(JSContext *cx, JSObject *obj, uint32 oldlen, uint32 newlen,
> >+            JSBool initializeAllSlots = JS_TRUE)
> 
> These days in JS-land we use bool except in JSAPI (or friend, I guess)

ABI is more important. See bug 453361.

/be

Comment 19

[Jeff Walden [:Waldo]]

(In reply to comment #18)
> > These days in JS-land we use bool except in JSAPI (or friend, I guess)
> 
> ABI is more important. See bug 453361.

Er, yes, called-from-trace methods fit as well.  But that's not relevant in this case (EnsureCapacity and ResizeSlots both having compiler-determined calling convention), is it, so bool-ification should proceed in these instances, right?

Comment 20

[Brendan Eich [:brendan]]

Yes, bool where we can.

>+            for (jsval *slots = obj->dslots + newcap;
>+                 slots < obj->dslots + newCapacity;
>+                 slots++)
>+                *slots = JSVAL_HOLE;

Nit: for head all on one line, or else brace even a single-line loop body.

/be

Comment 21

[Boris Zbarsky [:bzbarsky]]

Attachment: Additional m-c patch to make this build after the most recent merge

Comment 22

[Boris Zbarsky [:bzbarsky]]

Attachment: 1.9.2 interdiff addressing Jeff and Brendan's comments

Comment 23

[Boris Zbarsky [:bzbarsky]]

Attachment: m-c interdiff addressing review comments

Comment 24

[Boris Zbarsky [:bzbarsky]]

Attachment: 1.9.2 roll-up patch

Comment 25

[Boris Zbarsky [:bzbarsky]]

Attachment: m-c roll-up patch

Comment 26

[Boris Zbarsky [:bzbarsky]]

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

Comment 27

[Mike Shaver (:shaver emeritus)]

Comment on attachment 408311 [details] [diff] [review]
1.9.2 roll-up patch

Not blocking, so if it bounces it stays bounced, but would take for the good canvas win on well-baked patch.

Comment 28

[Mike Shaver (:shaver emeritus)]

Not a blocker, but the patch is (above) approved to land for 1.9.2; please make haste.

Comment 29

[Boris Zbarsky [:bzbarsky]]

Pushed http://hg.mozilla.org/releases/mozilla-1.9.2/rev/721a61ffeb01