Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Today I was asked this question. We have 2 cases with code blocks A, B and C. These code blocks 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;
}
share

migration rejected from stackoverflow.com Mar 14 at 21:55

This question came from our site for professional and enthusiast programmers. Votes, comments, and answers are locked due to the question being closed here, but it may be eligible for editing and reopening on the site where it originated.

closed as too broad by gnat, GlenH7, MichaelT, Bart van Ingen Schenau, Kilian Foth Jan 27 at 9:28

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

46  
What did you say? –  Oli Charlesworth Mar 31 '11 at 11:08
46  
The question is stupid. the only reasonable answer is "profile and see what is faster" –  BЈовић Mar 31 '11 at 11:21
7  
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 Mar 31 '11 at 11:25
33  
@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 Mar 31 '11 at 11:26
17  
@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 Mar 31 '11 at 11:30

20 Answers 20

up vote 186 down vote accepted

these are only reasons why it could be faster (of course it depends of what exactly are A B and C)

case1

  • only a single occurrence of loop prologue/epilogue (less code to run)
  • better scheduling of A B and C generated code (more parallelism)
  • may factorize code (no dependency on output, but A B and C may read the same inputs)

case2

  • lower register pressure in each loop (avoid spilling)
  • more likely to unroll loop (when A, B or C is trivial)
  • more likely the entire loop being into instruction cache (useful when N is big)
share
3  
I think this is the first answer that makes sense in the given context. –  Aston Mar 31 '11 at 14:10
4  
The more living variables an algorithm requires, the more hardware register you (the compiler) is likely to use to hold them. This possibly leads to use memory to save temporary data (spilling), which may slow the execution of the code (cache miss, dependencies etc ...). The hardware has limited resources (e.g. registers), the more complex is the algorithm, the more pressure is on those resources allocation. –  Laurent G Mar 31 '11 at 19:19

Case 1 faster for c/c++ because of three loops instead of one.

each time code does 'begin for' then 'end for' - it worth a time, some fraction of second is lost. for your case 1 - 1 action to begin for, 1 to end. Case 2 - 3 times more.

share

Concurrency, caching, complexity, compilation.

Case 1 could be faster if:

  1. (Relative Complexity) A, B and C are trivial operations and the cost of the iterator (increment, compare) is high relative to the cost of the operations.
  2. (Concurrency) The code blocks are processed in parallel on independent processors.
  3. (Compilation) Compiler optimizations allow for instruction interleaving that amounts to low-level concurrency.

Case 2 could be faster if:

  1. The instructions of A, B and C put together do not fit within the instruction cache, but they do fit separately. In this case, no new code is paged in from 'slow memory'.
  2. The code within one of A, B or C (or all) requires significant State Management. For example, rendering objects in a complex display engine.
  3. Reduced complexity within each loop allows the compiler is able to rely solely on registers rather than relying on stack memory for temporary storage.
share

Possible reason: the value of N is 0 in case 1 and INT_MAX in case 2.

The question has been carefully worded to allow this. It says, very specifically, that the only resource shared between the two blocks is the iterator. That means that N is not shared between them, and could be a different value in each block.

share

If code blocks in case 1 are closed over the iterator and perform deferred access then locking could occur on the iterator, slowing it down.

share

case 1

  • C[i] depends on B[i], B[i] depends on A[i]. Access from memory is faster.
  • A or B regularly has break statements. B or C don't always perform actions that will be used later.
  • A, B, and C are all manipulating the same source data. Access from memory is faster. (I feel like I'm kind of cheating -- this is basically the first bullet with a different cause).

case 2

  • Compiler may be able to better optimize individual loops
  • Tighter code may stay in CPU cache
  • A, B, and C all operate on data independent of each other. Memory stays primed instead of being dumped by data from other operations. Access from memory is faster...

Most of the memory ones assume fairly large data operations.

share

Another reason case 1 may be faster - Common Subexpression Elimination (CSE):

As an extreme example, suppose A, B, and C all contain calls to some expensive but pure function f(i) that the compiler recognizes as pure (perhaps it's defined in the same compilation unit, perhaps its prototype is annotated). The compiler could transform all three calls in case 1 to one call, but in case 2 would have to repeat the calls (unless it had some array available to stick the computed results in(!)).

share

IRL: Case 1 is faster.

In short, IRL, A, B, C all share more than "i". They share the OS-caches.

That will help you in an interview IF the interviewer cares about actual real-life experience.

share
1  
@Dov: Actually that's the exact reason why it is a good interview question. –  TheBigO Apr 1 '11 at 2:24

Just to throw out another possiblity that I havn't seen anyone bring up...

In both cases we don't see the type of i. We probably assume it's an int, but in the case that i is an object, the i++ will be calling i.operator++(), which could have enough overhead to make case 1 faster than case 2.

share

In addition to other answers:

Case 1

  • If only one of A, B, or C have a premature loop-break, then Case 1 should be faster.
  • If only C has a premature return, then Case 1 should be faster.
  • If only one of A, B, or C can/will decrement N, then Case 1 should be faster.
  • If only one of A, B, or C can/will increment i, then Case 1 should be faster.

Case 2

  • If only A has a premature return, then Case 2 should be faster.
  • If only one of A, B, or C can/will increment N, then Case 2 should be faster.
  • If only one of A, B, or C can/will stall or decrement i, then Case 2 should be faster.
share
2  
If any of the blocks have premature loop-breaks or returns, the two variants are not semantically equivalent. –  James Kanze Mar 31 '11 at 14:31
2  
@James Kanze: I did not see anything in the original question that implied the two were semantically equivalent. That's the whole issue here--What causes these two variants to be semantically different enough to allow one to be faster than the other. –  oosterwal Mar 31 '11 at 14:35

First of all, case 1 is not equivalent to case 2 in the general case.

Case 1 is

A;B;C;A;B;C; ...

while Case 2 is

A;A;A; ... B;B;B; ... C;C;C;

The loop is besides the point (maybe just to confuse you) and it will probably get unrolled anyway.

So, case 1 wins when

  1. A, B, C are independent and will run on different threads
  2. There can be an operation/memory reuse in the order A->B->C (eg. A: 2*i; B: 2*i+1)
  3. ...

case 2 wins when

  1. (Ai, Ai+1) are independent as well as (Bi, Bi+1) and (Ci, Ci+1)
  2. There can be an operation reuse Ai -> Ai+1 ...
share

Case 1 could be faster if

  1. If A,B and C and I are using a set unique registers, the overhead becomes the loop itself.
  2. If A,B and C are small pieces of code able to be cached, again the overhead becomes the loop itself.
  3. N is a function and there is an overhead in calling it 3 times more in case 2, this could be where N actually introduces a delay.
  4. Sections can be optimized away, but N is a function or declared volatile.

Case 2 could be faster if

  1. A,B and C are sufficiently complicated such that they cannot be made to use different sets of registers, in which case there would be an overhead in case 1 where those registers would have to be reloaded.

Somtimes Case 1 and sometimes Case 2

  1. N is a function where the runtime is non deterministic.
share

This might be a bit dependent upon the targeted operating environment, but if you are working with a multi-core processor then the A, B, and C blocks could be run on separate cores which could we could tend extend to assuming that the for loops could also be optimized to be run on separate cores as well before joining back into the main thread. This is kind of going with what Oli Charlesworth had to say in regards to branch prediction.

share

Assuming no dependencies between A, B and C, I would guess that Case 2 would normally be faster than case 1 because of:

  • Data locality
  • Code locality
  • Branch prediction

However, if the code blocks are very short, then theoretically the extra loop overhead in Case 2 might dominate. Note also @James Kanze's answer, which is another reason why Case 1 could be faster.

Of course, if there are truly no dependencies, then the compiler is free to transform Case 1 into Case 2, and vice versa.

share
1  
Why branch prediction? That should be the same in both cases. –  James Kanze Mar 31 '11 at 11:19
3  
@James: If A, B and C each have many branches, then constantly switching between them (as in Case 1) may constantly invalidate the prediction table. Unless, of course, the compiler is able to transform Case 1 into Case 2. –  Oli Charlesworth Mar 31 '11 at 11:21
2  
@VextoR: To understand why data/code locality is important, you should read up on cache (e.g. en.wikipedia.org/wiki/Cache). For branch prediction, see e.g. en.wikipedia.org/wiki/Branch_predictor. –  Oli Charlesworth Mar 31 '11 at 11:24
4  
@VectoR: if the three blocks between them contain more code, or use more data, than will fit in the CPU cache then, in the first case, by the time C has finished, some of the code/data needed by A will need to be fetched again from a slower cache, or even from main memory (which is much slower than the caches). In the second case, each block has a better chance of keeping all its code/data in the cache. –  Mike Seymour Mar 31 '11 at 11:27

One reason could be the absolute value of N

if N <=0 Case 1 is faster.

Another is that:

i=0 will be executed two times more and ++i 2*N times more.

and 3rd is:

comparison will happen 2*N times more.

hance case 1 seems to be better.

but what experts say?

share
  1. If A B and C are very short/quick then the overhead of setting up the loop 3 times may dominate making case 1 marginally faster.
  2. If one of the blocks relies on an external source for data or signals (e.g. Case 1 contains a WaitForData() function) then doing the other two while you wait for that resource to become available again will mean case 1 is faster. Note that this isn't an inter-code-block dependency.
  3. The compiler may be able to find optimisations which are only implementable for one of the cases. It's impossible to say which would be faster without seeing the blocks though.
share

In addition, here is another reason why case 2 could be faster than case 1: The first loop in case2 sets N to 0 (there will still be no resource sharing). This will only execute one A in the second case, but all of A, B and C in the first case.

share

In addition to the reasons already mentionned (locality favoring 2, loop overhead favoring 1), it's possible that the compiler could optimize them differently: case 1 gives it the possibility of interleaving instructions from the three blocks, possibliy avoiding pipeline stall if there are dependencies in the instructions of any one block.

share

Without knowing what A, B, and C are, it's impossible to actually judge the outcome, because it's easy to produce operations that are faster in either case. For example, consider if A was a string length operation and B was a string append operation on that string. In this case, doing all the lengths first will be faster than doing them interleaved with appends. However, if A is append and B is length, then you're going to want them interleaved instead of appending all first, then computing the length- assuming you have a C-style O(n) length function.

Of course they share resources. They share a runtime, a process, the whole execution environment. No resources explicitly expressed as int a; does not mean no resources shared.

share
3  
Assuming "don't share any resources" implies "no dependencies", then I think we can say something more than this. –  Oli Charlesworth Mar 31 '11 at 11:22
2  
+1 for the second paragraph. This is a silly interview question anyway. –  Lightness Races in Orbit Mar 31 '11 at 11:27
1  
@Tomalak Geret'kal - Not necessarily a silly question. –  DumbCoder Mar 31 '11 at 12:12
2  
I believe the point is to speculate on what A, B, or C could be to cause speed differences. Objecting that you don't know what they are is rejecting the (oddly worded) question. That said, I like your answer. –  Kate Gregory Mar 31 '11 at 12:58
1  
@DumbCoder: In my opinion, it is. It propagates the notion that premature optimisation is a good idea, and penalises those who just write code, profile it, enhance it and move on. –  Lightness Races in Orbit Mar 31 '11 at 13:24

Case 1: It will be faster, as it does not have to run through the iteration 3x times, and only once.

Case 2: The reason this one is faster, is that it does not need to evaluate 3 times(A,B or C) but evaluate each one only once in each loop.

But Case 1 will definitely be the best. Tricky question.

share
6  
@Aklopper: No, Case 1 will not definitely be the best. –  Oli Charlesworth Mar 31 '11 at 11:11
2  
Case 1 is faster, if blocks A, B and C are empty and the compiler is not allowed to eliminate dead code :) –  hrnt Mar 31 '11 at 11:16
2  
-1 Nah, nonsense. (Though hrnt has a point :P) –  Lightness Races in Orbit Mar 31 '11 at 11:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.