Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 '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 '14 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
    
Agreed. It's better than my answer, anyway. (And better formulated as well.) – James Kanze Mar 31 '11 at 14:29
    
excellent answer. I think the biggest/most pragmatic benefits of case 1 are concurrency and for case 2 they are loop unrolling/caching. – verhogen Mar 31 '11 at 16:20
    
Yes, excellent answer. I doubt either list is actually exhaustive, but OP only asks for 3 of each anyway, so that's academic. Having said that - with today's hardware the entire question is probably a bit academic. If it weren't, I'd side with VJo and profile the alternatives. – FumbleFingers Mar 31 '11 at 18:16
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

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
    
Can you pls explain? Why data/code locality is a reason to be faster and what is branch prediction? – VextoR Mar 31 '11 at 11:20
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

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
    
+1: I hadn't thought of dependencies within A, B and C. – Oli Charlesworth Mar 31 '11 at 11:31
    
A good example of this: if one of the operations is floating point, and the other is integer, they can both use different execution units. – Dov Mar 31 '11 at 17:44
    
This is a big point, I did a small test and concluded that my CPU use around 8 clocks from a variable is written until it may be used in a new calculation, even if all 3 loops use exactly the same ALUs it's easy to code up an example showing a plain factor 3 advantage for method 1. – aaaaaaaaaaaa Apr 19 '11 at 14:56

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

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

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 more general terms: If only one of A, B, or C can/will decrement the value of N, then Case 1 will be faster. Conversely, if only one of A, B, or C can/will increment the value of N, then Case 2 will be faster. – oosterwal Mar 31 '11 at 13:48
    
I would suggest that is sharing a resource, but still... – Jon Cage Mar 31 '11 at 18:17
    
@Jon making a performance comparison if you allow the blocks to change N doesn't make sense. But if it's a trick question, they might want to hear an answer that exploits this one :) – Johannes Schaub - litb Mar 31 '11 at 18:28
    
This is a well explained answer. The scenario would be: if (i – Philluminati Mar 31 '11 at 22:00

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
    
If the compiler is not allowed any optimizations, then case 1 is the fastest, period. Compilers are allowed optimizations, however (and in general, it's impossible to turn them all off), so the comment is irrelevant. – James Kanze Mar 31 '11 at 14:32
    
@James: Actually no, even if the compiler is not allowed to optimize, there are many reasons why case 2 could be faster. Maybe A needs memory equal to the size of the L1 cache, then case 2 could be MUCH faster, as A and B wont be thrashing at the cache halfway through the loop. There are lots of other reasons why case 2 could be faster. See the other answers. – TheBigO Apr 1 '11 at 2:26
  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

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

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

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

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
    
It says in the question that the iterator is int. – Vaibhav Mar 31 '11 at 16:42

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
    
If they actually have commonality in the resources they use, then case 1 is favored. If they all use disjoint resources that persist across loop iterations, then case 1 increases working set size, and exceed various levels of cache (CPU, OS buffer, disk, etc). – Novelocrat Mar 31 '11 at 17:00
    
If A, B, and C all beat on memory sequentially (ie are memory limited) it will be faster to do one sequential stream rather than break back and forth. The point is, this is a complicated question, with no single simplistic answer. For that reason, it's not a very good interview question. – Dov Mar 31 '11 at 17:47
1  
@Dov: Actually that's the exact reason why it is a good interview question. – TheBigO Apr 1 '11 at 2:24
    
@TheBigO: this is a good interview question only for someone who is interested in an applicant with a general computer science background. It's not useful to predict job performance, unless this is a compiler or computer architecture job and hence, not a useful question. Actually, it smacks of an "I'm a brilliant guy, let's see if you're worthy to work with me" kind of elitist question. And the real question is whether the interviewer actually knows these answers, or has some erroneous ideas formed from when they went to college and wrote code for a 68k. – Dov May 2 '11 at 13:54
    
@Dov: Well, there is more than one answerer here who insists that case 1 is faster, period. You mentioned a 68k but you can write code for a 6 core machine with 16MB of L1 cache, and case 2 can still be faster due to cache usage reasons (or many other reasons as we can see from other answers). Perhaps the job requires code that is performance sensitive -- would you want to hire someone that has no idea how to answer this other than to say "case 1 is always faster no matter what"? – TheBigO May 2 '11 at 15:08

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

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

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

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

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

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

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

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