602366 - Add a JSOP_COPYELEM bytecode

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine, defect)

Description

[Nicholas Nethercote [inactive]]

This idea has come up several times, most recently in bug 598655.  Repeating bug 598655 comment 17:

A GETELEM/SETELEM pair on an initialized dense array,
eg. a[j] = a[i]; involves these steps in trace-generated code (I imagine JM
code must do similar things):

GETELEM
1. load pointer to 'a' from the stack
2. if 'a' is not a dense array, exit
3. if 'i' exceeds the capacity of 'a', exit
4. load the dslots pointer of 'a'
5. compute the address of the dslot for a[i]
6. load a[i]'s tag from the dslot
7. if the tag doesn't match the expected type, exit
8. load a[i]'s payload 
9. unbox the value
10. store the unboxed value on the stack

SETELEM
11. load pointer to 'a' from the stack
12. if 'a' is not a dense array, exit
13. if 'j' exceeds the capacity of 'a', call js_EnsureDenseArrayCapacity()
14. load the dslots pointer of 'a'
15. compute the address of the dslot for a[j]
16. load the a[j]'s existing tag from the dslot
17. if the existing tag is for a hole, call js_Array_dense_setelem_hole
18. box the new value
19. store the boxed value into a[j]'s dslot

Horrid, isn't it?  

Here's what COPYELEM would do:

COPYELEM
1. load pointer to 'a' from the stack
2. if 'a' is not a dense array, exit
3. if 'i' exceeds the capacity of 'a', exit
4. if 'j' exceeds the capacity of 'a', call js_EnsureDenseArrayCapacity()
5. load the dslots pointer of 'a'
6. compute the address of the dslot for a[i]
7. load a[i]'s tag and payload from the dslot
8. compute the address of the dslot for a[j]
9. load a[j]'s existing tag
10. if the existing tag is for a hole, call js_Array_dense_setelem_hole
11. store a[i]'s tag and payload into a[j]'s slot.

So this has the following benefits (for trace-generated code):
- No need to reload 'a' from the stack and test if it's a dense array.
  (The tracer can omit these steps thanks to CSE, but the methodjit
  presumably can't.)

- No need to reload the dslots pointer and recompute the dslots address.
  (The tracer can't CSE those in the GETELEM/SETELEM version because of the
  possibly intervening call to js_EnsureDenseArrayCapacity(), which can
  reallocate dslots.)

- No need to do anything with the gotten value -- type-test it, unbox it, or
  store it to the stack.

So that's quite a bit better, I would guess close to 2x faster.  This
assumes that COPYELEM does not put a copy of the element on the stack;
doing so would negate several of the potential benefits, and it doesn't make
much sense.

One issue would be whether the front-end fuses separate GETELEM/SETELEM
pairs, eg:

  var tmp = a[i];
  a[j] = tmp;

You'd hope so, but I'm not certain, I don't know much about the front-end.
Things can get more complicated if there is code between the GETELEM and the
SETELEM.

Comment 1

[Alon Zakai (:azakai)]

New benchmark code and results in

https://bugzilla.mozilla.org/show_bug.cgi?id=601988#c14
https://bugzilla.mozilla.org/show_bug.cgi?id=601988#c15

appear to be good examples of code that would greatly benefit from a COPYELEM bytecode. In particular the combination of COPYELEM with typed arrays seems very promising for improving performance.

Comment 2

[Nicholas Nethercote [inactive]]

Nb: bug 486802 is a dup of this;  it was marked WONTFIX.  I'm not sure that's the right decision.

Comment 3

[Brendan Eich [:brendan]]

(In reply to comment #2)
> Nb: bug 486802 is a dup of this;  it was marked WONTFIX.  I'm not sure that's
> the right decision.

I was pretty sure at the time that it was premature, and I think you've proved the case.

/be

Comment 4

[Nicholas Nethercote [inactive]]

This might still be a good idea even once TM goes away, but I won't be working on it.

Comment 5

[David Anderson [:dvander] - inactive, e-mail if emergency]

This won't be needed in IM, if we read an untyped value off the heap we don't need to unbox it.