609896 - array_concat should be using a fast path for dense arrays

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Boris Zbarsky [:bzbarsky]]

Copying via memcpy instead of GetArrayElement/SetArrayElement, say!

Comment 1

[Paul Biggar]

I'll take this. I'm doing similar stuff in bug 581180.

Comment 2

[Luke Wagner [:luke]]

I don't think you can quite do memcpy (holes in dense arrays...).

Paul: I just added a GetElements() function in jsarray.cpp that I think could be reused here.

Comment 3

[Paul Biggar]

(In reply to comment #2)
> Paul: I just added a GetElements() function in jsarray.cpp that I think could
> be reused here.

Yes, looks like it. Aside: what a curious name you chose. It's called 'Get' but it actually copies into its 4th parameter...

Comment 4

[Luke Wagner [:luke]]

Yes, it's the vector form of GetElement, which takes a scalar Value outparam.

Comment 5

[Boris Zbarsky [:bzbarsky]]

Hmm.  Why can one not memcpy holes, exactly?

Comment 6

[Luke Wagner [:luke]]

(In reply to comment #5)

js> Array.prototype['3'] = "surprise"
"surprise"
js> ["hi"].concat([1,2,3,,5])
["hi", 1, 2, 3, "surprise", 5]

Comment 7

[Boris Zbarsky [:bzbarsky]]

We should just check obj->isDenseArray() && !js_PrototypeHasIndexedProperties(cx, obj) to handle that.

Might also need some sort of check on how length compares to capacity; other array functions have those.

Comment 8

[Luke Wagner [:luke]]

Awesome.  Can the js_PrototypeHasIndexProperties optimization can be put in GetElements (which is hot in, e.g., v8-raytrace)?

Comment 9

[Boris Zbarsky [:bzbarsky]]

GetElements doesn't seem to get holes off the proto.  Am I missing something?

Comment 10

[Luke Wagner [:luke]]

You are correct sir!  This is a regression, will file.

Comment 11

[Paul Biggar]

Luke, did you file this? I can't find it.

Comment 12

[Luke Wagner [:luke]]

bug 610038

Comment 13

[Paul Biggar]

This is nasty code with nasty edge cases, but it would look much nicer once we have Lua-style arrays, so waiting til after that.

Comment 14

[Terrence Cole [:terrence]]

Attachment: Micro-benchmark for array concat performance.

Comment 15

[Terrence Cole [:terrence]]

Attachment: Optimize array concat for dense arrays.

This ~doubles the perf on the attached benchmark and exposes a bug.  Go read 698140 if you want to know more.

Comment 16

[Jan de Mooij [:jandem]]

Terrence, can we land your patch? I'd love to have this in for bug 609835.

It probably needs a number of changes though, for instance passing obj->getDenseElements() to InitArrayElements will make GGC unhappy.

Comment 17

[Terrence Cole [:terrence]]

Yes, absolutely! I must have forgotten about this, let me rebase it.

Comment 18

[Terrence Cole [:terrence]]

Attachment: array_concat_dense_fastpath-v1.diff

With a clang3.3 opt build on the attached micro-benchmark:
  before: 6.53s
  after:  1.48s

Comment 19

[Terrence Cole [:terrence]]

(In reply to Jan de Mooij [:jandem] from comment #16)
> Terrence, can we land your patch? I'd love to have this in for bug 609835.
> 
> It probably needs a number of changes though, for instance passing
> obj->getDenseElements() to InitArrayElements will make GGC unhappy.

Oh, this isn't going to be unsafe: the actual memcpy has been gone for awhile now. The dense->dense path loops over elements and calls HeapSlot::set or init on each element. Now that I think about it, we should easily be able to hoist the barriers here and restore the memcpy. I'll test and whip up a patch.

Comment 20

[Terrence Cole [:terrence]]

Attachment: opt_copy_init_dense_elems-v0.diff

Without ggc, this is not a significant savings. With ggc our time goes from 1.8s to 1.6s.

Comment 21

[Jeff Walden [:Waldo]]

Comment on attachment 809360 [details] [diff] [review]
array_concat_dense_fastpath-v1.diff

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

This looks the same as the patch in bug 688852, no?  Same issues as there.

Comment 22

[Terrence Cole [:terrence]]

Comment on attachment 810177 [details] [diff] [review]
opt_copy_init_dense_elems-v0.diff

https://hg.mozilla.org/integration/mozilla-inbound/rev/2bbafd515595

Comment 23

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/2bbafd515595

Comment 24

[Chris Peterson [:cpeterson]]

Terrence: did you intend to leave this bug open after you landed opt_copy_init_dense_elems-v0.diff?

Comment 25

[Terrence Cole [:terrence]]

Yeah, I don't think there's more that needs to be done here unless we have some new test case.