[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


            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: 


takes twice the time of 


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