www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Can the D compiler detect final and optimize?

reply IGotD- <nise nise.com> writes:
A little bit related to that some want class methods to be final 
by default just like in C++. If I'm not mistaken one benefit of 
final as default is that the compiler will insert hard coded 
branches to the method as well as the possibility to do inlining. 
Are my assumptions correct?

Instead of having final as default, can't the compiler itself 
infer when a class is implicitly final and do the optimizations 
itself? Benefits would be that a programmer has the possibility 
to extend about all classes (in C++ would only be possible if 
class author makes all methods virtual). The final keyword would 
just mean that a class method is not allowed to be overridden.

Is this possible at all?
Mar 13 2020
next sibling parent reply rikki cattermole <rikki cattermole.co.nz> writes:
Why would this be needed?

With ldc -O3 the test function can be completely erased:

import std;
void main()
{
     Foo foo = new Foo;
     foo.x = 7;
     test(foo);
}

void test(Foo foo) {
     writeln(foo.get);
}

class Foo {
     int x;

     int get() { return x; }
}
Mar 13 2020
parent IGotD- <nise nise.com> writes:
On Friday, 13 March 2020 at 15:15:50 UTC, rikki cattermole wrote:

 Why would this be needed?

 With ldc -O3 the test function can be completely erased:

 import std;
 void main()
 {
     Foo foo = new Foo;
     foo.x = 7;
     test(foo);
 }

 void test(Foo foo) {
     writeln(foo.get);
 }

 class Foo {
     int x;

     int get() { return x; }
 }


The D programming language by Andrei Alexandrescu. Chapter 6.6.

"So final non-override methods are never subjected to indrect 
calls; instead they enjoy the same calling convention, low 
overhead and inlining opportunities as regular functions"

I think I saw a difference between DMD and LDC previously where 
LDC actually could in some cases infer that the method is final.

If the compiler can infer that a method is final (officially by 
language standard), then what would the argument for final as 
default be?
Mar 13 2020
prev sibling next sibling parent reply Dennis <dkorpel gmail.com> writes:
On Friday, 13 March 2020 at 15:08:34 UTC, IGotD- wrote:

 Instead of having final as default, can't the compiler itself 
 infer when a class is implicitly final and do the optimizations 
 itself?


The problem is that only at runtime are all the derived classes 
known, and by then the code is already compiled. I think the Java 
Virtual Machine can automatically elide virtual calls by virtue 
of being a JIT, but for D this would mean either telling the 
compiler 'assume all derived classes are present in the source 
files provided here' or doing fancy link-time optimization.
Mar 13 2020
next sibling parent reply Daniel Kozak <kozzi11 gmail.com> writes:
On Fri, Mar 13, 2020 at 5:15 PM Dennis via Digitalmars-d <
digitalmars-d puremagic.com> wrote:


 On Friday, 13 March 2020 at 15:08:34 UTC, IGotD- wrote:

 Instead of having final as default, can't the compiler itself
 infer when a class is implicitly final and do the optimizations
 itself?


 The problem is that only at runtime are all the derived classes
 known, and by then the code is already compiled. I think the Java
 Virtual Machine can automatically elide virtual calls by virtue
 of being a JIT, but for D this would mean either telling the
 compiler 'assume all derived classes are present in the source
 files provided here' or doing fancy link-time optimization.


I believe LTO could do that in some cases
Dec 25 2020
next sibling parent reply Johan <j j.nl> writes:
On Friday, 25 December 2020 at 19:29:26 UTC, Daniel Kozak wrote:

 On Fri, Mar 13, 2020 at 5:15 PM Dennis via Digitalmars-d < 
 digitalmars-d puremagic.com> wrote:


 On Friday, 13 March 2020 at 15:08:34 UTC, IGotD- wrote:

 Instead of having final as default, can't the compiler 
 itself infer when a class is implicitly final and do the 
 optimizations itself?


 The problem is that only at runtime are all the derived 
 classes known, and by then the code is already compiled. I 
 think the Java Virtual Machine can automatically elide virtual 
 calls by virtue of being a JIT, but for D this would mean 
 either telling the compiler 'assume all derived classes are 
 present in the source files provided here' or doing fancy 
 link-time optimization.


 I believe LTO could do that in some cases


"Whole program optimization", indeed. Search for `fwhole-program` 
for GCC and Clang C++ compilers.
I don't know how it works for GDC (I think it may have an edge 
over LDC on this topic), but for LDC we don't tell the optimizer 
that our vtables are indeed vtables, so I'm not sure if 
devirtualization works as well as for Clang (which does inform 
the optimizer about vtables).

-Johan
Dec 26 2020
parent reply Iain Buclaw <ibuclaw gdcproject.org> writes:
On Sunday, 27 December 2020 at 00:25:54 UTC, Johan wrote:

 On Friday, 25 December 2020 at 19:29:26 UTC, Daniel Kozak wrote:

 I believe LTO could do that in some cases


 "Whole program optimization", indeed. Search for 
 `fwhole-program` for GCC and Clang C++ compilers.
 I don't know how it works for GDC (I think it may have an edge 
 over LDC on this topic), but for LDC we don't tell the 
 optimizer that our vtables are indeed vtables, so I'm not sure 
 if devirtualization works as well as for Clang (which does 
 inform the optimizer about vtables).


When `scope` is used, the compiler does constant propagation of 
the vtable, because what the optimizer sees is:

     MyClass __scopeinit = MyClass.init;
     MyClass* var = &__scopeinit;
     (var.__vptr + 40)();

If the guts of _d_newclass were also made visible (such as, it 
was templatized in object.d), then such devirtualization through 
constant propagation would also occur for simple cases of classes 
new'd on the GC.

Other than that, I'm not sure about other ways to do full 
devirtualisation of method calls, you are more likely thinking of 
speculative devirtualization, which looks something like this:

     if ((&var.foo).funcptr is &MyClass.foo)
         MyClass.foo();
     else
         var.foo();

If the direct call is inlined, and if the condition is true, then 
the resulting code may run about 3-5x faster for simple functions.

Though these days, I think most CPUs have branch prediction for 
even indirect calls, so if no optimization happens, the 
speculative devirtualization like the above will just consume 
code space and branch prediction buffers.
Dec 27 2020
parent Johan Engelen <j j.nl> writes:
On Sunday, 27 December 2020 at 15:22:07 UTC, Iain Buclaw wrote:

 On Sunday, 27 December 2020 at 00:25:54 UTC, Johan wrote:

 On Friday, 25 December 2020 at 19:29:26 UTC, Daniel Kozak 
 wrote:

 I believe LTO could do that in some cases


 "Whole program optimization", indeed. Search for 
 `fwhole-program` for GCC and Clang C++ compilers.
 I don't know how it works for GDC (I think it may have an edge 
 over LDC on this topic), but for LDC we don't tell the 
 optimizer that our vtables are indeed vtables, so I'm not sure 
 if devirtualization works as well as for Clang (which does 
 inform the optimizer about vtables).


 When `scope` is used, the compiler does constant propagation of 
 the vtable, because what the optimizer sees is:

     MyClass __scopeinit = MyClass.init;
     MyClass* var = &__scopeinit;
     (var.__vptr + 40)();

 If the guts of _d_newclass were also made visible (such as, it 
 was templatized in object.d), then such devirtualization 
 through constant propagation would also occur for simple cases 
 of classes new'd on the GC.


This is already done by LDC (because of overwriting the vtable 
ptr after calling _d_newclass, which is redundant but indeed 
helps with devirtualizing).


 Other than that, I'm not sure about other ways to do full 
 devirtualisation of method calls, you are more likely thinking 
 of speculative devirtualization


No. I meant that if you know (or assume to know) the full 
inheritance hierarchy, you can devirtualize this:

void foo(A a) {
   a.some_virtual_call();
}


 speculative devirtualization, which looks something like this:

     if ((&var.foo).funcptr is &MyClass.foo)
         MyClass.foo();
     else
         var.foo();

 If the direct call is inlined, and if the condition is true, 
 then the resulting code may run about 3-5x faster for simple 
 functions.

 Though these days, I think most CPUs have branch prediction for 
 even indirect calls, so if no optimization happens, the 
 speculative devirtualization like the above will just consume 
 code space and branch prediction buffers.


Not so: 
http://johanengelen.github.io/ldc/2016/04/13/PGO-in-LDC-virtual-calls.html

The reason is that devirtualization enables other optimizations 
(like inlining, which in turn creates new profitable 
optimizations).

Rather than doing this whole program optimization with the 
assumption (!) of knowing the full calls hierarchy, I think it is 
better to work on preserving vtable knowledge for subsequent 
method calls, using the knowledge that the object's dynamic type 
can not change at runtime: although a class method call cannot 
change the vtable, the GDC and LDC optimizers assume that it may 
be overwritten because a non-const pointer to the object (the 
`this` ptr) is passed to the class method.

See: https://d.godbolt.org/z/xbajvT
```
     A a = new A();  // `scope` is needed for GDC
     a.foo(); // devirtualized
     a.foo(); // not devirtualized
     a.foo(); // not devirtualized
```

-Johan
Dec 27 2020
prev sibling parent Gregor =?UTF-8?B?TcO8Y2ts?= <gregormueckl gmx.de> writes:
On Friday, 25 December 2020 at 19:29:26 UTC, Daniel Kozak wrote:

 On Fri, Mar 13, 2020 at 5:15 PM Dennis via Digitalmars-d < 
 digitalmars-d puremagic.com> wrote:


 [...]


 I believe LTO could do that in some cases


If LTO devirtualizes, then there is the implicit assumption that 
there is additional code load at runtime, right? So this breaks 
potentially if you e.g. use dlopen() to load a plugin?
Dec 26 2020
prev sibling parent Daniel Kozak <kozzi11 gmail.com> writes:
On Fri, Dec 25, 2020 at 8:29 PM Daniel Kozak <kozzi11 gmail.com> wrote:


 On Fri, Mar 13, 2020 at 5:15 PM Dennis via Digitalmars-d <
 digitalmars-d puremagic.com> wrote:


 On Friday, 13 March 2020 at 15:08:34 UTC, IGotD- wrote:

 Instead of having final as default, can't the compiler itself
 infer when a class is implicitly final and do the optimizations
 itself?


 The problem is that only at runtime are all the derived classes
 known, and by then the code is already compiled. I think the Java
 Virtual Machine can automatically elide virtual calls by virtue
 of being a JIT, but for D this would mean either telling the
 compiler 'assume all derived classes are present in the source
 files provided here' or doing fancy link-time optimization.


 I believe LTO could do that in some cases


https://news.ycombinator.com/item?id=17504370
Dec 25 2020
prev sibling parent kindouchoud <jeyak10528 ailiking.com> writes:
On Friday, 13 March 2020 at 15:08:34 UTC, IGotD- wrote:

 A little bit related to that some want class methods to be 
 final by default just like in C++. If I'm not mistaken one 
 benefit of final as default is that the compiler will insert 
 hard coded branches to the method as well as the possibility to 
 do inlining. Are my assumptions correct?

 Instead of having final as default, can't the compiler itself 
 infer when a class is implicitly final and do the optimizations 
 itself? Benefits would be that a programmer has the possibility 
 to extend about all classes (in C++ would only be possible if 
 class author makes all methods virtual). The final keyword 
 would just mean that a class method is not allowed to be 
 overridden.

 Is this possible at all?


The issue is that just at runtime are for the most part the 
inferred classes known, and by then the code is as of now 
arranged.
Dec 25 2020