<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Hi eliot and clement (and others)<div><br></div><div>I'm not sure that this is something that we can gain from but I read and totally forgot :)</div><div>the paper:&nbsp;<span class="Apple-tab-span" style="white-space:pre">        </span></div><div><span class="Apple-tab-span" style="white-space:pre">        </span>optimizing Closures in O(0) time</div><div><br></div><div><a href="http://users-cs.au.dk/danvy/sfp12/papers/keep-hearn-dybvig-paper-sfp12.pdf">http://users-cs.au.dk/danvy/sfp12/papers/keep-hearn-dybvig-paper-sfp12.pdf</a></div><div><br></div><div>Stef</div>
                
        
        
                <div class="page" title="Page 1">
                        <div class="layoutArea">
                                <div class="column"><p><span style="font-size: 18pt; font-family: NimbusRomNo9L; ">&nbsp;<br></span></p>
                                </div>
                        </div>
                </div><div><br></div><div><br></div><div><br></div><div><div><blockquote type="cite"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; position: static; z-index: auto; "><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; position: static; z-index: auto; "><div dir="ltr">Hello Eliot,<div><br></div><div>So I implemented clean blocks with Opal in Pharo 3. I didn't know where to put the byte code of the clean block, so I put it at the end of the method.</div><div><br>

</div>

<div>ex:</div><div><div>exampleCleanBlock</div><div><span style="white-space:pre-wrap">        </span>^ [ 1 &nbsp;+ 2 ]&nbsp;</div>


</div><div><br></div><div><div>17 &lt;20&gt; pushConstant: [...]</div><div>18 &lt;7C&gt; returnTop</div><div>19 &lt;76&gt; pushConstant: 1</div><div>20 &lt;77&gt; pushConstant: 2</div><div>21 &lt;B0&gt; send: +</div><div>






22 &lt;7D&gt; blockReturn</div></div><div><br></div><div>having in the literal Array:</div><div>[ 1 + 2 ]</div>#exampleCleanBlock<div>OCOpalExamples</div><div><br></div><div>The startpc of the block is 19.</div>

<div>Its outerContext is a context with nil as receiver and the method OCOpalExamples&gt;&gt;#exampleCleanBlock.</div><div>Its numArgs is 0 and it has no copiedValues.</div><div><br></div><div>But it does not work with the JIT.<br>
</div></div></blockquote></div></blockquote><div><br></div><div>Thinking about it I'm pretty sure the problem is that the JIT scans for and counts pushClosure: bytecodes to know how many blocks a method contains, but clean blocks don't need pushClosure: bytecodes. &nbsp;So the JIT needs to look for clean blocks, e.g. either by scanning a method's literals or by looking at the arguments of pushLiteral: bytecodes. &nbsp;In any case the image will allow me to develop a fix.</div>
<div><br></div><div>&nbsp;</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr"><div>


</div><div>If I run:&nbsp;</div><div>OCOpalExamples new exampleCleanBlock value</div><div>I got 3 all the time, it's fine. Now</div><div><div>1 to: 5 do: [ :i |</div><div><span style="white-space:pre-wrap">        </span>OCOpalExamples new exampleCleanBlock value ]</div>






</div><div>Works on Stack VM, but crashes Cog VM. I don't know why (not enough knowledge about the Cog JIT).</div><div><br></div><div>Do you have any clue ?</div></div></blockquote><div><br></div><div>no. &nbsp;send me an image?</div>
<div><div class="h5">
<div>&nbsp;</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><br></div>


</div><div class="gmail_extra"><br><br><div class="gmail_quote">2013/7/31 Eliot Miranda <span dir="ltr">&lt;<a href="mailto:eliot.miranda@gmail.com" target="_blank">eliot.miranda@gmail.com</a>&gt;</span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">



&nbsp;<br><br><br><div class="gmail_quote">On Tue, Jul 30, 2013 at 1:56 PM, Clément Bera <span dir="ltr">&lt;<a href="mailto:bera.clement@gmail.com" target="_blank">bera.clement@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">




&nbsp;<br><div dir="ltr">Thanks for the answer it was very helpful. I got it now.<div><br></div><div>I had a look at the first posts of your blog (Closures I &amp; II) when I was working on the Opal compiler. Today I was looking at&nbsp;<a href="http://www.mirandabanda.org/cogblog/2009/01/14/under-cover-contexts-and-the-big-frame-up/" style="font-size:13px;font-family:arial,sans-serif" target="_blank">Under Cover Contexts and the Big Frame-Up</a>&nbsp;and I think I should read all your blog.&nbsp;</div>






<div><br></div><div>That is really nice that you wrote this blog it is the main documentation about an efficient Smalltalk VM. I learnt by looking at Cog's source mostly. VW VM source is closed so... I will have a look at Strongtalk implementation instead it seems it is open source.</div>






<div><br></div><div>Why are the clean blocks of VW much faster ? Are they activated like method ? I didn't find it in your blog (probably because it is not in Cog). Is it possible to implement clean blocks in Pharo/Squeak ? (I think that 53% of blocks non optimized by the compiler are clean in Pharo 3) Would it worth it ?</div>




</div></blockquote><div><br></div><div>Clean blocks are faster because they don't access their outer environment and hence their outer context does not have to be created. &nbsp;So there is no allocation associated with a clean block. &nbsp;It exists already as a literal and its outer context does not have to be reified. &nbsp;Normal closures are created when the point at which they are defined in method execution is reached (the pushClosure bytecode) and if the current context does not yet exist that must be instantiated too, so creating a closure usually takes two allocations.</div>




<div><br></div><div>Clean blocks are activated like blocks. &nbsp;Block and method activation is different in the first phase (the send side) but quite similar in the second phase (frame building). &nbsp;In VW for example, finding the machine code method associated with a block involves a cache lookup which can be slow. &nbsp;In Cog, it involves following a pointer in the method header (inside, the VM replaces the header of a method with a pointer to its machine code) and then jumping to a hard-coded binary search which jumps to the correct block's entry-point depending on the closure's startpc. &nbsp;If a method contains a single block then this is a direct jump. &nbsp;As a result, block dispatch in Cog is&nbsp;typically&nbsp;faster than in VW.</div>




<div><br></div><div>Yes, it is possible to implement clean blocks. &nbsp;It is only an issue to do with the representation of closures. &nbsp;Ideally they need a method inst var, making the outerContext inst var optional (or at least nil in a clean block). &nbsp;But that would require a change to BlockClosure's class definition and a VM change. &nbsp;To avoid having to change the class definition of BlockClosure and the VM, the compiler could create an empty context to hold onto the method, and that would work fine. &nbsp;So to implement clean blocks the compiler would instantiate a BlockClosure literal for each clean block and a MethodContext whose receiver was nil shared between all the clean blocks in a method. &nbsp;There are tricky issues such as setting breakpoints in methods (toggle break on entry), or copying methods, which would require scanning the literals for clean blocks and duplicating them and their outerCOntext too. &nbsp;But that's just detail. &nbsp;Some time I must try this for Squeak. &nbsp;Let me know if you try if=t for Opal. &nbsp;(and of course I'm very happy to help with advice).</div>




<div><br></div><div>I expect that in certain cases the speedup would be noticeable, but it is a micro-optimization. &nbsp;You'd of course only notice the difference in tight loops that used clean blocks.</div><div><br></div>




<div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">

<div>2013/7/30 Eliot Miranda <span dir="ltr">&lt;<a href="mailto:eliot.miranda@gmail.com" target="_blank">eliot.miranda@gmail.com</a>&gt;</span></div></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">&nbsp;<br><a href="http://www.mirandabanda.org/cogblog/2008/06/07/closures-part-i/" target="_blank">http://www.mirandabanda.org/cogblog/2008/06/07/closures-part-i/</a>Hi&nbsp;Clément,<br>






<br><div class="gmail_quote">On Mon, Jul 29, 2013 at 1:54 AM, Clément Bera <span dir="ltr">&lt;<a href="mailto:bera.clement@gmail.com" target="_blank">bera.clement@gmail.com</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">&nbsp;<br><div dir="ltr">Hello guys,<div><br></div><div>I was looking recently at the blockClosure model of Eliot in Pharo/Squeak and the blockClosure model of VisualWorks and I have a few questions.</div>







<div><br></div><div>- Why Pharo/Squeak does not have compiled block as in VW and has the block byte code in the enclosing method ? Is it to save memory ? Would it worth it to implement CompiledBlock in term of speed and memory consumption ?</div>







</div></blockquote><div><br></div><div>Squeak derives directly from the "blue book" Smalltalk-80 implementation in which CompiledMethod is a hybrid object, half pointers (method header and literals) and half bytes (bytecode and source pointer). &nbsp;This format was chosen to save space in the original 16-bit Smalltalk implementations on the Xerox D machines (Alto &amp; Dorado). &nbsp;VisualWorks has a few extra steps in between, &nbsp;In ObjectWorks 2.4 and ObjectWorks 2.5 Peter Deutsch both introduced closures and eliminated the hybrid CompiledMethod format, introducing CompiledBlock.</div>







<div><br></div><div>IMO adding CompiledBlock, while simplifying the VM a little would not improve performance, especially in the interpreter, essentially because activating and retuning form methods now requires an ecxtra level of indirection to get from the CompiledMethod object to its bytecodes in its bytecode object.</div>







<div><br></div><div>However, adding CompiledBlock (or rather eliminating the hybrid CompiledMethod format) would definitely *not* save space. &nbsp;The hybrid format is more compact (one less object per method). &nbsp;One can try and improve this as in VisualWorks by encoding the bytecodes of certain methods as SmallIntegers in the literal frame, but this is only feasible in a pure JIT VM. &nbsp;Squeak still has an interpreter, and Cog is a hybrid JIT and Interpreter. &nbsp;In an interpreter it is costly in performance to be able to interpret this additional form of bytecodes.</div>







<div><br></div><div>So IMO while the hybrid CompiledMethod isn't ideal it is acceptable, having important advantages to go along with its disadvantages.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">







<div dir="ltr">

<div>- Why Pharo/Squeak context have this variable closureOrNil instead of having the closure in the receiver field as in VW ? Is it an optimization because there are a lot of access to self and instance variables in the blocks in Pharo/Squeak ? Because if I'm correct it uses 1 more slot per stack frame to have this.</div>







</div></blockquote><div><br></div><div>I did this because I think its simpler and more direct. &nbsp;I don't like VW's access to the receiver and inst vars having to use different bytecodes within a block to within a method. &nbsp;There are lots of complexities resulting from this (e.g. in scanning code for inst var refs, the decompiler, etc).</div>







<div><br></div><div>But in fact there isn't really an additional stack slot because the frame format in the VM does not use the stacked receiver (the 0'th argument) as accessing the receiver in this position requires knowing the method's argument count. &nbsp;So in both methods and blocks the receiver is pushed on the stack immediately before allocating space for, and nilling, any temporaries. &nbsp;This puts the receiver in a known place relative to the frame pointer, making it accessible to the bytecodes without having to know the method's argument count. &nbsp;So the receiver always occurs twice on the stack in a method anyway. &nbsp;In a block, the block is on the stack in the 0'th argument position. &nbsp;The actual receiver is pushed after the temps.</div>







<div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">

<div>- Lastly, does VW have the tempVector optimization for escaping write temporaries in their blockClosure ? It seems they have not (I don't see any reference to it in VW 7). Did Pharo/Squeak blocks earns a lot of speed or memory with this optimization ?</div>







</div></blockquote><div><br></div><div>Yes, VW has this same organization. &nbsp;I implemented it in VisualWorks 5i in ~ 2000. &nbsp;It resulted in a significant increase in performance (for example, factors of two improvement in block-intensive code such as exception handling). &nbsp;This is because of details in the context-to-stack mapping machinery which mean that if an activation of a closure can update the temporaries of its outer contexts then keeping contexts and stack frames in sync is much more complex and costly. &nbsp;The 5i/Cog organization (which in fact derives from some Lisp implementations) results in much simpler context-to0stack mapping such that no tests need be done when returning from a method to keep frames and contexts in sync.</div>







<div><br></div><div>&nbsp;</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">

<div>Thank you for any answer.</div></div></blockquote></div><br>You're most welcome. &nbsp;Have you read my blog post on the design? &nbsp;It is "<a href="http://www.mirandabanda.org/cogblog/2009/01/14/under-cover-contexts-and-the-big-frame-up/" target="_blank">Under Cover Contexts and the Big Frame-Up</a>", with additional information in "Closures Part I" &amp; "<a href="http://www.mirandabanda.org/cogblog/2008/07/22/closures-part-ii-the-bytecodes/" target="_blank">Closures Part II – the Bytecodes</a>".<br>







-- <br>best,<div>Eliot</div>
<br></blockquote></div><br></div>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br>best,<div>Eliot</div>
<br></blockquote></div><br></div>
<br></blockquote></div></div></div><span class="HOEnZb"><font color="#888888"><br><br clear="all"><div><br></div>-- <br>best,<div>Eliot</div>
</font></span></blockquote></div><br><br clear="all"><div><br></div>-- <br>best,<div>Eliot</div>
</blockquote></div><br></div></body></html>