Bug 66363

Summary:

The executable allocator makes it difficult to free individual chunks of executable memory

Product:

WebKit

Reporter:

Filip Pizlo <fpizlo>

Component:

JavaScriptCore

Assignee:

Nobody <webkit-unassigned>

Status:

RESOLVED FIXED

Severity:

Normal

CC:

abecsi, barraclough, cmarcelo, fpizlo, ggaren, gustavo.noronha, gustavo, oliver, ossy, simophin, webkit.review.bot, xan.lopez, yong.li.webkit

Priority:

Version:

528+ (Nightly build)

Hardware:

All

OS:

All

Attachments:

Description	Flags
work in progress	webkit-ews: commit-queue-
work in progress - 32-bit works	webkit-ews: commit-queue-
work in progress - fix style, fix more platforms	none
work in progress - fix conflicts	none
work in progress - fix more style	gyuyoung.kim: commit-queue-
the patch - fix style, conflicts, architectures	gyuyoung.kim: commit-queue-
the patch - fix more style, build systems	none
the patch - changed unit tests to use TestWebKitAPI	none
the patch - fix conflicts	none
the patch - fix minor export file glitch	none
the patch - remove stray debug printf	none
the patch - added forgotten files	none
the patch - replaced the red black tree with one based on PODRedBlackTree	none
the patch - fix style	oliver: review+, fpizlo: commit-queue-

Filip Pizlo

Reported 2011-08-16 23:40:29 PDT

Executable memory is allocated in pools. Multiple separate allocations, with separate life-times, may be allocated in one pool. The pool will stay alive as long as any of the allocations within it are alive. This may lead to wasted memory, and precludes certain kinds of stub reallocation - for example if we allowed heap access stubs to be invalidated and allocated new ones, then doing so repeatedly may cause us to ultimately run out of memory. The executable memory allocator should allow for individual chunks to be freed and reused.

Attachments
work in progress (179.06 KB, patch) 2011-08-17 16:49 PDT, Filip Pizlo	webkit-ews: commit-queue-	Details Formatted Diff Diff
work in progress - 32-bit works (222.33 KB, patch) 2011-08-18 15:34 PDT, Filip Pizlo	webkit-ews: commit-queue-	Details Formatted Diff Diff
work in progress - fix style, fix more platforms (223.01 KB, patch) 2011-08-26 14:17 PDT, Filip Pizlo	no flags	Details Formatted Diff Diff
work in progress - fix conflicts (223.07 KB, patch) 2011-08-26 14:34 PDT, Filip Pizlo	no flags	Details Formatted Diff Diff
work in progress - fix more style (222.96 KB, patch) 2011-08-26 14:45 PDT, Filip Pizlo	gyuyoung.kim: commit-queue-	Details Formatted Diff Diff
the patch - fix style, conflicts, architectures (222.85 KB, patch) 2011-08-30 14:01 PDT, Filip Pizlo	gyuyoung.kim: commit-queue-	Details Formatted Diff Diff
the patch - fix more style, build systems (224.39 KB, patch) 2011-08-30 20:14 PDT, Filip Pizlo	no flags	Details Formatted Diff Diff
the patch - changed unit tests to use TestWebKitAPI (220.19 KB, patch) 2011-09-01 15:45 PDT, Filip Pizlo	no flags	Details Formatted Diff Diff
the patch - fix conflicts (220.28 KB, patch) 2011-09-01 15:57 PDT, Filip Pizlo	no flags	Details Formatted Diff Diff
the patch - fix minor export file glitch (220.22 KB, patch) 2011-09-01 16:45 PDT, Filip Pizlo	no flags	Details Formatted Diff Diff
the patch - remove stray debug printf (220.04 KB, patch) 2011-09-01 16:50 PDT, Filip Pizlo	no flags	Details Formatted Diff Diff
the patch - added forgotten files (222.00 KB, patch) 2011-09-01 18:35 PDT, Filip Pizlo	no flags	Details Formatted Diff Diff
the patch - replaced the red black tree with one based on PODRedBlackTree (222.20 KB, patch) 2011-09-08 23:06 PDT, Filip Pizlo	no flags	Details Formatted Diff Diff
the patch - fix style (222.07 KB, patch) 2011-09-08 23:13 PDT, Filip Pizlo	oliver: review+ fpizlo: commit-queue-	Details Formatted Diff Diff
Show Obsolete (13) View All Add attachment proposed patch, testcase, etc.

Filip Pizlo

Comment 1 2011-08-16 23:40:43 PDT

*** Bug 66203 has been marked as a duplicate of this bug. ***

Filip Pizlo

Comment 2 2011-08-16 23:48:28 PDT

Current performance impact of a best-fit allocator: Benchmark report for SunSpider, V8, and Kraken. VMs tested: "TipOfTree" at /Volumes/Data/pizlo/quinary/OpenSource/WebKitBuild/Release/jsc "BestFitExecAlloc" at /Volumes/Data/pizlo/senary/OpenSource/WebKitBuild/Release/jsc Collected 45 samples per benchmark/VM, with 15 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 BestFitExecAlloc SunSpider: 3d-cube 7.5848+-0.0895 ? 7.6980+-0.0913 ? might be 1.0149x slower 3d-morph 7.4992+-0.0902 7.4299+-0.0678 3d-raytrace 7.5167+-0.0967 ? 7.6565+-0.0865 ? might be 1.0186x slower access-binary-trees 2.1908+-0.0406 2.1906+-0.0265 access-fannkuch 11.5275+-0.1206 11.4809+-0.1055 access-nbody 4.2683+-0.0597 4.2403+-0.0361 access-nsieve 2.4786+-0.0511 2.4438+-0.0305 might be 1.0142x faster bitops-3bit-bits-in-byte 1.6919+-0.0255 ! 1.7734+-0.0259 ! definitely 1.0481x slower bitops-bits-in-byte 4.1634+-0.0680 ^ 4.0591+-0.0289 ^ definitely 1.0257x faster bitops-bitwise-and 3.5814+-0.0290 ^ 3.4740+-0.0246 ^ definitely 1.0309x faster bitops-nsieve-bits 5.3693+-0.0350 5.3506+-0.0326 controlflow-recursive 2.0457+-0.0223 ^ 1.9956+-0.0266 ^ definitely 1.0251x faster crypto-aes 6.5512+-0.0948 6.4834+-0.0812 might be 1.0105x faster crypto-md5 2.7238+-0.0306 2.7201+-0.0311 crypto-sha1 2.1835+-0.0309 ! 2.2627+-0.0397 ! definitely 1.0363x slower date-format-tofte 9.7838+-0.1275 ? 9.9886+-0.1203 ? might be 1.0209x slower date-format-xparb 8.5392+-0.1422 ? 8.7528+-0.1075 ? might be 1.0250x slower math-cordic 6.2146+-0.0660 6.1621+-0.0641 math-partial-sums 7.5369+-0.0822 7.5212+-0.0997 math-spectral-norm 2.4702+-0.0358 ? 2.4720+-0.0232 ? regexp-dna 10.2566+-0.0865 ! 10.7704+-0.0813 ! definitely 1.0501x slower string-base64 6.0445+-0.1184 5.9681+-0.0809 might be 1.0128x faster string-fasta 7.2674+-0.0775 ? 7.2963+-0.0770 ? string-tagcloud 13.3241+-0.1118 13.3222+-0.1283 string-unpack-code 18.3815+-0.1928 ? 18.5709+-0.1796 ? might be 1.0103x slower string-validate-input 6.9840+-0.1006 ? 6.9874+-0.1120 ? <arithmetic> 6.4684+-0.0138 ! 6.5027+-0.0165 ! definitely 1.0053x slower <geometric> 5.3575+-0.0113 ? 5.3737+-0.0134 ? <harmonic> 4.3735+-0.0149 ? 4.3878+-0.0149 ? TipOfTree BestFitExecAlloc V8: crypto 87.9887+-0.2026 ^ 87.4986+-0.2128 ^ definitely 1.0056x faster deltablue 261.7402+-0.7046 ! 264.2305+-0.9393 ! definitely 1.0095x slower earley-boyer 99.9972+-0.2294 99.6741+-0.1972 raytrace 76.4790+-0.3443 ^ 75.8491+-0.1981 ^ definitely 1.0083x faster regexp 107.5038+-0.2056 ^ 105.7876+-0.1971 ^ definitely 1.0162x faster richards 248.0936+-0.3812 ^ 238.6467+-0.3379 ^ definitely 1.0396x faster splay 108.0297+-0.3112 107.4892+-0.3354 <arithmetic> 141.4046+-0.1320 ^ 139.8823+-0.1787 ^ definitely 1.0109x faster <geometric> 126.1123+-0.1141 ^ 124.9021+-0.1382 ^ definitely 1.0097x faster <harmonic> 115.0262+-0.1278 ^ 114.0441+-0.1267 ^ definitely 1.0086x faster TipOfTree BestFitExecAlloc Kraken: ai-astar 1081.4993+-3.1740 ? 1083.8513+-3.7182 ? audio-beat-detection 453.1965+-1.4023 ^ 447.1013+-0.6723 ^ definitely 1.0136x faster audio-dft 411.1923+-3.7095 ? 412.7745+-2.2890 ? audio-fft 356.4072+-1.5136 354.6045+-0.9395 audio-oscillator 378.4706+-0.4562 ! 380.7842+-1.1168 ! definitely 1.0061x slower imaging-darkroom 590.5360+-2.1499 ^ 565.1859+-1.3840 ^ definitely 1.0449x faster imaging-desaturate 586.5267+-1.2839 ? 586.9413+-1.2455 ? imaging-gaussian-blur 1711.9912+-5.0103 ^ 1697.7598+-1.8843 ^ definitely 1.0084x faster json-parse-financial 48.0579+-0.1204 ^ 47.4060+-0.1959 ^ definitely 1.0138x faster json-stringify-tinderbox 62.0471+-0.3300 ^ 60.8928+-0.1510 ^ definitely 1.0190x faster stanford-crypto-aes 140.7944+-0.2706 ! 141.8431+-0.4629 ! definitely 1.0074x slower stanford-crypto-ccm 110.3081+-0.5687 110.2512+-0.3872 stanford-crypto-pbkdf2 367.4630+-1.4301 365.7738+-2.9701 stanford-crypto-sha256-iterative 138.3388+-0.4035 ? 138.6526+-0.2152 ? <arithmetic> 459.7735+-0.5107 ^ 456.7016+-0.4367 ^ definitely 1.0067x faster <geometric> 295.0588+-0.3691 ^ 293.2588+-0.3174 ^ definitely 1.0061x faster <harmonic> 179.3775+-0.3080 ^ 177.9309+-0.2398 ^ definitely 1.0081x faster TipOfTree BestFitExecAlloc All benchmarks: <arithmetic> 161.5923+-0.1607 ^ 160.4695+-0.1357 ^ definitely 1.0070x faster <geometric> 28.3039+-0.0368 28.2591+-0.0404 <harmonic> 7.7255+-0.0258 ? 7.7486+-0.0256 ?

Filip Pizlo

Comment 3 2011-08-17 16:49:19 PDT

Created attachment 104283 [details] work in progress Works on x86_64, not on anything else, yet. Putting it up in case someone wants to look at it before it's done.

WebKit Review Bot

Comment 4 2011-08-17 16:51:21 PDT

Attachment 104283 [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 Last 3072 characters of output: 15: Should have a space between // and comment [whitespace/comments] [4] Source/JavaScriptCore/wtf/MetaAllocator.cpp:418: Should have a space between // and comment [whitespace/comments] [4] Source/JavaScriptCore/wtf/MetaAllocator.cpp:421: Should have a space between // and comment [whitespace/comments] [4] Source/JavaScriptCore/wtf/MetaAllocator.h:34: Alphabetical sorting problem. [build/include_order] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:38: Alphabetical sorting problem. [build/include_order] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:45: Should have only a single space after a punctuation in a comment. [whitespace/comments] [5] Source/JavaScriptCore/wtf/RedBlackTree.h:161: One line control clauses should not use braces. [whitespace/braces] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:164: One line control clauses should not use braces. [whitespace/braces] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:166: One line control clauses should not use braces. [whitespace/braces] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:171: More than one command on the same line in if [whitespace/parens] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:180: One line control clauses should not use braces. [whitespace/braces] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:182: One line control clauses should not use braces. [whitespace/braces] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:184: More than one command on the same line in if [whitespace/parens] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:185: One line control clauses should not use braces. [whitespace/braces] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:235: One line control clauses should not use braces. [whitespace/braces] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:232: An else statement can be removed when the prior "if" concludes with a return, break, continue or goto statement. [readability/control_flow] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:240: More than one command on the same line in if [whitespace/parens] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:353: Missing space before ( in if( [whitespace/parens] [5] Source/JavaScriptCore/wtf/RedBlackTree.h:353: Extra space after ( in if [whitespace/parens] [5] Source/JavaScriptCore/wtf/RedBlackTree.h:374: Missing space before ( in if( [whitespace/parens] [5] Source/JavaScriptCore/wtf/RedBlackTree.h:374: Extra space after ( in if [whitespace/parens] [5] Source/JavaScriptCore/wtf/RedBlackTree.h:415: One line control clauses should not use braces. [whitespace/braces] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:412: An else statement can be removed when the prior "if" concludes with a return, break, continue or goto statement. [readability/control_flow] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:423: More than one command on the same line in if [whitespace/parens] [4] Source/JavaScriptCore/wtf/MetaAllocatorHandle.h:42: The parameter name "allocator" adds no information, so it should be removed. [readability/parameter_name] [5] Total errors found: 75 in 40 files If any of these errors are false positives, please file a bug against check-webkit-style.

Early Warning System Bot

Comment 5 2011-08-17 17:06:29 PDT

Comment on attachment 104283 [details] work in progress Attachment 104283 [details] did not pass qt-ews (qt): Output: http://queues.webkit.org/results/9420234

Gyuyoung Kim

Comment 6 2011-08-17 17:26:03 PDT

Comment on attachment 104283 [details] work in progress Attachment 104283 [details] did not pass efl-ews (efl): Output: http://queues.webkit.org/results/9422267

Gustavo Noronha (kov)

Comment 7 2011-08-17 18:44:38 PDT

Comment on attachment 104283 [details] work in progress Attachment 104283 [details] did not pass gtk-ews (gtk): Output: http://queues.webkit.org/results/9423235

Filip Pizlo

Comment 8 2011-08-17 18:56:50 PDT

This is the performance when right-allocation is enabled. This produces sub-optimal code layout as it's possible for two things allocated consecutively to lie on opposite sides of the heap. But, it minimizes the number of pages in use. It's not clear if this is a win, or not. Benchmark report for SunSpider, V8, and Kraken. VMs tested: "TipOfTree" at /Volumes/Data/pizlo/quinary/OpenSource/WebKitBuild/Release/jsc "BestFitExecAlloc" at /Volumes/Data/pizlo/senary/OpenSource/WebKitBuild/Release/jsc Collected 45 samples per benchmark/VM, with 15 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 BestFitExecAlloc SunSpider: 3d-cube 7.5292+-0.0860 ? 7.6575+-0.0832 ? might be 1.0171x slower 3d-morph 7.4882+-0.0696 7.4571+-0.0709 3d-raytrace 7.6368+-0.0993 7.5628+-0.0799 access-binary-trees 2.2285+-0.0342 2.1824+-0.0182 might be 1.0211x faster access-fannkuch 11.4710+-0.1021 11.3988+-0.0922 access-nbody 4.1968+-0.0381 ? 4.2456+-0.0731 ? might be 1.0116x slower access-nsieve 2.4720+-0.0354 2.4574+-0.0371 bitops-3bit-bits-in-byte 1.7080+-0.0368 ? 1.7586+-0.0251 ? might be 1.0296x slower bitops-bits-in-byte 4.1622+-0.0615 ! 4.4769+-0.0770 ! definitely 1.0756x slower bitops-bitwise-and 3.6113+-0.0459 3.5752+-0.0413 might be 1.0101x faster bitops-nsieve-bits 5.4251+-0.0643 ? 5.4367+-0.0533 ? controlflow-recursive 2.0054+-0.0202 1.9957+-0.0266 crypto-aes 6.5658+-0.0766 6.5456+-0.0811 crypto-md5 2.7402+-0.0324 2.7273+-0.0247 crypto-sha1 2.1952+-0.0228 ? 2.2520+-0.0423 ? might be 1.0259x slower date-format-tofte 9.9693+-0.1228 ? 10.1310+-0.1342 ? might be 1.0162x slower date-format-xparb 8.5465+-0.1080 ? 8.6580+-0.1145 ? might be 1.0130x slower math-cordic 6.2492+-0.0529 ? 6.2668+-0.0624 ? math-partial-sums 7.5516+-0.0834 ? 7.5654+-0.0807 ? math-spectral-norm 2.5182+-0.0329 2.4926+-0.0309 might be 1.0103x faster regexp-dna 10.2535+-0.0721 ! 10.8177+-0.0894 ! definitely 1.0550x slower string-base64 6.0013+-0.0908 ? 6.0495+-0.0992 ? string-fasta 7.3581+-0.0810 7.3069+-0.0761 string-tagcloud 13.3322+-0.1478 ? 13.4441+-0.1326 ? string-unpack-code 18.3448+-0.1520 ? 18.6119+-0.1853 ? might be 1.0146x slower string-validate-input 7.0115+-0.1431 ? 7.0499+-0.1044 ? <arithmetic> 6.4835+-0.0143 ! 6.5432+-0.0165 ! definitely 1.0092x slower <geometric> 5.3735+-0.0131 ! 5.4140+-0.0135 ! definitely 1.0075x slower <harmonic> 4.3890+-0.0166 ? 4.4165+-0.0144 ? TipOfTree BestFitExecAlloc V8: crypto 88.3855+-0.2304 88.0580+-0.3105 deltablue 262.9253+-1.2663 ? 263.8095+-0.6202 ? earley-boyer 100.0719+-0.2928 ? 100.3218+-0.2207 ? raytrace 75.9575+-0.2486 75.4541+-0.3980 regexp 108.7350+-0.5273 ^ 107.2281+-0.4855 ^ definitely 1.0141x faster richards 251.9579+-1.0113 ^ 241.2311+-1.2318 ^ definitely 1.0445x faster splay 108.6511+-0.3619 107.9194+-0.4180 <arithmetic> 142.3834+-0.2936 ^ 140.5746+-0.2242 ^ definitely 1.0129x faster <geometric> 126.7503+-0.2138 ^ 125.5102+-0.1853 ^ definitely 1.0099x faster <harmonic> 115.4135+-0.1802 ^ 114.5392+-0.1817 ^ definitely 1.0076x faster TipOfTree BestFitExecAlloc Kraken: ai-astar 1083.0171+-3.6911 1081.3665+-3.2078 audio-beat-detection 457.3596+-1.1298 ^ 454.2206+-1.4376 ^ definitely 1.0069x faster audio-dft 413.2815+-2.8334 ? 416.3008+-2.3072 ? audio-fft 357.1645+-1.2802 356.8773+-1.0993 audio-oscillator 378.9674+-1.0617 ! 381.9522+-1.1016 ! definitely 1.0079x slower imaging-darkroom 575.5395+-2.2349 ! 609.5229+-3.0018 ! definitely 1.0590x slower imaging-desaturate 592.2349+-2.9636 ? 593.5229+-1.6949 ? imaging-gaussian-blur 1716.1634+-3.0601 1710.2664+-4.5857 json-parse-financial 48.2717+-0.1376 ? 48.3075+-0.1697 ? json-stringify-tinderbox 61.8694+-0.1754 61.5657+-0.2802 stanford-crypto-aes 141.7960+-0.3397 ! 142.6480+-0.3741 ! definitely 1.0060x slower stanford-crypto-ccm 110.2550+-0.2987 ? 110.4126+-0.2987 ? stanford-crypto-pbkdf2 364.9750+-1.1447 ? 370.8834+-5.3735 ? might be 1.0162x slower stanford-crypto-sha256-iterative 137.8285+-0.3687 ! 138.7276+-0.2695 ! definitely 1.0065x slower <arithmetic> 459.9088+-0.5808 ! 462.6125+-0.6659 ! definitely 1.0059x slower <geometric> 295.1312+-0.3490 ! 296.9687+-0.4547 ! definitely 1.0062x slower <harmonic> 179.5327+-0.2189 ? 179.9774+-0.2983 ? TipOfTree BestFitExecAlloc All benchmarks: <arithmetic> 161.7868+-0.1712 ! 162.3557+-0.2025 ! definitely 1.0035x slower <geometric> 28.3740+-0.0410 ! 28.5031+-0.0414 ! definitely 1.0046x slower <harmonic> 7.7524+-0.0288 ? 7.7995+-0.0248 ?

Filip Pizlo

Comment 9 2011-08-18 15:34:53 PDT

Created attachment 104411 [details] work in progress - 32-bit works 32-bit support added. But, this is still only tested on x86.

WebKit Review Bot

Comment 10 2011-08-18 15:37:42 PDT

Attachment 104411 [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 Last 3072 characters of output: space between // and comment [whitespace/comments] [4] Source/JavaScriptCore/wtf/MetaAllocator.cpp:422: Should have a space between // and comment [whitespace/comments] [4] Source/JavaScriptCore/wtf/MetaAllocator.h:34: Alphabetical sorting problem. [build/include_order] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:38: Alphabetical sorting problem. [build/include_order] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:45: Should have only a single space after a punctuation in a comment. [whitespace/comments] [5] Source/JavaScriptCore/wtf/RedBlackTree.h:161: One line control clauses should not use braces. [whitespace/braces] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:164: One line control clauses should not use braces. [whitespace/braces] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:166: One line control clauses should not use braces. [whitespace/braces] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:171: More than one command on the same line in if [whitespace/parens] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:180: One line control clauses should not use braces. [whitespace/braces] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:182: One line control clauses should not use braces. [whitespace/braces] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:184: More than one command on the same line in if [whitespace/parens] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:185: One line control clauses should not use braces. [whitespace/braces] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:235: One line control clauses should not use braces. [whitespace/braces] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:232: An else statement can be removed when the prior "if" concludes with a return, break, continue or goto statement. [readability/control_flow] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:240: More than one command on the same line in if [whitespace/parens] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:353: Missing space before ( in if( [whitespace/parens] [5] Source/JavaScriptCore/wtf/RedBlackTree.h:353: Extra space after ( in if [whitespace/parens] [5] Source/JavaScriptCore/wtf/RedBlackTree.h:374: Missing space before ( in if( [whitespace/parens] [5] Source/JavaScriptCore/wtf/RedBlackTree.h:374: Extra space after ( in if [whitespace/parens] [5] Source/JavaScriptCore/wtf/RedBlackTree.h:415: One line control clauses should not use braces. [whitespace/braces] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:412: An else statement can be removed when the prior "if" concludes with a return, break, continue or goto statement. [readability/control_flow] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:423: More than one command on the same line in if [whitespace/parens] [4] Source/JavaScriptCore/jit/JITOpcodes32_64.cpp:43: The parameter type should use PassRefPtr instead of RefPtr. [readability/pass_ptr] [5] Source/JavaScriptCore/wtf/MetaAllocatorHandle.h:42: The parameter name "allocator" adds no information, so it should be removed. [readability/parameter_name] [5] Total errors found: 76 in 42 files If any of these errors are false positives, please file a bug against check-webkit-style.

Early Warning System Bot

Comment 11 2011-08-18 15:57:48 PDT

Comment on attachment 104411 [details] work in progress - 32-bit works Attachment 104411 [details] did not pass qt-ews (qt): Output: http://queues.webkit.org/results/9422952

Gyuyoung Kim

Comment 12 2011-08-18 16:02:03 PDT

Comment on attachment 104411 [details] work in progress - 32-bit works Attachment 104411 [details] did not pass efl-ews (efl): Output: http://queues.webkit.org/results/9422954

Collabora GTK+ EWS bot

Comment 13 2011-08-18 17:05:04 PDT

Comment on attachment 104411 [details] work in progress - 32-bit works Attachment 104411 [details] did not pass gtk-ews (gtk): Output: http://queues.webkit.org/results/9420874

Filip Pizlo

Comment 14 2011-08-26 14:17:20 PDT

Created attachment 105406 [details] work in progress - fix style, fix more platforms

Filip Pizlo

Comment 15 2011-08-26 14:34:38 PDT

Created attachment 105409 [details] work in progress - fix conflicts

WebKit Review Bot

Comment 16 2011-08-26 14:38:58 PDT

Attachment 105409 [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/assembler/AssemblerBuffer.h:33: Alphabetical sorting problem. [build/include_order] [4] Source/JavaScriptCore/runtime/InitializeThreading.cpp:33: Alphabetical sorting problem. [build/include_order] [4] Source/JavaScriptCore/jit/JITOpcodes.cpp:45: The parameter type should use PassRefPtr instead of RefPtr. [readability/pass_ptr] [5] Source/JavaScriptCore/jit/JIT.h:224: The parameter type should use PassRefPtr instead of RefPtr. [readability/pass_ptr] [5] Source/JavaScriptCore/jit/JIT.h:277: The parameter type should use PassRefPtr instead of RefPtr. [readability/pass_ptr] [5] Source/JavaScriptCore/jit/JIT.h:1037: The parameter name "globalData" adds no information, so it should be removed. [readability/parameter_name] [5] Source/JavaScriptCore/wtf/MetaAllocator.cpp:282: Should have only a single space after a punctuation in a comment. [whitespace/comments] [5] Source/JavaScriptCore/wtf/MetaAllocator.cpp:300: Should have only a single space after a punctuation in a comment. [whitespace/comments] [5] Source/JavaScriptCore/wtf/RedBlackTree.h:159: One line control clauses should not use braces. [whitespace/braces] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:230: An else statement can be removed when the prior "if" concludes with a return, break, continue or goto statement. [readability/control_flow] [4] Source/JavaScriptCore/wtf/RedBlackTree.h:410: An else statement can be removed when the prior "if" concludes with a return, break, continue or goto statement. [readability/control_flow] [4] Source/JavaScriptCore/jit/JITOpcodes32_64.cpp:43: The parameter type should use PassRefPtr instead of RefPtr. [readability/pass_ptr] [5] Total errors found: 12 in 45 files If any of these errors are false positives, please file a bug against check-webkit-style.

Filip Pizlo

Comment 17 2011-08-26 14:45:06 PDT

Created attachment 105411 [details] work in progress - fix more style

WebKit Review Bot

Comment 18 2011-08-26 14:48:19 PDT

Attachment 105411 [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/jit/JITOpcodes.cpp:45: The parameter type should use PassRefPtr instead of RefPtr. [readability/pass_ptr] [5] Source/JavaScriptCore/jit/JIT.h:224: The parameter type should use PassRefPtr instead of RefPtr. [readability/pass_ptr] [5] Source/JavaScriptCore/jit/JIT.h:277: The parameter type should use PassRefPtr instead of RefPtr. [readability/pass_ptr] [5] Source/JavaScriptCore/jit/JITOpcodes32_64.cpp:43: The parameter type should use PassRefPtr instead of RefPtr. [readability/pass_ptr] [5] Total errors found: 4 in 45 files If any of these errors are false positives, please file a bug against check-webkit-style.

Gyuyoung Kim

Comment 19 2011-08-26 15:47:58 PDT

Comment on attachment 105411 [details] work in progress - fix more style Attachment 105411 [details] did not pass efl-ews (efl): Output: http://queues.webkit.org/results/9548176

Filip Pizlo

Comment 20 2011-08-30 14:01:17 PDT

Created attachment 105689 [details] the patch - fix style, conflicts, architectures

WebKit Review Bot

Comment 21 2011-08-30 14:04:48 PDT

Attachment 105689 [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/jit/JITOpcodes.cpp:45: The parameter type should use PassRefPtr instead of RefPtr. [readability/pass_ptr] [5] Source/JavaScriptCore/jit/JIT.h:224: The parameter type should use PassRefPtr instead of RefPtr. [readability/pass_ptr] [5] Source/JavaScriptCore/jit/JIT.h:277: The parameter type should use PassRefPtr instead of RefPtr. [readability/pass_ptr] [5] Source/JavaScriptCore/jit/JITOpcodes32_64.cpp:43: The parameter type should use PassRefPtr instead of RefPtr. [readability/pass_ptr] [5] Total errors found: 4 in 45 files If any of these errors are false positives, please file a bug against check-webkit-style.

Gyuyoung Kim

Comment 22 2011-08-30 15:18:48 PDT

Comment on attachment 105689 [details] the patch - fix style, conflicts, architectures Attachment 105689 [details] did not pass efl-ews (efl): Output: http://queues.webkit.org/results/9572343

Filip Pizlo

Comment 23 2011-08-30 20:14:32 PDT

Created attachment 105731 [details] the patch - fix more style, build systems

Filip Pizlo

Comment 24 2011-09-01 15:45:34 PDT

Created attachment 106049 [details] the patch - changed unit tests to use TestWebKitAPI I'm going to let this patch simmer a little and see what the bots think.

Filip Pizlo

Comment 25 2011-09-01 15:57:29 PDT

Created attachment 106052 [details] the patch - fix conflicts

Filip Pizlo

Comment 26 2011-09-01 16:12:19 PDT

Comment on attachment 106052 [details] the patch - fix conflicts After loads of testing I'm happy with it.

Filip Pizlo

Comment 27 2011-09-01 16:21:21 PDT

Latest performance numbers, showing that this patch is neutral. Benchmark report for SunSpider, V8, and Kraken. VMs tested: "TipOfTree" at /Volumes/Data/pizlo/secondary/OpenSource/WebKitBuild/Release/jsc "BestFitExecAlloc" at /Volumes/Data/pizlo/tertiary/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 BestFitExecAlloc SunSpider: 3d-cube 8.2424+-0.0356 ? 8.2941+-0.0292 ? 3d-morph 8.0659+-0.0200 ? 8.1376+-0.0851 ? 3d-raytrace 8.2381+-0.0170 ! 8.3670+-0.0850 ! definitely 1.0156x slower access-binary-trees 2.5637+-0.0336 2.5208+-0.0239 might be 1.0170x faster access-fannkuch 13.0486+-0.0447 ^ 12.8329+-0.0476 ^ definitely 1.0168x faster access-nbody 4.9305+-0.0213 ? 4.9464+-0.0288 ? access-nsieve 3.0600+-0.0291 3.0566+-0.0310 bitops-3bit-bits-in-byte 1.8516+-0.0208 ! 1.9005+-0.0249 ! definitely 1.0264x slower bitops-bits-in-byte 5.6331+-0.1287 5.5657+-0.0209 might be 1.0121x faster bitops-bitwise-and 4.1417+-0.0459 ? 4.2102+-0.0932 ? might be 1.0165x slower bitops-nsieve-bits 5.7831+-0.0797 5.6827+-0.0560 might be 1.0177x faster controlflow-recursive 2.2998+-0.0423 ? 2.3287+-0.0635 ? might be 1.0126x slower crypto-aes 6.8640+-0.0406 ! 6.9435+-0.0383 ! definitely 1.0116x slower crypto-md5 3.0236+-0.0392 2.9972+-0.0279 crypto-sha1 2.4511+-0.0419 ? 2.4783+-0.0371 ? might be 1.0111x slower date-format-tofte 10.8777+-0.1200 ? 10.9595+-0.0560 ? date-format-xparb 9.3314+-0.0875 9.2892+-0.2093 math-cordic 7.1180+-0.0443 ? 7.1882+-0.0626 ? math-partial-sums 10.6896+-0.0236 ^ 10.5578+-0.0480 ^ definitely 1.0125x faster math-spectral-norm 2.7393+-0.0370 ? 2.7547+-0.0309 ? regexp-dna 12.1022+-0.1466 ! 12.6055+-0.1419 ! definitely 1.0416x slower string-base64 6.6552+-0.1049 ^ 6.4306+-0.0807 ^ definitely 1.0349x faster string-fasta 8.3584+-0.0981 8.3379+-0.0566 string-tagcloud 15.2124+-0.1241 ? 15.2881+-0.1190 ? string-unpack-code 20.9977+-0.4226 20.8723+-0.1439 string-validate-input 7.7509+-0.3805 7.6757+-0.2624 <arithmetic> 7.3858+-0.0369 ? 7.3931+-0.0399 ? <geometric> 6.1182+-0.0358 ? 6.1274+-0.0361 ? <harmonic> 4.9912+-0.0384 ? 5.0069+-0.0341 ? TipOfTree BestFitExecAlloc V8: crypto 102.7296+-0.3022 ? 102.8295+-0.2332 ? deltablue 299.1563+-2.1058 ^ 294.9475+-1.9623 ^ definitely 1.0143x faster earley-boyer 123.0179+-0.3984 ^ 121.4325+-0.2348 ^ definitely 1.0131x faster raytrace 87.8618+-0.6554 87.6322+-0.6501 regexp 131.3901+-0.4280 ? 131.9819+-0.5217 ? richards 302.6796+-1.2872 ! 310.3467+-2.1751 ! definitely 1.0253x slower splay 157.2502+-1.0175 ^ 154.8518+-0.7540 ^ definitely 1.0155x faster <arithmetic> 172.0122+-0.3585 172.0032+-0.5608 <geometric> 154.2418+-0.2833 153.9200+-0.4047 <harmonic> 140.3817+-0.3030 139.9424+-0.3581 TipOfTree BestFitExecAlloc Kraken: ai-astar 1668.8221+-17.0049 1651.4330+-20.5277 might be 1.0105x faster audio-beat-detection 538.9581+-2.3437 538.4865+-3.2596 audio-dft 455.6704+-3.1692 451.1725+-6.3277 audio-fft 421.9677+-0.9317 ! 426.7121+-3.5961 ! definitely 1.0112x slower audio-oscillator 403.8282+-0.8881 ! 422.7420+-0.1340 ! definitely 1.0468x slower imaging-darkroom 604.5569+-12.1375 589.1278+-14.8914 might be 1.0262x faster imaging-desaturate 635.8830+-17.4519 ^ 617.3209+-0.1102 ^ definitely 1.0301x faster imaging-gaussian-blur 1851.7010+-3.3110 ^ 1846.8209+-0.9521 ^ definitely 1.0026x faster json-parse-financial 63.0252+-0.2325 ^ 62.2055+-0.5269 ^ definitely 1.0132x faster json-stringify-tinderbox 75.9097+-0.5982 75.8490+-0.5308 stanford-crypto-aes 165.4873+-0.7138 ? 166.3387+-0.5963 ? stanford-crypto-ccm 130.3306+-0.5653 ? 130.5545+-0.9624 ? stanford-crypto-pbkdf2 373.1143+-1.2297 370.9983+-1.2860 stanford-crypto-sha256-iterative 144.4053+-0.1609 144.2738+-0.4925 <arithmetic> 538.1186+-1.8350 535.2883+-1.8512 <geometric> 340.0088+-0.9394 339.1368+-0.7567 <harmonic> 213.3180+-0.5265 212.7214+-0.4355 TipOfTree BestFitExecAlloc All benchmarks: <arithmetic> 189.9952+-0.5480 189.1549+-0.5801 <geometric> 32.7426+-0.1266 32.7344+-0.1028 <harmonic> 8.8268+-0.0667 ? 8.8534+-0.0590 ?

Filip Pizlo

Comment 28 2011-09-01 16:45:00 PDT

Created attachment 106063 [details] the patch - fix minor export file glitch

Filip Pizlo

Comment 29 2011-09-01 16:50:00 PDT

Created attachment 106064 [details] the patch - remove stray debug printf

Filip Pizlo

Comment 30 2011-09-01 18:35:00 PDT

Created attachment 106079 [details] the patch - added forgotten files

Oliver Hunt

Comment 31 2011-09-02 14:48:38 PDT

Comment on attachment 106079 [details] the patch - added forgotten files Okay, this patch basically looks okay, but I'm unsure the licensing is okay -- you're basing some of this code from another source that has already got a license: http://www.mit.edu/~emin/source_code/red_black_tree/LICENSE, so i don't believe you can just plant our our license at the top.

Filip Pizlo

Comment 32 2011-09-02 14:50:12 PDT

(In reply to comment #31) > (From update of attachment 106079 [details]) > Okay, this patch basically looks okay, but I'm unsure the licensing is okay -- you're basing some of this code from another source that has already got a license: http://www.mit.edu/~emin/source_code/red_black_tree/LICENSE, so i don't believe you can just plant our our license at the top. Geoff thought the license was sufficiently compatible that what I did was OK. But what do you recommend? Not use that code, or plant a different statement at the top of the file?

Oliver Hunt

Comment 33 2011-09-02 14:52:01 PDT

(In reply to comment #32) > (In reply to comment #31) > > (From update of attachment 106079 [details] [details]) > > Okay, this patch basically looks okay, but I'm unsure the licensing is okay -- you're basing some of this code from another source that has already got a license: http://www.mit.edu/~emin/source_code/red_black_tree/LICENSE, so i don't believe you can just plant our our license at the top. > > Geoff thought the license was sufficiently compatible that what I did was OK. But what do you recommend? Not use that code, or plant a different statement at the top of the file? In that case it should still have the specific license they provide rather than our usual license header

Filip Pizlo

Comment 34 2011-09-08 21:42:18 PDT

(In reply to comment #33) > (In reply to comment #32) > > (In reply to comment #31) > > > (From update of attachment 106079 [details] [details] [details]) > > > Okay, this patch basically looks okay, but I'm unsure the licensing is okay -- you're basing some of this code from another source that has already got a license: http://www.mit.edu/~emin/source_code/red_black_tree/LICENSE, so i don't believe you can just plant our our license at the top. > > > > Geoff thought the license was sufficiently compatible that what I did was OK. But what do you recommend? Not use that code, or plant a different statement at the top of the file? > > In that case it should still have the specific license they provide rather than our usual license header I've decided that this RedBlackTree is not good enough to warrant pulling in another license. I'm going to convert PODRedBlackTree from WebCore to do what I want. Sadly, as far as I can tell, it would be too complex to roll a template class that provides both the functionality of PODRedBlackTree and the functionality of my RedBlackTree, since PODRedBlackTree has a lot of stuff that I don't want, like virtual methods that it calls from various places. But the PODRedBlackTree does provide an awesome starting point, so I'll base my RedBlackTree on that.

Filip Pizlo

Comment 35 2011-09-08 23:06:12 PDT

Created attachment 106842 [details] the patch - replaced the red black tree with one based on PODRedBlackTree This replaces the RedBlackTree with one based on PODRedBlackTree. It shares no code with the one from MIT that the previous patch had, so the license issues should be entirely side-stepped. I could not use PODRedBlackTree directly because that tree does things that I do not want, and lacks features that I need: - PODRedBlackTree removes nodes by copying one node over another one. MetaAllocator needs to be able to hold references to nodes in the tree, and expects that these pointers remain valid until MetaAllocator deletes those nodes itself. Hence, I needed to change the PODRedBlackTree's removal method to move y into z's position rather than copying the contents of y into z. - PODRedBlackTree calls virtual methods all over the place to support features that WebCore needs. I don't need these features, and I don't want virtual calls. The MetaAllocator is designed to be decently fast, and so it avoids virtual calls inside the hot paths. - PODRedBlackTree has additional features to support partial ordering. I don't need these features at all. - PODRedBlackTree allocates nodes internally and presents an API that does not expose nodes. MetaAllocator wants to be able to allocate nodes itself, and is carefully written to not allocate (or free) any nodes in the common case - it simply moves a node from one place to another in the tree. I thought about combining PODRedBlackTree and my RedBlackTree into a common implementation, with features to specialize as needed. This would be doable. Pro: one less tree in the code base. Con: the code for the tree becomes more complex, because users of PODRedBlackTree and MetaAllocator require significantly different functionality and make different assumptions about the inner workings. I ultimately decided that the cons of combining the trees into one outweighed the pros. Mainly, my thinking is that the tree logic itself is unlikely to be ever modified - so having two copies does not increase maintenance burden. But the interface that the tree presents is likely to be modified - so having two simple implementations of that interface seems better than having one much more complex one that mixes the requirements of WebCore and the JSC JIT.

WebKit Review Bot

Comment 36 2011-09-08 23:10:07 PDT

Attachment 106842 [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/JavaScriptGlue/ForwardingHeaders/wtf/MetaAllocatorHandle.h:2: "JavaScriptCore/MetaAllocatorHandle.h" already included at Source/JavaScriptGlue/ForwardingHeaders/wtf/MetaAllocatorHandle.h:1 [build/include] [4] Source/WebCore/ForwardingHeaders/wtf/MetaAllocatorHandle.h:2: "JavaScriptCore/MetaAllocatorHandle.h" already included at Source/WebCore/ForwardingHeaders/wtf/MetaAllocatorHandle.h:1 [build/include] [4] Total errors found: 2 in 49 files If any of these errors are false positives, please file a bug against check-webkit-style.

Filip Pizlo

Comment 37 2011-09-08 23:13:58 PDT

Created attachment 106843 [details] the patch - fix style Fixed a style goof arising from a bizarre merge conflict that duplicated the code of some files.

Filip Pizlo

Comment 38 2011-09-10 16:32:47 PDT

Comment on attachment 106843 [details] the patch - fix style Performance is unchanged through the multiple rounds of merging and replacing the RB tree. Ready to land!

Filip Pizlo

Comment 39 2011-09-10 22:37:21 PDT

Comment on attachment 106843 [details] the patch - fix style Commit queue is taking forever. Landing manually.

Filip Pizlo

Comment 40 2011-09-10 22:48:57 PDT

Landed in r94920.

Csaba Osztrogonác

Comment 41 2011-09-10 23:35:58 PDT

It broke Qt ARM and Qt MIPS build. Could you check it, please?

Filip Pizlo

Comment 42 2011-09-10 23:57:48 PDT

(In reply to comment #41) > It broke Qt ARM and Qt MIPS build. Could you check it, please? Yeah, that's my fault. Tracking the fix here: https://bugs.webkit.org/show_bug.cgi?id=67903

Andras Becsi

Comment 43 2011-09-12 04:03:10 PDT

The newly added header wtf/RedBlackTree.h has some dead variables which might be parts of later-to-add features. Removing them for now is tracked by https://bugs.webkit.org/show_bug.cgi?id=67928

Yong Li

Comment 44 2012-01-20 12:12:46 PST

This breaks ENALBE(ASSEMBLER_WX_EXCLUSIVE) Bug 76724 is opened for this

LFC

Comment 45 2012-02-24 01:13:41 PST

After I patched this, I got crash in JIT code with armv5 based Qt port. Even in the most recent revision (r108450), the crashed hasn't been fixed. Does anyone meet this problem?

Note You need to log in before you can comment on or make changes to this bug.