Incorrect optimisation

[ltratt]

SOMpp tries to optimise ifFalse / ifTrue but does so in an incorrect way. Consider this contrived program:

T = (
    ifTrue: x = ( ^2 )

    run = (
        (self ifTrue: 3) println.
    )
)

On yksom and Java-SOM this prints out 2, but in SOM++ it prints out 3. The offending code is here:

diff --git a/src/compiler/Parser.cpp b/src/compiler/Parser.cpp
index 300dd06..276aeff 100644
--- a/src/compiler/Parser.cpp
+++ b/src/compiler/Parser.cpp
@@ -690,13 +690,6 @@ void Parser::keywordMessage(MethodGenerationContext* mgenc, bool super) {
     StdString kw = keyword();
     
     // special compilation for ifTrue and ifFalse
-    if (!super && kw == "ifTrue:") {
-        ifTrueMessage(mgenc);
-        return;
-    } else if (!super && kw == "ifFalse:") {
-        ifFalseMessage(mgenc);
-        return;
-    }
     formula(mgenc);
     while (sym == Keyword) {
         kw.append(keyword());

Basically SOMpp compiles any function called ifFalse / ifTrue into optimised versions that are only correct if the self object is a boolean. While I appreciate this is a useful optimisation for SOMpp, it seems a fairly clear violation of the intended language semantics?

[krono]

Am 15. November 2019 16:47:12 MEZ schrieb Laurence Tratt <notifications@github.com>:

SOMpp tries to optimise `ifFalse` / `ifTrue` but does so in an incorrect way. Consider this contrived program: ```som T = ( ifTrue: x = ( ^2 ) run = ( (self ifTrue: 3) println. ) ) ``` On yksom and Java-SOM this prints out 2, but in SOM++ it prints out 3. The offending code is here: ``` diff --git a/src/compiler/Parser.cpp b/src/compiler/Parser.cpp index 300dd06..276aeff 100644 --- a/src/compiler/Parser.cpp +++ b/src/compiler/Parser.cpp @@ -690,13 +690,6 @@ void Parser::keywordMessage(MethodGenerationContext* mgenc, bool super) { StdString kw = keyword(); // special compilation for ifTrue and ifFalse - if (!super && kw == "ifTrue:") { - ifTrueMessage(mgenc); - return; - } else if (!super && kw == "ifFalse:") { - ifFalseMessage(mgenc); - return; - } formula(mgenc); while (sym == Keyword) { kw.append(keyword()); ``` Basically SOMpp compiles *any* function called `ifFalse` / `ifTrue` into optimised versions that are only correct if the `self` object is a boolean. While I appreciate this is a useful optimisation for SOMpp, it seems a fairly clear violation of the intended language semantics?

this is true for most Smalltalks, btw. pharo alleviates this, but most compile #ifTrue/#ifFalse to a virtue bytecode jump. for practical purposes this has rather been a minor annoyance than a true bug, as traditionally this shortcut gives hundred- to thousandfold speedup

…

-t -- Sent from a mobile device

[ltratt]

Leaving aside the philosophical point about correctness, there's no way this change gives 100x or 1000x -- or even 10x! When I measured it -- quickly, admittedly! -- on a simple while loop program with SOM++, it made ~7-10% difference.

[krono]

Am 15. November 2019 23:05:08 MEZ schrieb Laurence Tratt <notifications@github.com>:

Leaving aside the philosophical point about correctness, there's no way this change gives 100x or 1000x -- or even 10x! When I measured it -- quickly, admittedly! -- on a simple while loop program with SOM++, it made ~7-10% difference.

yeah, I was talking about the traditional Smalltalks and maybe CSOM. -- Sent from a mobile device

[ltratt]

I don't think I've ever seen an interpreter so inept that this optimisations (or an equivalent) could give even a 10x performance increase, let alone 100x or 1000x. When I quickly benchmarked CSOM, it looked to be maybe 10x slower than SOM++ overall, and I'm pretty sure that ifTrue does not account for all of that. I think the numbers you quoted probably come from folklore, and we all know how reliable that can be :)

[smarr]

SOM++ benefits a little less because it has lookup caching. Here the benchmark results:

cmd: SOMpp/cmake-build$ ./SOM++ -cp ../Smalltalk:../Examples/Benchmarks:../Examples/Benchmarks/LanguageFeatures ../Examples/Benchmarks/All.som

Fibonacci
   w/if*:  85 ms
   w/o:   155 ms

Dispatch
   w/if*: 106 ms
   w/o:   115 ms

Bounce
   w/if*:  89 ms
   w/o:   112 ms

Loop
   w/if*:  96 ms
   w/o:   107 ms

Permute
   w/if*:  99 ms
   w/o:   118 ms

Queens
   w/if*: 112 ms
   w/o:   129 ms

List
   w/if*: 138 ms
   w/o:   177 ms

Recurse
   w/if*: 111 ms
   w/o:   128 ms

Storage
   w/if*: 72 ms
   w/o:   95 ms

Sieve
   w/if*: 110 ms
   w/o:   124 ms

BubbleSort
   w/if*:  92 ms
   w/o:   104 ms

QuickSort
   w/if*: 70 ms
   w/o:   86 ms

Sum
   w/if*:  93 ms
   w/o:   104 ms

Towers
   w/if*: 131 ms
   w/o:   171 ms

TreeSort
   w/if*:  60 ms
   w/o:   159 ms

IntegerLoop
   w/if*: 187 ms
   w/o:   213 ms

FieldLoop
   w/if*: 353 ms
   w/o:   367 ms

I am willing to consider patches...

[ltratt]

@smarr Thanks for the numbers!

I am willing to consider patches...

As in "remove the optimisation entirely"? I will happily produce a PR for that if so.

[smarr]

Given the significant benefit, I would argue that SOM++ should make sure that the receiver is Boolean and bailout otherwise to a normal send. There are various ways to do this. Quickening and guards coming to mind. I would not remove the optimization. It’s a classic one, as discussed before. It is a nice teaching example of trade offs and issues with naive optimizations.

[ltratt]

OK, that sort of thing is beyond my C++ skills and desires.

[ltratt]

@jacob-hughes and I have re-realised this issue in SOMpp. AFAIK SOMpp is the only SOM with this "optimisation"? We have disabled it locally and wonder if we should make a PR against SOMpp to remove it so that benchmarking SOMpp doesn't give misleading numbers relative to other SOMs?

[smarr]

I fear SOM++ isn't the only SOM with this optimization.

See:

• https://github.com/SOM-st/TruffleSOM/blob/master/src/trufflesom/interpreter/nodes/specialized/IfTrueIfFalseInlinedLiteralsNode.java#L51-L53 (here you see the todo...)
• https://github.com/SOM-st/TruffleSOM/blob/master/src/trufflesom/interpreter/nodes/bc/BytecodeLoopNode.java#L795-L836 Here there's no attempt to support non-boolean values
• and PySOM is basically more of the same: Implement inlining of #ifTrue:*/#ifFalse:* messages SOM-st/PySOM#32

As long as no-one writes a specification, this is an "accepted Smalltalk lie". It's lies, all the way down...

And I fear, numbers won't be anymore or less misleading with or without the optimization.
Handling things correctly would normally be a fallback case, with possible bytecode rewriting. So, except for code-size-related effects, performance in the ideal case would hopefully be unaffected in a "correct" implementation.

[ltratt]

OK, then I think we should close this issue.

[For full disclosure, we'll benchmark with this optimisation removed from SOMpp, because it's one less lie to explain :)]

[krono]

(Sidenote: sending ifTrue:/ifFalse: to something else than Boolean in ST-80 and Squeak sends #mustBeBoolean to the "offending" object…)