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

RESOLVED FIXED in mozilla21

Status

()

Core
JavaScript Engine
RESOLVED FIXED
6 years ago
5 years ago

People

(Reporter: bhackett, Assigned: bhackett)

Tracking

Other Branch
mozilla21
x86
Mac OS X
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment, 2 obsolete attachments)

(Assignee)

Description

6 years ago
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.
(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.
(Assignee)

Comment 2

6 years ago
(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.
(Assignee)

Comment 3

6 years ago
Created attachment 706204 [details] [diff] [review]
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.
Assignee: general → bhackett1024
(Assignee)

Comment 4

6 years ago
Created attachment 706648 [details] [diff] [review]
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.
Attachment #706204 - Attachment is obsolete: true
Attachment #706648 - Flags: review?(jdemooij)
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?
(Assignee)

Comment 6

6 years ago
(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 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 = ...;
Attachment #706648 - Flags: review?(jdemooij) → review+
(Assignee)

Updated

6 years ago
Depends on: 836138
This is showing possible 4% or so kraken regressions on Mac and WinXP on Tinderbox....
(Assignee)

Comment 10

6 years ago
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

6 years ago
This change seems to have caused Kraken FFT to blow up on 64-bit AWFY.
https://hg.mozilla.org/mozilla-central/rev/d7dd65663469
Status: NEW → RESOLVED
Last Resolved: 6 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla21
(Assignee)

Comment 13

6 years ago
(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).
Note that x86 on Mac is basically an unsupported configuration; the numbers in comment 9 for Mac are of course 64-bit.
Depends on: 836774

Comment 15

6 years ago
(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

6 years ago
(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?
(Assignee)

Comment 17

6 years ago
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

6 years ago
(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.
(Assignee)

Comment 19

6 years ago
(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.
Depends on: 854157
Created attachment 746701 [details] [diff] [review]
Rebase Shu's patch and avoid duplicate code paths
Attachment #706648 - Attachment is obsolete: true
Attachment #746701 - Flags: review?(bhackett1024)
Attachment #746701 - Flags: feedback?(shu)
(Assignee)

Updated

5 years ago
Attachment #706648 - Attachment is obsolete: false
(Assignee)

Comment 21

5 years ago
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
Attachment #746701 - Flags: review?(bhackett1024) → review+
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!
Attachment #746701 - Attachment is obsolete: true
Attachment #746701 - Flags: feedback?(shu)

Comment 23

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

Updated

5 years ago
Depends on: 890524
You need to log in before you can comment on or make changes to this bug.