8

Is there a way to tell gcc that a function that has side effects should only be called once if two subsequent calls have the same arguments. I want the following behaviour:

foo(6);//run this function
foo(6);//optimize this away
foo(6);//optimize this away
foo(5);//run this function
foo(6);//run this function again

I can make foo check a global variable before it does any work, but that is less than optimal. 

void inline foo(int i){
   static int last_i=i+1;
   if(last_i != i){
        last_i==i;
        //do_work...
    }
}

Since foo is an inline function the compiler should be able to look across invokations of foo() and see that it doesn't have to execute it. The problem is the compiler can't optimize like that for global variables, is there a way to let the compiler know it is safe to do so?

Deduplicator
  • 44,692
  • 7
  • 66
  • 118
vanjoe
  • 439
  • 4
  • 12
  • 5
    Suppose you could somehow tell the compiler to do this for you. How do you think it would pull this off, short of saving the last-used parameter in a global variable? What exactly is your objection to this technique - what's "less than optimal" about it, in your opinion? – Igor Tandetnik Aug 22 '14 at 21:21
  • something like attribute((const))? – vanjoe Aug 22 '14 at 21:22
  • a function that has side effects is not const. – Adam Aug 22 '14 at 21:26
  • 1
    this would have to be a pretty heavy function to justify the overhead, but you could store the numbers in a set, and conditionally execute them... the set could be static in the method... – Grady Player Aug 22 '14 at 21:26
  • You could also use a static variable instead of the global. That would retain encapsulation while allowing you to check what was passed during the previous call. – Degustaf Aug 22 '14 at 21:27
  • @GradyPlayer: I think you misread, a set would be serious overkill. – Mooing Duck Aug 22 '14 at 21:28
  • 1
    You can run that block of code through `uniq` (after stripping away comments) before compiling. – jxh Aug 22 '14 at 21:29
  • @IgorTandetnik I need extremely high throughput, and I don't have branch prediction. – vanjoe Aug 22 '14 at 21:33
  • So you want to optimize within a single function (otherwise the compiler can't know about previous calls and can't avoid global variable), and you are coding a very tight loop (otherwise performance wouldn't be *that* important). In this case, can't you optimize the calling code? Teach it to not call `foo` redundantly? – Igor Tandetnik Aug 22 '14 at 21:41
  • Well It's buried in a few layers of template metaprogramming so it makes it difficult. – vanjoe Aug 22 '14 at 21:47
  • let the code always call the function. have the function contain a static variable (init to some value that will never be passed) and have the function first compare the current parameter with the static value and return immediately if they are the same. Otherwise update the static variable with the new parameter and continue. – user3629249 Aug 23 '14 at 04:06

6 Answers6

7

... a function that has side effects should only be called once if two subsequent calls have the same arguments...

That function has to be idempotent then although it has side effects.

C++ standard only distinguish functions with side effects (I/O functions) and without. From compilers point of view if the function is opaque (no definition in the same translation unit) then it must have side effects and therefore it is a compiler memory barrier and the compiler cannot optimize the call away or deduce the return value (unless it is a compiler intrinsic function like memcpy).

Idempotence, computer science meaning:

In computer science, the term idempotent is used more comprehensively to describe an operation that will produce the same results if executed once or multiple times.[4] This may have a different meaning depending on the context in which it is applied. In the case of methods or subroutine calls with side effects, for instance, it means that the modified state remains the same after the first call. In functional programming, though, an idempotent function is one that has the property f(f(x)) = f(x) for any value x.[5]

And C++ does not have that notion.

Maxim Egorushkin
  • 131,725
  • 17
  • 180
  • 271
  • Interesting. I Knew about the f(f(x))=f(x) definition, but not the "the modified state remains the same after the first call." Definition. I'm going to accept this answer even though it is disappointing. – vanjoe Aug 22 '14 at 21:39
  • 1
    There's a simple way to enable the optimization: Just provide a small inline-function for checking, which will call an external function to do the heavy work if needed. – Deduplicator Aug 22 '14 at 22:59
5

You could use static variables:

int foo(int param){
   static int last=0;
   static int result=1;
   if(last==param) return result;
   else{
      last=param;
      result=param/2+1;
      return result;
   }
}
Paweł Stawarz
  • 3,952
  • 2
  • 17
  • 26
  • What if function is called first time? What values `static` variables are going to have then? – GingerPlusPlus Aug 22 '14 at 21:28
  • usually you set `static int result = -1` or some invalid input. (I've done code like this occasionally) – Mooing Duck Aug 22 '14 at 21:29
  • @MooingDuck And they don't are initialized in each function invocation? – GingerPlusPlus Aug 22 '14 at 21:31
  • 1
    @GingerPlusPlus You can simply set the values on creation. Added those four characters for clarity :) No. They're static. They're initialized only once. – Paweł Stawarz Aug 22 '14 at 21:31
  • 1
    [Statics are automatically initialized to zero unless you say they should be not.](http://stackoverflow.com/questions/13251083/the-initialization-of-static-variables-in-c) – Jongware Aug 22 '14 at 21:42
3

in order for a compiler to optimize away a function with side effects it would have to understand the side effects it produces. GCC has no annotation to describe the type of side effects so it is not possible.

If the function is in the same compilation unit the compiler might be able to figure out the calls are redundant, but as that only works if the function is simple enough for the compiler to completely understand which is seldom the case. You are better of putting that logic into the caller or callee.

For completeness, if the function does not have side affects you can use __attribute__((pure)) and __attribute__((const)) to tell the compiler this.

jtaylor
  • 2,389
  • 19
  • 19
2

You can use functor:

class{
        auto foo(int a);
        int last_arg;
        bool first_invoke=true;
    public:
        auto operator(int a){
            if(first_invoke){
                first_invoke=false;
                last_arg=a;
                return foo(a);
            }
            if(a==last_arg)
                //do_something_special;
            else{
                last_arg=a;
                return foo(a);
            }
        }
}foo;

This solution is Standard-dependent, not compiler-dependent.

Or you can play with foo's static varaibles.

GingerPlusPlus
  • 5,336
  • 1
  • 29
  • 52
2

No. This behavior is not part of the semantics of any language of the many I have seen and certainly not C/C++. Gcc can't provide options to compile code with wrong semantic behavior!

The reverse is possible however. If a function foo() is "pure" ie with no side effects then a good compiler will deal with eg y=foo(x)+foo(x); using only a single call to foo(). The Ada language provides a pragma to assert pureness for this purpose.

Gene
  • 46,253
  • 4
  • 58
  • 96
0

So the reason I was hesitant to just put a check against the last arguments used is that the function call was inside some very tight inner loops, so the extra comparison and branch instructions would be annoying especially on platforms with (or very poor) branch prediction.

I decided to see what gcc does when I tried it. I used the following code:

#include <stdio.h>
int check;

void myfun(int num){
        printf("changing to %d\n",num);
}
static inline __attribute__((always_inline)) void idem(int num){
    if(num!=check){
        myfun(num);
        check=num;
    }
}

int main(){
    idem(5);
    idem(5);
    idem(4);
    idem(4);
    return 0;
}

This compiles (gcc -O2 main.c) on x86 (not my final target) to :

0000000000400440 <main>:
  400440:       48 83 ec 08             sub    $0x8,%rsp
  400444:       83 3d e5 0b 20 00 05    cmpl   $0x5,0x200be5(%rip)        # 601030 <check>
  40044b:       74 14                   je     400461 <main+0x21>
  40044d:       bf 05 00 00 00          mov    $0x5,%edi
  400452:       e8 09 01 00 00          callq  400560 <myfun>
  400457:       c7 05 cf 0b 20 00 05    movl   $0x5,0x200bcf(%rip)        # 601030 <check>
  40045e:       00 00 00 
  400461:       bf 04 00 00 00          mov    $0x4,%edi
  400466:       e8 f5 00 00 00          callq  400560 <myfun>
  40046b:       c7 05 bb 0b 20 00 04    movl   $0x4,0x200bbb(%rip)        # 601030 <check>
  400472:       00 00 00 
  400475:       31 c0                   xor    %eax,%eax
  400477:       5a                      pop    %rdx
  400478:       c3                      retq   
  400479:       90                      nop
  40047a:       90                      nop
  40047b:       90                      nop

So as you can see myfun is only called twice like I want. Therefore it looks like it is possible for gcc to do this correctly. If someone would like to chime in on any limitations to the optimizations here I would be very intererested

vanjoe
  • 439
  • 4
  • 12