Bug 209176 - Array.prototype.shift() has O(N) perf for dense Arrays
Summary: Array.prototype.shift() has O(N) perf for dense Arrays
Status: NEW
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: Safari Technology Preview
Hardware: Mac macOS 10.14
: P2 Normal
Assignee: Nobody
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2020-03-17 06:36 PDT by Pierre-Yves Gérardy
Modified: 2022-07-06 17:43 PDT (History)
5 users (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Pierre-Yves Gérardy 2020-03-17 06:36:41 PDT
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]
Comment 1 Radar WebKit Bug Importer 2022-07-01 11:41:32 PDT
<rdar://problem/96305718>
Comment 2 Raiyan Sayeed 2022-07-06 17:43:31 PDT
I'd like to take a shot at working on this if no one else is :)