Почему мой код вызывает пропадание кэша инструкций?
Согласно 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);
}
Возможно, это вызвано развертыванием цикла, но сгенерированный объектный код не кажется слишком избыточным.
Как я могу улучшить код?
Обновить
- Поскольку функция контрольной суммы находилась в анонимном пространстве имен, она была встроена и дублирована двумя функциями, находящимися в одном файле cpp.
- Развертывание цикла все еще полезно. Удаление замедлило код.
-
Улучшение бесконечного цикла ускоряет код (но по какой-то причине я получаю противоположные результаты на моем Mac).
- До исправления: здесь вы можете увидеть две контрольные суммы и 17210 L1 IR промахов
- После исправления: после исправления проблемы с встраиванием и исправления бесконечного цикла, кэш инструкций L1 упал до 8324.
- «InstructionFetch» выше в фиксированном примере. Я не уверен, как это интерпретировать. Означает ли это просто, что именно там произошла большая активность? Или это намекает на проблему?
Решение
замените основной цикл просто:
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;
}
Сравнение с этим (CLEAN LOOP) и ваша улучшенная версия (UGLY 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;
}
Который работает лучше, чем OP с -O3, но хуже с -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
Таким образом, пробег может варьироваться, и если точная архитектура не известна, я бы просто стал проще
Другие решения
detector