Bug 144013 – It shouldn't take 1846 lines of code and 5 FIXMEs to sort an array.

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Geoffrey Garen]

It shouldn't take 1846 lines of code and 5 FIXMEs to sort an array.

[Geoffrey Garen]

Created attachment 251462 [details]
Patch

[Geoffrey Garen]

Baseline:/Volumes/Big/ggaren/OpenSource/WebKitBuildBaseline/Release/jsc Patch:/Volumes/Big/ggaren/OpenSource/WebKitBuild/Release/jsc
Warning: could not identify checkout location for Baseline
Warning: refusing to run JSBench because not all VMs are DumpRenderTree or WebKitTestRunner.
Warning: refusing to run DSPJS because not all VMs are DumpRenderTree or WebKitTestRunner.
3292/3292                                                                                    
Generating benchmark report at /Volumes/Big/ggaren/Internal/Baseline_Patch_SunSpiderLongSpiderV8SpiderOctaneKrakenJSRegressAsmBenchCompressionBench_Geoffrey-Garens-Mac-Pro_20150421_1435_report.txt
And raw data at /Volumes/Big/ggaren/Internal/Baseline_Patch_SunSpiderLongSpiderV8SpiderOctaneKrakenJSRegressAsmBenchCompressionBench_Geoffrey-Garens-Mac-Pro_20150421_1435.json

Benchmark report for SunSpider, LongSpider, V8Spider, Octane, Kraken, JSRegress, AsmBench, and CompressionBench on Geoffrey-Garens-Mac-Pro (MacPro6,1).

VMs tested:
"Baseline" at /Volumes/Big/ggaren/OpenSource/WebKitBuildBaseline/Release/jsc
"Patch" at /Volumes/Big/ggaren/OpenSource/WebKitBuild/Release/jsc (r183036)

Collected 4 samples per benchmark/VM, with 4 VM invocations per benchmark. Emitted a call to gc() between sample measurements.
Used 1 benchmark iteration per VM invocation for warm-up. Used the jsc-specific preciseTime() function to get microsecond-level
timing. Reporting benchmark execution times with 95% confidence intervals in milliseconds.

                                                         Baseline                   Patch                                       
SunSpider:
   3d-cube                                            5.5677+-0.7728            5.3825+-0.2220          might be 1.0344x faster
   3d-morph                                           6.1693+-0.1987            6.1157+-0.0410        
   3d-raytrace                                        6.8361+-0.1144     ?      6.9913+-0.3576        ? might be 1.0227x slower
   access-binary-trees                                2.4767+-0.0942     ?      2.4887+-0.1224        ?
   access-fannkuch                                    6.2525+-0.1460     ?      6.2554+-0.2226        ?
   access-nbody                                       3.2916+-0.4163            3.0532+-0.0306          might be 1.0781x faster
   access-nsieve                                      3.8262+-0.2284            3.7385+-0.0647          might be 1.0235x faster
   bitops-3bit-bits-in-byte                           1.8043+-0.0622     ?      1.8215+-0.1008        ?
   bitops-bits-in-byte                                3.6970+-0.1164            3.6378+-0.1394          might be 1.0163x faster
   bitops-bitwise-and                                 2.4180+-0.0683     ?      2.4342+-0.3351        ?
   bitops-nsieve-bits                                 4.0034+-0.0785     ?      4.1245+-0.1513        ? might be 1.0303x slower
   controlflow-recursive                              2.6765+-0.3857            2.4520+-0.0799          might be 1.0916x faster
   crypto-aes                                         4.8315+-0.6163            4.6675+-0.2707          might be 1.0352x faster
   crypto-md5                                         2.6105+-0.0582     ?      2.7078+-0.2331        ? might be 1.0373x slower
   crypto-sha1                                        2.7966+-0.0718     ?      2.8128+-0.0067        ?
   date-format-tofte                                 10.2387+-0.1914     ?     10.2669+-0.1977        ?
   date-format-xparb                                  5.8578+-0.2059     ?      6.1187+-0.6560        ? might be 1.0445x slower
   math-cordic                                        3.4519+-0.1443     ?      3.5068+-0.1411        ? might be 1.0159x slower
   math-partial-sums                                  5.8187+-0.2908            5.5450+-0.1255          might be 1.0494x faster
   math-spectral-norm                                 2.2040+-0.1859            2.1609+-0.0693          might be 1.0199x faster
   regexp-dna                                         7.7953+-0.3243            7.6183+-0.1443          might be 1.0232x faster
   string-base64                                      4.6689+-0.0981     ?      4.8115+-0.2734        ? might be 1.0305x slower
   string-fasta                                       7.1084+-0.1103     ?      7.2725+-0.5848        ? might be 1.0231x slower
   string-tagcloud                                   10.1756+-0.2671           10.1475+-0.4400        
   string-unpack-code                                21.1628+-1.2764           21.1196+-0.4574        
   string-validate-input                              5.1068+-0.4456     ?      5.1253+-0.3623        ?

   <arithmetic>                                       5.4941+-0.0729            5.4760+-0.0785          might be 1.0033x faster

                                                         Baseline                   Patch                                       
LongSpider:
   3d-cube                                          887.0122+-20.8954    ^    860.3473+-4.1141        ^ definitely 1.0310x faster
   3d-morph                                        1629.5960+-6.2563     ?   1631.1393+-6.6875        ?
   3d-raytrace                                      793.3199+-18.7722         785.7487+-7.8263        
   access-binary-trees                             1009.6404+-13.9421        1006.8672+-10.4661       
   access-fannkuch                                  362.7690+-17.2503         356.3654+-13.7783         might be 1.0180x faster
   access-nbody                                     650.6440+-2.4717     ?    657.1128+-19.8439       ?
   access-nsieve                                    833.9120+-7.6673     ?    834.5908+-4.3252        ?
   bitops-3bit-bits-in-byte                          49.4887+-1.0497     ?     50.1646+-0.9087        ? might be 1.0137x slower
   bitops-bits-in-byte                               99.2305+-0.5604     ?     99.4317+-2.1340        ?
   bitops-nsieve-bits                               744.7573+-1.9660     !    764.3015+-4.6385        ! definitely 1.0262x slower
   controlflow-recursive                            527.5343+-20.7141         525.9948+-7.3874        
   crypto-aes                                       718.5527+-3.0679          718.3098+-2.9095        
   crypto-md5                                       589.8535+-2.6433          588.7848+-4.5623        
   crypto-sha1                                      650.0023+-0.7419     ?    659.9891+-16.1040       ? might be 1.0154x slower
   date-format-tofte                                789.6113+-12.1471    ?    791.7051+-16.2973       ?
   date-format-xparb                                812.5604+-51.2902         806.5718+-24.3214       
   math-cordic                                      630.0166+-4.2850          628.8588+-1.0235        
   math-partial-sums                                552.0300+-14.3384         543.8149+-12.0292         might be 1.0151x faster
   math-spectral-norm                               627.2335+-61.5716         604.0975+-5.6619          might be 1.0383x faster
   string-base64                                    377.6727+-1.0512     ?    379.1585+-11.0813       ?
   string-fasta                                     459.1750+-3.3120          458.9230+-6.9162        
   string-tagcloud                                  230.3871+-1.2264     ^    212.1227+-9.5972        ^ definitely 1.0861x faster

   <geometric>                                      524.2341+-2.4103          521.0470+-2.1548          might be 1.0061x faster

                                                         Baseline                   Patch                                       
V8Spider:
   crypto                                            59.8617+-0.8946           59.2698+-0.7479        
   deltablue                                         79.8693+-2.2981     ?     80.5650+-1.0764        ?
   earley-boyer                                      46.3749+-1.2060           46.3386+-1.0401        
   raytrace                                          35.2684+-0.2628           35.2287+-0.1933        
   regexp                                            70.4697+-1.4735     ?     71.1258+-2.7274        ?
   richards                                          82.8699+-2.5135     ?     84.3646+-1.4174        ? might be 1.0180x slower
   splay                                             39.8848+-2.8721     ?     41.5512+-3.0335        ? might be 1.0418x slower

   <geometric>                                       56.4189+-0.8379     ?     56.9443+-0.7310        ? might be 1.0093x slower

                                                         Baseline                   Patch                                       
Octane:
   encrypt                                           0.23418+-0.00176    ?     0.23779+-0.00724       ? might be 1.0154x slower
   decrypt                                           4.30039+-0.16977    ?     4.35327+-0.02320       ? might be 1.0123x slower
   deltablue                                x2       0.22356+-0.01669          0.21887+-0.00922         might be 1.0214x faster
   earley                                            0.55289+-0.00308    ?     0.55639+-0.01237       ?
   boyer                                             6.90810+-0.02899    ?     6.91300+-0.02594       ?
   navier-stokes                            x2       5.52322+-0.01298    ?     5.52815+-0.00882       ?
   raytrace                                 x2       1.27607+-0.07928          1.27430+-0.07017       
   richards                                 x2       0.12364+-0.00263          0.12353+-0.00206       
   splay                                    x2       0.41213+-0.00149    ^     0.40800+-0.00190       ^ definitely 1.0101x faster
   regexp                                   x2      33.56686+-1.01507         33.23486+-0.35511       
   pdfjs                                    x2      46.65090+-1.74282         45.72426+-0.54246         might be 1.0203x faster
   mandreel                                 x2      56.39650+-0.80499         56.29856+-0.17832       
   gbemu                                    x2      42.95156+-1.65639         42.45541+-0.30524         might be 1.0117x faster
   closure                                           0.63235+-0.00394    ?     0.63482+-0.00368       ?
   jquery                                            7.96260+-0.05127          7.95972+-0.06325       
   box2d                                    x2      13.57527+-0.05180    ?    13.67634+-0.29886       ?
   zlib                                     x2     394.50187+-29.24636   ?   411.35183+-3.01397       ? might be 1.0427x slower
   typescript                               x2     890.05432+-21.59462   ?   900.04626+-13.18710      ? might be 1.0112x slower

   <geometric>                                       7.13849+-0.02942    ?     7.14114+-0.05586       ? might be 1.0004x slower

                                                         Baseline                   Patch                                       
Kraken:
   ai-astar                                          357.706+-7.014            355.855+-10.479        
   audio-beat-detection                              114.962+-1.072            114.598+-0.774         
   audio-dft                                         147.864+-1.855            147.753+-1.228         
   audio-fft                                          84.965+-0.781             84.459+-1.334         
   audio-oscillator                                  220.126+-3.593            218.508+-1.209         
   imaging-darkroom                                  110.796+-0.530            110.663+-0.612         
   imaging-desaturate                                 68.986+-0.817      ?      69.190+-2.597         ?
   imaging-gaussian-blur                             120.578+-6.964            117.766+-1.128           might be 1.0239x faster
   json-parse-financial                               47.461+-0.642      ?      47.833+-1.472         ?
   json-stringify-tinderbox                           60.874+-2.431             59.954+-1.502           might be 1.0153x faster
   stanford-crypto-aes                                68.495+-1.784             67.108+-2.266           might be 1.0207x faster
   stanford-crypto-ccm                                64.395+-8.390             62.453+-7.470           might be 1.0311x faster
   stanford-crypto-pbkdf2                            177.650+-2.095      ?     180.404+-9.641         ? might be 1.0155x slower
   stanford-crypto-sha256-iterative                   58.750+-2.628             57.804+-0.724           might be 1.0164x faster

   <arithmetic>                                      121.686+-1.080            121.025+-0.433           might be 1.0055x faster

                                                         Baseline                   Patch                                       
JSRegress:
   abs-boolean                                        2.9094+-0.1151            2.8706+-0.1008          might be 1.0135x faster
   adapt-to-double-divide                            17.7902+-0.2613           17.5744+-0.2143          might be 1.0123x faster
   aliased-arguments-getbyval                         1.4661+-0.0634            1.4111+-0.0916          might be 1.0390x faster
   allocate-big-object                                2.8365+-0.1412     ?      2.8466+-0.2833        ?
   arguments-named-and-reflective                    12.5333+-0.4746           12.3802+-0.0832          might be 1.0124x faster
   arguments-out-of-bounds                           15.3045+-0.2324     ?     15.4169+-0.0845        ?
   arguments-strict-mode                             11.2045+-0.2630     ?     11.3172+-0.1610        ? might be 1.0101x slower
   arguments                                         10.1086+-0.9549            9.9953+-0.1285          might be 1.0113x faster
   arity-mismatch-inlining                            1.0524+-0.1134            1.0432+-0.0782        
   array-access-polymorphic-structure                 6.7587+-0.4709            6.5449+-0.1193          might be 1.0327x faster
   array-nonarray-polymorhpic-access                 36.4120+-1.8565           35.9543+-4.1115          might be 1.0127x faster
   array-prototype-every                             91.4720+-1.6474           90.6045+-0.3903        
   array-prototype-forEach                           91.9144+-1.1860     ^     88.5771+-0.6226        ^ definitely 1.0377x faster
   array-prototype-map                              100.6151+-1.7543          100.3936+-0.9512        
   array-prototype-some                              91.9785+-1.7787           91.0440+-0.7031          might be 1.0103x faster
   array-splice-contiguous                           43.1200+-0.4139     ?     43.7303+-2.0848        ? might be 1.0142x slower
   array-with-double-add                              4.3311+-0.1221     ?      4.4105+-0.0555        ? might be 1.0183x slower
   array-with-double-increment                        3.5062+-0.1784            3.4887+-0.0898        
   array-with-double-mul-add                          5.3138+-0.0742            5.2813+-0.1747        
   array-with-double-sum                              3.5532+-0.1424            3.5170+-0.0270          might be 1.0103x faster
   array-with-int32-add-sub                           7.1514+-0.1529     ?      7.2803+-0.2799        ? might be 1.0180x slower
   array-with-int32-or-double-sum                     3.6124+-0.0797            3.5643+-0.0789          might be 1.0135x faster
   ArrayBuffer-DataView-alloc-large-long-lived   
                                                     33.2905+-0.9426     ?     33.4192+-0.9062        ?
   ArrayBuffer-DataView-alloc-long-lived             14.0106+-0.6232     ?     14.0468+-0.6647        ?
   ArrayBuffer-Int32Array-byteOffset                  4.1122+-0.3320     ?      4.1419+-0.2097        ?
   ArrayBuffer-Int8Array-alloc-large-long-lived   
                                                     35.1407+-0.6321           34.6693+-0.7550          might be 1.0136x faster
   ArrayBuffer-Int8Array-alloc-long-lived-buffer   
                                                     23.4186+-1.0638     ?     24.3345+-1.2385        ? might be 1.0391x slower
   ArrayBuffer-Int8Array-alloc-long-lived            13.6414+-0.6080           13.6016+-0.6798        
   ArrayBuffer-Int8Array-alloc                       11.8489+-1.6121           11.2255+-0.2632          might be 1.0555x faster
   asmjs_bool_bug                                     8.1063+-0.1908     ?      8.2493+-0.2555        ? might be 1.0176x slower
   assign-custom-setter-polymorphic                   3.6128+-0.2408            3.4476+-0.2088          might be 1.0479x faster
   assign-custom-setter                               4.8065+-0.2370            4.4275+-0.1516          might be 1.0856x faster
   basic-set                                          9.4175+-0.2282     ?      9.5522+-0.1614        ? might be 1.0143x slower
   big-int-mul                                        4.3123+-0.1057            4.1713+-0.0645          might be 1.0338x faster
   boolean-test                                       3.2523+-0.1012     ?      3.2888+-0.0749        ? might be 1.0112x slower
   branch-fold                                        4.0492+-0.2695            4.0244+-0.1662        
   by-val-generic                                     8.3965+-0.6057            8.2150+-0.3167          might be 1.0221x faster
   call-spread-apply                                 31.6777+-0.6910     ?     33.5292+-5.1304        ? might be 1.0585x slower
   call-spread-call                                  26.1017+-0.7777     ?     26.4108+-0.6924        ? might be 1.0118x slower
   captured-assignments                               0.5575+-0.0160            0.5470+-0.0218          might be 1.0192x faster
   cast-int-to-double                                 5.8088+-0.2091            5.7172+-0.2502          might be 1.0160x faster
   cell-argument                                      8.7584+-0.3149            8.5868+-0.4153          might be 1.0200x faster
   cfg-simplify                                       3.0412+-0.0826     ?      3.0623+-0.1372        ?
   chain-getter-access                               10.8195+-0.3086     ?     10.9815+-0.6609        ? might be 1.0150x slower
   cmpeq-obj-to-obj-other                            11.6938+-0.0268           11.4757+-0.3539          might be 1.0190x faster
   constant-test                                      5.5484+-0.1910            5.4340+-0.2063          might be 1.0210x faster
   create-lots-of-functions                          11.9831+-1.2744           11.6940+-0.7576          might be 1.0247x faster
   DataView-custom-properties                        39.0237+-0.9481     ?     39.6093+-1.7499        ? might be 1.0150x slower
   deconstructing-parameters-overridden-by-function   
                                                      0.6750+-0.0388            0.6731+-0.0783        
   delay-tear-off-arguments-strictmode               14.5137+-1.0844           14.1950+-0.2538          might be 1.0225x faster
   deltablue-varargs                                214.6038+-2.6073     ?    218.0558+-2.2539        ? might be 1.0161x slower
   destructuring-arguments                           17.6169+-0.7706           17.6015+-0.7268        
   destructuring-swap                                 5.5090+-0.1994     ?      5.6208+-0.1626        ? might be 1.0203x slower
   direct-arguments-getbyval                          1.4108+-0.0745     ?      1.4285+-0.1377        ? might be 1.0125x slower
   div-boolean-double                                 5.5641+-0.0677     ?      5.6941+-0.3294        ? might be 1.0234x slower
   div-boolean                                        8.7202+-0.5452     ?      8.9539+-1.6962        ? might be 1.0268x slower
   double-get-by-val-out-of-bounds                    4.6752+-0.0863     ?      4.7353+-0.1974        ? might be 1.0129x slower
   double-pollution-getbyval                          9.4255+-0.2810     ?      9.6119+-0.3883        ? might be 1.0198x slower
   double-pollution-putbyoffset                       4.6297+-0.2159     ?      4.7104+-0.1706        ? might be 1.0174x slower
   double-to-int32-typed-array-no-inline              2.6053+-0.0949     ?      2.6315+-0.1447        ? might be 1.0101x slower
   double-to-int32-typed-array                        2.2092+-0.0635     ?      2.2324+-0.0601        ? might be 1.0105x slower
   double-to-uint32-typed-array-no-inline             2.6342+-0.0826     ?      2.6847+-0.0382        ? might be 1.0192x slower
   double-to-uint32-typed-array                       2.3294+-0.2728            2.2415+-0.0368          might be 1.0392x faster
   elidable-new-object-dag                           41.9064+-0.9755     ?     42.1622+-0.7659        ?
   elidable-new-object-roflcopter                    46.9862+-0.6008           46.7589+-1.5929        
   elidable-new-object-then-call                     36.8167+-3.9337     ?     38.0142+-6.0864        ? might be 1.0325x slower
   elidable-new-object-tree                          46.0569+-2.1536           44.4938+-0.9560          might be 1.0351x faster
   empty-string-plus-int                              5.7245+-0.2284            5.6328+-0.2186          might be 1.0163x faster
   emscripten-cube2hash                              40.8355+-0.6106     ?     41.9808+-1.4297        ? might be 1.0280x slower
   exit-length-on-plain-object                       14.6993+-0.3555           14.5534+-1.2699          might be 1.0100x faster
   external-arguments-getbyval                        1.4156+-0.0219     ?      1.5408+-0.2956        ? might be 1.0884x slower
   external-arguments-putbyval                        2.5085+-0.0811     ?      2.5780+-0.1528        ? might be 1.0277x slower
   fixed-typed-array-storage-var-index                1.4658+-0.0549     ?      1.5037+-0.1505        ? might be 1.0259x slower
   fixed-typed-array-storage                          1.1517+-0.0725            1.1207+-0.0428          might be 1.0277x faster
   Float32Array-matrix-mult                           4.6752+-0.0575            4.6550+-0.2147        
   Float32Array-to-Float64Array-set                  58.5582+-2.3890     ?     58.6997+-0.4127        ?
   Float64Array-alloc-long-lived                     73.5706+-3.0572           72.4182+-0.3813          might be 1.0159x faster
   Float64Array-to-Int16Array-set                    70.1050+-0.9200     ?     74.2009+-3.5602        ? might be 1.0584x slower
   fold-double-to-int                                15.2723+-0.9452           14.8812+-0.2792          might be 1.0263x faster
   fold-get-by-id-to-multi-get-by-offset-rare-int   
                                                      9.0269+-0.7765     ?      9.2622+-0.5734        ? might be 1.0261x slower
   fold-get-by-id-to-multi-get-by-offset              7.5248+-0.3105     ?      7.7972+-0.3617        ? might be 1.0362x slower
   fold-multi-get-by-offset-to-get-by-offset   
                                                      6.9977+-0.8436            6.8033+-1.0456          might be 1.0286x faster
   fold-multi-get-by-offset-to-poly-get-by-offset   
                                                      7.2759+-0.7964     ?      7.4968+-0.7903        ? might be 1.0304x slower
   fold-multi-put-by-offset-to-poly-put-by-offset   
                                                      6.7702+-0.8682     ?      7.0533+-0.0892        ? might be 1.0418x slower
   fold-multi-put-by-offset-to-put-by-offset   
                                                      5.2223+-0.0497     !      5.3822+-0.0412        ! definitely 1.0306x slower
   fold-multi-put-by-offset-to-replace-or-transition-put-by-offset   
                                                     11.0278+-0.6893     ?     11.1487+-1.4232        ? might be 1.0110x slower
   fold-put-by-id-to-multi-put-by-offset              7.5066+-0.3450            7.0890+-0.0744          might be 1.0589x faster
   fold-put-structure                                 4.7961+-0.8946            4.5361+-0.0354          might be 1.0573x faster
   for-of-iterate-array-entries                       4.7314+-0.3139            4.6050+-0.2087          might be 1.0274x faster
   for-of-iterate-array-keys                          3.9197+-0.1572     ?      3.9472+-0.1828        ?
   for-of-iterate-array-values                        3.8558+-0.0772            3.7812+-0.2246          might be 1.0197x faster
   fround                                            20.4633+-0.5491     ?     20.6503+-0.7596        ?
   ftl-library-inlining-dataview                     83.2618+-1.2690     ?     85.8697+-11.9908       ? might be 1.0313x slower
   ftl-library-inlining                              79.7913+-32.4172          79.7305+-33.6498       
   function-dot-apply                                 2.5000+-0.1349            2.4999+-0.0711        
   function-test                                      3.6436+-0.0634            3.5603+-0.0935          might be 1.0234x faster
   function-with-eval                               104.6974+-0.5757     ?    107.7865+-2.7821        ? might be 1.0295x slower
   gcse-poly-get-less-obvious                        19.9857+-1.2704     !     24.8235+-3.1354        ! definitely 1.2421x slower
   gcse-poly-get                                     24.4490+-6.5179           22.8880+-3.2762          might be 1.0682x faster
   gcse                                               4.5554+-0.0645     ?      4.6890+-0.2343        ? might be 1.0293x slower
   get-by-id-bimorphic-check-structure-elimination-simple   
                                                      3.0457+-0.1641            2.9805+-0.1158          might be 1.0219x faster
   get-by-id-bimorphic-check-structure-elimination   
                                                      6.6837+-0.2884            6.5342+-0.1803          might be 1.0229x faster
   get-by-id-chain-from-try-block                     7.3915+-0.4488            7.0908+-0.3223          might be 1.0424x faster
   get-by-id-check-structure-elimination              5.6979+-0.1629            5.4233+-0.2034          might be 1.0506x faster
   get-by-id-proto-or-self                           21.3553+-2.3495     ^     18.0282+-0.8640        ^ definitely 1.1845x faster
   get-by-id-quadmorphic-check-structure-elimination-simple   
                                                      3.2388+-0.1759            3.2083+-0.1533        
   get-by-id-self-or-proto                           21.0477+-1.4021           18.8860+-1.2192          might be 1.1145x faster
   get-by-val-out-of-bounds                           4.5901+-0.1605            4.4645+-0.0669          might be 1.0281x faster
   get_callee_monomorphic                             2.7032+-0.3453            2.6510+-0.1478          might be 1.0197x faster
   get_callee_polymorphic                             3.7428+-0.3348            3.5882+-0.1220          might be 1.0431x faster
   getter-no-activation                               5.5292+-0.1162     ?      5.5577+-0.0311        ?
   getter-richards                                  105.1459+-1.6929          104.5331+-2.6928        
   getter                                             5.9775+-0.1015     ?      6.1130+-0.1237        ? might be 1.0227x slower
   global-var-const-infer-fire-from-opt               1.0563+-0.0354     ?      1.1340+-0.3016        ? might be 1.0736x slower
   global-var-const-infer                             1.1948+-0.2108            1.0437+-0.2097          might be 1.1447x faster
   HashMap-put-get-iterate-keys                      28.0132+-0.3075     ?     28.5099+-1.1406        ? might be 1.0177x slower
   HashMap-put-get-iterate                           28.8633+-2.0218           28.4125+-0.7358          might be 1.0159x faster
   HashMap-string-put-get-iterate                    27.1171+-0.7642     ?     27.4158+-0.8218        ? might be 1.0110x slower
   hoist-make-rope                                   11.7551+-2.7456     ?     11.9830+-1.8950        ? might be 1.0194x slower
   hoist-poly-check-structure-effectful-loop   
                                                      5.5980+-0.2939            5.5310+-0.2166          might be 1.0121x faster
   hoist-poly-check-structure                         4.0390+-0.3803            3.9198+-0.0604          might be 1.0304x faster
   imul-double-only                                   8.3347+-1.2914            8.1788+-1.0365          might be 1.0191x faster
   imul-int-only                                     10.1284+-0.7330            9.9365+-0.7853          might be 1.0193x faster
   imul-mixed                                         7.7749+-0.3717     ?      8.0840+-0.1760        ? might be 1.0398x slower
   in-four-cases                                     20.0421+-0.3802     ?     20.5680+-0.8189        ? might be 1.0262x slower
   in-one-case-false                                 10.7999+-0.1297     ?     10.8692+-0.1303        ?
   in-one-case-true                                  10.8538+-0.2015     ?     10.9510+-0.2660        ?
   in-two-cases                                      11.3312+-0.3854           11.1518+-0.1251          might be 1.0161x faster
   indexed-properties-in-objects                      3.2654+-0.1699            3.1768+-0.1503          might be 1.0279x faster
   infer-closure-const-then-mov-no-inline             4.6840+-0.0525     ?      4.7139+-0.1532        ?
   infer-closure-const-then-mov                      21.4635+-0.2662           21.3054+-0.4004        
   infer-closure-const-then-put-to-scope-no-inline   
                                                     15.7256+-0.9889           15.2602+-0.9636          might be 1.0305x faster
   infer-closure-const-then-put-to-scope             24.4890+-0.6259           23.4423+-0.7379          might be 1.0447x faster
   infer-closure-const-then-reenter-no-inline   
                                                     66.5543+-2.1922           65.6005+-0.8278          might be 1.0145x faster
   infer-closure-const-then-reenter                  23.6190+-1.0882           23.5042+-1.5250        
   infer-constant-global-property                    32.5217+-1.2698           31.7505+-0.7211          might be 1.0243x faster
   infer-constant-property                            2.9675+-0.1916            2.8633+-0.0368          might be 1.0364x faster
   infer-one-time-closure-ten-vars                   12.7314+-0.5340     ?     12.9506+-0.3939        ? might be 1.0172x slower
   infer-one-time-closure-two-vars                   12.3081+-0.1821     ?     12.8495+-1.2093        ? might be 1.0440x slower
   infer-one-time-closure                            12.3171+-0.4983     ?     12.5190+-1.6315        ? might be 1.0164x slower
   infer-one-time-deep-closure                       21.4243+-0.4128     ?     22.3924+-1.7422        ? might be 1.0452x slower
   inline-arguments-access                            4.5353+-0.2916     ?      4.7390+-0.5464        ? might be 1.0449x slower
   inline-arguments-aliased-access                    4.5366+-0.1217            4.5284+-0.2606        
   inline-arguments-local-escape                      4.7930+-0.3467            4.5610+-0.1318          might be 1.0509x faster
   inline-get-scoped-var                              5.5200+-0.0947            5.4669+-0.0524        
   inlined-put-by-id-transition                      10.9617+-0.8398           10.9065+-0.7564        
   int-or-other-abs-then-get-by-val                   5.6992+-0.3623            5.4805+-0.0603          might be 1.0399x faster
   int-or-other-abs-zero-then-get-by-val             19.2844+-0.5763     ^     18.0856+-0.1715        ^ definitely 1.0663x faster
   int-or-other-add-then-get-by-val                   4.7267+-0.1398     !      5.0997+-0.1516        ! definitely 1.0789x slower
   int-or-other-add                                   5.8188+-0.1028            5.8063+-0.2168        
   int-or-other-div-then-get-by-val                   4.7885+-0.2473            4.7780+-0.1635        
   int-or-other-max-then-get-by-val                   4.8740+-0.2931            4.6931+-0.0310          might be 1.0385x faster
   int-or-other-min-then-get-by-val                   4.9388+-0.2386            4.9221+-0.2019        
   int-or-other-mod-then-get-by-val                   4.3675+-0.1319            4.1954+-0.2654          might be 1.0410x faster
   int-or-other-mul-then-get-by-val                   4.4780+-0.3448            4.3141+-0.2117          might be 1.0380x faster
   int-or-other-neg-then-get-by-val                   5.0284+-0.0868            4.9285+-0.0736          might be 1.0203x faster
   int-or-other-neg-zero-then-get-by-val             18.9901+-0.7357           18.3657+-0.1439          might be 1.0340x faster
   int-or-other-sub-then-get-by-val                   4.6493+-0.1366     !      5.1746+-0.2324        ! definitely 1.1130x slower
   int-or-other-sub                                   3.8831+-0.1287     ?      3.9573+-0.2892        ? might be 1.0191x slower
   int-overflow-local                                 4.7625+-0.1670            4.7220+-0.1353        
   Int16Array-alloc-long-lived                       51.2442+-0.4705     ?     51.4240+-1.1816        ?
   Int16Array-bubble-sort-with-byteLength            20.5860+-0.9416     ?     20.5948+-0.8057        ?
   Int16Array-bubble-sort                            20.5998+-0.4349     ?     21.0256+-0.2802        ? might be 1.0207x slower
   Int16Array-load-int-mul                            1.6882+-0.0474     ?      1.7139+-0.0469        ? might be 1.0152x slower
   Int16Array-to-Int32Array-set                      52.8524+-1.0131     ?     59.6533+-15.5013       ? might be 1.1287x slower
   Int32Array-alloc-large                            22.1255+-2.5554           21.6679+-0.5149          might be 1.0211x faster
   Int32Array-alloc-long-lived                       59.0287+-1.7037           58.0013+-1.5312          might be 1.0177x faster
   Int32Array-alloc                                   3.0342+-0.1372            3.0108+-0.2692        
   Int32Array-Int8Array-view-alloc                    8.2670+-1.6515            6.8789+-0.1286          might be 1.2018x faster
   int52-spill                                        7.0615+-0.3609            6.7220+-0.1933          might be 1.0505x faster
   Int8Array-alloc-long-lived                        48.6080+-1.4742     ?     48.9330+-2.1192        ?
   Int8Array-load-with-byteLength                     3.5845+-0.0505     ?      3.6327+-0.0759        ? might be 1.0134x slower
   Int8Array-load                                     3.6232+-0.1532     ?      3.6365+-0.0788        ?
   integer-divide                                    12.3243+-0.3675     ?     12.4622+-0.1446        ? might be 1.0112x slower
   integer-modulo                                     2.4131+-0.1436     ?      2.5792+-0.5207        ? might be 1.0688x slower
   large-int-captured                                 4.7529+-0.6254            4.5573+-0.1795          might be 1.0429x faster
   large-int-neg                                     17.2642+-0.3643     ?     17.7886+-0.7136        ? might be 1.0304x slower
   large-int                                         16.1411+-1.0549           15.9443+-0.4588          might be 1.0123x faster
   logical-not                                        4.9774+-0.1163     ?      5.0394+-0.0418        ? might be 1.0124x slower
   lots-of-fields                                    13.6369+-0.4456           13.6218+-0.3821        
   make-indexed-storage                               3.3918+-0.6359            3.2209+-0.6400          might be 1.0531x faster
   make-rope-cse                                      4.0998+-0.4404            3.8295+-0.0454          might be 1.0706x faster
   marsaglia-larger-ints                             41.4015+-1.7866           41.0850+-1.3415        
   marsaglia-osr-entry                               24.3041+-0.5590           23.4384+-0.4273          might be 1.0369x faster
   max-boolean                                        2.6593+-0.0880     ?      2.7771+-0.1590        ? might be 1.0443x slower
   method-on-number                                  19.9067+-0.1212           18.7903+-1.9443          might be 1.0594x faster
   min-boolean                                        2.6902+-0.1038     ?      2.7271+-0.0652        ? might be 1.0137x slower
   minus-boolean-double                               3.3341+-0.0322            3.3179+-0.0601        
   minus-boolean                                      2.5505+-0.1365            2.4977+-0.0734          might be 1.0211x faster
   misc-strict-eq                                    40.0247+-2.5346     ?     42.3330+-4.7212        ? might be 1.0577x slower
   mod-boolean-double                                11.5089+-0.2432     ?     11.7336+-0.5686        ? might be 1.0195x slower
   mod-boolean                                        8.5070+-0.2636            8.5048+-0.1307        
   mul-boolean-double                                 3.9818+-0.0689     ?      4.0060+-0.2999        ?
   mul-boolean                                        3.0635+-0.0404     ?      3.1466+-0.1677        ? might be 1.0271x slower
   neg-boolean                                        3.4128+-0.1914     ?      3.4681+-0.1957        ? might be 1.0162x slower
   negative-zero-divide                               0.4371+-0.0342     ?      0.4597+-0.0386        ? might be 1.0518x slower
   negative-zero-modulo                               0.4958+-0.1131     ?      0.5012+-0.1195        ? might be 1.0110x slower
   negative-zero-negate                               0.4586+-0.0942            0.4225+-0.0376          might be 1.0852x faster
   nested-function-parsing                           40.6443+-1.2286     ?     40.9342+-1.6214        ?
   new-array-buffer-dead                              3.0907+-0.1616     ?      3.2468+-0.2757        ? might be 1.0505x slower
   new-array-buffer-push                              6.7543+-0.5682            6.6116+-0.2935          might be 1.0216x faster
   new-array-dead                                    12.5408+-1.7713     ?     12.8027+-1.3509        ? might be 1.0209x slower
   new-array-push                                     4.0477+-0.1923     ?      4.0612+-0.1600        ?
   no-inline-constructor                            116.8820+-0.8080          115.6589+-0.7059          might be 1.0106x faster
   number-test                                        3.1821+-0.0281     ?      3.2955+-0.1658        ? might be 1.0356x slower
   object-closure-call                                6.0718+-0.3817            5.9651+-0.1466          might be 1.0179x faster
   object-test                                        3.3118+-0.0844     ?      3.3960+-0.2179        ? might be 1.0254x slower
   obvious-sink-pathology-taken                     130.1315+-5.1633          128.4725+-1.3687          might be 1.0129x faster
   obvious-sink-pathology                           121.4161+-2.8040          120.4976+-1.3237        
   obviously-elidable-new-object                     34.5986+-0.2854     ?     35.0461+-0.8574        ? might be 1.0129x slower
   plus-boolean-arith                                 2.7036+-0.0513            2.6896+-0.0504        
   plus-boolean-double                                3.4060+-0.1439     ?      3.4170+-0.1190        ?
   plus-boolean                                       2.6425+-0.1893            2.6183+-0.1075        
   poly-chain-access-different-prototypes-simple   
                                                      3.5597+-0.2249            3.4790+-0.0558          might be 1.0232x faster
   poly-chain-access-different-prototypes             2.8995+-0.1854            2.8965+-0.1629        
   poly-chain-access-simpler                          3.5113+-0.0232     ?      3.7368+-0.4338        ? might be 1.0642x slower
   poly-chain-access                                  2.8120+-0.0181     ?      2.8436+-0.0554        ? might be 1.0112x slower
   poly-stricteq                                     61.7170+-1.7783     ?     62.0993+-0.8923        ?
   polymorphic-array-call                             1.3843+-0.1338     ?      1.4333+-0.0665        ? might be 1.0354x slower
   polymorphic-get-by-id                              3.3296+-0.1802     ?      3.4681+-0.2420        ? might be 1.0416x slower
   polymorphic-put-by-id                             30.8491+-1.4378     ?     32.6600+-2.3183        ? might be 1.0587x slower
   polymorphic-structure                             15.5881+-0.3119     ?     15.6896+-0.3797        ?
   polyvariant-monomorphic-get-by-id                  9.2390+-0.0807     ?      9.3296+-0.0792        ?
   proto-getter-access                               10.7971+-0.3053           10.6278+-0.4782          might be 1.0159x faster
   put-by-id-replace-and-transition                   9.3727+-0.7520     ?      9.4220+-0.1184        ?
   put-by-id-slightly-polymorphic                     3.1254+-0.1894     ?      3.1448+-0.1022        ?
   put-by-id                                         13.3989+-1.5146           13.1417+-0.5633          might be 1.0196x faster
   put-by-val-direct                                  0.6219+-0.1498            0.5909+-0.0762          might be 1.0525x faster
   put-by-val-large-index-blank-indexing-type   
                                                      5.5932+-0.0590            5.5737+-0.2250        
   put-by-val-machine-int                             3.0563+-0.4014            2.7640+-0.1843          might be 1.1058x faster
   rare-osr-exit-on-local                            15.9012+-0.2611     ?     16.1818+-0.4525        ? might be 1.0176x slower
   register-pressure-from-osr                        23.3110+-0.4679           23.1919+-0.5172        
   setter                                             5.9892+-0.1082            5.9137+-0.0351          might be 1.0128x faster
   simple-activation-demo                            27.0500+-2.0148     ?     27.5398+-0.7151        ? might be 1.0181x slower
   simple-getter-access                              13.7763+-0.5639           13.4545+-0.2189          might be 1.0239x faster
   simple-poly-call-nested                            9.0325+-0.1893     ?      9.0833+-0.1710        ?
   simple-poly-call                                   1.5851+-0.0500            1.5650+-0.0746          might be 1.0129x faster
   sin-boolean                                       20.0225+-1.0025           19.5280+-0.5666          might be 1.0253x faster
   singleton-scope                                   71.0651+-1.0281     ?     71.1440+-0.4721        ?
   sinkable-new-object-dag                           72.2231+-2.6787     ?     72.6106+-2.7900        ?
   sinkable-new-object-taken                         54.4644+-3.0579     ?     55.3016+-5.1681        ? might be 1.0154x slower
   sinkable-new-object                               40.0522+-2.9281           39.0502+-1.3797          might be 1.0257x faster
   slow-array-profile-convergence                     3.0457+-0.0452     ?      3.1494+-0.1408        ? might be 1.0341x slower
   slow-convergence                                   3.0182+-0.3461            2.9833+-0.3865          might be 1.0117x faster
   sorting-benchmark                                 22.5609+-0.0926     ^     20.7278+-0.6849        ^ definitely 1.0884x faster
   sparse-conditional                                 1.3547+-0.0320            1.3480+-0.0822        
   splice-to-remove                                  17.1979+-0.6025     ?     17.3720+-0.5953        ? might be 1.0101x slower
   string-char-code-at                               17.2379+-0.2115     ?     17.4885+-0.6691        ? might be 1.0145x slower
   string-concat-object                               2.3848+-0.2652            2.3435+-0.2369          might be 1.0176x faster
   string-concat-pair-object                          2.2933+-0.1304            2.2437+-0.2398          might be 1.0221x faster
   string-concat-pair-simple                         11.9855+-0.1087     ?     12.2153+-1.2030        ? might be 1.0192x slower
   string-concat-simple                              12.8290+-1.4901           12.6882+-1.4629          might be 1.0111x faster
   string-cons-repeat                                 7.8910+-0.3131            7.7726+-0.3273          might be 1.0152x faster
   string-cons-tower                                  7.8138+-0.3253            7.7081+-0.1655          might be 1.0137x faster
   string-equality                                   18.5762+-0.6451     ?     19.2319+-0.9758        ? might be 1.0353x slower
   string-get-by-val-big-char                         7.8150+-0.2785            7.5640+-0.2695          might be 1.0332x faster
   string-get-by-val-out-of-bounds-insane             3.8489+-0.1089     ?      4.0306+-0.4800        ? might be 1.0472x slower
   string-get-by-val-out-of-bounds                    5.7870+-0.2416            5.7411+-0.1266        
   string-get-by-val                                  3.4217+-0.0316     !      3.7233+-0.1345        ! definitely 1.0882x slower
   string-hash                                        2.3846+-0.1428            2.2858+-0.0435          might be 1.0433x faster
   string-long-ident-equality                        15.9120+-1.0202     ?     16.3937+-1.0794        ? might be 1.0303x slower
   string-out-of-bounds                              15.6583+-0.8115     ?     15.7007+-0.6202        ?
   string-repeat-arith                               33.4465+-1.1011     ?     33.8704+-0.7442        ? might be 1.0127x slower
   string-sub                                        66.9725+-1.1497     ?     68.4734+-0.6941        ? might be 1.0224x slower
   string-test                                        3.2484+-0.3642            3.1146+-0.0802          might be 1.0429x faster
   string-var-equality                               38.8778+-2.3596           38.6916+-0.6764        
   structure-hoist-over-transitions                   2.7111+-0.1315     ?      2.7653+-0.1477        ? might be 1.0200x slower
   substring-concat-weird                            41.6284+-1.3169     ?     42.0735+-2.0585        ? might be 1.0107x slower
   substring-concat                                  42.6646+-0.2971     ?     43.4982+-1.2702        ? might be 1.0195x slower
   substring                                         47.7443+-1.8314           47.7068+-1.8116        
   switch-char-constant                               3.0320+-0.2579            2.9606+-0.1061          might be 1.0241x faster
   switch-char                                        7.7990+-0.0803     ^      7.0922+-0.0868        ^ definitely 1.0997x faster
   switch-constant                                    9.3627+-0.7913            8.7604+-0.1575          might be 1.0688x faster
   switch-string-basic-big-var                       15.5233+-0.2419           15.5052+-0.2059        
   switch-string-basic-big                           14.1606+-0.1085     ?     14.5585+-0.4931        ? might be 1.0281x slower
   switch-string-basic-var                           14.9198+-0.2648     ?     14.9225+-0.7580        ?
   switch-string-basic                               13.4817+-0.2402     ?     13.7347+-0.5253        ? might be 1.0188x slower
   switch-string-big-length-tower-var                20.9870+-0.4479     ?     21.0053+-0.5422        ?
   switch-string-length-tower-var                    15.4657+-0.7295     ?     15.9496+-1.0643        ? might be 1.0313x slower
   switch-string-length-tower                        12.9510+-0.1741     ?     13.2574+-0.3620        ? might be 1.0237x slower
   switch-string-short                               13.1969+-0.3666     ?     13.3582+-0.6163        ? might be 1.0122x slower
   switch                                            13.1130+-0.0739     ?     13.1978+-0.7233        ?
   tear-off-arguments-simple                          3.4486+-0.1377     ?      3.4529+-0.1529        ?
   tear-off-arguments                                 4.8719+-0.2929            4.8173+-0.1661          might be 1.0113x faster
   temporal-structure                                12.9145+-0.1130     ?     13.1350+-0.4200        ? might be 1.0171x slower
   to-int32-boolean                                  14.6807+-0.6033           14.4744+-0.4869          might be 1.0143x faster
   try-catch-get-by-val-cloned-arguments             14.2733+-0.3463     ?     14.7277+-0.5330        ? might be 1.0318x slower
   try-catch-get-by-val-direct-arguments              6.6127+-0.9881            6.4135+-0.4473          might be 1.0311x faster
   try-catch-get-by-val-scoped-arguments              7.8650+-0.2240            7.7143+-0.6459          might be 1.0195x faster
   undefined-property-access                        370.0018+-1.9359     ?    371.5791+-1.7469        ?
   undefined-test                                     3.3199+-0.1113            3.2123+-0.0781          might be 1.0335x faster
   unprofiled-licm                                   23.9647+-0.7879           23.2492+-0.5111          might be 1.0308x faster
   varargs-call                                      17.5212+-0.1020           17.5209+-0.5859        
   varargs-construct-inline                          23.3658+-1.0190           22.8248+-0.9456          might be 1.0237x faster
   varargs-construct                                 34.1817+-0.9736     ?     34.6476+-1.3970        ? might be 1.0136x slower
   varargs-inline                                     9.9994+-0.4089            9.8880+-0.2856          might be 1.0113x faster
   varargs-strict-mode                               11.0100+-1.0367           10.6146+-0.2007          might be 1.0373x faster
   varargs                                           10.5338+-0.1003     ?     10.6870+-0.4134        ? might be 1.0145x slower
   weird-inlining-const-prop                          2.4048+-0.1160            2.3984+-0.1915        

   <geometric>                                        9.0942+-0.0204            9.0699+-0.0248          might be 1.0027x faster

                                                         Baseline                   Patch                                       
AsmBench:
   bigfib.cpp                                       527.8453+-4.7890     ?    528.8416+-4.5860        ?
   cray.c                                           457.9510+-3.3883          457.7573+-4.5121        
   dry.c                                            522.6187+-18.1359         521.7680+-16.8284       
   FloatMM.c                                        763.0771+-4.2214     ?    764.7709+-10.1078       ?
   gcc-loops.cpp                                   4460.0385+-36.5182        4432.7841+-23.3158       
   n-body.c                                        1038.3492+-4.7112         1037.3658+-2.6211        
   Quicksort.c                                      455.1869+-17.6462    ?    455.4370+-5.9530        ?
   stepanov_container.cpp                          3935.8091+-30.2955    ?   3936.5145+-30.1089       ?
   Towers.c                                         270.8192+-1.0717     ?    275.1235+-14.6857       ? might be 1.0159x slower

   <geometric>                                      843.6566+-5.2953     ?    844.7098+-3.1847        ? might be 1.0012x slower

                                                         Baseline                   Patch                                       
CompressionBench:
   huffman                                          382.6453+-4.4196          380.9722+-5.7205        
   arithmetic-simple                                422.0490+-1.5252          420.0300+-6.9245        
   arithmetic-precise                               310.6108+-1.7842     ?    313.3753+-2.9157        ?
   arithmetic-complex-precise                       310.3244+-4.0230     ?    312.2260+-2.7202        ?
   arithmetic-precise-order-0                       450.8635+-18.4893         446.4185+-9.4843        
   arithmetic-precise-order-1                       349.9102+-12.6022         344.2668+-4.2443          might be 1.0164x faster
   arithmetic-precise-order-2                       392.5510+-1.6324          389.6470+-2.1989        
   arithmetic-simple-order-1                        443.3873+-2.7466     ?    444.3158+-2.6391        ?
   arithmetic-simple-order-2                        501.3690+-2.8329          500.7195+-3.4928        
   lz-string                                        315.1551+-3.7846     ?    318.2733+-8.1165        ?

   <geometric>                                      382.7656+-0.5336          382.1184+-1.2432          might be 1.0017x faster

                                                         Baseline                   Patch                                       
Geomean of preferred means:
   <scaled-result>                                   67.1724+-0.1347           67.1026+-0.1757          might be 1.0010x faster

[Mark Lam]

Comment on attachment 251462 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=251462&action=review

> Source/JavaScriptCore/builtins/Array.prototype.js:295
> +        for (var i = 0; i < aString.length; ++i) {

Shouldn't we be using min(aString.length, bString.length) as the iteration limit of this loop?

> Source/JavaScriptCore/builtins/Array.prototype.js:424
> +        var deleteCount = min(valueCount, holeCount);

Why is deleteCount != holeCount?  What is the difference between a deleted entry and a hole?  Can you please clarify?

[Darin Adler]

Comment on attachment 251462 [details]
Patch

Need to remove AVLTree.h from Source/WTF/wtf/CMakeLists.txt to fix the GTK build.

[Geoffrey Garen]

Created attachment 251567 [details]
Patch

[Geoffrey Garen]

> View in context:
> https://bugs.webkit.org/attachment.cgi?id=251462&action=review
> 
> > Source/JavaScriptCore/builtins/Array.prototype.js:295
> > +        for (var i = 0; i < aString.length; ++i) {
> 
> Shouldn't we be using min(aString.length, bString.length) as the iteration
> limit of this loop?

Not required for correctness, since NaN does its thing, but I made this change for clarity.

> > Source/JavaScriptCore/builtins/Array.prototype.js:424
> > +        var deleteCount = min(valueCount, holeCount);
> 
> Why is deleteCount != holeCount?  What is the difference between a deleted
> entry and a hole?  Can you please clarify?

The goal was to avoid doing lots of deletes in new Array(BIG), but the algorithm proved incorrect. Updated patch fixes this and includes two new tests.

[Mark Lam]

(In reply to comment #6)
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=251462&action=review
> > 
> > > Source/JavaScriptCore/builtins/Array.prototype.js:295
> > > +        for (var i = 0; i < aString.length; ++i) {
> > 
> > Shouldn't we be using min(aString.length, bString.length) as the iteration
> > limit of this loop?
> 
> Not required for correctness, since NaN does its thing, but I made this
> change for clarity.

This change also avoids unnecessary work in the case where the first string is longer than the second.  Hence, it can be a perf gain if there are a mix of lots of long and short strings in the array.

[Geoffrey Garen]

> > > Shouldn't we be using min(aString.length, bString.length) as the iteration
> > > limit of this loop?
> > 
> > Not required for correctness, since NaN does its thing, but I made this
> > change for clarity.
> 
> This change also avoids unnecessary work in the case where the first string
> is longer than the second.  Hence, it can be a perf gain if there are a mix
> of lots of long and short strings in the array.

We don't avoid any work. charCodeAt past the end of a string returns NaN, which breaks you out of the loop.

[Mark Lam]

(In reply to comment #8)
> > > > Shouldn't we be using min(aString.length, bString.length) as the iteration
> > > > limit of this loop?
> > > 
> > > Not required for correctness, since NaN does its thing, but I made this
> > > change for clarity.
> > 
> > This change also avoids unnecessary work in the case where the first string
> > is longer than the second.  Hence, it can be a perf gain if there are a mix
> > of lots of long and short strings in the array.
> 
> We don't avoid any work. charCodeAt past the end of a string returns NaN,
> which breaks you out of the loop.

Oh, you're right.

[Mark Lam]

Comment on attachment 251567 [details]
Patch

r=me

[Geoffrey Garen]

Committed r183288: <http://trac.webkit.org/changeset/183288>

[Simon Fraser (smfr)]

js/sort-with-side-effecting-comparisons.html is timing out after this:
https://build.webkit.org/results/Apple%20Mavericks%20Debug%20WK1%20(Tests)/r183306%20(12194)/results.html

[Alexey Proskuryakov]

Yes, so rolling out.

https://webkit-test-results.appspot.com/dashboards/flakiness_dashboard.html#showAllRuns=true&tests=js%2Fsort-with-side-effecting-comparisons.html

[WebKit Commit Bot]

Re-opened since this is blocked by bug 144189

[Geoffrey Garen]

Committed r183570: <http://trac.webkit.org/changeset/183570>

[Geoffrey Garen]

(In reply to comment #15)
> Committed r183570: <http://trac.webkit.org/changeset/183570>

Relevant ChangeLog:

        * script-tests/sort-with-side-effecting-comparisons.js: Made this test
        shorter so that it wouldn't hang debug builds. This test is O(N^2). It
        used to terminate sooner because our sort implementation would (sometimes)
        terminate sooner if you shrank the array. Our new sort does not accept
        intermediate updates to the array's length, matching Firefox. I spoke
        to Gavin and Alexey about this, and we think that going out of our way
        to honor length changes mid-sort doesn't make much sense because it's
        not possible to honor the general case of value changes in a predictable
        way.

[Andreas Kling]

This caused a ~22% regression on the jslib-traverse-jquery test:

https://perf.webkit.org/#mode=charts&chartList=%5B%5B%22mac-yosemite%22%2C%22Dromaeo%2Fjslib-traverse-jquery%3ARuns%22%5D%5D

[Geoffrey Garen]

(In reply to comment #17)
> This caused a ~22% regression on the jslib-traverse-jquery test:
> 
> https://perf.webkit.org/#mode=charts&chartList=%5B%5B%22mac-
> yosemite%22%2C%22Dromaeo%2Fjslib-traverse-jquery%3ARuns%22%5D%5D

I just tested a micro benchmark of node sorting using the jQuery node sorting comparator, and this new sort is a 10X speedup over the old. What gives? :(

[Geoffrey Garen]

If you run PerformanceTests/Dromaeo/jslib-traverse-jquery.html manually, and average the 9 mean runs/s numbers from parent, parents, prev, prevAll, etc., the new sort is 2% faster. 

But the :Runs number reported is 27% slower. What does the :Runs number measure?

[Geoffrey Garen]

Looks like the actual test is controlled by Dromaeo/resources/dromaeo/web/tests/jslib-traverse-jquery.html, and the :Runs number is maybe total time across all tests, so it is dominated by the slowest test.

In prevail, one of the tests that got slower, we are spending lots more time Node::compareDocumentPosition. Presumably, we are doing more comparisons, and the comparisons are very expensive.

Perhaps we should optimize Node::compareDocumentPosition.

An initial test seems to indicate that ending early when the array is already sorted -- which is easy for merge sort to do -- is a big speedup. Assuming I did it right, and didn't just break all sorting.

[Geoffrey Garen]

s/prevail/prevAll/

[Andreas Kling]

(In reply to comment #20)
> Looks like the actual test is controlled by
> Dromaeo/resources/dromaeo/web/tests/jslib-traverse-jquery.html, and the
> :Runs number is maybe total time across all tests, so it is dominated by the
> slowest test.
> 
> In prevail, one of the tests that got slower, we are spending lots more time
> Node::compareDocumentPosition. Presumably, we are doing more comparisons,
> and the comparisons are very expensive.
> 
> Perhaps we should optimize Node::compareDocumentPosition.

That seems like a generally useful thing to do.

> An initial test seems to indicate that ending early when the array is
> already sorted -- which is easy for merge sort to do -- is a big speedup.
> Assuming I did it right, and didn't just break all sorting.

This sounds promising :)

[Geoffrey Garen]

> > Perhaps we should optimize Node::compareDocumentPosition.
> 
> That seems like a generally useful thing to do.

This doesn't look possible. Node::compareDocumentPosition is linear time by design, and I don't see an immediate way to fix it. If you have two nodes that are siblings, the only way to know if A comes before B is to search backwards from B until you find A or null.

[Geoffrey Garen]

Regression covered in https://bugs.webkit.org/show_bug.cgi?id=144476.