The Original Question
Why is one loop so much slower than two loops?
Conclusion:
Case 1 is a classic interpolation problem that happens to be an inefficient one. I also think that this was one of the leading reasons of why many machine architectures and developers ended up building and designing multi-core systems with the ability to do multi-threaded applications as well as parallel programming.
Looking at it from this kind of an approach without involving how the Hardware, OS and Compiler(s) works together to do heap allocations that involves working with RAM, Cache, Page Files, etc.; the mathematics that are at the foundation of these algorithms shows us which of these two is the better solution. We can use an analogy where a Boss or Summation that will represent a For Loop that has to travel between workers A & B we can easily see that Case 2 is at least 1/2 as fast if not a little more than Case 1 due to the difference in the distance that is needed to travel and the time taken between the workers. This math lines up almost virtually and perfectly with both the Bench Mark Times as well as the amount of differences in Assembly Instructions.
I will now begin to explain how all of this works below.
Assessing The Problem
The OP's code:
const int n=100000;
for(int j=0;j
c1[j] += d1[j];
}
And
for(int j=0;j
}
for(int j=0;j
}
The Consideration
Considering the OP's original question about the 2 variants of the for loops and his amended question towards the behavior of caches along with many of the other excellent answers and useful comments; I'd like to try and do something different here by taking a different approach about this situation and problem.
The Approach
Considering the two loops and all of the discussion about cache and page filing I'd like to take another approach as to looking at this from a different perspective. One that doesn't involve the cache and page files nor the executions to allocate memory, in fact this approach doesn't even concern the actual hardware or the software at all.
The Perspective
After looking at the code for a while it became quite apparent what the problem is and what is generating it. Lets break this down into an algorithmic problem and look at it from the perspective of using mathematical notations then apply an analogy to the math problems as well as to the algorithms.
What We Do Know
We know is that his loop will run 100,000 times. We also know that a1, b1, c1 & d1 are pointers on a 64-bit architecture. Within C++ on a 32-bit machine all pointers are 4 bytes and on a 64-bit machine they are 8 bytes in size since pointers are of a fixed length. We know that we have 32 bytes in which to allocate for in both cases. The only difference is we are allocating 32 bytes or 2 sets of 2-8bytes on each iteration where in the 2nd case we are allocating 16 bytes for each iteration for both of the independent loops. So both loops still equals 32 bytes in total allocations. With this information let's go ahead and show the general math, algorithm and analogy of it. We do know the amount of times that the same set or group of operations will have to be performed in both cases. We do know the amount of memory that needs to be allocated in both cases. We can asses that the overall work load of the allocations between both cases will be approximately the same.
What We Don't Know
We do not know how long it will take for each case unless if we set a counter and run a bench mark test. However the bench marks were already included from the original question and from some of the answers and comments as well and we can see a significant difference between the two and this is the whole reasoning of this question to this problem and for the answering of it to begin with.
Let's Investigate
It is already apparent that many have already done this by looking at the heap allocations, bench mark tests, looking at RAM, Cache and Page Files. Looking at specific data points and specific iteration indexes was also included and the various conversations about this specific problem has many people starting to question other related things about it. So how do we begin to look at this problem by using mathematical algorithms and applying an analogy to it? We start off by making a couple of assertions! Then we build out our algorithm from there.
Our Assertions:
- We will let our loop and its iterations be a Summation that starts at 1 and ends at 100000 instead of starting with 0 as in the loops for we don't need to worry about the 0 indexing scheme of memory addressing since we are just interested in the algorithm itself.
- In both cases we have 4 functions to work with and 2 function calls with 2 operations being done on each function call. So we will set these up as functions and function calls to be
F1(),F2(),f(a),f(b),f(c)andf(d).
The Algorithms:
1st Case: - Only one summation but two independent function calls.
Sum n=1 : [1,100000] = F1(), F2();
F1() = { f(a) = f(a) + f(b); }
F2() = { f(c) = f(c) + f(d); }
2nd Case: - Two summations but each has its own function call.
Sum1 n=1 : [1,100000] = F1();
F1() = { f(a) = f(a) + f(b); }
Sum2 n=1 : [1,100000] = F1();
F1() = { f(c) = f(c) + f(d); }
If you noticed F2() only exists in Sum where both Sum1 and Sum2 only contains F1(). This will also be evident later on as well when we begin to conclude that there is sort of an optimization happening from the second algorithm.
The iterations through the first case Sum calls f(a) that will add to its self f(b) then it calls f(c) that will do the same but add f(d) to itself for each 100000 iterations. In the second case we have Sum1 and Sum2 And both act the same as if they were the same function being called twice in a row.
In this case we can treat Sum1 and Sum2 as just plain old Sum where Sum in this case looks like this: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); } and now this looks like an optimization where we can just consider it to be the same function.
Summary with Analogy
With what we seen in the second case it almost appears as if there is optimization since both for loops have the same exact signature, but this isn't the real issue. The issue isn't the work that is being done by f(a),f(b),f(c)&f(d) in both cases and the comparison between the two it is the difference in the distance that the Summation has to travel in both cases that gives you the difference in time execution.
Think of the For Loops as being the Summations that does the iterations as being a Boss that is giving orders to two people A & B and that their jobs are to meat C & D respectively and to pick up some package from them and return it. In the analogy here the for loop or summation iterations and condition checks themselves doesn't actually represent the Boss. What actually represents the Boss here is not from the actual mathematical algorithms directly, but from the actual concept of Scope and Code Block within a routine or sub-routine, method, function, translation unit, etc. The first algorithm has 1 scope where the 2nd algorithm has 2 consecutive scopes.
Within the first case on each call slip the Boss goes to A and gives the order and A goes off to fetch B's package then the Boss goes to C and gives the orders to do the same and receive the package from D on each iteration.
Within the second case the Boss works directly with A to go and fetch B's package until all packages are received. Then the Boss works with C to do the same for getting all of D's packages.
Since we are working with an 8 byte pointer and dealing with Heap allocation let's consider this problem here. Let us say that the Boss is 100 feet from A and that A is 500 feet from C. We don't need to worry about how far the Boss is initially from C because of the order of executions. In both cases the Boss initially travels from A first then to B. This analogy isn't to say that this distance is exact; it is just a use test case scenario to show the workings of the algorithms. In many cases when doing heap allocations and working with the cache and page files, these distances between address locations may not vary that much in differences or they can very significantly depending on the nature of the data types and the array sizes.
The Test Cases:
First Case: On first iteration the Boss has to initially go 100 feet to give the order slip to A and A goes off and does his thing, but then the Boss has to travel 500 feet to C to give him his order slip. Then on the next iteration and every other iteration after the Boss has to go back and forth 500 feet between the two.
Second Case: The Boss has to travel 100 feet on the first iteration to A, but after that he is already there and just waits for A to get back until all slips are filled. Then the Boss has to travel 500 feet on the first iteration to C because C is 500 feet from A since this Boss( Summation, For Loop ) is being called right after working with A and then just waits like he did with A until all of C's order slips are done.
The Difference In Distances Traveled
const n = 100000
distTraveledOfFirst = (100 + 500) + ((n-1)*(500 + 500);
// Simplify
distTraveledOfFirst = 600 + (99999*100);
distTraveledOfFirst = 600 + 9999900;
distTraveledOfFirst = 10000500;
// Distance Traveled On First Algorithm = 10,000,500ft
distTraveledOfSecond = 100 + 500 = 600;
// Distance Traveled On Second Algorithm = 600ft;
The Comparison of Arbitrary Values
We can easily see that 600 is far less than 10 million. Now this isn't exact, because we don't know the actual difference in distance between which address of RAM or from which Cache or Page File each call on each iteration is going to be due to many other unseen variables, but this is just an assessment of the situation to be aware of and trying to look at it from the worst case scenario.
So by these numbers it would almost look as if Algorithm One should be 99% slower than Algorithm Two; however, this is only the The Boss's part or responsibility of the algorithms and it doesn't account for the actual workers A, B, C, & D and what they have to do on each and every iteration of the Loop. So the bosses job only accounts for about 15 - 40% of the total work being done. So the bulk of the work which is done through the workers has a slight bigger impact towards keeping the ratio of the speed rate differences to about 50-70%
The Observation: - The differences between the two algorithms
In this situation it is the structure of the process of the work being done and it does go to show that Case 2 is more efficient from both that partial optimization of having a similar function declaration and definition where it is only the variables that differ by name. And we also see that the total distance traveled in Case 1 is much farther than it is in Case 2 and we can consider this distance traveled our Time Factor between the two algorithms. Case 1 has considerable more work to do than Case 2 does. This was also seen in the evidence of the ASM that was shown between both cases. Even with what was already said about these cases, it also doesn't account for the fact that in Case 1 the boss will have to wait for both A & C to get back before he can go back to A again on the next iteration and it also doesn't account for the fact that if A or B is taking an extremely long time then both the Boss and the other worker(s) are also waiting at an idle. In Case 2 the only one being idle is the Boss until the worker gets back. So even this has an impact on the algorithm.
The OPs Amended Question(s)
EDIT: The question turned out to be of no relevance, as the behavior severely depends on the sizes of the arrays (n) and the CPU cache. So if there is further interest, I rephrase the question:
Could you provide some solid insight into the details that lead to the different cache behaviors as illustrated by the five regions on the following graph?
It might also be interesting to point out the differences between CPU/cache architectures, by providing a similar graph for these CPUs.
Regarding These Questions
As I have demonstrated without a doubt, there is an underlying issue even before the Hardware and Software becomes involved. Now as for the management of memory and caching along with page files, etc. which all works together in an integrated set of systems between: The Architecture { Hardware, Firmware, some Embedded Drivers, Kernels and ASM Instruction Sets }, The OS{ File and Memory Management systems, Drivers and the Registry }, The Compiler { Translation Units and Optimizations of the Source Code }, and even the Source Code itself with its set(s) of distinctive algorithms; we can already see that there is a bottleneck that is happening within the first algorithm before we even apply it to any machine with any arbitrary Architecture, OS, and Programmable Language compared to the second algorithm. So there already existed a problem before involving the intrinsics of a modern computer.
The Ending Results
However; it is not to say that these new questions are not of importance because they themselves are and they do play a role after all. They do impact the procedures and the overall performance and that is evident with the various graphs and assessments from many who have given their answer(s) and or comment(s). If you pay attention to the analogy of the Boss and the two workers A & B who had to go and retrieve packages from C & D respectively and considering the mathematical notations of the two algorithms in question you can see that without even the involvement of the computer Case 2 is approximately 60% faster than Case 1 and when you look at the graphs and charts after these algorithms have been applied to source code, compiled and optimized and executed through the OS to perform operations on the given hardware you even see a little more degradation between the differences in these algorithms.
Now if the "Data" set is fairly small it may not seem all that bad of a difference at first but since Case 1 is about 60 - 70% slower than Case 2 we can look at the growth of this function as being in terms of the differences in time executions:
DeltaTimeDifference approximately = Loop1(time) - Loop2(time)
//where
Loop1(time) = Loop2(time) + (Loop2(time)*[0.6,0.7]) // approximately
// So when we substitute this back into the difference equation we end up with
DeltaTimeDifference approximately = (Loop2(time) + (Loop2(time)*[0.6,0.7])) - Loop2(time)
// And finally we can simplify this to
DeltaTimeDifference approximately = [0.6,0.7]*(Loop2(time)
And this approximation is the average difference between these two loops both algorithmically and machine operations involving software optimizations and machine instructions. So when the data set grows linearly, so does the difference in time between the two. Algorithm 1 has more fetches than algorithm 2 which is evident when the Boss had to travel back and forth the maximum distance between A & C for every iteration after the first iteration while Algorithm 2 the Boss had to travel to A once and then after being done with A he had to travel a maximum distance only one time when going from A to C.
So trying to have the Boss focusing on doing two similar things at once and juggling them back and forth instead of focusing on similar consecutive tasks is going to make him quite angry by the end of the day because he had to travel and work twice as much. Therefor do not lose the scope of the situation by letting your boss getting into an interpolated bottleneck because the boss's spouse and children wouldn't appreciate it.
No comments:
Post a Comment