[squeak-dev] Question regarding compilation of #caseOf:[otherwise:] messages

Levente Uzonyi leves at caesar.elte.hu
Sun Feb 23 18:33:02 UTC 2020


On Sun, 23 Feb 2020, Thiede, Christoph wrote:

> > > (At the moment I'm trying to optimize #caseOf: to use binary search if appropriate, let's see what will come of it ^^)
> 
> > When is it appropriate to use binary search there?
> 
> Looking up numbers can be reduced from O(n) to O(log n) complexity.
> 
> x caseOf: {
>  [2] -> [1].
>  [3] -> [2].
>  [5] -> [3].
>  [7] -> [4].
>  [11] -> [5] ... }
>

What if the value of x is nil?
What if the branches are not sorted by "key"?
What if there are multiple branches with the same "key"?
What if some "keys" are not literals?

Levente

> This could also help us to both clean up and accelerate #interpretNextV3ClosuresInstructionFor:.
> 
> Best,
> Christoph
> 
> _________________________________________________________________________________________________________________________________________________________________________________________________________________________________
> Von: Squeak-dev <squeak-dev-bounces at lists.squeakfoundation.org> im Auftrag von Levente Uzonyi <leves at caesar.elte.hu>
> Gesendet: Sonntag, 23. Februar 2020 00:19:09
> An: The general-purpose Squeak developers list
> Betreff: Re: [squeak-dev] Question regarding compilation of #caseOf:[otherwise:] messages  
> On Sat, 22 Feb 2020, Thiede, Christoph wrote:
> 
> >
> > > If you already analyzed it, I trust you, you are more advanced than me on the subject :)
> >
> >
> > I would not say that I have an overview of the entire compiler system at the moment. Someone else should definitively review this before. :)
> >
> > > 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 :)
> >
> > Hm, maybe this could be some of my next adventures :-)
> > (At the moment I'm trying to optimize #caseOf: to use binary search if appropriate, let's see what will come of it ^^)
> 
> When is it appropriate to use binary search there?
> 
> Levente
> 
> >
> > Best,
> > Christoph
> >
> >________________________________________________________________________________________________________________________________________________________________________________________________________________________________
> __________________________________________________________________________________________
> > Von: Squeak-dev <squeak-dev-bounces at lists.squeakfoundation.org> im Auftrag von Nicolas Cellier <nicolas.cellier.aka.nice at gmail.com>
> > Gesendet: Samstag, 22. Februar 2020 18:50:26
> > An: The general-purpose Squeak developers list
> > Betreff: Re: [squeak-dev] Question regarding compilation of #caseOf:[otherwise:] messages  
> > It was just a wild guess, because I did not look at the code nor any other detail.
> > If you already analyzed it, I trust you, you are more advanced than me on the subject :)
> > 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 :)
> >
> > Le sam. 22 févr. 2020 à 18:44, Thiede, Christoph <Christoph.Thiede at student.hpi.uni-potsdam.de> a écrit :
> >
> >       Hi Nicolas,
> >
> >
> >       > could it be for the case when there is no otherwise?
> >
> >
> > 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 ...
> >
> > Best,
> > Christoph
> >
> >________________________________________________________________________________________________________________________________________________________________________________________________________________________________
> __________________________________________________________________________________________
> > Von: Squeak-dev <squeak-dev-bounces at lists.squeakfoundation.org> im Auftrag von Nicolas Cellier <nicolas.cellier.aka.nice at gmail.com>
> > Gesendet: Samstag, 22. Februar 2020 18:36:01
> > An: The general-purpose Squeak developers list
> > Betreff: Re: [squeak-dev] Question regarding compilation of #caseOf:[otherwise:] messages  
> > Hi Christoph,
> > could it be for the case when there is no otherwise?
> >
> > Le sam. 22 févr. 2020 à 18:24, Thiede, Christoph <Christoph.Thiede at student.hpi.uni-potsdam.de> a écrit :
> >
> >       Hi all,
> >
> >
> >       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?
> >
> >
> >       Let's look into MessageNode >> #emitCodeForCase:encoder:value:, which contains the following passage:
> >
> >
> >       (isLast and: [allReturn]) ifTrue:
> >
> >     [self emitCodeForJump: elseSize encoder: encoder]
> >
> >
> > Btw, the equivalent in #sizeCodeForCase:value: is:
> >
> >
> >       (isLast and: [allReturn]) ifTrue: [thenSize := thenSize + (self sizeCode: encoder forJump: elseSize)].
> >
> >
> > In the bytecode of a method, this will look like this:
> >
> >
> >       89 <23> pushConstant: 2
> >
> > 90 <88> dup
> >
> > 91 <76> pushConstant: 1
> >
> > 92 <B6> send: =
> >
> > 93 <9A> jumpFalse: 97
> >
> > 94 <87> pop
> >
> > 95 <22> pushConstant: #one
> >
> > 96 <7C> returnTop
> >
> > 97 <77> pushConstant: 2
> >
> > 98 <B6> send: =
> >
> > 99 <9A> jumpFalse: 103
> >
> > 100 <21> pushConstant: #two
> >
> > 101 <7C> returnTop
> >
> > 102 <90> jumpTo: 104 "here!"
> >
> > 103 <20> pushConstant: 42
> >
> > 104 <87> pop
> >
> >
> > I cannot see when this jump would be ever reached.
> >
> > 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).
> >
> > Case 2: No case is selected, so the execution will jump straightly to the inlined otherwiseBlock (this is pc99 in the example).
> >
> > For what purpose do we need this jump (ex: pc102)? Should we maybe remove it?
> >
> >
> > 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?
> >
> > Or was the dubious jump just designed as a fallback to catch any hypothetic failures in any other component of the compiler system?
> >
> >
> > 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.
> >
> > Please find a minimum changeset in the attachment that demonstrates my question.
> >
> >
> > I am looking forward to your replies!
> >
> >
> > Best,
> >
> > Christoph
> >
> >
> >
> >
> >
> 
>


More information about the Squeak-dev mailing list