RESOLVED FIXED 69235
DFG should speculate more aggressively on obvious cases on polymorphic get_by_id
https://bugs.webkit.org/show_bug.cgi?id=69235
Summary DFG should speculate more aggressively on obvious cases on polymorphic get_by_id
Filip Pizlo
Reported 2011-10-02 21:27:07 PDT
Many get_by_id's that go polymorphic in V8 end up performing accesses at one offset regardless of the structure. In those cases, we can still use GetByOffset and CheckStructure, so long as CheckStructure is extended to be able to check multiple structures.
Attachments
work in progress (21.17 KB, patch)
2011-10-02 21:30 PDT, Filip Pizlo
no flags
the patch (41.70 KB, patch)
2011-10-02 23:13 PDT, Filip Pizlo
no flags
the patch - fix style, mostly (41.72 KB, patch)
2011-10-02 23:18 PDT, Filip Pizlo
webkit-ews: commit-queue-
the patch - added some forgotten 32-bit stuff (46.33 KB, patch)
2011-10-02 23:46 PDT, Filip Pizlo
oliver: review+
Filip Pizlo
Comment 1 2011-10-02 21:30:01 PDT
Created attachment 109435 [details] work in progress Benchmark report for SunSpider, V8, and Kraken. VMs tested: "TipOfTree" at /Volumes/Data/pizlo/quinary/OpenSource/WebKitBuild/Release/jsc "PolyGetById" at /Volumes/Data/pizlo/senary/OpenSource/WebKitBuild/Release/jsc Collected 12 samples per benchmark/VM, with 4 VM invocations per benchmark. 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. TipOfTree PolyGetById SunSpider: 3d-cube 7.4802+-0.2051 ? 7.5662+-0.2457 ? might be 1.0115x slower 3d-morph 7.4047+-0.1666 7.4019+-0.1256 3d-raytrace 8.2055+-0.2450 ^ 7.6090+-0.2031 ^ definitely 1.0784x faster access-binary-trees 1.9520+-0.1161 ^ 1.7650+-0.0517 ^ definitely 1.1060x faster access-fannkuch 6.3952+-0.1257 6.3839+-0.1022 access-nbody 3.6135+-0.1259 3.5215+-0.0844 might be 1.0261x faster access-nsieve 2.6273+-0.0694 ? 2.6825+-0.0772 ? might be 1.0210x slower bitops-3bit-bits-in-byte 1.7307+-0.0258 ? 1.7378+-0.0204 ? bitops-bits-in-byte 2.7378+-0.0734 2.7376+-0.0666 bitops-bitwise-and 3.1737+-0.0341 ? 3.2256+-0.0921 ? might be 1.0163x slower bitops-nsieve-bits 5.5207+-0.1615 5.5002+-0.1703 controlflow-recursive 2.0332+-0.0440 2.0238+-0.0508 crypto-aes 6.8061+-0.2144 6.7950+-0.2456 crypto-md5 2.8211+-0.0715 2.7946+-0.1060 crypto-sha1 2.5510+-0.0921 2.5062+-0.0428 might be 1.0179x faster date-format-tofte 10.0702+-0.2434 9.9412+-0.3018 might be 1.0130x faster date-format-xparb 9.3993+-0.3214 9.3923+-0.3008 math-cordic 6.3349+-0.1338 ? 6.4220+-0.2151 ? might be 1.0138x slower math-partial-sums 7.6382+-0.1566 ? 7.7272+-0.1600 ? might be 1.0117x slower math-spectral-norm 2.8143+-0.0813 ? 2.8189+-0.0596 ? regexp-dna 10.7468+-0.0974 ? 10.7851+-0.1443 ? string-base64 5.6549+-0.1856 ? 5.7496+-0.2816 ? might be 1.0168x slower string-fasta 6.6589+-0.1586 ? 6.8564+-0.1918 ? might be 1.0297x slower string-tagcloud 11.8219+-0.2949 11.6058+-0.2792 might be 1.0186x faster string-unpack-code 21.5388+-0.5473 ? 21.7617+-0.7630 ? might be 1.0103x slower string-validate-input 6.2991+-0.1684 ? 6.4473+-0.2245 ? might be 1.0235x slower <arithmetic> * 6.3088+-0.0321 6.2984+-0.0335 <geometric> 5.1750+-0.0327 5.1528+-0.0279 <harmonic> 4.2541+-0.0454 4.2174+-0.0399 TipOfTree PolyGetById V8: crypto 72.0420+-0.2361 ! 72.6393+-0.2663 ! definitely 1.0083x slower deltablue 226.0377+-2.2138 ^ 222.4414+-1.3674 ^ definitely 1.0162x faster earley-boyer 87.5112+-0.3216 ? 88.2521+-0.6321 ? raytrace 61.6821+-0.5257 ? 62.4898+-0.4579 ? might be 1.0131x slower regexp 103.2826+-0.5215 103.0298+-0.6185 richards 185.8201+-0.7279 ? 187.5975+-1.3956 ? splay 90.7084+-0.3449 90.4355+-0.5553 <arithmetic> 118.1549+-0.4235 118.1265+-0.3624 <geometric> * 106.2625+-0.2895 ? 106.5311+-0.2887 ? <harmonic> 97.1732+-0.2613 ? 97.6353+-0.2647 ? TipOfTree PolyGetById Kraken: ai-astar 487.9140+-1.2525 486.3753+-1.1255 audio-beat-detection 194.2983+-2.8350 191.1177+-1.6340 might be 1.0166x faster audio-dft 279.9974+-3.1451 ^ 270.8231+-1.9973 ^ definitely 1.0339x faster audio-fft 128.0543+-0.8223 ? 128.5125+-1.0330 ? audio-oscillator 257.3560+-1.9724 ^ 246.3795+-2.0638 ^ definitely 1.0446x faster imaging-darkroom 419.3905+-0.9765 ? 420.3736+-1.5820 ? imaging-desaturate 223.6224+-0.9294 ? 224.8275+-0.5870 ? imaging-gaussian-blur 579.8734+-1.3646 ? 580.5274+-1.4157 ? json-parse-financial 49.2241+-0.2084 ! 50.7065+-0.8707 ! definitely 1.0301x slower json-stringify-tinderbox 67.5603+-0.4213 ! 68.4149+-0.4177 ! definitely 1.0126x slower stanford-crypto-aes 129.8032+-1.5508 ? 131.3744+-1.3683 ? might be 1.0121x slower stanford-crypto-ccm 100.6605+-0.3288 ? 101.6856+-0.7074 ? might be 1.0102x slower stanford-crypto-pbkdf2 194.6971+-1.2720 194.3023+-0.5494 stanford-crypto-sha256-iterative 76.9877+-0.3741 76.6157+-0.2952 <arithmetic> * 227.8171+-0.6186 ^ 226.5740+-0.4488 ^ definitely 1.0055x faster <geometric> 177.5602+-0.4815 177.2219+-0.4616 <harmonic> 137.3444+-0.3335 ? 138.1071+-0.5591 ? TipOfTree PolyGetById All benchmarks: <arithmetic> 88.9479+-0.2062 88.5677+-0.1772 <geometric> 23.2671+-0.0911 23.2075+-0.0818 <harmonic> 7.4772+-0.0778 7.4155+-0.0686 TipOfTree PolyGetById Geomean of preferred means: <scaled-result> 53.4525+-0.1159 53.3705+-0.1081
Filip Pizlo
Comment 2 2011-10-02 23:08:51 PDT
Updated numbers. Benchmark report for SunSpider, V8, and Kraken. VMs tested: "TipOfTree" at /Volumes/Data/pizlo/quinary/OpenSource/WebKitBuild/Release/jsc "PolyGetById" at /Volumes/Data/pizlo/senary/OpenSource/WebKitBuild/Release/jsc Collected 30 samples per benchmark/VM, with 10 VM invocations per benchmark. 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. TipOfTree PolyGetById SunSpider: 3d-cube 7.4617+-0.1034 7.4526+-0.1151 3d-morph 7.4606+-0.0887 7.4365+-0.0834 3d-raytrace 8.2420+-0.1147 ^ 7.7820+-0.1234 ^ definitely 1.0591x faster access-binary-trees 1.7895+-0.0448 ? 1.7961+-0.0455 ? access-fannkuch 6.3124+-0.0547 ? 6.3763+-0.0769 ? might be 1.0101x slower access-nbody 3.5895+-0.0703 3.5023+-0.0547 might be 1.0249x faster access-nsieve 2.6121+-0.0409 ? 2.6302+-0.0403 ? bitops-3bit-bits-in-byte 1.7307+-0.0198 ? 1.7413+-0.0154 ? bitops-bits-in-byte 2.7374+-0.0427 ? 2.7884+-0.0551 ? might be 1.0187x slower bitops-bitwise-and 3.2574+-0.0601 3.2269+-0.0450 bitops-nsieve-bits 5.4171+-0.0626 ? 5.4872+-0.0837 ? might be 1.0129x slower controlflow-recursive 2.0842+-0.0298 ? 2.0907+-0.0324 ? crypto-aes 6.8417+-0.1346 6.7743+-0.1371 crypto-md5 2.8669+-0.0543 2.8525+-0.0602 crypto-sha1 2.5060+-0.0458 2.5034+-0.0418 date-format-tofte 10.1911+-0.1981 9.9102+-0.1504 might be 1.0284x faster date-format-xparb 9.4119+-0.1436 9.3752+-0.1469 math-cordic 6.2322+-0.0542 ? 6.2370+-0.0557 ? math-partial-sums 7.5658+-0.0878 7.5025+-0.0732 math-spectral-norm 2.8764+-0.0392 2.8682+-0.0580 regexp-dna 10.9170+-0.0949 ? 10.9202+-0.1689 ? string-base64 5.6590+-0.0913 5.6038+-0.1394 string-fasta 6.6458+-0.0872 ? 6.6492+-0.1068 ? string-tagcloud 11.8912+-0.1948 ? 12.0330+-0.2048 ? might be 1.0119x slower string-unpack-code 21.3281+-0.2824 21.1507+-0.2839 string-validate-input 6.3290+-0.1368 6.3204+-0.0888 <arithmetic> * 6.3060+-0.0137 6.2697+-0.0253 <geometric> 5.1665+-0.0136 5.1465+-0.0210 <harmonic> 4.2350+-0.0197 4.2296+-0.0251 TipOfTree PolyGetById V8: crypto 72.1259+-0.2271 ? 72.2060+-0.3149 ? deltablue 225.0479+-1.0014 ? 226.4046+-1.0914 ? earley-boyer 87.5991+-0.1713 ? 87.6375+-0.2942 ? raytrace 61.4064+-0.2985 61.3754+-0.3465 regexp 104.0808+-0.4639 103.7140+-0.3796 richards 186.9374+-0.5667 186.4882+-0.5270 splay 91.2943+-0.3209 91.2434+-0.3609 <arithmetic> 118.3560+-0.1797 ? 118.4385+-0.2442 ? <geometric> * 106.4654+-0.1328 ? 106.4734+-0.2054 ? <harmonic> 97.3225+-0.1318 97.3019+-0.2024 TipOfTree PolyGetById Kraken: ai-astar 492.7137+-2.1612 ^ 488.8511+-1.3972 ^ definitely 1.0079x faster audio-beat-detection 192.8215+-1.4299 ^ 190.6301+-0.5796 ^ definitely 1.0115x faster audio-dft 278.8327+-1.5564 ^ 271.9584+-1.7589 ^ definitely 1.0253x faster audio-fft 128.4893+-0.7137 ? 128.5923+-0.6978 ? audio-oscillator 257.6952+-1.4953 ^ 246.6424+-0.9898 ^ definitely 1.0448x faster imaging-darkroom 420.0356+-1.3004 419.9649+-1.3683 imaging-desaturate 225.0034+-0.9091 223.9795+-0.4624 imaging-gaussian-blur 582.8256+-1.7895 581.5096+-1.4356 json-parse-financial 49.2039+-0.2322 48.9254+-0.2208 json-stringify-tinderbox 68.1326+-0.2636 ! 68.9949+-0.2137 ! definitely 1.0127x slower stanford-crypto-aes 130.5265+-1.0122 130.4759+-1.3555 stanford-crypto-ccm 102.2631+-0.5399 ^ 100.8593+-0.3557 ^ definitely 1.0139x faster stanford-crypto-pbkdf2 195.9558+-1.1230 193.9616+-1.0843 might be 1.0103x faster stanford-crypto-sha256-iterative 77.5329+-0.3205 77.4402+-0.5185 <arithmetic> * 228.7166+-0.3183 ^ 226.6275+-0.3175 ^ definitely 1.0092x faster <geometric> 178.2956+-0.2542 ^ 176.8639+-0.3042 ^ definitely 1.0081x faster <harmonic> 137.9784+-0.2156 ^ 137.3059+-0.2782 ^ definitely 1.0049x faster TipOfTree PolyGetById All benchmarks: <arithmetic> 89.2443+-0.0906 ^ 88.6142+-0.1108 ^ definitely 1.0071x faster <geometric> 23.2815+-0.0377 ^ 23.1759+-0.0602 ^ definitely 1.0046x faster <harmonic> 7.4452+-0.0338 7.4355+-0.0430 TipOfTree PolyGetById Geomean of preferred means: <scaled-result> 53.5489+-0.0465 ^ 53.2835+-0.0919 ^ definitely 1.0050x faster
Filip Pizlo
Comment 3 2011-10-02 23:13:10 PDT
Created attachment 109441 [details] the patch
WebKit Review Bot
Comment 4 2011-10-02 23:15:17 PDT
Attachment 109441 [details] did not pass style-queue: Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/ChangeLog', u'Source..." exit_code: 1 Source/JavaScriptCore/dfg/DFGStructureSet.h:67: More than one command on the same line in if [whitespace/parens] [4] Source/JavaScriptCore/bytecode/Instruction.h:74: _stubRoutine is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:74: _base is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:83: _stubRoutine is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:83: _base is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:83: _proto is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:92: _stubRoutine is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:92: _base is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:92: _chain is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/dfg/DFGGraph.h:333: Place brace on its own line for function definitions. [whitespace/braces] [4] Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:1202: Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons. [readability/comparison_to_zero] [5] Total errors found: 11 in 15 files If any of these errors are false positives, please file a bug against check-webkit-style.
Filip Pizlo
Comment 5 2011-10-02 23:18:11 PDT
Created attachment 109442 [details] the patch - fix style, mostly I didn't fix all of the style errors in Instruction.h, but I "avoided" the preexisting problem by using "this->x = x" instead of "x = _x".
WebKit Review Bot
Comment 6 2011-10-02 23:20:45 PDT
Attachment 109442 [details] did not pass style-queue: Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/ChangeLog', u'Source..." exit_code: 1 Source/JavaScriptCore/bytecode/Instruction.h:74: _stubRoutine is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:74: _base is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:83: _stubRoutine is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:83: _base is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:83: _proto is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:92: _stubRoutine is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:92: _base is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:92: _chain is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Total errors found: 8 in 15 files If any of these errors are false positives, please file a bug against check-webkit-style.
Early Warning System Bot
Comment 7 2011-10-02 23:26:44 PDT
Comment on attachment 109442 [details] the patch - fix style, mostly Attachment 109442 [details] did not pass qt-ews (qt): Output: http://queues.webkit.org/results/9900974
Filip Pizlo
Comment 8 2011-10-02 23:46:03 PDT
Created attachment 109443 [details] the patch - added some forgotten 32-bit stuff
WebKit Review Bot
Comment 9 2011-10-02 23:48:17 PDT
Attachment 109443 [details] did not pass style-queue: Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/ChangeLog', u'Source..." exit_code: 1 Source/JavaScriptCore/bytecode/Instruction.h:74: _stubRoutine is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:74: _base is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:83: _stubRoutine is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:83: _base is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:83: _proto is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:92: _stubRoutine is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:92: _base is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Source/JavaScriptCore/bytecode/Instruction.h:92: _chain is incorrectly named. Don't use underscores in your identifier names. [readability/naming] [4] Total errors found: 8 in 16 files If any of these errors are false positives, please file a bug against check-webkit-style.
Filip Pizlo
Comment 10 2011-10-03 12:24:47 PDT
Landed in r96527.
Joseph Pecoraro
Comment 11 2011-10-03 14:45:59 PDT
On ToT r96537 I'm seeing an ASSERT when opening the web inspector: ASSERTION FAILED: !contains(structure) /Volumes/Data/Code/webkit-open-source/Source/JavaScriptCore/dfg/DFGStructureSet.h(48) : void JSC::DFG::StructureSet::add(JSC::Structure *) 1 JSC::DFG::StructureSet::add(JSC::Structure*) 2 JSC::DFG::ByteCodeParser::parseBlock(unsigned int) 3 JSC::DFG::ByteCodeParser::parse() 4 JSC::DFG::parse(JSC::DFG::Graph&, JSC::JSGlobalData*, JSC::CodeBlock*) 5 JSC::DFG::compile(JSC::DFG::CompileMode, JSC::ExecState*, JSC::ExecState*, JSC::CodeBlock*, JSC::JITCode&, JSC::MacroAssemblerCodePtr*) 6 JSC::DFG::tryCompileFunction(JSC::ExecState*, JSC::ExecState*, JSC::CodeBlock*, JSC::JITCode&, JSC::MacroAssemblerCodePtr&) 7 JSC::FunctionExecutable::compileForCallInternal(JSC::ExecState*, JSC::ScopeChainNode*, JSC::ExecState*, JSC::JITCode::JITType) 8 JSC::FunctionExecutable::compileOptimizedForCall(JSC::ExecState*, JSC::ScopeChainNode*, JSC::ExecState*) 9 JSC::FunctionExecutable::compileOptimizedFor(JSC::ExecState*, JSC::ScopeChainNode*, JSC::CodeSpecializationKind) 10 JSC::FunctionCodeBlock::compileOptimized(JSC::ExecState*, JSC::ScopeChainNode*) 11 cti_optimize_from_ret 12 jscGeneratedNativeCode 13 JSC::JITCode::execute(JSC::RegisterFile*, JSC::ExecState*, JSC::JSGlobalData*) 14 JSC::Interpreter::executeCall(JSC::ExecState*, JSC::JSObject*, JSC::CallType, JSC::CallData const&, JSC::JSValue, JSC::ArgList const&) 15 JSC::call(JSC::ExecState*, JSC::JSValue, JSC::CallType, JSC::CallData const&, JSC::JSValue, JSC::ArgList const&) 16 JSC::JSObject::put(JSC::ExecState*, JSC::Identifier const&, JSC::JSValue, JSC::PutPropertySlot&) 17 JSC::JSValue::put(JSC::ExecState*, JSC::Identifier const&, JSC::JSValue, JSC::PutPropertySlot&) 18 cti_op_put_by_id_generic 19 jscGeneratedNativeCode 20 JSC::JITCode::execute(JSC::RegisterFile*, JSC::ExecState*, JSC::JSGlobalData*) 21 JSC::Interpreter::executeCall(JSC::ExecState*, JSC::JSObject*, JSC::CallType, JSC::CallData const&, JSC::JSValue, JSC::ArgList const&) 22 JSC::call(JSC::ExecState*, JSC::JSValue, JSC::CallType, JSC::CallData const&, JSC::JSValue, JSC::ArgList const&) 23 JSC::JSObject::put(JSC::ExecState*, JSC::Identifier const&, JSC::JSValue, JSC::PutPropertySlot&) 24 JSC::JSValue::put(JSC::ExecState*, JSC::Identifier const&, JSC::JSValue, JSC::PutPropertySlot&) 25 cti_op_put_by_id 26 jscGeneratedNativeCode 27 JSC::JITCode::execute(JSC::RegisterFile*, JSC::ExecState*, JSC::JSGlobalData*) 28 JSC::Interpreter::executeCall(JSC::ExecState*, JSC::JSObject*, JSC::CallType, JSC::CallData const&, JSC::JSValue, JSC::ArgList const&) 29 JSC::call(JSC::ExecState*, JSC::JSValue, JSC::CallType, JSC::CallData const&, JSC::JSValue, JSC::ArgList const&) 30 WebCore::JSMainThreadExecState::call(JSC::ExecState*, JSC::JSValue, JSC::CallType, JSC::CallData const&, JSC::JSValue, JSC::ArgList const&) 31 WebCore::ScheduledAction::executeFunctionInContext(JSC::JSGlobalObject*, JSC::JSValue, WebCore::ScriptExecutionContext*)
Joseph Pecoraro
Comment 12 2011-10-03 14:52:44 PDT
(In reply to comment #11) > On ToT r96537 I'm seeing an ASSERT when opening the web inspector: I opened bug 69293 and CC'd a number of JSC folks.
Note You need to log in before you can comment on or make changes to this bug.