矢量回路的优化

Question

Visual以某种方式优化了下面的代码，使其速度提高了20倍(以优化方式发布，而非优化发布)。它能做什么？

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类有一个大小数组(10个成员)。前两个循环给出了向量中所有可能的“单位”序列。(1-2，1-3，1-100，2-3，2-4，2-100等)，然后我用大小图进行比较。我试着打开内部循环，只添加了10次大小图，从而提高了大约2%的性能。我使用Visual 2013编译。这是否是矢量化(一次将(* it ).sizes添加到sizesmap )？还是循环无效？

Answer 1

有理有据的猜测是:在这种情况下，回路展开可能会在很大程度上发挥作用，并且可能是20X改进的主要原因。此外，随着循环的展开，它可能会使指令级并行甚至高速缓存线管理等其他事情更加有效。

从本质上说，对你的情况只有两点评论：

1. 非优化的代码将会变慢.你花钱买编译器是有原因的，很多聪明的人会让它“快走”。
2. 您需要检查编译器生成的指令级代码(asm)，以便了解这两个版本之间的主要区别.其他的都只是受过教育的猜测。

编辑

当然，纯粹是为了兴趣..。，您可能希望手动展开您的最内部循环，并查看这是否产生了显著的差异：

        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];
        }

Answer 2

您声明了sizesMap[11]，但是用13个条目初始化了它。如果这样做有效的话，它可能会覆盖一些邻近的记忆。您可以简单地编写sizesMap[11] = { 0 }。

如果您将n普遍添加到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
        }

编写这样的C++也更有习性：

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
    }
 }

假设当您“使用sizesMap做一些事情”，您不会覆盖它的任何条目，您可以构建在您以前构建的sizesMap之上。

 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
     }
 }

我认为你甚至可以更进一步：

 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];
     }
 }

编译器会自动为您完成所有这些操作吗？这似乎有点奇怪，它可能是足够聪明这样做。判断优化器正在做什么的唯一方法是检查它的汇编程序输出。