978077 - 2D TypedObject arrays much slower than 1D arrays due to intermediate allocations

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Lars T Hansen [:lth]]

A program that convolves an image is an order of magnitude faster if it uses 1D TypedObject arrays to simulate a 2D array than if it uses 2D TypedObject arrays (2.6s vs 30s for 100 iterations on my system).  The reason for the discrepancy is (likely) boxing of intermediate results: when a[h][w] is evaluated, an intermediate object is created for a[h].

JS shell, release build, 64-bit.

Numbers to back this up: Running with MOZ_GCTIMER=file.txt, the log reveals about 9GB of allocation for the 100 iterations.  The image is 640x600, and each array element is evaluated nine times.  This works out to about 39 bytes per element, which is a credible object size for the intermediate result (four or five words).

Comment 1

[Lars T Hansen [:lth]]

Attachment: 1D benchmark

Comment 2

[Lars T Hansen [:lth]]

Attachment: 2D benchmark

Comment 3

[Lars T Hansen [:lth]]

Attachment: Input file

Comment 4

[Lars T Hansen [:lth]]

From nmatsakis on IRC:

they used to be fast ;) but I think that as part of bug 898356 I may have introduced a perf hit
in particular, we used to optimize away all intermediate objects,
but I think because we now check for nullability,
that is, neutering of a buffer due to sending to another thread,
we introduce fallibility,
and the temporary wrappers get introduced for bailout recovery
fixing this is a bit tricky but doable
(to clarify: when you write x[1][2], there is an intermediate object introduced for x[1])
(we used to optimize this object away entirely, but I suspect we no longer do)

Comment 5

[Lars T Hansen [:lth]]

Observation: when the call to Math.max() is replaced by calls to a straightforward local max() function, the running time drops from 29s to 1.5s.  It looks like perhaps the call to Math.max() causes some sort of deoptimization / pessimization that forces an intermediate allocation.  Without the call to Math.max, there is hardly any allocation/GC.

Comment 6

[Lars T Hansen [:lth]]

Re the last comment, the performance cliff is particularly ironic because by the time Math.max() is called, all the intermediate objects but one will be dead.  Thus if we're able to optimize out intermediate objects for the max() case we ought - somewhat reasonably - to be able to do almost as well for the Math.max() case.

Comment 7

[Lars T Hansen [:lth]]

Attachment: 1D benchmark

Comment 8

[Lars T Hansen [:lth]]

Attachment: 2D benchmark

Comment 9

[Lars T Hansen [:lth]]

Perhaps related, though probably not: in the 1D case, using Math.max() instead of the hand-written max() doubles the running time of the benchmark.

Comment 10

[Hannes Verschore [:h4writer]]

Did some detective work. And it is indeed correct that Math.max() will be much slower than using the self-made max function. The reason is that the input types to Math.max() are integer and double, but we see only integer as output to Math.max(). (e.g. Math.max(0.4, 100)). In that case we don't shortcut Math.max to use MMinMax and use a full call, which is much slower than doing the self-made max function that gets inlined. (This is due to former TI restrictions).

I think we now can just remove that extra condition and always inline. I already tried this and noticed something odd afterwards. So need to investigate further. I will try to come back on this towards the end of the week.

Comment 11

[Hannes Verschore [:h4writer]]

Attachment: Patch

Like said before, we don't need to update TI accordingly anymore. So we can inline math.max when outputtype is integer and there is an input type double. By default generate a double minmax, since using an integer minmax will add ToInteger to the double argument, letting us bail.

Without patch, Math.max: infinity ms
Without patch, max5(): 990ms
With patch, Math.max: 604ms

Comment 12

[Tom S [:evilpie]]

Sorry, I don't really understand what changed with TI so this is allowed. Can you please ask somebody else. :(

Comment 13

[Hannes Verschore [:h4writer]]

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

Comment 14

[Carsten Book [:Tomcat]]

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