Chromium Code Reviews
Help | Chromium Project | Sign in
(236)

Issue 11365189: Optimizing the loop algorithm for Array.prototype.map. (Closed)

Can't Edit
Can't Publish+Mail
Start Review
Created:
1 year, 5 months ago by mattrobenolt
Modified:
1 year, 5 months ago
Reviewers:
mads.s.ager, Sven Panne, rossberg, Yang
CC:
v8-dev_googlegroups.com
Visibility:
Public.

Description

Optimizing the loop algorithm for Array.prototype.map.

The current version yields an O(n^2) algorithm because on each iteration of the loop,
it's also checking "i in array", which itself, scans the whole array.
This was changed by substituting the "in" call in favor of !IS_UNDEFINED
to keep a linear time loop.

General test run showing the performance issue: http://jsperf.com/loop-vs-map/3

Patch Set 1 #

Total comments: 1
Unified diffs Side-by-side diffs Delta from patch set Stats (+5 lines, -4 lines) Lint Patch
M AUTHORS View 1 chunk +1 line, -0 lines 0 comments 0 errors Download
M src/array.js View 2 chunks +4 lines, -4 lines 1 comment 0 errors Download
Trybot results:
Commit:

Messages

Total messages: 11
mattrobenolt
1 year, 5 months ago #1
Sven Panne
https://codereview.chromium.org/11365189/diff/1/src/array.js File src/array.js (right): https://codereview.chromium.org/11365189/diff/1/src/array.js#newcode1243 src/array.js:1243: if (!IS_UNDEFINED(element)) { Quick drive-by-comment: I think that this ...
1 year, 5 months ago #2
mattrobenolt
The only scenario I could come up with where the behavior changes is when explicitly ...
1 year, 5 months ago #3
mattrobenolt
Disregard that. This is a problem with the difference between a variable being "undefined" vs ...
1 year, 5 months ago #4
Sven Panne
On 2012/11/11 17:08:30, mattrobenolt wrote: > Disregard that. This is a problem with the difference ...
1 year, 5 months ago #5
rossberg
On 2012/11/12 08:06:50, Sven Panne wrote: > On 2012/11/11 17:08:30, mattrobenolt wrote: > > Disregard ...
1 year, 5 months ago #6
rossberg
On 2012/11/12 10:51:03, rossberg wrote: > But yes, you might wonder why the red version ...
1 year, 5 months ago #7
mattrobenolt
Thanks for your feedback. :) Are there any ways that this can be optimized specifically ...
1 year, 5 months ago #8
rossberg
On 2012/11/12 18:06:03, mattrobenolt wrote: > Are there any ways that this can be optimized ...
1 year, 5 months ago #9
mattrobenolt
Wow, that's terrible. So because of all of this, the conclusion is that as a ...
1 year, 5 months ago #10
rossberg
1 year, 5 months ago #11
On 2012/11/13 15:30:22, mattrobenolt wrote:
> Wow, that's terrible.
> 
> So because of all of this, the conclusion is that as a developer, they should
> avoid using map() if they care about performance.

The "premature optimisation is the root of all evil" mantra still applies,
though. In particular, the relevance of micro benchmarks like those seen on
jsperf often is vastly overestimated.

> And that's a shame, because map() is a beautiful syntax for a lot of things.
> 
> I almost want a proposed "fastMap()" or something that says, "Yeah, we don't
> care about the insanity checks, I know what I'm doing!". But that's more than
> likely not going to work. ;)

What they should have done is defining map and friends not to filter holes.
Sign in to reply to this message.

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld 1280:2d3e6564b7b6