Hi Igor,<br><br><div class="gmail_quote">On Sat, Nov 20, 2010 at 1:51 AM, Igor Stasenko <span dir="ltr"><<a href="mailto:siguctua@gmail.com">siguctua@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im"><br>
On 20 November 2010 01:43, Eliot Miranda <<a href="mailto:eliot.miranda@gmail.com">eliot.miranda@gmail.com</a>> wrote:<br>
><br>
> Hi Igor,<br>
><br>
> On Fri, Nov 19, 2010 at 2:50 PM, Igor Stasenko <<a href="mailto:siguctua@gmail.com">siguctua@gmail.com</a>> wrote:<br>
>><br>
</div><div class="im">>> i think that with agressive optimization, this loop can be turned into no-op.<br>
>> or more presisely to an instruction which sets i to 100000001 :)<br>
><br>
><br>
> Are you missing the point, which is to try and generate efficient loop code, not to optimize empty loops? I stripped the example down to the smallest possible code (an empty loop) just to show how much better VW code is and how limited the effect of merely doing the booleanCheat:. But loops that /can't/ be optimized away are very common in the system, and right now Cog isn't doing a great job at making these go fast.<br>
><br>
>> But i wonder what kind of analysis should be applied to determine that<br>
>> loop is bound<br>
>> to 100000000, and there is no other side effects than just incrementing counter.<br>
>> Btw, i think it is much easier to optimize original<br>
>> 1 to: 100000 do:<br>
>> since you know beforehead the loop bounds, and need only to analyze if<br>
>> loop body has any side effects.<br>
><br>
> Imagine the loop had something meaningful in it such as Set>>do:.<br>
>><br>
>> In that way, it is better to analyze the code at AST level, than on<br>
>> bytecode level, since once you turn it into bytecode,<br>
>> you losing a precious information that loop has bounds and have no<br>
>> choice but to strictly follow bytecode semantics.<br>
>> While of course, Cog have not much choice, since it can't operate with<br>
>> AST, just a bytecode.<br>
><br>
> Yes, but you're missing the point. One can still generate faster jitted code than Cog is producing now. My message was trying to show how much more there is to be gained by a better jit code generator, not about higher-level optimization.<br>
<br>
</div>Yes, there is a space for improvement.<br>
My point was, that you have even more potential for optimizations when<br>
dealing at AST level, not bytecode level.<br>
And one of my intents is to create a compiler which could transform<br>
AST directly to native code.<br>
<br>
For example, a loop bounds , since they are smallint constants, could<br>
be turned into machine integers, so code like following:<br>
<div class="im"><br>
32 <76> pushConstant: 1<br>
a1ee2: movl $0x00000003, %eax : B8 03 00 00 00<br>
a1ee7: pushl %eax : 50<br>
33 <B0> send: +<br>
a1ee8: movl %ss:0x4(%esp), %edx : 8B 54 24 04<br>
a1eec: movl $0x0045ae64=#+, %ecx : B9 64 AE 45 00<br>
a1ef1: call .+0xfff5e59a (0x00000490=ceSend1Args) : E8 9A E5 F5 FF<br>
IsSendCall:<br>
a1ef6: pushl %edx : 52<br>
34 <68> popIntoTemp: 0<br>
a1ef7: popl %eax : 58<br>
<br>
</div>could be replaced just by<br>
<br>
inc %eax<br>
<br>
and if loop counter passed somewhere, where it can't use optimized<br>
value, then it can be turned back to smallint, like:<br>
<br>
shl %eax,1<br>
inc %eax<br></blockquote><div><br></div><div>Yes, I agree. But I don't think that AST vs bytecode is really anything to do with it; they can be easily transformed into each other (via decompiler & compiler). The bytecode is a convenient form because it is compact and can efficiently be interpreted. The issue is *when* and *where* to spend the cycles trying to optimise aggressively. That's where performance counters come in. If one decorates the jitted code with e.g. a taken and untaken count at each conditional branch then when these counters trip one suspends execution, examines the current call stack, collecting concrete type information from inline caches, and optimises several nested activations into a single large method that is worth optimising with traditional static techniques (good register allocation etc). If one tries to optimise everything the system becomes unresponsive (see Craig Chambers' Self 2 compiler). If one defers optimization until finding a "hot spot" things work much better (see Urs Höltzle's Self 3 compiler, HotSpot et al).</div>
<div><br></div><div>So</div><div><br></div><div>- keep bytecode and an interpreter for compactness, portability and the ability to always fall back on the interpreter (e.g. when the JIT runs out of memory during some tricky relinking operation)</div>
<div><br></div><div>- use a simple JIT to optimize code run more than once, that does a reasonable job of stack to register mapping, implements PICs to collect type info and performance counters to collect block usage and invoke the aggressive optimizer</div>
<div><br></div><div>- use a speculative inliner and an aggressive optimiser to inline code based on hot spots, basic block counts, and PIC info, and optimize it using traditional techniques.</div><div><br></div><div>All of the above exists in various production VMs, AFAIA none all in the same place. So the above is arguably a proven architecture. Hence it is my direction (and Marcus' and I hope yours too). I can send you my architectural sketch if you're interested.</div>
<div><br></div><div>best</div><div>Eliot</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div><div></div><div class="h5"><br>
<br>
> best<br>
> Eliot<br>
<br>
<br>
<br>
--<br>
Best regards,<br>
Igor Stasenko AKA sig.<br>
</div></div></blockquote></div><br>