Bug 144013

Summary: It shouldn't take 1846 lines of code and 5 FIXMEs to sort an array.
Product: WebKit Reporter: Geoffrey Garen <ggaren>
Component: New BugsAssignee: Geoffrey Garen <ggaren>
Status: RESOLVED FIXED    
Severity: Normal CC: benjamin, cmarcelo, commit-queue, kling, mark.lam, simon.fraser
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Bug Depends on: 144189    
Bug Blocks:    
Attachments:
Description Flags
Patch
none
Patch mark.lam: review+

Geoffrey Garen
Reported 2015-04-21 14:54:17 PDT
It shouldn't take 1846 lines of code and 5 FIXMEs to sort an array.
Attachments
Patch (95.65 KB, patch)
2015-04-23 12:01 PDT, Geoffrey Garen 		no flags
DetailsFormatted DiffDiff
Patch (105.23 KB, patch)
2015-04-24 12:43 PDT, Geoffrey Garen 		mark.lam: review+
DetailsFormatted DiffDiff
Show Obsolete (1) View All Add attachment proposed patch, testcase, etc.
Geoffrey Garen
Comment 1 2015-04-23 12:01:36 PDT
Created attachment 251462 [details] Patch
Geoffrey Garen
Comment 2 2015-04-23 12:01:59 PDT
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 3 2015-04-23 16:12:53 PDT
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 4 2015-04-23 18:14:40 PDT
Comment on attachment 251462 [details] Patch Need to remove AVLTree.h from Source/WTF/wtf/CMakeLists.txt to fix the GTK build.
Geoffrey Garen
Comment 5 2015-04-24 12:43:58 PDT
Created attachment 251567 [details] Patch
Geoffrey Garen
Comment 6 2015-04-24 12:48:23 PDT
> 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
Comment 7 2015-04-24 12:54:35 PDT
(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
Comment 8 2015-04-24 14:58:11 PDT
> > > 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
Comment 9 2015-04-24 15:01:54 PDT
(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 10 2015-04-24 15:12:36 PDT
Comment on attachment 251567 [details] Patch r=me
Geoffrey Garen
Comment 11 2015-04-24 16:03:38 PDT
Committed r183288: <http://trac.webkit.org/changeset/183288>
Simon Fraser (smfr)
Comment 12 2015-04-24 21:49:07 PDT
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
WebKit Commit Bot
Comment 14 2015-04-24 23:55:09 PDT
Re-opened since this is blocked by bug 144189
Geoffrey Garen
Comment 15 2015-04-29 12:49:12 PDT
Committed r183570: <http://trac.webkit.org/changeset/183570>
Geoffrey Garen
Comment 16 2015-04-29 12:50:44 PDT
(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
Comment 17 2015-04-29 18:59:20 PDT
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
Comment 18 2015-04-30 11:13:47 PDT
(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
Comment 19 2015-04-30 11:29:02 PDT
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
Comment 20 2015-04-30 12:13:47 PDT
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
Comment 21 2015-04-30 12:14:12 PDT
s/prevail/prevAll/
Andreas Kling
Comment 22 2015-04-30 15:35:45 PDT
(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
Comment 23 2015-04-30 15:49:47 PDT
> > 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
Comment 24 2015-05-04 11:16:54 PDT
Regression covered in https://bugs.webkit.org/show_bug.cgi?id=144476.
Note You need to log in before you can comment on or make changes to this bug.