<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto">Hi Clément, Hi Ben,<br><br><div id="AppleMailSignature"><span style="background-color: rgba(255, 255, 255, 0);">_,,,^..^,,,_ (phone)</span></div><div><br>On Aug 3, 2018, at 1:19 AM, Clément Béra <<a href="mailto:bera.clement@gmail.com">bera.clement@gmail.com</a>> wrote:<br><br></div><blockquote type="cite"><div><span></span></div></blockquote><blockquote type="cite"><div><div dir="ltr">Hi,<div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Aug 3, 2018 at 4:28 AM, Ben Coman <span dir="ltr"><<a href="mailto:btc@openinworld.com" target="_blank">btc@openinworld.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <br>
Just a brain twitch about something I'd like to understand better...<br>
<br>
At <a href="http://www.mirandabanda.org/cogblog/2011/03/01/build-me-a-jit-as-fast-as-you-can/" rel="noreferrer" target="_blank">http://www.mirandabanda.org/co<wbr>gblog/2011/03/01/build-me-a-ji<wbr>t-as-fast-as-you-can/</a><br>
it says... "[Monomorphic] inline caching depends on the fact that in<br>
most programs at most send sites there is no polymorphism and that<br>
most sends bind to *exactly_one* class of receiver over some usefully<br>
long period of time. ... In Cog we implement inline caches in three<br>
forms ... monomorphic inline cache ... closed polymorphic inline cache<br>
... open polymorphic cache. What’s nice is that while these sends are<br>
increasingly expensive moving from monomorphic to megamorphic they are<br>
also decreasingly common in roughly a 90%, 9% 0.9% ratio, at least for<br>
typical Smalltalk programs"<br></blockquote><div><br></div><div>Note that in my experience the ratio was, each time I measured in the Cog Simulator, 93%, 4%, 3% or something like that. Cliff Click told me recently he had the same feeling with Java code, sends are either mono or megamorphic, but rarely poly (through in the JVM polymorphism is up to 4). </div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
First, I'm curious what is the relative performance of the three<br>
different caches ?<br></blockquote></div></div></div></div></div></blockquote><div><br></div>Towards the bottom of the blog post is an example that measures relative performance. The table I give is as follows, but the data are from a V3 image. Ben, maybe you could run the example on Spur and see if things are much different.<div><br></div><div><span style="background-color: rgba(255, 255, 255, 0);">homogenous immediate 2.8 nsecs<br>homogenous compact 8.6 nsecs<br>homogenous normal 8.5 nsecs<br>polymorphic 11.2 nsecs<br>megamorphic 16.7 nsecs</span><br><div><br></div><div><br><blockquote type="cite"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div>I guess you can measure that with micro benchs. Levente can help with that, I would write complete crap. Note that our polymorphism is up to 6.</div><div><br></div><div>In the Case of Cog, I would expect monomorphic caches to be almost as fast as direct calls, polymorphic caches to be almost as fast as monomorphic, and megamorphic caches to be considerably slower. To be confirmed.</div><div><br></div><div>Note also that for some reason in Cog PICs are called ClosedPICs and megamorphic caches are called OpenPICs.</div></div></div></div></blockquote><div><br></div>Here’s my explanation from the blog post:<div><br></div><div><p style="line-height: 30px; margin: 1em 0px;"><span style="background-color: rgba(255, 255, 255, 0);">In Cog we implement inline caches in three forms:</span></p><p style="line-height: 30px; margin: 1em 0px;"><span style="background-color: rgba(255, 255, 255, 0);">– a monomorphic inline cache; a load of a cache tag and a call of a target method whose prolog checks that the current receiver’s class matches the cache tag</span></p><p style="line-height: 30px; margin: 1em 0px;"><span style="background-color: rgba(255, 255, 255, 0);">– a closed polymorphic inline cache; a growable but finite jump table of class checks and jumps to method bodies, (closed because it deals with a closed set of classes).</span></p><p style="line-height: 30px; margin: 1em 0px;"><span style="background-color: rgba(255, 255, 255, 0);">– an open polymorphic cache; a first-level method lookup probe specialized for a particular selector, (open since it deals with an open set of classes).</span></p><p style="line-height: 30px; margin: 1em 0px;"><span style="background-color: rgba(255, 255, 255, 0);"><br></span></p><blockquote type="cite"><div><div dir="ltr"><div><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Second, I'm curious how Booleans are dealt with. Boolean handling<br>
must be fairly common, and at the Image level these are two different<br>
classes, which pushes out of the monomorphic inline cache, which may<br>
be a significant impact on performance.<br>
<br></blockquote><div><br></div><div>Control flow operations are inlined by the bytecode compiler, and they're the most critical performance wise.</div><div><br></div><div>The VM fixes the addresses of specific objects (nil, true, false). Become and become forward don't work with those objects. The JIT can generate constants in machine code for the addresses of those objects. That allows to quicken inlined control flow operations.</div><div><br></div><div>Non inlined operations are usually dealt with PICs with 2 cases.</div><div><br></div><div>One issue I had in Sista was with early PIC promotion. Currently in Cog if there's already a megamorphic cache for a selector, monomorphic caches are rewritten to the megamorphic cache directly and not to PIC then megamorphic. This is a problem typically with sends such as #isNil. In some cases the isNil is megamorphic and using such cache is relevant. In other case there's just a given type and Undefined object, and there the VM currently uses a megamorphic cache instead of a PIC. This was especially annoying since megamorphic caches don't provide any runtime type feedback. Similar 2 cases issue, non boolean.</div></div></div></div></div></div></blockquote><div><br></div>Hence we disable the optimisation in the Sista JIT right?</div><div><br><blockquote type="cite"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I started wondering if under the hood the VM could treat the two<br>
booleans as one class and in the instance store "which-boolean" it<br>
actually is. Then for example the #ifTrue:ifFalse: method of each<br>
class would be compiled into a single method conditioned at the start<br>
on "which-boolean" as to which path is executed. How feasible would<br>
that be, and would it make much of a difference in performance of<br>
booleans ?<br>
<br></blockquote><div><br></div><div>Some VMs have boolean as primitive types or as immediate objects. Honestly, given our optimization that the booleans can't move in memory and that we can use their address as a constant, I don't think any of these optimizations would make any significant difference in terms of performance. </div><div><br></div><div>What might make a difference is to add as primitive operations / inlined operations some other boolean methods, such as #not. It's a trade-off between system flexibility, boolean and non boolean performance, etc. </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Except then I realized that this situation is already bypassed by<br>
common boolean methods being inlined by the compiler. Still curious,<br>
if there are quick answers to my questions.<br></blockquote><div><br></div><div>..</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
cheers -ben<br>
</blockquote></div><br>-- <br><div class="m_8990572560477080597gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><span style="font-size:12.8px">Clément Béra<br></span><span style="color:rgb(0,0,238)"><a href="https://clementbera.github.io/" target="_blank">https://clementbera.github.io/</a></span><div style="font-size:12.8px"><a href="https://clementbera.wordpress.com/" target="_blank">https://clementbera.wordpress.<wbr>com/</a></div></div></div></div></div></div>
</div></div>
</blockquote></div></div></div></body></html>