www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Formal annotating Code for Optimizations?

reply "Manfred_Nowak" <svv1999 hotmail.com> writes:
Example:
If two actions `a1',`a2' are based on a binary decision `b' then on a 
pure logical level one can code:

  if( b)
    a1.do; // actions have `do'- and `undo'-methods
  else
    a2.do; 

But if one knows, that the probability of `b' to be `true' is much 
greater than .5, then in order to use the precomputing capabilities 
of the CPU one would probably like to code:

  a1.do;
  if( !b){
    a1.undo;
    a2.do;
  }    
    
The other case requires similar code.

In this latter code the abstraction of a simple binary decision seems 
to be less obvious, which seems to be bad for maintenance.

Of course one can annotate with comments. But since comments can be 
hints for defencies in the language, the question rises whether one 
should formalize this:

  if( b)note( p(b)>.8)
    a1.do;
    undo a1.undo;
  else
    a2;
    undo a2.undo;

-manfred
-- 
Maybe some knowledge of some types of disagreeing and their relation 
can turn out to be useful:
http://blog.createdebate.com/2008/04/07/writing-strong-arguments/
Jul 18 2008
next sibling parent reply "Craig Black" <cblack ara.com> writes:
"Manfred_Nowak" <svv1999 hotmail.com> wrote in message 
news:g5ptdk$2t8f$1 digitalmars.com...

 Example:
 If two actions `a1',`a2' are based on a binary decision `b' then on a
 pure logical level one can code:

  if( b)
    a1.do; // actions have `do'- and `undo'-methods
  else
    a2.do;

 But if one knows, that the probability of `b' to be `true' is much
 greater than .5, then in order to use the precomputing capabilities
 of the CPU one would probably like to code:

  a1.do;
  if( !b){
    a1.undo;
    a2.do;
  }

 The other case requires similar code.

 In this latter code the abstraction of a simple binary decision seems
 to be less obvious, which seems to be bad for maintenance.

 Of course one can annotate with comments. But since comments can be
 hints for defencies in the language, the question rises whether one
 should formalize this:

  if( b)note( p(b)>.8)
    a1.do;
    undo a1.undo;
  else
    a2;
    undo a2.undo;

 -manfred
 -- 
 Maybe some knowledge of some types of disagreeing and their relation
 can turn out to be useful:
 http://blog.createdebate.com/2008/04/07/writing-strong-arguments/


It'll never be implemented, but it's a good idea.  Along the same lines, 
(another good idea that'll never be implemented), is to assign a priority to 
a virtual function.  A higher priority means that the virtual function will 
be called more.  This allows the compiler to optimize out the function 
pointer invokation for high-priority virtual functions.

-Craig
Jul 18 2008
parent reply Walter Bright <newshound1 digitalmars.com> writes:
Craig Black wrote:

 It'll never be implemented, but it's a good idea.  Along the same lines, 
 (another good idea that'll never be implemented), is to assign a priority to 
 a virtual function.  A higher priority means that the virtual function will 
 be called more.  This allows the compiler to optimize out the function 
 pointer invokation for high-priority virtual functions.


That optimization is not possible, because the compiler doesn't know if 
the virtual function is overridden or not. Bypassing the virtual 
dispatch will break the program.

However, you can tell the compiler a virtual function will not be 
overridden by declaring it 'final', and the compiler will use direct 
rather than virtual dispatch (and it does this already).
Jul 18 2008
parent downs <default_357-line yahoo.de> writes:
The following mixin code can be used to generate optimized code for specific,
final types automatically.

This can really speed up some inner loops if used carefully. It allows the
compiler to inline at the cost of one dynamic cast.

import std.stdio;

string repl(string text, string what, string by) {
  string res;
  int i;
  while (i + what.length !> text.length) {
    if (text[i .. i+what.length] == what) {
      res ~= by;
      i += what.length;
    } else {
      res ~= text[i];
      i ++;
    }
  }
  res ~= text[i .. $];
  return res;
}

static assert(repl("foobarfobes", "ob", "kn") == "foknarfknes");

template ExpectCall(string VAR, string OP, TYPES...) {
  static if (!TYPES.length)
    const string ExpectCall = repl(OP, "$$", VAR)~"; ";
  else
    const string ExpectCall = "if (auto ec_var = cast("~TYPES[0]~") "~VAR~") {
  "~repl(OP, "$$", "ec_var")~";
} else {
  "~ExpectCall!(VAR, OP, TYPES[1 .. $])~"
}";
}

class A { void test() { writefln("test A"); } }
final class B : A { void test() { writefln("test B"); } }
final class C : A { void test() { writefln("test C"); } }

void main() {
  A[] foo = [new A, new B, new C];
  pragma(msg, ExpectCall!("entry", "$$.test()", "B", "C"));
  foreach (entry; foo) {
    mixin(ExpectCall!("entry", "$$.test()", "B", "C"));
  }
}
Jul 18 2008
prev sibling parent reply JAnderson <ask me.com> writes:
Manfred_Nowak wrote:

 Example:
 If two actions `a1',`a2' are based on a binary decision `b' then on a 
 pure logical level one can code:
 
   if( b)
     a1.do; // actions have `do'- and `undo'-methods
   else
     a2.do; 
 
 But if one knows, that the probability of `b' to be `true' is much 
 greater than .5, then in order to use the precomputing capabilities 
 of the CPU one would probably like to code:
 
   a1.do;
   if( !b){
     a1.undo;
     a2.do;
   }    
     
 The other case requires similar code.
 
 In this latter code the abstraction of a simple binary decision seems 
 to be less obvious, which seems to be bad for maintenance.
 
 Of course one can annotate with comments. But since comments can be 
 hints for defencies in the language, the question rises whether one 
 should formalize this:
 
   if( b)note( p(b)>.8)
     a1.do;
     undo a1.undo;
   else
     a2;
     undo a2.undo;
 
 -manfred


MSVC++ 2005 has this profile that you can run on the code and then it 
will use that to optimize the code to use the most common paths.  I'm 
not sure if it also optimizes IF statements.  I know it optimizes 
functions layout to be more cache friendly.

-Joel
Jul 18 2008
next sibling parent Sean Kelly <sean invisibleduck.org> writes:
JAnderson wrote:

 Manfred_Nowak wrote:

 Example:
 If two actions `a1',`a2' are based on a binary decision `b' then on a 
 pure logical level one can code:

   if( b)
     a1.do; // actions have `do'- and `undo'-methods
   else
     a2.do;
 But if one knows, that the probability of `b' to be `true' is much 
 greater than .5, then in order to use the precomputing capabilities of 
 the CPU one would probably like to code:

   a1.do;
   if( !b){
     a1.undo;
     a2.do;
   }        The other case requires similar code.

 In this latter code the abstraction of a simple binary decision seems 
 to be less obvious, which seems to be bad for maintenance.

 Of course one can annotate with comments. But since comments can be 
 hints for defencies in the language, the question rises whether one 
 should formalize this:

   if( b)note( p(b)>.8)
     a1.do;
     undo a1.undo;
   else
     a2;
     undo a2.undo;

 -manfred


 
 MSVC++ 2005 has this profile that you can run on the code and then it 
 will use that to optimize the code to use the most common paths.  I'm 
 not sure if it also optimizes IF statements.  I know it optimizes 
 functions layout to be more cache friendly.


The Sun compiler does this too.  It's the code rearranging that's the 
killer feature here IMO.  I love that the compiler can ensure that the 
code for heavily used functions doesn't cross page boundaries, etc.


Sean
Jul 18 2008
prev sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
JAnderson wrote:

 MSVC++ 2005 has this profile that you can run on the code and then it 
 will use that to optimize the code to use the most common paths.  I'm 
 not sure if it also optimizes IF statements.  I know it optimizes 
 functions layout to be more cache friendly.


The dmd profiler does this too. It emits a file, trace.def, which 
optimally orders functions based on the runtime profile, which you can 
then use as input to optlink.
Jul 18 2008
next sibling parent reply BCS <ao pathlink.com> writes:
Reply to Walter,


 JAnderson wrote:
 

 MSVC++ 2005 has this profile that you can run on the code and then it
 will use that to optimize the code to use the most common paths.  I'm
 not sure if it also optimizes IF statements.  I know it optimizes
 functions layout to be more cache friendly.
 


 The dmd profiler does this too. It emits a file, trace.def, which
 optimally orders functions based on the runtime profile, which you can
 then use as input to optlink.
 


Oh? Cool! Link?
Jul 18 2008
parent Walter Bright <newshound1 digitalmars.com> writes:
BCS wrote:

 Reply to Walter,
 

 JAnderson wrote:


 MSVC++ 2005 has this profile that you can run on the code and then it
 will use that to optimize the code to use the most common paths.  I'm
 not sure if it also optimizes IF statements.  I know it optimizes
 functions layout to be more cache friendly.


 The dmd profiler does this too. It emits a file, trace.def, which
 optimally orders functions based on the runtime profile, which you can
 then use as input to optlink.


 
 Oh? Cool! Link?



http://www.digitalmars.com/ctg/trace.html
Jul 18 2008
prev sibling next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Walter Bright Wrote:

 The dmd profiler does this too. It emits a file, trace.def, which 
 optimally orders functions based on the runtime profile, which you can 
 then use as input to optlink.


Oh, good, so in the future you may do the last little step, adding to dmd a
compilation flag to perform such profile-driven optimization, like the
-fprofile-generate/-fprofile-use pair of flags of GCC.

Bye,
bearophile
Jul 18 2008
prev sibling parent JAnderson <ask me.com> writes:
Walter Bright wrote:

 JAnderson wrote:

 MSVC++ 2005 has this profile that you can run on the code and then it 
 will use that to optimize the code to use the most common paths.  I'm 
 not sure if it also optimizes IF statements.  I know it optimizes 
 functions layout to be more cache friendly.


 
 The dmd profiler does this too. It emits a file, trace.def, which 
 optimally orders functions based on the runtime profile, which you can 
 then use as input to optlink.


That's cool! It sums over multiple runs as well.  I might leave it on 
most of the time.

-Joel
Jul 18 2008