# Optimizing a vector loop

Visual Studio somehow optimizes the below code to be 20 times faster (release with optimization vs. release with no optimization). What could it be doing?

for (unsigned n = 1; n != units.size(); n++)
for (unsigned j = 0; j != (units.size() - n); j++)
{
unsigned sizesMap[11] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

for (auto it = units.begin() + n; it != (units.begin() + (n + j + 1)); it++)
{
for (unsigned k = 1; k != 11; k++)
{
sizesMap[k] += (*it).sizes[k];

}
}
//do something with sizesmap
}


Unit class has a sizes array (10 members). The first two loops give all the possible sequences of "unit" in the vector. (1-2, 1-3, 1-100, 2-3, 2-4, 2-100, etc), which I then compare with one another using the sizesmap. I tried unrolling the inner loop and just adding sizesmap 10 times, that gave about 2% performance improvement. I compiled with Visual Studio 2013. Could it be vectorization (adds the (*it).sizes to sizesmap in one go)? Or are the loops ineffective somehow?

• is it intentional that sizesMap[0] is untouched in the inner loop? Commented Jan 13, 2014 at 14:04
• The logic of the data has an order from 1 to 10 therefore I left the 0 member out. It's just for my own convenience. Commented Jan 13, 2014 at 15:40
• Please add the type (declaration) of your units variable, or Unit class. Commented Jan 13, 2014 at 18:07
• There are so many optimizations that can be done on loops. Unrolling/code-hoisting/loop-reversal/array-remapping/predictive branching marks etc. the list is long and you really need to look at a compiler optimizing book. amazon.com/… Commented Jan 13, 2014 at 18:31
• When you do "something" with sizesMap, do you modify the entries of sizesMap or not? Commented Jan 13, 2014 at 19:11

Educated guesses are: in this case, loop unrolling will probably feature in a big way, and may account for most of the 20X improvement. Additionally, with the loop unroll it may make other things like instruction-level-parallelism more effective, and even cache-line management.

1. non-optimized code is going to be slower.... you pay money for the compiler for a reason, lots of smart people make it 'go fast'.
2. you need to inspect the instruction-level code (asm) generated by the compiler in order to understand the main differences between the two versions ... anything else is just educated guessing.

## Edit

FWIW, Purely for interest sake.... , you may want to try to manually unroll your inner-most loop, and see if this makes a significant difference:

        for (auto it = units.begin() + n; it != (units.begin() + (n + j + 1)); it++)
{
sizesMap[1] += (*it).sizes[1];
sizesMap[2] += (*it).sizes[2];
sizesMap[3] += (*it).sizes[3];
sizesMap[4] += (*it).sizes[4];
sizesMap[5] += (*it).sizes[5];
sizesMap[6] += (*it).sizes[6];
sizesMap[7] += (*it).sizes[7];
sizesMap[8] += (*it).sizes[8];
sizesMap[9] += (*it).sizes[9];
sizesMap[10] += (*it).sizes[10];
sizesMap[11] += (*it).sizes[11];
}

• The problem is that I intend to frequently use this basic algorithm in different forms and I will need to debug it A LOT, and the long waits for the non-optimized builds could get really annoying. I really wish I could figure this one out thoroughly, unfortunately I can't read assembler. I understand that adding "register" is not really going to help anything, so I'll probably have to look into multithreading options. Commented Jan 13, 2014 at 16:03
• You can try to manually unroll the innermost loop, and see what that gets you.... I will edit my answer.... Commented Jan 13, 2014 at 18:14
• @user34888: Don't try and write code to be optimized. Write code to be readable. The compiler has so many techniques that if you try to do something tricky then you may hit one but cause the compiler to reject a couple of others. Write clean simple code; the compiler are very sophisticated and will do the rest and apply a whole bunch of techniques. Commented Jan 13, 2014 at 18:34
• I did the unrolling already, I mentioned that - only 2% improvement. Of course, the compiler might be unrolling the outer loops as well. Commented Jan 13, 2014 at 23:50

You declared sizesMap[11], but initialized it with 13 entries. If that works at all, it might be overwriting some neighbouring memory. You could simply write sizesMap[11] = { 0 }.

Your code would be easier to understand if you universally added n to j:

for (unsigned n = 1; n != units.size(); n++)
for (unsigned j = n; j != units.size(); j++)
{
unsigned sizesMap[11] = { 0 };

for (auto it = units.begin() + n; it != units.begin() + (j + 1); it++)
{
for (unsigned k = 1; k != 11; k++)
{
sizesMap[k] += (*it).sizes[k];

}
}
//do something with sizesmap
}


It's also more idiomatic C++ to write:

for (auto i = units.begin() + 1; i != units.end(); ++i) {
for (auto j = i; j != units.end(); ++j) {
unsigned sizesMap[11] = { 0 };
for (auto it = i; it != j + 1; ++it) {
for (size_t k = 1; k != sizeof(sizesMap) / sizeof(sizesMap[0]); k++) {
sizesMap[k] += it->sizes[k];
}
}
//do something with sizesMap
}
}


Assuming that when you "do something with sizesMap", you don't overwrite any of its entries, you can build on top of the sizesMap you previously constructed.

 for (auto i = units.begin() + 1; i != units.end(); ++i) {
unsigned sizesMap[11] = { 0 };
for (auto j = i; j != units.end(); ++j) {
for (size_t k = 1; k != sizeof(sizesMap) / sizeof(sizesMap[0]); k++) {
sizesMap[k] += j->sizes[k];
}
//do something non-destructive with sizesMap
}
}


I think you could even go further:

 unsigned sizesMap[11] = { 0 };
for (auto i = units.begin() + 1; i != units.end(); ++i) {
for (auto j = i; j != units.end(); ++j) {
for (size_t k = 1; k != sizeof(sizesMap) / sizeof(sizesMap[0]); k++) {
sizesMap[k] += j->sizes[k];
}
//do something non-destructive with sizesMap
}
for (size_t k = 1; k != sizeof(sizesMap) / sizeof(sizesMap[0]); k++) {
sizesMap[k] -= i->sizes[k];
}
}


Is the compiler doing all that for you automatically? It seems a bit freaky that it could be smart enough to do so. The only way to tell what the optimizer is doing is to inspect its assembler output.

• I don't think you correctly understood what I was trying to do. I'm calculating this sizesmap for each separate sequential sequence of these "units" that it is possible to have and then I store it in a vector of sizemaps so that I can compare them to each other. The point is to find a sequence of units where these "sizes" change the least. Like nr. 23 to nr. 47. The vector of the sizemaps is not relevant here because the profiler shows that all the time is spent in these few lines. (the 13 members is a mistake that I made in adapting the code for reviewing it here.) Commented Jan 13, 2014 at 23:48
• I corrected the (n+j) as you suggested in the first example, but I'm unsure about the iterators in the outer loops. Is the "iterator arithmetic" faster? I also need the integers because I store them for reference (the sizesmap vector also contains the beginning and end unit for each sequence analyzed). I could change that but I doubt that I would get a speed increase because I initially had it != units.begin() + n + j + 1 and I got a big speed boost just from putting the parentheses around. So adding the integers was a lot faster than adding iterators. Commented Jan 14, 2014 at 0:21
• Redefining j to include n wouldn't make it significantly faster, nor does would changing it to use the iterator syntax. With those moves, I was mainly aiming for readability so that I could understand what was going on. What could make a significant performance difference is changing the code to avoid rebuilding sizesMap from scratch every single iteration. Consider: how does one sizesMap differ from the sizesMap of the previous round? Then change your code to do the minimum necessary to get there. Commented Jan 14, 2014 at 8:37
• I don't think I can do that. Right now sizesmap doesn't change that much, but in the future I will be adding weighed calculations, with every new added unit having a lot more weight so that I could precisely catch the break line where the statistical unit.sizes pattern changes suddenly (example: 100 units with a regular sizes pattern, then suddenly 1 with irregular - doesn't change the overall picture enough to be "caught", so it has to be multiplied to be worth at least a third of the previous units put together). So each sizesmap is basically unique. Commented Jan 14, 2014 at 9:43
• But you're right - at this point, the compiler could possibly optimize that way: the sizesmap for units 1-21 can be obtained by just adding unit 21 to sizesmap for units 1-20. That would actually be a cheat because it won't work when I add the weighing algorithm. Commented Jan 14, 2014 at 10:32