logo标签列表

为什么我的代码会导致指令缓存未命中？

c++performancecpu-cache
5
根据cachegrind的结果显示，这个校验和计算程序是整个应用中指令高速缓存加载和指令高速缓存未命中率最大的贡献者之一。
#include <stdint.h>

namespace {

uint32_t OnesComplementSum(const uint16_t * b16, int len)  {
    uint32_t sum = 0;

    uint32_t a = 0;
    uint32_t b = 0;
    uint32_t c = 0;
    uint32_t d = 0;

    // helper for the loop unrolling
    auto run8 = [&] {
        a += b16[0];
        b += b16[1];
        c += b16[2];
        d += b16[3];
        b16 += 4;
    };

    for (;;) {
        if (len > 32) {
            run8();
            run8();
            run8();
            run8();
            len -= 32;
            continue;
        }

        if (len > 8) {
            run8();
            len -= 8;
            continue;
        }
        break;
    }

    sum += (a + b) + (c + d);

    auto reduce = [&]() {
        sum = (sum & 0xFFFF) + (sum >> 16);
        if (sum > 0xFFFF) sum -= 0xFFFF;
    };

    reduce();

    while ((len -= 2) >= 0) sum += *b16++;

    if (len == -1) sum += *(const uint8_t *)b16; // add the last byte

    reduce();

    return sum;
}    

} // anonymous namespace     

uint32_t get(const uint16_t* data, int length)
{
    return OnesComplementSum(data, length);
}

这里可以查看汇编输出。

也许是由于循环展开导致的，但生成的目标代码似乎并不过多。

如何改进代码呢？

更新

3
你的数据有多大？请注意，有时避免缓存未命中是很难的——你必须将数据实际读入内存中。而且下一次调用此函数时，它可能已经不在缓存中了（或者被内联在11个不同的地方，因此代码不在缓存中，因为上一次调用时，它是一个不同的实例），有时最好确保函数不被内联。 - Mats Petersson
缓存未命中数量并不重要，除非知道代码执行的频率和如何调用它（在循环中/从完全不同的代码点调用？）。除此之外：您是否进行了任何实际测量，表明所有手动展开循环都实际上增加了性能？如果编译器认为这会增加性能，它们可以自行展开简单的循环。 - MikeMB
3
首先，指令缓存而非数据。其次，如果您在不同的循环中处理小循环，您的循环展开将更加整洁：除非编译器能够检测到它（未检查汇编代码），否则似乎这种方法效率较低。即使编译器可以检测到，为什么不显式地进行拆分呢？ - Yakk - Adam Nevraumont
@MatsPetersson 每次调用的数据接近1500字节。这是程序被迫迭代所有数据的地方，因此数据缓存未命中并不意外。但我无法解释指令缓存未命中的情况。 - StackedCrooked
2
那么你正在运行一个完整的Web服务器来处理每个请求？在这种情况下，我不会感到惊讶，你的代码在每次调用之间“没有命中缓存” - 只是其余的代码不是那么“集中”，因此大多数其他事物的缓存未命中都是一点点，意味着你不会将它们视为一个巨大的峰值，而是0.1%在这里，1%在那里，0.5%在其他地方，所有这些加起来，但并不突出。 - Mats Petersson
显示剩余12条评论
1个回答
3

将主循环替换为以下内容：

const int quick_len=len/8;
const uint16_t * const the_end=b16+quick_len*4;
len -= quick_len*8;
for (; b16+4 <= the_end; b16+=4)
{
    a += b16[0];
    b += b16[1];
    c += b16[2];
    d += b16[3];
}

如果你使用-O3编译选项，似乎没有必要手动循环展开。

此外，测试用例允许进行过多的优化，因为输入是静态的且结果未被使用。同时，输出结果有助于验证优化版本不会出现问题。

我使用的完整测试如下：

int main(int argc, char *argv[])
{

    using namespace std::chrono;
    auto start_time = steady_clock::now();
    int ret=OnesComplementSum((const uint8_t*)(s.data()+argc), s.size()-argc, 0);
    auto elapsed_ns = duration_cast<nanoseconds>(steady_clock::now() - start_time).count();

    std::cout << "loop=" << loop << " elapsed_ns=" << elapsed_ns << " = " << ret<< std::endl;

    return ret;
}

与您改进版的 (UGLY LOOP) 和 theis 版本(CLEAN LOOP) 进行比较，并使用更长的测试字符串：

loop=CLEAN_LOOP  elapsed_ns=8365  =  14031
loop=CLEAN_LOOP  elapsed_ns=5793  =  14031
loop=CLEAN_LOOP  elapsed_ns=5623  =  14031
loop=CLEAN_LOOP  elapsed_ns=5585  =  14031
loop=UGLY_LOOP   elapsed_ns=9365  =  14031
loop=UGLY_LOOP   elapsed_ns=8957  =  14031
loop=UGLY_LOOP   elapsed_ns=8877  =  14031
loop=UGLY_LOOP   elapsed_ns=8873  =  14031

这里是验证链接：http://coliru.stacked-crooked.com/a/52d670039de17943

编辑：

实际上，整个函数可以简化为：

uint32_t OnesComplementSum(const uint8_t* inData, int len, uint32_t sum)
{
  const uint16_t * b16 = reinterpret_cast<const uint16_t *>(inData);
  const uint16_t * const the_end=b16+len/2;

  for (; b16 < the_end; ++b16)
  {
    sum += *b16;
  }

  sum = (sum & uint16_t(-1)) + (sum >> 16);
  return (sum > uint16_t(-1)) ? sum - uint16_t(-1) : sum;
}

这个代码在使用 -O3 优化级别时比 OPs 更好，但在使用 -O2 优化级别时更差：

http://coliru.stacked-crooked.com/a/bcca1e94c2f394c7

loop=CLEAN_LOOP  elapsed_ns=5825  =  14031
loop=CLEAN_LOOP  elapsed_ns=5717  =  14031
loop=CLEAN_LOOP  elapsed_ns=5681  =  14031
loop=CLEAN_LOOP  elapsed_ns=5646  =  14031
loop=UGLY_LOOP   elapsed_ns=9201  =  14031
loop=UGLY_LOOP   elapsed_ns=8826  =  14031
loop=UGLY_LOOP   elapsed_ns=8859  =  14031
loop=UGLY_LOOP   elapsed_ns=9582  =  14031

因此，里程可能会有所不同，除非确切的架构已知，否则我会选择更简单的方法。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接