Thread: getting the max of some numbers

To get the maximum of two numbers, it seems common practice to define it like this:

Code:

#define MAX(a,b) ((a)>(b)?(a):(b))

For my project, I need to repeatedly find the maximum of 2-5 numbers. And I want to do it efficient as it will be used billions of times.
The time I call, I know which case I need, so I could define functions for each case.

I saw people using this:

Code:

#define MAX4(a,b,c,d) (MAX(a,b) > MAX(c,d) ? MAX(a,b) : MAX(c,d))

But then I need 4 comparisons (which could be done in 3).


So, would it make sense to have functions max3(a,b,c), max4(a,b,c,d) and max5(a,b,c,d,e) like the following?

Code:

int max4(int a, int b, int c, int d) {
  int max =a;
  if (b>max) {max = b;}
  if (c>max) {max = c;}
  if (d>max) {max = d;}
  return max;
}

Alternatively do the same row of computations in the main function itself, does it create any overhead to pass it to a function etc?


To get the maximum of several (abritrary large number of) numbers, one can use sth like:

Code:

int max(int *arr, int arr_size) {
  int max = *(arr+0);
  int i;
  for(i=1; i<arr_size; i++) {
    if(*(arr+i) > max) {
      max = *(arr+i);
    }
  }
  return max;
}

But to use such an approach, one needs to create an array to hold all the values first. Is it the same complexity as the one above?

The values for a,b,c do also have to be computed and I could call a max4(what-i-do-to-get-first-value,comp-for-2nd,...) which means I don't need to allocate the space in main first, will I gain anything by this approach? Or is it just less readable?

As you can see, I was thinking about it and I programmed quite a lot, but I am new to C, and need to get the concepts clear... I can think of many alternatives to the same problem, but I can not argue which one is 'smartest', fastest, least memory hungry, ... (which I know often are different answers!)

Not having seen enough of your code to form a real opinion, I would suggest you investigate the C capability of handling function calls with varying numbers of arguments.

The C Book — Variable numbers of arguments

Cprogramming.com Tutorial: Variable Argument Lists for Functions

How to use variable argument lists (va_list) in C / C++ « Bobobobo’s Weblog


Some examples we use all the time are printf(), sprintf() etc.

Is it the bottleneck of your code?
Have you measured?

You won't find a significant difference in computation time. Today's instructions are parallelized and cached such that the nested if's approach's longer code would get collapsed, time-wise, just as the overhead of managing the loop counter.

But it would be interesting to see actual execute times when it's done millions of times. The conclusions would still be invalid since you could move to a different architecture.

Thanks for your input, also good to know how to call a fuction with variable number of arguments.
It is not THE bottleneck in the code, but whatever is called so often, should be done efficiently, other calculations have to be done just as often, but I didn't see a way to get an addition much faster...
I tried to benchmark a testrun with ~60 billion calls to the max-function. So it runs the whole code with all the other things, but the only difference between the binaries was the way to get the max. All code has been compiled with -O3.

Code:

#using the maxof implementation from http://publications.gbdirect.co.uk/c_book/chapter9/stdarg.html
1363.62user 0.07system 22:43.98elapsed 99%CPU (0avgtext+0avgdata 236864maxresident)k
32inputs+0outputs (1major+14846minor)pagefaults 0swaps

#using 'max(int *arr, int arr_size)' as above
850.17user 0.04system 14:10.40elapsed 99%CPU (0avgtext+0avgdata 236864maxresident)k
32inputs+0outputs (1major+14846minor)pagefaults 0swaps

#using '#define MAX4(a,b,c,d) ...' as above and similar for MAX3, MAX5 (more comparisons than needed)
863.20user 0.35system 14:23.70elapsed 99%CPU (0avgtext+0avgdata 236864maxresident)k
0inputs+0outputs (0major+14847minor)pagefaults 0swaps

# using 'int max4(int a, int b, int c, int d)' as above and similar for max3, max5
849.84user 0.03system 14:10.04elapsed 99%CPU (0avgtext+0avgdata 236864maxresident)k
0inputs+0outputs (0major+14847minor)pagefaults 0swaps

# also using max4 etc, but not storing the different possible values in tmp variables before
# calculations in call directly, i.e. max4(0, somevalue != 0 ? somevalue + another : -1, ...)
783.40user 0.06system 13:03.62elapsed 99%CPU (0avgtext+0avgdata 236864maxresident)k
0inputs+0outputs (0major+14847minor)pagefaults 0swaps

#not using functions, but doing all in main with subsequent ifs (*)
845.72user 0.04system 14:05.93elapsed 99%CPU (0avgtext+0avgdata 236864maxresident)k
0inputs+0outputs (0major+14847minor)pagefaults 0swaps

(*)
tmp_max = 0;
if ((tmp_score = somevalue != 0 ? somevalue + another : -1) > tmp_max)
  tmp_max = tmp_score;
if ((tmp_score = ...) > tmp_max)
  tmp_max = tmp_score;
...

The times given are for a complete run of my whole real program. So it does make a difference. And it was not only about shaving off some minutes, but to understand which concepts create overhead, and which don't.
So, I now learned that I won't use variable argument lists when performance is critical. And the difference in the other cases might be negligible.
btw: I did not spent a day on it. And the whole code will run a long time on large queries, so I'm not in doubt that loosing time is worth the effort. But again, it's mostly my own curiosity.

It'd be more effective to optimize bottleneck.
Since your function will be called millions of times, where does it get its input???
From a file? Then IO is probably overhead. Try to change IO buffer size to optimal value and you'll probably get some speed....