<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<meta name="Generator" content="Microsoft Exchange Server">
<!-- converted from text --><style><!-- .EmailQuote { margin-left: 1pt; padding-left: 4pt; border-left: #800000 2px solid; } --></style>
</head>
<body>
<meta content="text/html; charset=UTF-8">
<style type="text/css" style="">
<!--
p
{margin-top:0;
margin-bottom:0}
-->
</style>
<div dir="ltr">
<div id="x_divtagdefaultwrapper" dir="ltr" style="font-size:12pt; color:#000000; font-family:Calibri,Helvetica,sans-serif">
<div>> > (At the moment I'm trying to optimize #caseOf: to use binary search if appropriate, let's see what will come of it ^^)</div>
<div><br>
</div>
<div>> When is it appropriate to use binary search there?</div>
<div><br>
</div>
<div>Looking up numbers <span style="font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols; font-size:16px">can be reduced from O(n) to O(log n) complexity.</span></div>
<div><br>
</div>
<div>x caseOf: {</div>
<div> [2] -> [1].</div>
<div> [3] -> [2].</div>
<div> [5] -> [3].</div>
<div> [7] -> [4].</div>
<div> [11] -> [5] <span style="font-size:12pt">... }</span></div>
<div><span style="font-size:12pt"><br>
</span></div>
<div><span style="font-size:12pt">This could also help us to both clean up and accelerate #<span>interpretNextV3ClosuresInstructionFor:.</span></span></div>
<div><span style="font-size:12pt"><span><br>
</span></span></div>
<div><span style="font-size:12pt"><span>Best,</span></span></div>
<div><span style="font-size:12pt"><span>Christoph</span></span></div>
</div>
<hr tabindex="-1" style="display:inline-block; width:98%">
<div id="x_divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" color="#000000" style="font-size:11pt"><b>Von:</b> Squeak-dev <squeak-dev-bounces@lists.squeakfoundation.org> im Auftrag von Levente Uzonyi <leves@caesar.elte.hu><br>
<b>Gesendet:</b> Sonntag, 23. Februar 2020 00:19:09<br>
<b>An:</b> The general-purpose Squeak developers list<br>
<b>Betreff:</b> Re: [squeak-dev] Question regarding compilation of #caseOf:[otherwise:] messages</font>
<div> </div>
</div>
</div>
<font size="2"><span style="font-size:10pt;">
<div class="PlainText">On Sat, 22 Feb 2020, Thiede, Christoph wrote:<br>
<br>
> <br>
> > If you already analyzed it, I trust you, you are more advanced than me on the subject :)<br>
> <br>
> <br>
> I would not say that I have an overview of the entire compiler system at the moment. Someone else should definitively review this before. :)<br>
> <br>
> > Fixing the Decompiler might be a bit more involved the way it is written now... > But with your fast progress and fearless diving in lower level details, I think you can do it :)<br>
> <br>
> Hm, maybe this could be some of my next adventures :-)<br>
> (At the moment I'm trying to optimize #caseOf: to use binary search if appropriate, let's see what will come of it ^^)<br>
<br>
When is it appropriate to use binary search there?<br>
<br>
Levente<br>
<br>
> <br>
> Best,<br>
> Christoph<br>
> <br>
> __________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________<br>
> Von: Squeak-dev <squeak-dev-bounces@lists.squeakfoundation.org> im Auftrag von Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com><br>
> Gesendet: Samstag, 22. Februar 2020 18:50:26<br>
> An: The general-purpose Squeak developers list<br>
> Betreff: Re: [squeak-dev] Question regarding compilation of #caseOf:[otherwise:] messages <br>
> It was just a wild guess, because I did not look at the code nor any other detail.<br>
> If you already analyzed it, I trust you, you are more advanced than me on the subject :)<br>
> Fixing the Decompiler might be a bit more involved the way it is written now...<br>
> But with your fast progress and fearless diving in lower level details, I think you can do it :)<br>
> <br>
> Le sam. 22 févr. 2020 à 18:44, Thiede, Christoph <Christoph.Thiede@student.hpi.uni-potsdam.de> a écrit :<br>
><br>
> Hi Nicolas,<br>
> <br>
><br>
> > could it be for the case when there is no otherwise?<br>
> <br>
> <br>
> In this case, a "self caseError" will be generated (though this is no correct behavior either IMO, see Problems with #caseError). I don't see how this should affect the jumps or returns before the otherwise part ...<br>
> <br>
> Best,<br>
> Christoph<br>
> <br>
> __________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________<br>
> Von: Squeak-dev <squeak-dev-bounces@lists.squeakfoundation.org> im Auftrag von Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com><br>
> Gesendet: Samstag, 22. Februar 2020 18:36:01<br>
> An: The general-purpose Squeak developers list<br>
> Betreff: Re: [squeak-dev] Question regarding compilation of #caseOf:[otherwise:] messages <br>
> Hi Christoph,<br>
> could it be for the case when there is no otherwise?<br>
> <br>
> Le sam. 22 févr. 2020 à 18:24, Thiede, Christoph <Christoph.Thiede@student.hpi.uni-potsdam.de> a écrit :<br>
><br>
> Hi all,<br>
> <br>
><br>
> this a question regarding the Compiler's implementation. I spent some time on it but could not yet find a satisfying explanation. Maybe someone of you can help me?<br>
> <br>
><br>
> Let's look into MessageNode >> #emitCodeForCase:encoder:value:, which contains the following passage:<br>
> <br>
><br>
> (isLast and: [allReturn]) ifTrue:<br>
> <br>
> [self emitCodeForJump: elseSize encoder: encoder]<br>
> <br>
> <br>
> Btw, the equivalent in #sizeCodeForCase:value: is:<br>
> <br>
><br>
> (isLast and: [allReturn]) ifTrue: [thenSize := thenSize + (self sizeCode: encoder forJump: elseSize)].<br>
> <br>
> <br>
> In the bytecode of a method, this will look like this:<br>
> <br>
><br>
> 89 <23> pushConstant: 2<br>
> <br>
> 90 <88> dup<br>
> <br>
> 91 <76> pushConstant: 1<br>
> <br>
> 92 <B6> send: =<br>
> <br>
> 93 <9A> jumpFalse: 97<br>
> <br>
> 94 <87> pop<br>
> <br>
> 95 <22> pushConstant: #one<br>
> <br>
> 96 <7C> returnTop<br>
> <br>
> 97 <77> pushConstant: 2<br>
> <br>
> 98 <B6> send: =<br>
> <br>
> 99 <9A> jumpFalse: 103<br>
> <br>
> 100 <21> pushConstant: #two<br>
> <br>
> 101 <7C> returnTop<br>
> <br>
> 102 <90> jumpTo: 104 "here!"<br>
> <br>
> 103 <20> pushConstant: 42<br>
> <br>
> 104 <87> pop<br>
> <br>
> <br>
> I cannot see when this jump would be ever reached.<br>
> <br>
> Case 1: Any case is selected, and because allReturn is true, its inlined value block is guaranteed to #returnTop and thus not to reach the last jump (in the above example, this happens in pc101).<br>
> <br>
> Case 2: No case is selected, so the execution will jump straightly to the inlined otherwiseBlock (this is pc99 in the example).<br>
> <br>
> For what purpose do we need this jump (ex: pc102)? Should we maybe remove it?<br>
> <br>
> <br>
> Are there any special situations in which #returns is true but there is any code path that does *not* return? Some weird exception handling trick, for example?<br>
> <br>
> Or was the dubious jump just designed as a fallback to catch any hypothetic failures in any other component of the compiler system?<br>
> <br>
> <br>
> I removed the generation of this jump for testing and could not investigate any anomalies so far. All compiler tests are passing - except of a number of Decompiler tests, which probably would need to be updated as well.<br>
> <br>
> Please find a minimum changeset in the attachment that demonstrates my question.<br>
> <br>
> <br>
> I am looking forward to your replies!<br>
> <br>
> <br>
> Best,<br>
> <br>
> Christoph<br>
> <br>
> <br>
> <br>
> <br>
></div>
</span></font>
</body>
</html>