394448 - Array.shift() performance

Status: RESOLVED DUPLICATE of bug 322889

(Core :: JavaScript Engine, defect)

Description

[Victor]

User-Agent:       Mozilla/5.0 (X11; U; Linux i686 (x86_64); ru; rv:1.8.1.5) Gecko/20061023 SUSE/2.0.0.5-1.1 Firefox/2.0.0.5
Build Identifier: Mozilla/5.0 (X11; U; Linux i686 (x86_64); ru; rv:1.8.1.5) Gecko/20061023 SUSE/2.0.0.5-1.1 Firefox/2.0.0.5

Hi!
It looks like Array.shift() was not optimized for performance. Of course, there is an obvious workaround: an array might be easily iterated using indexes. But anyway, I did not expect shift() to be a performance killer.
My javascript iterates several thousand lines of text, parses every line with a regex and puts the result into an object. Using shift-iteration, it works for >3sec, using for-iteration it works <0.5sec.

Reproducible: Always

Steps to Reproduce:
1. get a 10000-line file by XmlHttpRequest
2. split('\n') it, then iterate/empty the array using shift()
3. performance is not very good
Actual Results:  
It works for several seconds.

Expected Results:  
Must be faster.

Comment 1

[Jeff Walden [:Waldo]]

Array.prototype.shift can probably be made somewhat faster, but to be completely honest, it's never going to be as efficient as you wish.  The specification says that the function returns this[0] and shifts every element or hole down an index.  The specification requires that [[Get]] and [[Put]] be called for each element in this, holes not included, so the time complexity of shifting elements off the front of the array to iterate over the array is quadratic.  We can't do something clever like keep the array as a vector and increment a start-index to shift off an element, because that doesn't do the [[Get]]/[[Put]] calls, and they're the cost of the method.

If we care about preserving spec compatibility (I presume we do), then for the purposes of this bug's request this must be WONTFIX.  We can do nothing about the quadratic complexity of repeated shifts if we follow the spec.

Comment 2

[Blake Kaplan (:mrbkap) (inactive)]

We have to follow the spec here, it allows one to use objects that aren't arrays with Array.prototype.shift (the object only has to have a 'length' attribute and numbered elements 0..length - 1).

Comment 3

[Jesse Ruderman]

Can't we check whether the object is an array and whether it has any special getters/setters?  Seems like it should be possible to optimize the common case.  I don't know if it's worth it, though.

Comment 4

[Brendan Eich [:brendan]]

Yes, the spec applies in general, but specific |this| types could be optimized.

/be

Comment 5

[Victor]

I've checked the spec and, as I see, array.reverse() then array.pop() is a perfect O(N) workaround, so WONTFIX is OK.

Comment 6

[Brendan Eich [:brendan]]

I think we should optimize native arrays, if it can be done without too much code. The spec is describing generic method behavior, not bounding big-O complexity on the low end.

/be

Comment 7

[Igor Bukanov]

(In reply to comment #6)
> I think we should optimize native arrays, if it can be done without too much
> code.

There are two issues here. 

The first is to optimize access to array elements when the array is native one. Clearly this could be done but then we have already bug 322889 for that.

The second issue is to make shift performance O(1), not O(N), for native arrays. I suggest WONTFIX here to emphasis that for 0-based array shift is equivalent to moving the elements from the tail to the start.

Overall this bug should be a dup of bug 322889.

Comment 8

[Brendan Eich [:brendan]]

Thanks for the bug pointer.

/be