Interesting interview question...

[Please support Stackprinter with a donation]

[+72] [0] VextoR

[2011-03-31 11:06:06]

[ c++ c interview-questions for-loop ]

[ http://stackoverflow.com/questions/5498831] [DELETED]

Today I was asked this question. We have 2 cases with code blocks A, B and C. These code block don't share any resources except an iterator (int i).

Please give 3 possible reasons why case 1 could be faster than case 2, and 3 possible reasons why case 2 could be faster than case 1:

case 1

for (i=0; i<N; ++i){
 A;
 B;
 C;
}

case 2

for (i=0; i<N; ++i){
 A;
}
for (i=0; i<N; ++i){
 B;
}
for (i=0; i<N; ++i){
 C;
}

Are you in Java, C++ or C? Because the answer could be very different. - DeadMG

(27) What did you say? - Oli Charlesworth

(1) Is that question really what three conditions would make one fater than the other or were they looking for 6 independent reasons? - Jon Cage

(13) The question is stupid. the only reasonable answer is "profile and see what is faster" - VJo

(3) Case x is faster because 1) profiling showed as much, 2) profiling revealed as much, and 3) profiling barfed on case y. Alternative answer: depends on system cache size, code size of the functions, what the functions do (what data they access, which could make the previous point moot) etc... - rubenvb

(7) @VJo: I disagree. There are important differences between Case 1 and Case 2. In some cases, the compiler may be able to transform one into the other (I don't know), but fundamentally there are some important lessons here, independent of whether there's one right answer. I believe this is a good interview question, because it should provoke an interesting discussion about CPU architecture, locality, optimization, etc. - Oli Charlesworth

(5) @VJo: without understanding the reasons why each version might be faster, how would you even know that it's worth trying both versions? - Mike Seymour

(1) Have a look at loop fusion (case 1) and loop fission (case 2), two optimizations sometimes performed by compilers. - Luc Touraille

Should this be on programmers.se? - zzzzBov

The vote count on the question and answers suggest this has been posted on reddit or something. - Johannes Schaub - litb

@Oli Charlesworth, I didn't know the answer.. So I just said that case 1 is faster because of single loop.. - VextoR

Is it possible that a compiler could convert case 2 into case 1 provided there are no statements between the for loops in case 2? - Thomas Matthews

All depends on language, compiler, and target CPU/chipset. - Unsigned Code Labs

I was a little confused by you calling 'int i' an iterator. Maybe I lack knowledge and that can really be called an iterator, but for me an iterator is something a little more complex related to Data Structures. - Omar Kohl