Performance Optimization of Arrays - Part I

re: Performance Optimization of Arrays - Part I

Sebastian Werner — Wed, 26 Mar 2008 09:51:16 GMT

That's really interesting. We already thought that you have implemented it this way in the old engine.

Would be great if IE8 would also allow to extending (inheriting) from arrays using the normal prototype chain:

function QxArray() {

Array.prototype.call(this);

}

QxArray.prototype = new Array;

This still seems not to be possible. This works in all other browsers. Please have a look at this as well.

re: Performance Optimization of Arrays - Part I

Dave — Wed, 26 Mar 2008 15:31:08 GMT

Great work! This will definitely improve performance. Like Sebastian, I would like to see it be possible to extend Array. Right now, that seems to break because of issues with the .length property.

re: Performance Optimization of Arrays - Part I

Hold your Horses — Wed, 26 Mar 2008 16:23:05 GMT

Woah! that was definately messed up!

But as Sebastian questions...

Can I prototype on the JavaScript Array Object or not? If not, GO BACK TO THE DRAWING BOARD!

Otherwise, thanks for the performance improvement, it is much appreciated.

re: Performance Optimization of Arrays - Part I

TNO — Wed, 26 Mar 2008 21:53:12 GMT

Out of curiosity, why didn't you use the array literal? []

re: Performance Optimization of Arrays - Part I

Jaiprakash — Fri, 28 Mar 2008 16:27:11 GMT

Sebastian, Dave - Thanks for pointing out the issue with inheriting from Array.prototype scenarios.

TNO - There is no specific reason for not using array literals, I just started with new Array() and continued with it for consistency. The fix works for all array objects, no matter how they are declared in code.

- JP

ECMAScript doesn't make an array dense just because you specify a length in the Array constructor

liorean — Tue, 08 Apr 2008 18:08:57 GMT

Is this safe though? For something like "var a=new Array(0xffffffff),a[0xfffffffe]=0xfffffffe;" I really hope you're not allocating a true array of 2^32 elements.

Oh, and not really on topic but still related, you have a set of bugs in those functions that extend the array in IE8b1 and earlier. I'll show you the case of Array.prototype.push, but you have analogous bugs in the other array functions:

----<example>----

var

a=[0,1,2,3],

b=[],

i=0xfffffffd;

a[i]=i++;

try{

alert('Initial length: '+a.length);

alert('a.push returns: '+a.push(i++,i++,i++));

}catch(err){

alert('ERROR:\n\n Name: '+err.name+'\n\n Description: '+err.description+'\n\n Message: '+err.message+'\n\n Number: '+err.number);

}finally{

for(i in a)

b.push(i+': '+a[i]);

b.push('length: '+a.length);

alert(b.join('\n'));

}

----</example>----

----<IE8b1 results>----

- "Initial length:4294967294"

- "a.push returns: 1"

- No RangeError!

- Array members listed in the finally clause:

0: 4294967296

-2: 4294967294

-1: 4294967295

length: 1

----</IE8b1 results>----

----<Correct results>----

- "Initial length: 4294967294"

- RangeError

- a.push doesn't return, it throws a RangeError

- Array members listed in the finally clause:

0: 0

1: 1

2: 2

3: 3

4294967293: 4294967293

4294967294: 4294967294

4294967295: 4294967295

4294967296: 4294967296

length: 4294967295

----</Correct results>----

Why is that the correct behaviour? Well, the relevant pieces of the ECMAScript spec are "15.4.4.7 Array.prototype.push", "9.6 ToUint32" and "15.4.5.1 [[Put]]".

In step 2 in the algorithm of 15.4.4.7 the variable n is set to the result of calling ToUint32 with the length of the array as argument. This is the only time the length is read out in that algorithm. The type of the variable n is not specified here.

In step 4 in the algorithm of 9.6 the variable k is specified to be of Number type. The result of ToUint32 is thus a uint32 value stored in a Number (double precision floating point) type and not a uint32 type.

In step 5 in the algorithm of 15.4.4.7 the variable n is increased by 1. Since n is a Number and not a uint32 type, this means n may contain values of 2^32 or larger.

In step 4 in the algorithm of 15.4.4.7 a property with the name gotten from ToString(n) is assigned the value of the respective argument.

In step 7 in the algorithm of 15.4.4.7 [[put]] is called with "length" and the value of n.

In step 13 in the algorithm of 15.4.5.1 the value to set is compared to the result of calling ToUint32 on that value. If not equal, a RangeError should here be thrown.

Applied to the example, this is what should happen:

00. a.length is 4294967294 (2^32-2)

01. a.push is called

02. n is set to ToUint32(length)

03. The property a[n] is set to 4294967294

04. n is an array index thus a.length is set to n+1 = 4294967295 (2^32-1, which is maximum value for the length)

05. n is increased to 4294967295

06. The property a[n] is set to 4294967295

07. n is increased to 4294967296 (2^32, one larger than maximum length)

08. The property a[n] is set to 4294967296

09. n is increased to 4294967297 (2^32+1, two larger than maximum length)

10. [[put]] is called with "length" and n as arguments.

11. [[put]] compares 4294967297 to ToUint32(4294967297)=1 and finds they are not equal, and throws a RangeError

Relevant spec text (ECMA262-3ed):

----

15.4.4.7 Array.prototype.push ( [ item1 [ , item2 [ , … ] ] ] )

The arguments are appended to the end of the array, in the order in which they appear. The new length of the array is returned as the result of the call.

When the push method is called with zero or more arguments item1, item2, etc., the following steps are taken:

1. Call the [[Get]] method of this object with argument "length".

2. Let n be the result of calling ToUint32(Result(1)).

3. Get the next argument in the argument list; if there are no more arguments, go to step 7.

4. Call the [[Put]] method of this object with arguments ToString(n) and Result(3).

5. Increase n by 1.

6. Go to step 3.

7. Call the [[Put]] method of this object with arguments "length" and n.

8. Return n.

The length property of the push method is 1.

NOTE

The push function is intentionally generic; it does not require that its this value be an Array object.

Therefore it can be transferred to other kinds of objects for use as a method. Whether the push function can be applied successfully to a host object is implementation-dependent.

----

9.6 ToUint32: (Unsigned 32 Bit Integer)

The operator ToUint32 converts its argument to one of 2^32 integer values in the range 0 through 2^32−1, inclusive. This operator functions as follows:

1. Call ToNumber on the input argument.

2. If Result(1) is NaN, +0, −0, +∞, or −∞, return +0.

3. Compute sign(Result(1)) * floor(abs(Result(1))).

4. Compute Result(3) modulo 2^32; that is, a finite integer value k of Number type with positive sign and less than 2^32 in magnitude such the mathematical difference of Result(3) and k is mathematically an integer multiple of 2^32.

5. Return Result(4).

NOTE

Given the above definition of ToUInt32:

Step 5 is the only difference between ToUint32 and ToInt32.

The ToUint32 operation is idempotent: if applied to a result that it produced, the second application leaves that value unchanged.

ToUint32(ToInt32(x)) is equal to ToUint32(x) for all values of x. (It is to preserve this latter property that +∞ and −∞ are mapped to +0.)

ToUint32 maps −0 to +0.

----

15.4.5.1 [[Put]] (P, V)

Array objects use a variation of the [[Put]] method used for other native ECMAScript objects (8.6.2.2).

Assume A is an Array object and P is a string.

When the [[Put]] method of A is called with property P and value V, the following steps are taken:

1. Call the [[CanPut]] method of A with name P.

2. If Result(1) is false, return.

3. If A doesn’t have a property with name P, go to step 7.

4. If P is "length", go to step 12.

5. Set the value of property P of A to V.

6. Go to step 8.

7. Create a property with name P, set its value to V and give it empty attributes.

8. If P is not an array index, return.

9. If ToUint32(P) is less than the value of the length property of A, then return.

10. Change (or set) the value of the length property of A to ToUint32(P)+1.

11. Return.

12. Compute ToUint32(V).

13. If Result(12) is not equal to ToNumber(V), throw a RangeError exception.

14. For every integer k that is less than the value of the length property of A but not less than Result(12), if A itself has a property (not an inherited property) named ToString(k), then delete that property.

15. Set the value of property P of A to Result(12).

16. Return.

Performance Optimization of Arrays - Part II

JScript Blog — Wed, 09 Apr 2008 08:20:12 GMT

Hello Friends, Hope you have read part I of this topic which I posted few days ago. If not then I would

re: Performance Optimization of Arrays - Part I

Jaiprakash — Wed, 09 Apr 2008 08:31:32 GMT

@liorean - No we don’t allocate memory for elements upfront. It is allocated only when indexes are actually populated.

And many thanks for reporting the bug and writing such a detailed explanation.

-JP

Interesting Finds: 2008.04.24

gOODiDEA.NET — Thu, 24 Apr 2008 05:44:08 GMT

.NET Video: Write Your First Silverlight Game Increasing the Size of your Stack Web CSS 真的可以浮动么？ xUnit

Interesting Finds: 2008.04.24

gOODiDEA — Thu, 24 Apr 2008 05:45:29 GMT

.NETVideo:WriteYourFirstSilverlightGameIncreasingtheSizeofyourStackWebCSS真的可以浮动么...

re: Performance Optimization of Arrays - Part I

Darryl — Tue, 03 Jun 2008 16:34:14 GMT

I'm using JScript 5.7.5730 as a server-side language in a classic-ASP-like environment, and I'm a little confused.

You talk about arrays "now" and arrays "before", and the difference appears to be based on IE7/8. But what are the real version numbers?

Do I in 5.7.5730 have the new array handling?

Thanks,

Darryl.

re: Performance Optimization of Arrays - Part I

JSBlog — Tue, 03 Jun 2008 17:30:55 GMT

Sorry if I was not clear. As of today, the only way to get these fixes on your box is to install IE8 Beta1 from http://www.microsoft.com/windows/products/winfamily/ie/ie8/readiness/Install.htm.

The 5.7.0.5730 is I think IE7, and will not have these fixes.

- JP [MSFT]

re: Performance Optimization of Arrays - Part I

Dan Breslau — Tue, 01 Dec 2009 15:51:53 GMT

Sorry for coming in late; I know that by now your team is working on finishing up IE9.

I've been looking into array performance, and I found something that I think is interesting: Passing the array's size into the array constructor does improve the performance for indexed entries in the array (as you described). But it doesn't help when looking up undefined values -- that is, elements that aren't currently indexed in the array. In fact, compared to arrays where the size *isn't* passed into the constructor, it seems there's even a *penalty* for looking up undefined values. Of course, I don't know how this is implemented, but that penalty isn't what I'd expect; is it a bug?

For details, see http://www.outofwhatbox.com/blog/2009/12/javascript-array-performance-and-why-it-matters/

I'd be glad to send you the raw data if it would be helpful.