What can I do to optimize the following code?

Question

int FindingMoves(int input1) {
    int result = 0;
    int input2 = input1 + 1;

    result = (2 * input2 + 1) * (2 * input2 + 1);
    return result;
}

What should I do to optimize the above C program which must be considered as efficient?

Should I use another programming language to a better result for above program maybe Java8, C++?

What does it do? Does it work? What brought you to the conclusion that it could be optimized? — E_net4, Jul 15 '17 at 12:01
This question is more suitable for [Code Review](http://codereview.stackexchange.com/) — gp_sflover, Jul 15 '17 at 12:02
["Premature optimization is the root of all evil"](http://wiki.c2.com/?PrematureOptimization) — pmg, Jul 15 '17 at 12:45

score 6 · Answer 1 · edited Jul 15 '17 at 12:20

One way to optimize a code is to let the compiler do the job for you.

Consider different versions of the same function:

int Finding_Moves(int input)
{
    ++input;
    input *= 2;
    ++input;
    return input * input;
}

int Finding__Moves(int input1)
{
    int input2 = 2*(input1 + 1) + 1;
    return input2*input2;
}

int FindingMoves(int input1)
{
    int result = 0;
    int input2 = input1 + 1;

    result = (2*input2 + 1)*(2*input2 + 1);
    return result;
}

In all cases the generated assembly is the same:

    lea     eax, [rdi+3+rdi]
    imul    eax, eax
    ret

HERE

Which optimizations flags where used? – sg7 Jul 15 '17 at 13:06 — sg7, Jul 15 '17 at 13:06

score 1 · Answer 2 · answered Jul 15 '17 at 12:03

1

Very little need to optimize this simple code, but alas:

int FindingMoves(int input1)
{
    int input2 = 2*(input1 + 1) + 1;
    return input2*input2;
}

answered Jul 15 '17 at 12:03

Paul Ogilvie

25,048
4
23
41

will it make a bit more optimizing if I use bitwise multiplication in-place ++input; input <<=1;++input; return input*input; like this. – Mickey Jack Jul 17 '17 at 06:18
@Mickey Jack, `++input` will result in another store, i.e. is equivalent to `input= input+1;` and so is slower. Same for `input<<=1;`. A shift-left instead of multiplication with 2 is possibly faster. – Paul Ogilvie Jul 17 '17 at 10:09

score 1 · Answer 3 · answered Jul 15 '17 at 13:07

If you are interested in micro-optimization, you can play with Godbolt's fantastic Compiler Explorer

For example both gcc -O2 and clang -O2 compile your code into just 2 instructions:

FindingMoves(int):                      # @FindingMoves(int)
        lea     eax, [rdi + rdi + 3]
        imul    eax, eax
        ret

You could rewrite the source to make it more readable, but modern compilers already squeeze every bit of performance from it.

I personally would write:

int FindingMoves(int input) {
    int x = 2 * (input + 1) + 1;
    return x * x;
}

Be aware that optimizing a tiny piece of code like this is not worth it, first get the full program to perform correctly and use an extensive test suite to verify that. Then improve your code to make it more readable, more secure, more reliable, and still fully correct as verified by the test suite.

Then, if measured performance is not satisfactory, write performance tests with benchmark data and use a profiler to identify areas of improvement.

Focussing on optimization too soon is called premature optimization, a condition that causes frustration at many levels.

what about this ++input; input <<=1;++input; return input*input; — Mickey Jack, Jul 17 '17 at 06:17
`++input; input <<=1;++input; return input*input; ` compiles to the same code, but it is less readable and has undefined behavior for negative values of `input`. As a rule of thumb, it is more complicated to optimize expressions with side effects. Computing intermediary values in separate variables actually improves both readability and code generation. — chqrlie, Jul 17 '17 at 07:55

score 1 · Answer 4 · answered Jul 15 '17 at 13:46

1

Without resorting to assember, the simple optimisation is

int FindingMoves(int input1)
{
    int term = 2*input1 + 3;
    return term*term;
}

Two multiplications, one addition, and then the result is returned. And it's simple enough that any decent quality compiler can produce effective output quite easily.

I'd want to see significant evidence from test cases and profiling before I would try to optimise further.

answered Jul 15 '17 at 13:46

Peter

35,646
4
32
74

`int term = (input1 << 1) + 3;` would be a micro-optimization more. `int term = input1 + input1 + 3;` would also be a little bit better, 2 additions and 1 multiplication. – mch Jul 15 '17 at 14:08
Most compilers can decide, based on their own criteria, whether a multiplication by two is better left as is, converted to a bit shift, or converted to an addition. No need for a human to do those transformations. It's a fair bet that most mere mortals can simplify basic algebraic expressions (e.g. `2*(input + 1) + 1` to `2*input + 3`) as I have done - and I tend to lean to comprehensible code. – Peter Jul 15 '17 at 14:19

What can I do to optimize the following code?

4 Answers4