Closed Bug 394448 Opened 17 years ago Closed 17 years ago

Array.shift() performance

Categories

(Core :: JavaScript Engine, defect)

x86
Linux
defect
Not set
minor

Tracking

()

RESOLVED DUPLICATE of bug 322889

People

(Reporter: victor.grishchenko, Unassigned)

Details

(Keywords: perf)

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.
Keywords: perf
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.
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).
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.
Yes, the spec applies in general, but specific |this| types could be optimized.

/be
Status: UNCONFIRMED → NEW
Ever confirmed: true
I've checked the spec and, as I see, array.reverse() then array.pop() is a perfect O(N) workaround, so WONTFIX is OK.
Status: NEW → RESOLVED
Closed: 17 years ago
Resolution: --- → WONTFIX
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
Status: RESOLVED → REOPENED
Resolution: WONTFIX → ---
(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.
Thanks for the bug pointer.

/be
Status: REOPENED → RESOLVED
Closed: 17 years ago17 years ago
Resolution: --- → DUPLICATE
You need to log in before you can comment on or make changes to this bug.