Looping is to programming like walking is to running from the cops… you don’t want to exactly be slow or you might get busted! But how exactly do we improve our loops to increase performance? There are a few tips I can share on how to make that loop super charged so you can jump over the fence and laugh at the cop on the other side as he tries to follow and tears his pants…. on this episode of the Programming Underground!
Loops… many newbies find this a real struggle to comprehend at times and pros think they have it in the bag without a second thought. But how much do we know about loop tuning and squeezing out that little extra juice to increase performance? I must say, I didn’t learn a few of these tips until later in my career, but once I knew them I couldn’t believe some of the differences it made. So lets get onto our first tip.
1. Not all loops are created equal – Sure two loops may look the same from a logical standpoint, but as far as a computer is concerned they can be the difference between an energy bar in the morning or a piece of crummy anchovy pizza for breakfast. Lets take a look at the following for loop below…
for (column = 0; column < 100; column++) {
for (row = 0; row < 5; row++) {
cout << "Hey there! This is column " << column << " and row " << row << endl;
}
}
Above we have a classic nested loop where the outer loop runs 100 times and the inner loop runs five times for each iteration of the outer loop. So what is the running time of this loop? Well if you do the math you will have 100 * 5 = 500 for the inner loop and 100 for the outer loop which equals 600. Not too bad right? But this tip is to put the busiest loop on the inside. If we were to switch around the loops we wouldn’t be changing the logic but our performance sure would. Look below…
for (row = 0; row < 5; row++) {
for (column = 0; column < 5; column++) {
cout << "Hey there! This is column " << column << " and row " << row << endl;
}
}
With this configuration we would get 5 * 100 = 500 iterations for the inner loop and only 5 for the outer loop making it execute 505 times! We save about 95 loop iterations. This has a time savings about 30% in C++, 35% in Java and 10% in PHP.
2. Increase performance with addition rather than muliplication if you can – Often times I see new and experts alike (myself included… I must admit I am lazy when fixing some problems) use a multiplication operation in a loop when they could have easily done the multiplication BEFORE the loop and just add the result in the loop. This is great for values which are static in nature and don’t need to be calculated each and every time through the loop. Multiplication is expensive so use addition instead.
For i = 0 to 100 whatever(i) = (i + 1) * myvar1 * myvar2 * myvar3 next
The above example does several multiplications with some random vars here for each time the loop runs. That is nice and dandy but if we had done it the way below, we would have seen dramatic improvements…
mymultiplications = myvar1 * myvar2 * myvar3 myvalue = mymultiplications For i = 0 to 100 whatever(i) = myvalue myvalue = myvalue + mymultiplications next
In this example we are simply adding the “mymultiplications” on top of one another rather than multiplying the counter against all those multiplications. So for the first run we set whatever(i) to myvalue, then we add the multiplications on top of it for the next pass so the second iteration will be like going 2 * mymultiplications. The third loop would be 3 * mymultiplications etc. Adding is much less intensive for a computer than multiplying and increases the speed in several languages. Time savings for this can be around 49% or so for visual basic and 12% in C++.
3. Use integers rather than floating point or doubles for indexes – A lot of experienced programmers have this one down like second nature. You should always use an integer for your index variable in a loop rather than any other data type. For instance, the below example is BAD!
Dim x As Single for x = 0 to 99 // Do something next
The code above is bad because by specifying a Single data type we are having the compiler keep track of multiple digits of precision and a bunch of baggage related to decimals that never gets used. Compilers also find it easier to work with integers for addition and multiplication because of not having to worry about the precision. By making this change you can save as much as 96% percent on VB! Additionally you can save 71% on C++ and 7% on PHP. At 96% for VB, that is essentially doubling your speed! Incredible!
4. Setup loops to access as few array dimensions as possible – If you can setup an array as a one dimensional array rather than two or more, do it if you know that you are going to be looping through it a lot. It can reduce your access times because you don’t have the compiler jumping through one dimension to get to another. For instance, this is a bit slow…
for (currentRow = 0; currentRow < intTotalRows; currentRow++) {
for (currentColumn = 0; currentColumn < intTotalColumns; currentColumn++) {
mytable[currentRow][currentColumn] = 0;
}
}
Instead if you can reduce this to one bigger single dimension array you will get savings on all your loops that are looping through it. Try something like…
for (item = 0; item < intTotalRows * intTotalColumns; item++) {
mytable[item] = 0;
}
Now these two loops are not directly the same, but by restructuring the array from a multiple to a single dimension array you can avoid having to jump through one dimension to get access to a second dimension. This makes access a bit quicker for compilers. This trick has wide ranging time savings from about 60% in VB to as much as 10% in C#. It really depends on your compiler though.
In general these tips will save you time no matter what compiler, but that savings will vary from compiler to compiler and from platform to platform. Generally though you should see performance increases with your loops and your programs if they have a lot of loops. Never blindly follow tuning tips, even my brilliant tips, without doing your own testing. Do remember though never sacrifice readability for time savings unless it is absolutely worth it. Losing readability can doom a project, even if it is fast. Document any tuning tips for future programmers so they know why it is formatted that way.
Thanks! 🙂
