Which one of the two is efficient?

Question

I have been reading a blog where the author has mentioned the below two styles of coding.

Min and Max 1

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int x : array) {
if (x < min) min = X;
if (x > max) max = X; 
}

Min and Max 2

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int x : array) {
    if (x < min) min = X;
}
for (int x : array) {
    if (x > max) max = X;
}

But never gave the conclusion which one is efficient.

Can anyone point out which one is efficient & why ?

Possible duplicate of [Is micro-optimisation important when coding?](https://softwareengineering.stackexchange.com/questions/99445/is-micro-optimisation-important-when-coding) — gnat, Jun 17 '17 at 15:45
Hopefully, the compiler will render them into identical machine code. — 4castle, Jun 17 '17 at 17:47
You should use the first code since it is shorter and expected to be faster... — Phil1970, Jun 17 '17 at 19:58
You should use the second because slowing down the CPU is by far preferable to failing to indent. :P — candied_orange, Jun 17 '17 at 21:07

Erik Eidt · Answer 1 · 2017-06-17T16:05:47.700

Both of these have O(N) performance, which is to say they scale linearly with the size of the array.

However, and without consideration of whether this is an optimization or not, if the size of the array is significant relative to the processor cache size(s), then the first one will have fewer cache misses, which will be a considerable factor in performance, since cache usage is a big deal to modern processors.

The latter approach will scan the memory linearly twice. So, if the array is sufficiently large, on the first pass, the beginning of the array will get pulled into the cache, but be purged by subsequent parts of the array.

The second pass will then have to pull the whole array thru the cache once more. If the work of the second pass can overlap with the work of the first, this extra pull thru the cache will be avoided.

For the best separation of concerns, we would do each separately, but that would look like this:

int min = Integer.MAX_VALUE;
for (int x : array) {
    if (x < min) min = x;
}

int max = Integer.MIN_VALUE;
for (int x : array) {
    if (x > max) max = x;
}

and perhaps each in its own method. (The difference being that we don't initialize min and max together then do min, then max.)

However, if you always need the pair together, you might use your first approach, and I would not even consider that an optimization over the latter approach, given obtaining the min/max pair as a requirement.

Also, these days it's relatively uncommon to deal with an array itself. If you have a stream (or other iterable) walking it twice is less efficient (and may produce different results!) — Telastyn, Jun 17 '17 at 16:25

score 0 · Answer 2 · answered Jun 17 '17 at 17:32

What you are trying to do is called a "micro-optimisation". Micro-optimisations usually don't gain very much; much much bigger savings can often be made from looking at things in a bigger context.

An example: I start with an empty array. Then I add ten thousand random integers at the end of the array, and after adding each integer I want to know the largest and smallest array element. The micro-optimisation of finding the maximum and minimum of an array as fast as possible may make this twice as fast, or maybe five times as fast. The higher level optimisation, remembering the maximum and minimum of the previous array and then just comparing these with the newly added value, makes it 1,000 times faster.

This does not address the question (and the difference can be substantial). It is like me telling you you should have had a beer instead of writing that answer. — Martin Maat, Jun 17 '17 at 21:55

Which one of the two is efficient?

Min and Max 1

Min and Max 2

2 Answers2