RESOLVED FIXED 97691
Add ability for JSArray::unshiftCount to unshift in middle of an array 
https://bugs.webkit.org/show_bug.cgi?id=97691
Summary Add ability for JSArray::unshiftCount to unshift in middle of an array
Michael Saboff
Reported 2012-09-26 08:51:13 PDT
Currently JSArray::unshiftCount only handles unshifting at the beginning of an array. This severely limits its usefulness in real world code. It should be updated to handle unshifting from the middle of an array.
Attachments
Patch (8.05 KB, patch)
2012-09-26 09:12 PDT, Michael Saboff 		fpizlo: review+
DetailsFormatted DiffDiff
View All Add attachment proposed patch, testcase, etc.
Michael Saboff
Comment 1 2012-09-26 09:12:37 PDT
Created attachment 165819 [details] Patch Here is the performance data for this patch. I reran just browsermark-js and saw no slowdown on array_blur. Benchmark report for SunSpider, V8Spider, Octane, Kraken, JSBench, JSRegress, DSP, BrowsermarkJS, and BrowsermarkDOM on msaboff-pro (MacPro5,1). VMs tested: "Base" at /Volumes/Data/src/webkit.baseline/WebKitBuild/Release/DumpRenderTree (r129520) "UnshiftOpt" at /Volumes/Data/src/webkit.work/WebKitBuild/Release/DumpRenderTree (r129520) Collected 12 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. Base UnshiftOpt SunSpider: 3d-cube 8.9070+-0.4115 ? 8.9251+-0.4109 ? 3d-morph 7.6528+-0.0695 ? 7.6684+-0.0421 ? 3d-raytrace 12.5421+-0.2923 ? 12.6467+-0.3392 ? access-binary-trees 2.3043+-0.4384 2.2860+-0.4285 access-fannkuch 6.7549+-0.0455 6.7246+-0.0249 access-nbody 4.2389+-0.0286 4.2266+-0.0355 access-nsieve 3.4221+-0.0470 ? 3.4816+-0.0555 ? might be 1.0174x slower bitops-3bit-bits-in-byte 1.3607+-0.0100 1.3580+-0.0082 bitops-bits-in-byte 5.7671+-0.0209 5.7443+-0.0195 bitops-bitwise-and 2.1956+-0.0513 ? 2.2041+-0.0293 ? bitops-nsieve-bits 3.5128+-0.0097 ? 3.5316+-0.0370 ? controlflow-recursive 2.5124+-0.0187 2.5089+-0.0154 crypto-aes 9.5934+-0.4560 ? 9.6112+-0.4311 ? crypto-md5 4.0577+-0.1782 3.9596+-0.1115 might be 1.0248x faster crypto-sha1 3.3370+-0.2377 3.1824+-0.0369 might be 1.0486x faster date-format-tofte 14.1293+-0.9179 13.9694+-0.9034 might be 1.0114x faster date-format-xparb 11.9128+-0.5754 11.6569+-0.5107 might be 1.0220x faster math-cordic 4.2426+-0.0875 ? 4.2898+-0.0920 ? might be 1.0111x slower math-partial-sums 10.3206+-0.0611 ? 10.3240+-0.1010 ? math-spectral-norm 3.0738+-0.0323 3.0583+-0.0219 regexp-dna 10.4303+-0.4001 ? 10.5125+-0.3420 ? string-base64 5.6996+-0.5414 5.5063+-0.4130 might be 1.0351x faster string-fasta 8.2432+-0.3093 8.1925+-0.3201 string-tagcloud 13.7845+-0.2941 13.6668+-0.2291 string-unpack-code 25.5450+-0.6396 ? 25.6005+-0.5872 ? string-validate-input 8.7420+-0.5940 ? 8.7485+-0.5456 ? <arithmetic> * 7.4724+-0.1442 7.4456+-0.1685 might be 1.0036x faster <geometric> 5.9231+-0.1214 5.8993+-0.1267 might be 1.0040x faster <harmonic> 4.6432+-0.1006 4.6259+-0.0985 might be 1.0037x faster Base UnshiftOpt V8Spider: crypto 77.0292+-0.3806 ? 77.0435+-0.4834 ? deltablue 119.2475+-0.4669 119.0133+-0.4813 earley-boyer 91.6742+-1.6376 91.0826+-1.7689 raytrace 64.0670+-0.3897 63.8701+-0.2537 regexp 87.7629+-0.8198 87.3886+-0.3580 richards 96.7946+-1.3499 96.4373+-1.1282 splay 98.7116+-23.1225 ? 99.7802+-22.7950 ? might be 1.0108x slower <arithmetic> 90.7553+-3.1565 90.6594+-3.1229 might be 1.0011x faster <geometric> * 88.6343+-2.7126 88.5591+-2.6503 might be 1.0008x faster <harmonic> 86.6357+-2.3376 86.5846+-2.2512 might be 1.0006x faster Base UnshiftOpt Octane and V8v7: encrypt 0.40942+-0.00057 ? 0.41136+-0.00217 ? decrypt 7.12104+-0.00754 7.11715+-0.00825 deltablue x2 0.54869+-0.00745 0.54839+-0.00480 earley 0.94881+-0.00687 0.94426+-0.00725 boyer 13.47526+-0.05659 13.45574+-0.05278 raytrace x2 4.53751+-0.15072 4.46667+-0.04337 might be 1.0159x faster regexp x2 26.67053+-0.20591 ? 26.67730+-0.07058 ? richards x2 0.25499+-0.00451 ? 0.25510+-0.00470 ? splay x2 0.74306+-0.00581 ! 0.76202+-0.00733 ! definitely 1.0255x slower navier-stokes x2 12.68348+-0.03432 12.67114+-0.00967 closure 0.47538+-0.00181 0.47409+-0.00272 jquery 7.02118+-0.04120 7.01439+-0.04609 gbemu x2 286.90147+-6.31100 278.03032+-5.27124 might be 1.0319x faster mandreel x2 195.16883+-0.60392 194.36253+-0.50723 pdfjs x2 134.29441+-0.84228 ^ 107.20744+-0.84321 ^ definitely 1.2527x faster box2d x2 30.73129+-0.12063 ? 30.74297+-0.16862 ? V8v7: <arithmetic> 7.05194+-0.03238 7.04311+-0.01079 might be 1.0013x faster <geometric> * 2.36319+-0.01291 ? 2.36572+-0.00942 ? might be 1.0011x slower <harmonic> 0.86159+-0.00680 ? 0.86480+-0.00766 ? might be 1.0037x slower Octane including V8v7: <arithmetic> 54.40460+-0.42715 ^ 51.57172+-0.35589 ^ definitely 1.0549x faster <geometric> * 7.82205+-0.02826 ^ 7.67092+-0.01404 ^ definitely 1.0197x faster <harmonic> 1.24321+-0.00908 ? 1.24670+-0.00985 ? might be 1.0028x slower Base UnshiftOpt Kraken: ai-astar 483.462+-4.054 481.843+-5.005 audio-beat-detection 195.527+-11.930 ? 197.143+-10.996 ? audio-dft 260.557+-1.592 ? 262.163+-0.610 ? audio-fft 117.010+-0.199 ? 117.039+-0.273 ? audio-oscillator 244.856+-0.645 244.355+-0.865 imaging-darkroom 285.666+-0.947 285.506+-1.183 imaging-desaturate 200.736+-0.354 200.483+-0.227 imaging-gaussian-blur 435.764+-0.605 435.714+-0.603 json-parse-financial 62.927+-0.387 ? 63.055+-0.189 ? json-stringify-tinderbox 80.967+-0.402 80.667+-0.324 stanford-crypto-aes 89.317+-0.606 ? 90.517+-0.999 ? might be 1.0134x slower stanford-crypto-ccm 85.535+-0.369 ? 85.815+-0.238 ? stanford-crypto-pbkdf2 208.172+-1.008 207.635+-0.946 stanford-crypto-sha256-iterative 99.527+-0.444 ? 99.621+-0.417 ? <arithmetic> * 203.573+-0.981 ? 203.683+-0.907 ? might be 1.0005x slower <geometric> 167.917+-0.735 ? 168.170+-0.661 ? might be 1.0015x slower <harmonic> 139.379+-0.450 ? 139.682+-0.427 ? might be 1.0022x slower Base UnshiftOpt JSBench: amazon 18.6667+-0.3128 ? 18.7500+-0.2874 ? facebook 73.4167+-1.4453 ? 73.8333+-1.3770 ? google 91.8333+-0.7082 91.7500+-0.7232 twitter 54.9167+-0.1834 54.4167+-0.3272 yahoo 23.0000+-0.0000 ? 23.2500+-0.2874 ? might be 1.0109x slower <arithmetic> * 52.3667+-0.3901 ? 52.4000+-0.4018 ? might be 1.0006x slower <geometric> 43.6714+-0.2153 ? 43.7665+-0.2934 ? might be 1.0022x slower <harmonic> 35.7634+-0.2066 ? 35.9193+-0.2928 ? might be 1.0044x slower Base UnshiftOpt JSRegress: adapt-to-double-divide 73.0738+-0.1438 73.0585+-0.1970 aliased-arguments-getbyval 0.8723+-0.0121 0.8723+-0.0099 allocate-big-object 4.0945+-1.4557 3.6423+-1.2375 might be 1.1242x faster arity-mismatch-inlining 0.6920+-0.0142 ? 0.7248+-0.0451 ? might be 1.0474x slower big-int-mul 8.8438+-1.0023 8.7682+-1.0091 boolean-test 3.4274+-0.0152 ? 3.4368+-0.0074 ? cast-int-to-double 12.4430+-0.0512 ? 12.4569+-0.0544 ? cfg-simplify 3.0893+-0.0068 ? 3.0934+-0.0123 ? cmpeq-obj-to-obj-other 9.0467+-0.1588 ? 9.2484+-0.1687 ? might be 1.0223x slower constant-test 6.9192+-0.0548 6.8756+-0.0115 direct-arguments-getbyval 0.7965+-0.0093 0.7961+-0.0110 double-pollution-getbyval 9.2394+-0.0108 ? 9.2564+-0.0260 ? double-pollution-putbyoffset 5.3846+-0.8091 5.3254+-0.7926 might be 1.0111x faster external-arguments-getbyval 1.9645+-0.1569 ? 1.9850+-0.1661 ? might be 1.0105x slower external-arguments-putbyval 3.7186+-0.3413 3.6394+-0.3638 might be 1.0218x faster Float32Array-matrix-mult 12.3239+-0.7644 ? 12.6120+-0.8141 ? might be 1.0234x slower fold-double-to-int 20.8663+-0.1262 20.7966+-0.0961 function-dot-apply 2.6230+-0.0081 ? 2.6493+-0.0244 ? might be 1.0100x slower function-test 3.8375+-0.0459 3.8356+-0.0467 indexed-properties-in-objects 3.5964+-0.0183 ? 3.6296+-0.0417 ? inline-arguments-access 1.1932+-0.0329 1.1886+-0.0146 inline-arguments-local-escape 18.6463+-0.6293 18.5442+-0.1713 int-overflow-local 85.5216+-0.2483 ? 85.5880+-0.2436 ? Int16Array-bubble-sort 66.9978+-1.5906 ? 67.5916+-2.1150 ? Int16Array-load-int-mul 1.8024+-0.0092 ? 1.8174+-0.0146 ? Int8Array-load 4.6186+-0.1022 4.6064+-0.0712 integer-divide 12.9638+-0.0717 12.9484+-0.0411 method-on-number 182.4060+-0.6054 ? 185.9722+-3.0797 ? might be 1.0196x slower new-array-dead 23.4450+-0.1019 23.4385+-0.0991 new-array-push 10.7090+-3.2304 ? 10.8295+-3.3065 ? might be 1.0112x slower number-test 3.3650+-0.0135 ? 3.3891+-0.0355 ? object-test 3.7599+-0.0318 ? 3.7814+-0.0400 ? poly-stricteq 84.2638+-1.2666 83.2393+-0.1524 might be 1.0123x faster rare-osr-exit-on-local 137.3691+-0.2507 137.2561+-0.1932 simple-activation-demo 31.4492+-0.5116 30.9943+-0.5030 might be 1.0147x faster slow-convergence 72.8972+-0.3993 72.6256+-0.4252 sparse-conditional 1.0892+-0.0098 ? 1.0904+-0.0091 ? string-hash 4.6249+-0.4814 ? 4.6360+-0.5094 ? string-test 3.3305+-0.0313 3.3231+-0.0192 tear-off-arguments 3.1053+-0.0266 3.0822+-0.0131 to-int32-boolean 23.1521+-0.0255 ? 23.1936+-0.0846 ? undefined-test 3.5517+-0.0218 ? 3.5860+-0.0589 ? <arithmetic> 23.0265+-0.1780 ? 23.0815+-0.1591 ? might be 1.0024x slower <geometric> * 7.7670+-0.1299 7.7661+-0.1252 might be 1.0001x faster <harmonic> 3.4972+-0.0224 ? 3.5112+-0.0396 ? might be 1.0040x slower Base UnshiftOpt DSP: filtrr-posterize-tint 42.7914+-0.1800 ? 43.1624+-0.2714 ? filtrr-tint-contrast-sat-bright 64.0433+-0.3528 63.7483+-0.2926 filtrr-tint-sat-adj-contr-mult 80.7600+-1.1376 ? 81.0677+-1.0036 ? filtrr-blur-overlay-sat-contr 225.2779+-7.4716 224.8127+-7.0852 filtrr-sat-blur-mult-sharpen-contr 246.0099+-1.9833 245.9871+-1.1113 filtrr-sepia-bias 29.1553+-0.4512 ? 29.1689+-0.4793 ? route9-vp8 x5 1159.8174+-4.5878 1157.9030+-6.9694 starfield x5 1132.2744+-6.5787 1125.2117+-4.0868 zynaps-quake3 x5 1638.8412+-10.3403 1629.3045+-13.8232 zynaps-mandelbrot x5 949.1073+-5.6078 ? 958.7376+-4.5850 ? might be 1.0101x slower <arithmetic> 964.9323+-2.5486 963.2204+-3.4773 might be 1.0018x faster <geometric> * 648.1368+-1.3753 647.8374+-1.6353 might be 1.0005x faster <harmonic> 233.7241+-1.5693 ? 234.1014+-1.3999 ? might be 1.0016x slower Base UnshiftOpt BrowsermarkJS: array_blur 13.46028+-0.03228 ! 13.56296+-0.06393 ! definitely 1.0076x slower array_weighted 0.00618+-0.00005 0.00616+-0.00004 string_chat 0.01554+-0.00007 ? 0.01560+-0.00005 ? string_filter 0.01819+-0.00012 0.01815+-0.00023 string_weighted 0.01165+-0.00008 ? 0.01170+-0.00009 ? <arithmetic> 2.70237+-0.00644 ! 2.72291+-0.01281 ! definitely 1.0076x slower <geometric> * 0.04871+-0.00011 ? 0.04879+-0.00020 ? might be 1.0017x slower <harmonic> 0.01363+-0.00005 0.01362+-0.00007 might be 1.0007x faster Base UnshiftOpt BrowsermarkDOM: advanced_search 1.08540+-0.01474 1.08518+-0.01076 create_source 3.49763+-0.78096 ? 3.49837+-0.78237 ? dynamic_create 3.53932+-0.82359 3.53063+-0.81326 search 0.10536+-0.00081 ? 0.10641+-0.00059 ? <arithmetic> 2.05693+-0.40116 2.05515+-0.39906 might be 1.0009x faster <geometric> * 1.07348+-0.12882 ? 1.07567+-0.12848 ? might be 1.0020x slower <harmonic> 0.36168+-0.00589 ? 0.36476+-0.00575 ? might be 1.0085x slower Base UnshiftOpt All benchmarks: <arithmetic> 202.7938+-0.5797 202.0491+-0.7009 might be 1.0037x faster <geometric> 19.6040+-0.1509 19.5300+-0.1440 might be 1.0038x faster <harmonic> 0.3717+-0.0014 0.3716+-0.0016 might be 1.0002x faster Base UnshiftOpt Geomean of preferred means: <scaled-result> 22.4142+-0.2480 22.3653+-0.2352 might be 1.0022x faster
Filip Pizlo
Comment 2 2012-09-26 10:58:12 PDT
Comment on attachment 165819 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=165819&action=review > Source/JavaScriptCore/runtime/ArrayPrototype.cpp:245 > - if (!header && isJSArray(thisObj) && asArray(thisObj)->unshiftCount(exec, count)) > + if (isJSArray(thisObj) && asArray(thisObj)->unshiftCount(exec, header, count)) You'll have to rebase this against my recent bugfix to this line of code.
Michael Saboff
Comment 3 2012-09-26 11:37:04 PDT
Committed r129676: <http://trac.webkit.org/changeset/129676>
Note You need to log in before you can comment on or make changes to this bug.