438889 - Inefficient Unshift Operation

Status: VERIFIED FIXED

(Tamarin Graveyard :: Virtual Machine, defect)

Description

[Mingqiu Sun]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.8.1.14) Gecko/20080404 Firefox/2.0.0.14
Build Identifier: tamarin-central-228c19321257

The interpreted array unshift operation is very inefficient. For example, it takes tamarin-central many hours to complete the JS-speed/object-array workload. We introduced a helper function in the VM to speed up the unshift operation significantly (250X for JS-speed/object-array, and 8% for sunspider/bitops-bitwise-and).

Reproducible: Always

Steps to Reproduce:
1. run JS speed object-array
2. wait for a day for it to finish
3.
Actual Results:  
perf improvement with the patch:

sunspider\access-binary-trees.as                      47.0    46.0     2.1
sunspider\access-fannkuch.as                         125.0   125.0     0.0
sunspider\access-nbody.as                            171.0   172.0    -0.6
sunspider\access-nsieve.as                            62.0    62.0     0.0
sunspider\bitops-3bit-bits-in-byte.as                 15.0    15.0     0.0
sunspider\bitops-bits-in-byte.as                      15.0    15.0     0.0
sunspider\bitops-bitwise-and.as                      203.0   187.0     7.9
sunspider\bitops-nsieve-bits.as                       46.0    46.0     0.0
sunspider\controlflow-recursive.as                    46.0    46.0     0.0
sunspider\crypto-aes.as                               62.0    62.0     0.0
sunspider\crypto-md5.as                               31.0    31.0     0.0
sunspider\crypto-sha1.as                              31.0    31.0     0.0
sunspider\math-cordic.as                              93.0    93.0     0.0
sunspider\math-partial-sums.as                       203.0   203.0     0.0
sunspider\math-spectral-norm.as                      156.0   156.0     0.0
sunspider\s3d-cube.as                                109.0   109.0     0.0
sunspider\s3d-morph.as                                93.0    93.0     0.0
sunspider\s3d-raytrace.as                            125.0   125.0     0.0
sunspider\string-fasta.as                             93.0    94.0    -1.1
sunspider\string-unpack-code.as                     7609.0  7468.0     1.9
sunspider\string-validate-input.as                    93.0    93.0     0.0

Comment 1

[Mingqiu Sun]

Attachment: Unshift patch

Comment 2

[Werner Sharp]

This is only with the prototype version of unshift.  Why is any code calling that on purpose?  Are some of our performance test cases doing prototype hacking and need to run in the slow mode?   And if so, shouldn’t it be able to just call the native unshift instead of adding a new function…
 
             native AS3 function unshift(...args):uint
+
+              private static native function _unshift(o, args:Array):uint
+
               prototype.unshift = function(...args):uint
               {
+                      if (this is Array) {
+                              return _unshift(this, args); // why can’t we somehow call “native AS3 function unshift”?
+                      }

Comment 3

[Mingqiu Sun]

Interesting. We measured 99% of CPU spent on this prototype method for object-array.js in JS Speed. Can someone at Adobe check why the array.unshift in JavaScript is compiled into this prototype method call? 

Comment 4

[Mingqiu Sun]

Sergey Salishev, who is the primary developer of this feature, has the following comment:

1. The AS3 implementation of unshift is incompatible with the ECMA Script specification. The ECMA Script spec very strictly describes the unshift algorithm and requires it can be applied to any object (array or not). This leads to two different unshift versions for AS3 and ECMA Script. See the comment for unshift.

2. It's hard to factor out the common part of AS3 and ECMA Script unshift routine as in function pop for example, due to different nature of arguments. In case of AS3 unshift it's just a C array of Object pointers, in case of ECMA Script it's a Java Script Array object. I've tried to write the native unshift implementation according to the spec but the code became very bloated. Also due to generic spec on ECMA Script unshift the native version wouldn't be significantly faster than script version.

The current Tamarin Array just follows the spec and provides the generic implementation in script. The only problem is the performance.

The patch factors out the common case and provides the optimized specialization for it, without modifying the generic slow path.

Comment 5

[Steven Johnson]

Comment on attachment 324828 [details] [diff] [review]
Unshift patch

apologies for the belated review. we should land this.

Comment 6

[Steven Johnson]

Actually, before we land this, pondering Werner's comment above and your response...

How is the AS3 implementation incompatible with ECMA, aside from applying only to Array? (If that's the only issue then it seems to be a nonfactor, since the patch is only applying the native call to items of type Array anyway...)

It does seem like we could avoid the new native function and do

prototype.unshift = function(...args):uint
               {
+                      if (this is Array) {
+                              return this.AS3::unshift(args); 
+                      }

?

Comment 7

[Sergey Salishev]

I think reusing AS3 method is the best solution. The semantics is mostly the same, but the type conversion is done by the compiler. The performance of this solution on JS Speed object-array is exactly the same as with the new native function.

Comment 8

[Lars T Hansen]

(In reply to comment #6)
> It does seem like we could avoid the new native function and do
> 
> prototype.unshift = function(...args):uint
>                {
> +                      if (this is Array) {
> +                              return this.AS3::unshift(args); 
> +                      }

I don't think so.  AS3::unshift takes a variable number of arguments; trying to call it on the ...args won't have the desired effect.  You can use apply() but that removes most of the benefit.

I will land this (in some re-integrated form) unless there are further objections.

Comment 9

[Lars T Hansen]

Attachment: revised patch

Patch is updated to conform to current reality but is otherwise unchanged.

Comment 10

[Lars T Hansen]

(And of course the builtins must be rebuilt when this lands.)

Comment 11

[Lars T Hansen]

redux changeset:   1405:731443039a0d

Comment 12

[Chris Peyer]

removing QRB request, bug verified