833898 - Investigate converting mixed arrays of ints and doubles to arrays of doubles

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Brian Hackett [Laid off!]]

TI can't say that a value is definitely a double, but rather that the value may be either an int or a double.  Thus, when loading values from arrays that may be int or double we need to test for an integer and convert it to a double if necessary.  This can be pretty costly, and it would be nice if we could say an array does not contain integers.  A sketch of how this would work:

- An array starts out being assigned a mix of integers and doubles.
- When code is first compiled which accesses the array, and sees that type tests are necessary on loads, loop hoist a fragment of code which eagerly converts integer elements of the array to doubles.  This code can change the object's shape to set a flag indicating the walk has been performed and is no longer necessary.
- Ensure that integers are converted to doubles when assigning to elements of an array that has this flag set.

Allowing unchecked loads for double array elements is important for imaging-gaussian-blur on kraken and probably other kraken tests.

Comment 1

[Luke Wagner [:luke]]

(In reply to Brian Hackett (:bhackett) from comment #0)
> - Ensure that integers are converted to doubles when assigning to elements
> of an array that has this flag set.

Does it make sense to propagate this information into the TypeObject so that new arrays will be eagerly constructed to have the only-contains-doubles shape, thereby avoiding the later O(n) double-conversion pass?  This wouldn't matter for code that created 1 big array and then banged on it a bunch (I'm guessing the kraken test), but I think it would for code that made lots of arrays, working just a little on each.  One way this would be bad is if the TypeObject was too coarse-grained, in which case we'd create arrays-of-only-doubles that didn't need to be.

Comment 2

[Brian Hackett [Laid off!]]

(In reply to Luke Wagner [:luke] from comment #1)
> Does it make sense to propagate this information into the TypeObject so that
> new arrays will be eagerly constructed to have the only-contains-doubles
> shape, thereby avoiding the later O(n) double-conversion pass?  This
> wouldn't matter for code that created 1 big array and then banged on it a
> bunch (I'm guessing the kraken test), but I think it would for code that
> made lots of arrays, working just a little on each.  One way this would be
> bad is if the TypeObject was too coarse-grained, in which case we'd create
> arrays-of-only-doubles that didn't need to be.

Potentially, yeah.  I think any time we created a type object whose element types are int|double we should do this eagerly, but more investigation is definitely needed.

Comment 3

[Brian Hackett [Laid off!]]

Attachment: WIP

WIP.  Works on small examples and on the kraken test in question (imaging-gaussian-blur).  On that test, this improves our score from 248 to 190 (v8 is 182).  Still some miscellaneous stuff to fix, and performance testing at a broader level.

Comment 4

[Brian Hackett [Laid off!]]

Attachment: patch

Patch.  This improves our kraken score by 3.5% on my machine (2469 -> 2385, x86/darwin), mostly in imaging-gaussian-blur and audio-dft.

Comment 5

[Jan de Mooij [:jandem]]

The baseline compiler will have to guard on ObjectElements::convertDoubleElements in its SETELEM IC. Can we make the shape determine this flag so that we don't need a separate branch?

Comment 6

[Brian Hackett [Laid off!]]

(In reply to Jan de Mooij [:jandem] from comment #5)
> The baseline compiler will have to guard on
> ObjectElements::convertDoubleElements in its SETELEM IC. Can we make the
> shape determine this flag so that we don't need a separate branch?

I originally started this patch by adding a new base shape flag that indicates the object needs int elements converted to doubles.  I abandoned that approach because the consequences for Ion optimization were unappealing.  For this to have any benefit we need to be able to consolidate or loop hoist the is-double-array test, and if that test can modify the object's shape then there are two approaches that could be taken.

- Specify the possible shape modification in MConvertElementsToDoubles.  This causes the instruction to become a store, and I do not believe we ever move store instructions currently.  Working through the consequences wrt the alias analysis and analysis passes of allowing stores to be moved seems hard and error prone.

- Lie, and pretend that MConvertElementsToDoubles doesn't modify the object's shape.  This instruction already lies and pretends it doesn't modify the elements, for reasons explained in the patch, but I don't think a similar argument can be made for the shape.  This can make MGuardShape behave differently depending on which order it executes wrt MConvertElementsToDoubles, and could lead to weird behavior down the road with potential future optimizations --- e.g. inlining monomorphic addprop (as do for getprop and setprop) could end up accidentally clearing the known-doubles flag.

As things stand I don't think the second option would be horrible, but I'd kind of like to know what the actual performance impact of the extra branches on the baseline/ion stack would be.

Comment 7

[Jan de Mooij [:jandem]]

Comment on attachment 706648 [details] [diff] [review]
patch

Review of attachment 706648 [details] [diff] [review]:
-----------------------------------------------------------------

Cool, r=me with comments addressed. Does this affect v8-navier-stokes? I think it was added to v8bench after v8 added double arrays.

Would you mind adding a testcase that likely fails with the baseline compiler? E.g. pass an array with the convertDoubles flag set to a function with a SETELEM and a try..catch (so that Ion won't compile it).

::: js/src/ion/IonBuilder.cpp
@@ +5318,5 @@
> +    // the array has been converted to homogenous doubles first.
> +    bool loadDouble = !barrier && oracle->elementReadShouldAlwaysLoadDoubles(script(), pc);
> +    if (loadDouble) {
> +        JS_ASSERT(!maybeUndefined && !needsHoleCheck && knownType == JSVAL_TYPE_DOUBLE);
> +        elements = addConvertElementsToDoubles(elements);

Would it make sense to do this only in loops, to avoid converting to doubles in cases where it likely won't help or will make us slower?

::: js/src/ion/MIR.h
@@ +3475,5 @@
> +        // property is ensured by chaining this instruction with the elements
> +        // themselves, in the same manner as MBoundsCheck.
> +        return AliasSet::None();
> +    }
> +    bool fallible() {

Nit: remove this method

::: js/src/ion/x64/CodeGenerator-x64.cpp
@@ +251,5 @@
>      Operand source = createArrayElementOperand(ToRegister(load->elements()), load->index());
> +
> +    if (load->mir()->loadDoubles()) {
> +        if (source.kind() == Operand::REG_DISP)
> +            masm.loadDouble(source.toAddress(), fpreg);

FloatRegister fpreg = ...;

Comment 8

[Brian Hackett [Laid off!]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/d7dd65663469

Comment 9

[Boris Zbarsky [:bzbarsky]]

This is showing possible 4% or so kraken regressions on Mac and WinXP on Tinderbox....

Comment 10

[Brian Hackett [Laid off!]]

On my machine and on AWFY this was a 4% kraken improvement.  I don't really have any interest anymore in investigating tinderbox "regressions".

Comment 11

[Paul Wright]

This change seems to have caused Kraken FFT to blow up on 64-bit AWFY.

Comment 12

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/d7dd65663469

Comment 13

[Brian Hackett [Laid off!]]

(In reply to Paul Wright from comment #11)
> This change seems to have caused Kraken FFT to blow up on 64-bit AWFY.

Interesting, will look at this later.  On x86 this patch and bug 836138 improved our score on this test by 50% (132 -> 89).

Comment 14

[Boris Zbarsky [:bzbarsky]]

Note that x86 on Mac is basically an unsupported configuration; the numbers in comment 9 for Mac are of course 64-bit.

Comment 15

[Paul Wright]

(In reply to Brian Hackett (:bhackett) from comment #13)
> (In reply to Paul Wright from comment #11)
> > This change seems to have caused Kraken FFT to blow up on 64-bit AWFY.
> 
> Interesting, will look at this later.  On x86 this patch and bug 836138
> improved our score on this test by 50% (132 -> 89).

Had a chance to take a look at this?

Comment 16

[Paul Wright]

(In reply to Boris Zbarsky (:bz) from comment #14)
> Note that x86 on Mac is basically an unsupported configuration; the numbers
> in comment 9 for Mac are of course 64-bit.

I'm curious... If x86 on Mac is basically unsupported, yet x86 is the primary architecture of the userbase (so I've been told), why is AWFY based on MacOS and not the actual OS we seem to care about (presumably Windows)?  Would it not make sense to better align the tests and testing platforms with what the truly supported and targeted platforms are?  Does it make a difference?

Comment 17

[Brian Hackett [Laid off!]]

The OS doesn't (or shouldn't) matter.  The JS engine interacts little with the underlying system, so the main differences will be in things like how well the OS services page faults and differences between the compilers used.  These should be minor, and the latter matters even less nowadays since benchmark perf is most dependent on jitcode.

Comment 18

[Paul Wright]

(In reply to Brian Hackett (:bhackett) from comment #13)
> (In reply to Paul Wright from comment #11)
> > This change seems to have caused Kraken FFT to blow up on 64-bit AWFY.
> 
> Interesting, will look at this later.  On x86 this patch and bug 836138
> improved our score on this test by 50% (132 -> 89).

Did you get a chance to look at this?  Thanks.

Comment 19

[Brian Hackett [Laid off!]]

(In reply to Paul Wright from comment #18)
> Did you get a chance to look at this?  Thanks.

I'll look into this pretty soon, but for at least the next week or so my focus will be on the baseline compiler.

Comment 20

[Niko Matsakis [:nmatsakis]]

Attachment: Rebase Shu's patch and avoid duplicate code paths

Comment 21

[Brian Hackett [Laid off!]]

Comment on attachment 746701 [details] [diff] [review]
Rebase Shu's patch and avoid duplicate code paths

Review of attachment 746701 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/ion/IonBuilder.cpp
@@ +6512,5 @@
> +        writeOutOfBounds)
> +    {
> +        // If the current PC is a call to UnsafeSetElement, then arrayWriteHole
> +        // should always be false.
> +        JS_ASSERT(safety != SetElem_UnsafeSet);

This assert is implied by the test on |safety| in the 'if' just above.

::: js/src/ion/IonBuilder.h
@@ +32,5 @@
>      };
>  
> +    enum SetElemSafety {
> +        // Normal write like a[b] = c.
> +        SetElem_NormalSet,

Maybe SetElem_Normal instead?

@@ +37,5 @@
> +
> +        // Write due to UnsafeSetElement:
> +        // - assumed to be in bounds,
> +        // - not checked for data races
> +        SetElem_UnsafeSet,

Ditto for SetElem_Unsafe

Comment 22

[Niko Matsakis [:nmatsakis]]

Comment on attachment 746701 [details] [diff] [review]
Rebase Shu's patch and avoid duplicate code paths

Argh. I just realized I atttached this patch to the wrong bug!

Comment 23

[Paul Wright]

Is there still a valid concern regarding comment 11, or are we comfortable with this as-is?