Most efficient way to find the greatest of three ints

Question

(pseudo code)

function highest(i, j, k)
{

  if(i > j && i > k)
  {
    return i;
  }
  else if (j > k)
  {
    return j;
  }
  else
  {
    return k;
  }
}

I think that works, but is that the most efficient way?

Answer 1

To find the greatest you need to look at exactly 3 ints, no more no less. You're looking at 6 with 3 compares. You should be able to do it in 3 and 2 compares.

int ret = max(i,j);
ret = max(ret, k);
return ret;

Answer 2

Pseudocode:

result = i
if j > result:
  result = j
if k > result:
  result = k
return result

Answer 3

How about

return i > j? (i > k? i: k): (j > k? j: k);

two comparisons, no use of transient temporary stack variables...

Answer 4

Your current method: http://ideone.com/JZEqZTlj (0.40s)

Chris's solution:

int ret = max(i,j);
ret = max(ret, k);
return ret;

http://ideone.com/hlnl7QZX (0.39s)

Solution by Ignacio Vazquez-Abrams:

result = i;
if (j > result)
  result = j;
if (k > result)
  result = k;
return result;

http://ideone.com/JKbtkgXi (0.40s)

And Charles Bretana's:

return i > j? (i > k? i: k): (j > k? j: k);

http://ideone.com/kyl0SpUZ (0.40s)

Of those tests, all the solutions take within 3% the amount of time to execute as the others. The code you are trying to optimize is extremely short as it is. Even if you're able to squeeze 1 instruction out of it, it's not likely to make a huge difference across the entirety of your program (modern compilers might catch that small optimization). Spend your time elsewhere.

EDIT: Updated the tests, turns out it was still optimizing parts of it out before. Hopefully it's not anymore.

Answer 5

Not sure if this is the most efficient or not, but it might be, and it's definitely shorter:

int maximum = max( max(i, j), k);

Answer 6

For a question like this, there is no substitute for knowing just what your optimizing compiler is doing and just what's available on the hardware. If the fundamental tool you have is binary comparison or binary max, two comparisons or max's are both necessary and sufficient.

I prefer Ignacio's solution:

result = i;
if (j > result)
  result = j;
if (k > result)
  result = k;
return result;

because on the common modern Intel hardware, the compiler will find it extremely easy to emit just two comparisons and two cmov instructions, which place a smaller load on the I-cache and less stress on the branch predictor than conditional branches. (Also, the code is clear and easy to read.) If you are using x86-64, the compiler will even keep everything in registers.

Note you are going to be hard pressed to embed this code into a program where your choice makes a difference...

Answer 7

I like to eliminate conditional jumps as an intellectual exercise. Whether this has any measurable effect on performance I have no idea though :)

#include <iostream>
#include <limits>

inline int max(int a, int b)
{
    int difference = a - b;
    int b_greater = difference >> std::numeric_limits<int>::digits;
    return a - (difference & b_greater);
}

int max(int a, int b, int c)
{
    return max(max(a, b), c);
}

int main()
{
    std::cout << max(1, 2, 3) << std::endl;
    std::cout << max(1, 3, 2) << std::endl;
    std::cout << max(2, 1, 3) << std::endl;
    std::cout << max(2, 3, 1) << std::endl;
    std::cout << max(3, 1, 2) << std::endl;
    std::cout << max(3, 2, 1) << std::endl;
}

This bit twiddling is just for fun, the cmov solution is probably a lot faster.