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

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Filip Pizlo]

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.

[Filip Pizlo]

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

[Filip Pizlo]

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]

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]

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 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 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 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]

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]

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]

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 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 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 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]

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

[Filip Pizlo]

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

[WebKit Review Bot]

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]

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

[WebKit Review Bot]

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 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]

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

[WebKit Review Bot]

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 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]

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

[Filip Pizlo]

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]

Created attachment 106052 [details]
the patch - fix conflicts

[Filip Pizlo]

Comment on attachment 106052 [details]
the patch - fix conflicts

After loads of testing I'm happy with it.

[Filip Pizlo]

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]

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

[Filip Pizlo]

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

[Filip Pizlo]

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

[Oliver Hunt]

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]

(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]

(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]

(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]

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]

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]

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 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 on attachment 106843 [details]
the patch - fix style

Commit queue is taking forever.  Landing manually.

[Filip Pizlo]

Landed in r94920.

[Csaba Osztrogonác]

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

[Filip Pizlo]

(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]

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]

This breaks ENALBE(ASSEMBLER_WX_EXCLUSIVE)

Bug 76724 is opened for this

[LFC]

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?