Bug 72467 – Code block jettisoning should be part of the GC's transitive closure

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Filip Pizlo]

Currently if the recompilation system determines that a code block should be ditched, we "jettison" it from its owner executable and transfer its ownership to the GC.  The GC then deletes it if on the next GC cycle it proves that no call frame is using that code block.  This ensures sound execution even if the code block was running at the time that the recompilation system determined that it should be ditched.

But this mechanism does not allow for the collector to decide, on its own, that a code block should be jettisoned.  For example, the collector may find that references that the code block needs in order to survive are no longer live (such as inlined references to structures and callees).  In that case, the collector should delete the code block if it is not referenced from call frames; otherwise it should let it live and ensure that all of those references are marked to ensure sound execution.  But by the time that the collector could have made such a decision (i.e. during the transitive closure, or "drain", portion of Heap::markRoots()), the JettisonedCodeBlocks class no longer remembers which code blocks are live on call frames and which are dead.

This mechanism also provides no way for a code block to decide, when it is asked to mark its references, if it is being asked to do so because it is live on call frames, or because it is reachable from live executables, or both.  What we would like is for it to be able to mark its inlined references strongly if it is live on call frames or ephemeronically otherwise, and if it finds any of them to be dead, then it should jettison itself.  The information necessary to make these decisions should be made available to CodeBlocks at time of garbage collection.

[Filip Pizlo]

Created attachment 115331 [details]
the patch

The performance is neutral.



[pizlo@nitroflex bencher] ./bencher TipOfTree:/Volumes/Data/pizlo/quinary/OpenSource/WebKitBuild/Release/jsc DFGCodeBlocks:/Volumes/Data/pizlo/OpenSource/WebKitBuild/Release/jsc --remote oldmac,bigmac
Packaging VM builds for remote hosts...
Sending VM builds to oldmac...
Running on oldmac...
376/376                                                            
Generating benchmark report at TipOfTree_DFGCodeBlocks_SunSpiderV8Kraken_20111115_2314_benchReport.txt

Benchmark report for SunSpider, V8, and Kraken on oldmac.local (MacPro4,1).

VMs tested:
"TipOfTree" at /Volumes/Data/pizlo/quinary/OpenSource/WebKitBuild/Release/jsc (r100409)
"DFGCodeBlocks" at /Volumes/Data/pizlo/OpenSource/WebKitBuild/Release/jsc (r100409)

Collected 12 samples per benchmark/VM, with 4 VM invocations per benchmark. Emitted a call to gc() between sample
measurements. Used 1 benchmark iteration per VM invocation for warm-up. Used the jsc-specific preciseTime()
function to get microsecond-level timing. Reporting benchmark execution times with 95% confidence intervals in
milliseconds.

                                            TipOfTree             DFGCodeBlocks                                  
SunSpider:
   3d-cube                                8.9733+-0.0345          8.9398+-0.0383       
   3d-morph                              10.2372+-0.1515         10.1285+-0.0455         might be 1.0107x faster
   3d-raytrace                            9.2397+-0.0742          9.1624+-0.0545       
   access-binary-trees                    1.9173+-0.0072    ?     1.9408+-0.0322       ? might be 1.0122x slower
   access-fannkuch                        9.0949+-0.0126          9.0948+-0.0071       
   access-nbody                           5.0517+-0.0030    ?     5.0521+-0.0082       ?
   access-nsieve                          3.7642+-0.0502    ?     3.7751+-0.0610       ?
   bitops-3bit-bits-in-byte               1.4801+-0.0036    ?     1.4915+-0.0233       ?
   bitops-bits-in-byte                    5.9961+-0.0722          5.9393+-0.0177       
   bitops-bitwise-and                     3.9795+-0.0132    ?     3.9905+-0.0393       ?
   bitops-nsieve-bits                     6.8535+-0.0496          6.8342+-0.0470       
   controlflow-recursive                  2.7475+-0.0141    ?     2.7628+-0.0278       ?
   crypto-aes                             8.5666+-0.0595    ?     8.5803+-0.0550       ?
   crypto-md5                             2.9998+-0.0220    !     3.0373+-0.0143       ! definitely 1.0125x slower
   crypto-sha1                            2.6110+-0.0189    ?     2.6411+-0.0386       ? might be 1.0115x slower
   date-format-tofte                     12.9748+-0.0927    ?    13.1372+-0.0830       ? might be 1.0125x slower
   date-format-xparb                     13.2369+-0.1701    ^    12.3930+-0.2693       ^ definitely 1.0681x faster
   math-cordic                            8.7441+-0.1110    ^     8.6104+-0.0221       ^ definitely 1.0155x faster
   math-partial-sums                     12.7435+-0.0541    ^    12.6258+-0.0271       ^ definitely 1.0093x faster
   math-spectral-norm                     3.1236+-0.0049    ?     3.1276+-0.0076       ?
   regexp-dna                            16.4603+-0.1241    ?    16.5574+-0.1390       ?
   string-base64                          4.7776+-0.0475    ?     4.8275+-0.0737       ? might be 1.0105x slower
   string-fasta                           8.5676+-0.0147          8.5315+-0.0253       
   string-tagcloud                       16.2332+-0.1278    ?    16.3223+-0.1204       ?
   string-unpack-code                    27.8863+-0.0675    ?    27.9467+-0.0562       ?
   string-validate-input                  6.8559+-0.0649    !     6.9918+-0.0519       ! definitely 1.0198x slower

   <arithmetic> *                         8.2737+-0.0292          8.2478+-0.0335       
   <geometric>                            6.5343+-0.0218          6.5301+-0.0278       
   <harmonic>                             5.0532+-0.0154    ?     5.0704+-0.0259       ?

                                            TipOfTree             DFGCodeBlocks                                  
V8:
   crypto                                93.4016+-0.3318    ?    93.7145+-0.3372       ?
   deltablue                            204.9667+-1.4906        203.3539+-1.5126       
   earley-boyer                         126.5092+-1.3792    ?   126.9296+-1.1904       ?
   raytrace                              76.4015+-0.5830    ?    77.0431+-1.0522       ?
   regexp                               149.2949+-0.4518    ?   149.7389+-0.5129       ?
   richards                             166.8745+-0.7934        166.1569+-0.6842       
   splay                                107.5215+-1.2185        106.4858+-1.0981       

   <arithmetic>                         132.1386+-0.3973        131.9175+-0.3444       
   <geometric> *                        125.6869+-0.4015        125.6151+-0.3484       
   <harmonic>                           119.5030+-0.4236    ?   119.5705+-0.4232       ?

                                            TipOfTree             DFGCodeBlocks                                  
Kraken:
   ai-astar                             895.1716+-0.5152        894.8411+-0.9014       
   audio-beat-detection                 249.6966+-1.1852        248.9893+-0.5309       
   audio-dft                            314.5609+-2.8841    ?   314.9799+-3.0798       ?
   audio-fft                            161.8402+-0.1154    ?   162.2922+-0.8093       ?
   audio-oscillator                     355.5835+-2.8221    ?   355.6017+-3.1301       ?
   imaging-darkroom                     409.5399+-8.0807        402.5688+-5.4728         might be 1.0173x faster
   imaging-desaturate                   291.1407+-0.0368    ?   291.2704+-0.2197       ?
   imaging-gaussian-blur                750.8037+-0.2328    ?   752.9228+-4.4614       ?
   json-parse-financial                  87.7746+-0.2768    ?    87.9518+-0.2255       ?
   json-stringify-tinderbox              95.6810+-0.2857    ?    95.7273+-0.3303       ?
   stanford-crypto-aes                  141.2817+-1.1004    ?   143.0116+-1.6139       ? might be 1.0122x slower
   stanford-crypto-ccm                  136.9733+-0.3995        136.8832+-0.6449       
   stanford-crypto-pbkdf2               283.3259+-2.1650        281.2825+-2.4035       
   stanford-crypto-sha256-iterative     118.9495+-0.4448    ^   117.9656+-0.2000       ^ definitely 1.0083x faster

   <arithmetic> *                       306.5945+-0.6486        306.1634+-0.6200       
   <geometric>                          238.9861+-0.4570        238.7401+-0.4551       
   <harmonic>                           192.6643+-0.3043        192.6255+-0.3288       

                                            TipOfTree             DFGCodeBlocks                                  
All benchmarks:
   <arithmetic>                         115.5832+-0.1803        115.4075+-0.1934       
   <geometric>                           29.6532+-0.0617         29.6310+-0.0769       
   <harmonic>                             8.9074+-0.0267    ?     8.9371+-0.0446       ?

                                            TipOfTree             DFGCodeBlocks                                  
Geomean of preferred means:
   <scaled-result>                       68.3148+-0.1231         68.1984+-0.1369       

Sending VM builds to bigmac...
Running on bigmac...
376/376                                                            
Generating benchmark report at TipOfTree_DFGCodeBlocks_SunSpiderV8Kraken_20111115_2317_benchReport.txt

Benchmark report for SunSpider, V8, and Kraken on bigmac.local (MacPro5,1).

VMs tested:
"TipOfTree" at /Volumes/Data/pizlo/quinary/OpenSource/WebKitBuild/Release/jsc (r100409)
"DFGCodeBlocks" at /Volumes/Data/pizlo/OpenSource/WebKitBuild/Release/jsc (r100409)

Collected 12 samples per benchmark/VM, with 4 VM invocations per benchmark. Emitted a call to gc() between sample
measurements. Used 1 benchmark iteration per VM invocation for warm-up. Used the jsc-specific preciseTime()
function to get microsecond-level timing. Reporting benchmark execution times with 95% confidence intervals in
milliseconds.

                                            TipOfTree             DFGCodeBlocks                                  
SunSpider:
   3d-cube                                7.5032+-0.0332    ^     7.4309+-0.0181       ^ definitely 1.0097x faster
   3d-morph                               8.3867+-0.0400    ?     8.5196+-0.1343       ? might be 1.0158x slower
   3d-raytrace                            7.6770+-0.0596          7.6764+-0.0514       
   access-binary-trees                    1.6034+-0.0128          1.5922+-0.0058       
   access-fannkuch                        7.5298+-0.0150    ?     7.5350+-0.0078       ?
   access-nbody                           4.1868+-0.0069    ?     4.1895+-0.0055       ?
   access-nsieve                          3.1571+-0.0506          3.1541+-0.0586       
   bitops-3bit-bits-in-byte               1.2455+-0.0160    ?     1.2463+-0.0146       ?
   bitops-bits-in-byte                    4.9072+-0.0098    ?     4.9074+-0.0093       ?
   bitops-bitwise-and                     3.3099+-0.0291          3.2965+-0.0208       
   bitops-nsieve-bits                     5.6445+-0.0358          5.6423+-0.0363       
   controlflow-recursive                  2.2810+-0.0145          2.2797+-0.0150       
   crypto-aes                             7.1286+-0.0415          7.1140+-0.0373       
   crypto-md5                             2.5067+-0.0200    ?     2.5234+-0.0150       ?
   crypto-sha1                            2.1769+-0.0140    ?     2.1820+-0.0120       ?
   date-format-tofte                     10.6355+-0.0416    !    10.8784+-0.0788       ! definitely 1.0228x slower
   date-format-xparb                     10.8949+-0.0855    ^     9.9760+-0.1471       ^ definitely 1.0921x faster
   math-cordic                            7.1929+-0.0520          7.1629+-0.0285       
   math-partial-sums                     10.4968+-0.0233         10.4538+-0.0267       
   math-spectral-norm                     2.6073+-0.0141          2.6035+-0.0097       
   regexp-dna                            13.2815+-0.1455    ?    13.3551+-0.1555       ?
   string-base64                          3.9459+-0.0158    ?     3.9620+-0.0272       ?
   string-fasta                           7.0967+-0.0215    ^     7.0327+-0.0121       ^ definitely 1.0091x faster
   string-tagcloud                       13.2739+-0.0774    ?    13.3888+-0.0780       ?
   string-unpack-code                    22.4806+-0.0984    ?    22.5374+-0.1118       ?
   string-validate-input                  5.6743+-0.1153    ?     5.7204+-0.0318       ?

   <arithmetic> *                         6.8010+-0.0223          6.7831+-0.0249       
   <geometric>                            5.4034+-0.0184          5.3923+-0.0172       
   <harmonic>                             4.2017+-0.0169          4.1970+-0.0133       

                                            TipOfTree             DFGCodeBlocks                                  
V8:
   crypto                                77.4166+-0.2837    ?    77.5058+-0.2328       ?
   deltablue                            171.6202+-1.6061        170.0732+-1.0567       
   earley-boyer                         104.9058+-1.1736    ?   104.9624+-0.9954       ?
   raytrace                              64.0433+-1.6441         63.4618+-0.4197       
   regexp                               124.1412+-0.3760    !   125.3017+-0.1466       ! definitely 1.0093x slower
   richards                             137.6363+-0.4870        137.6235+-0.3622       
   splay                                 90.7661+-1.5559         89.3494+-1.0397         might be 1.0159x faster

   <arithmetic>                         110.0757+-0.5509        109.7540+-0.1916       
   <geometric> *                        104.7400+-0.6172        104.4071+-0.1902       
   <harmonic>                            99.6374+-0.7276         99.2725+-0.1916       

                                            TipOfTree             DFGCodeBlocks                                  
Kraken:
   ai-astar                             818.4744+-11.3281   ?   826.7462+-0.3904       ? might be 1.0101x slower
   audio-beat-detection                 204.3252+-0.6030    ?   205.0148+-0.7475       ?
   audio-dft                            262.5186+-2.1914        260.3697+-2.2269       
   audio-fft                            132.8021+-0.1407        132.7924+-0.0995       
   audio-oscillator                     293.3498+-0.3937        293.3062+-0.4924       
   imaging-darkroom                     335.2181+-5.0709        333.1090+-4.5439       
   imaging-desaturate                   240.8844+-0.1673    ?   240.8881+-0.1606       ?
   imaging-gaussian-blur                620.5048+-0.1724    ?   623.3088+-3.3815       ?
   json-parse-financial                  72.0124+-0.2967    ?    72.1616+-0.1456       ?
   json-stringify-tinderbox              78.9461+-0.2363    !    80.0372+-0.7569       ! definitely 1.0138x slower
   stanford-crypto-aes                  117.9708+-1.2254        117.0255+-0.3211       
   stanford-crypto-ccm                  114.1310+-0.3159    ?   114.5858+-0.5152       ?
   stanford-crypto-pbkdf2               230.7736+-0.8957    ?   232.4556+-1.4659       ?
   stanford-crypto-sha256-iterative      97.7790+-0.1591    ^    97.1193+-0.2832       ^ definitely 1.0068x faster

   <arithmetic> *                       258.5493+-0.8837    ?   259.2086+-0.4631       ?
   <geometric>                          198.5446+-0.4188    ?   198.7658+-0.2959       ?
   <harmonic>                           159.1494+-0.3278    ?   159.3555+-0.2159       ?

                                            TipOfTree             DFGCodeBlocks                                  
All benchmarks:
   <arithmetic>                          97.1712+-0.2955    ?    97.3097+-0.1310       ?
   <geometric>                           24.5832+-0.0563         24.5518+-0.0466       
   <harmonic>                             7.4060+-0.0291          7.3977+-0.0230       

                                            TipOfTree             DFGCodeBlocks                                  
Geomean of preferred means:
   <scaled-result>                       56.8944+-0.1572         56.8329+-0.0775       

[pizlo@nitroflex bencher]

[WebKit Review Bot]

Attachment 115331 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/CMakeLists.txt', u'S..." exit_code: 1

Source/JavaScriptCore/heap/Heap.h:40:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
Source/JavaScriptCore/heap/Heap.h:107:  The parameter name "codeBlock" adds no information, so it should be removed.  [readability/parameter_name] [5]
Total errors found: 2 in 17 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Filip Pizlo]

Created attachment 115333 [details]
the patch

Fixed style.

[WebKit Review Bot]

Attachment 115333 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/CMakeLists.txt', u'S..." exit_code: 1

Source/JavaScriptCore/heap/Heap.h:40:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
Total errors found: 1 in 17 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Filip Pizlo]

Created attachment 115441 [details]
the patch

Fix no-DFG builds.

[WebKit Review Bot]

Attachment 115441 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/CMakeLists.txt', u'S..." exit_code: 1

Source/JavaScriptCore/heap/Heap.h:40:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
Total errors found: 1 in 17 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Geoffrey Garen]

Comment on attachment 115333 [details]
the patch

View in context: https://bugs.webkit.org/attachment.cgi?id=115333&action=review

r=me -- but make sure to check in the version that builds on Windows.

> Source/JavaScriptCore/bytecode/CodeBlock.h:1109
> +                : isMarked(false)

Let's reserve the word "mark" for things with standard mark bits, and call this "mightBeExecuting".

> Source/JavaScriptCore/heap/DFGCodeBlocks.cpp:46
> +    for (unsigned i = 0; i < toRemove.size(); ++i) {

You can use Vector's deleteAllValues here.

> Source/JavaScriptCore/heap/DFGCodeBlocks.cpp:85
> +    for (unsigned i = 0; i < toRemove.size(); ++i) {

Helper function here too.

[Filip Pizlo]

Created attachment 115466 [details]
the patch

Applied Geoff's suggestions, and attempting, again, to fix the Windows build.

[WebKit Review Bot]

Attachment 115466 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/CMakeLists.txt', u'S..." exit_code: 1

Source/JavaScriptCore/heap/Heap.h:40:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
Total errors found: 1 in 17 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Filip Pizlo]

Created attachment 115487 [details]
the patch

Merged with http://trac.webkit.org/changeset/100527

[WebKit Review Bot]

Attachment 115487 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/CMakeLists.txt', u'S..." exit_code: 1

Source/JavaScriptCore/heap/Heap.h:40:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
Total errors found: 1 in 17 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Filip Pizlo]

Landed in http://trac.webkit.org/changeset/100556