[Webkit-unassigned] [Bug 209176] New: Array.prototype.shift() has O(N) perf for dense Arrays
bugzilla-daemon at webkit.org
bugzilla-daemon at webkit.org
Tue Mar 17 06:36:41 PDT 2020
https://bugs.webkit.org/show_bug.cgi?id=209176
Bug ID: 209176
Summary: Array.prototype.shift() has O(N) perf for dense Arrays
Product: WebKit
Version: Safari Technology Preview
Hardware: Unspecified
OS: Unspecified
Status: NEW
Severity: Normal
Priority: P2
Component: JavaScriptCore
Assignee: webkit-unassigned at lists.webkit.org
Reporter: org.webkit at py.gy
While the spec mandates Array.prototype.shift() to be generic, and that for the generic case, O(N) operations are necessary, this is not the case for plain Arrays, especially if they are dense (no idea what goes under the hood for arrays with holesin JSC).
For dense arrays, once can bump the array pointer, decrement the length and call it a day in O(1).
SpiderMonkey and V8 actually do this, the perf of myArray.shift() is identical to myArray.pop(), whereas in JSC the latter takes O(N) time:
a.slice().shift()
takes twice the time of
a.slice().pop()
Observed in Safari 13 and Safari TP on MacOS Mojave. Test here: https://jsperf.com/shiftcorn/1
It would be nice if the common case of dense arrays was optimized in Safari.
----
Aside, I've tried to get the three latest Mojave Build Archives to run to no avail (258541, 258543 and 258545); this may be a local problem on my machine, I also have periodic Core Audio crashes.
Setting DYLD FRAMEWORK and LIBRARY paths to /Users/pygy/Downloads/258545/Release
dyld: lazy symbol binding failed: Symbol not found: _WKContextConfigurationSetShouldCaptureAudioInUIProcess
Referenced from: /System/Library/StagedFrameworks/Safari/Safari.framework/Versions/A/Safari
Expected in: /Users/pygy/Downloads/258545/Release/WebKit.framework/Versions/A/WebKit
dyld: Symbol not found: _WKContextConfigurationSetShouldCaptureAudioInUIProcess
Referenced from: /System/Library/StagedFrameworks/Safari/Safari.framework/Versions/A/Safari
Expected in: /Users/pygy/Downloads/258545/Release/WebKit.framework/Versions/A/WebKit
[Process completed]
--
You are receiving this mail because:
You are the assignee for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.webkit.org/pipermail/webkit-unassigned/attachments/20200317/881c00a1/attachment.htm>
More information about the webkit-unassigned
mailing list