Почему позиция функции в файле С++ влияет на ее производительность

Почему позиция функции в файле С++ влияет на ее производительность? В частности, в приведенном ниже примере мы имеем две идентичные функции, которые имеют разные, согласованные профили производительности. Как можно разобраться с этим и определить, почему производительность настолько отличается?

Пример довольно прост в том, что у нас есть две функции: a и b. Каждый из них выполняется много раз в узкой петле и оптимизирован (-O3 -march=corei7-avx) и синхронизирован. Вот код:

#include <cstdint>
#include <iostream>
#include <numeric>

#include <boost/timer/timer.hpp>

bool array[] = {true, false, true, false, false, true};

uint32_t __attribute__((noinline)) a() {
    asm("");
    return std::accumulate(std::begin(array), std::end(array), 0);
}

uint32_t __attribute__((noinline)) b() {
    asm("");
    return std::accumulate(std::begin(array), std::end(array), 0);
}

const size_t WARM_ITERS = 1ull << 10;
const size_t MAX_ITERS = 1ull << 30;

void test(const char* name, uint32_t (*fn)())
{
    std::cout << name << ": ";
    for (size_t i = 0; i < WARM_ITERS; i++) {
        fn();
        asm("");
    }
    boost::timer::auto_cpu_timer t;
    for (size_t i = 0; i < MAX_ITERS; i++) {
        fn();
        asm("");
    }
}

int main(int argc, char **argv)
{
    test("a", a);
    test("b", b);
    return 0;
}

Некоторые примечательные функции:

  • Функция a и b идентичны. Они выполняют ту же операцию накопления и сводятся к тем же инструкциям сборки.
  • Каждая тестовая итерация имеет период разогрева до начала отсчета времени и пытается устранить любые проблемы с разогревом кешей.

Когда это скомпилировано и выполняется, мы получаем следующий результат, показывающий, что a значительно медленнее, чем b:

[[email protected]:~/code/mystery] make && ./mystery 
g++-4.8 -c -g -O3 -Wall -Wno-unused-local-typedefs -std=c++11 -march=corei7-avx -I/usr/local/include/boost-1_54/ mystery.cpp -o mystery.o
g++-4.8  mystery.o -lboost_system-gcc48-1_54 -lboost_timer-gcc48-1_54 -o mystery
a:  7.412747s wall, 7.400000s user + 0.000000s system = 7.400000s CPU (99.8%)
b:  5.729706s wall, 5.740000s user + 0.000000s system = 5.740000s CPU (100.2%)

Если мы инвертируем два теста (т.е. вызов test(b), а затем test(a)) a все еще медленнее, чем b:

[[email protected]:~/code/mystery] make && ./mystery 
g++-4.8 -c -g -O3 -Wall -Wno-unused-local-typedefs -std=c++11 -march=corei7-avx -I/usr/local/include/boost-1_54/ mystery.cpp -o mystery.o
g++-4.8  mystery.o -lboost_system-gcc48-1_54 -lboost_timer-gcc48-1_54 -o mystery
b:  5.733968s wall, 5.730000s user + 0.000000s system = 5.730000s CPU (99.9%)
a:  7.414538s wall, 7.410000s user + 0.000000s system = 7.410000s CPU (99.9%)

Если мы теперь инвертируем расположение функций в файле С++ (переместите определение b выше a), результаты будут инвертированы, а a станет быстрее, чем b!

[[email protected]:~/code/mystery] make && ./mystery 
g++-4.8 -c -g -O3 -Wall -Wno-unused-local-typedefs -std=c++11 -march=corei7-avx -I/usr/local/include/boost-1_54/ mystery.cpp -o mystery.o
g++-4.8  mystery.o -lboost_system-gcc48-1_54 -lboost_timer-gcc48-1_54 -o mystery
a:  5.729604s wall, 5.720000s user + 0.000000s system = 5.720000s CPU (99.8%)
b:  7.411549s wall, 7.420000s user + 0.000000s system = 7.420000s CPU (100.1%)

Итак, по существу какая-либо функция находится в верхней части файла С++ медленнее.

Некоторые ответы на интересующие вас вопросы:

  • Скомпилированный код идентичен для a и b. Проверка была проверена. (Для заинтересованных: http://pastebin.com/2QziqRXR)
  • Код был скомпилирован с использованием gcc 4.8, gcc 4.8.1 на ubuntu 13.04, ubuntu 13.10 и ubuntu 12.04.03.
  • Эффекты, наблюдаемые на процессоре Intel Sandy Bridge i7-2600 и Intel Xeon X5482.

Зачем это происходит? Какие инструменты доступны для исследования чего-то подобного?

Ответы

Ответ 1

Мне кажется, что это проблема с псевдонимом кеша.

Тест-тест довольно умный и правильно загружает все в кеш, прежде чем синхронизировать его. Похоже, все вписывается в кеш - хотя и имитировано, я проверил это, посмотрев на результат утилиты valgrind cachegrind, и, как можно было бы ожидать в таком маленьком тестовом случае, существенных промахов в кеше не было:

valgrind --tool=cachegrind --I1=32768,8,64 --D1=32768,8,64  /tmp/so
==11130== Cachegrind, a cache and branch-prediction profiler
==11130== Copyright (C) 2002-2012, and GNU GPL'd, by Nicholas Nethercote et al.
==11130== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==11130== Command: /tmp/so
==11130== 
--11130-- warning: L3 cache found, using its data for the LL simulation.
a:  6.692648s wall, 6.670000s user + 0.000000s system = 6.670000s CPU (99.7%)
b:  7.306552s wall, 7.280000s user + 0.000000s system = 7.280000s CPU (99.6%)
==11130== 
==11130== I   refs:      2,484,996,374
==11130== I1  misses:            1,843
==11130== LLi misses:            1,694
==11130== I1  miss rate:          0.00%
==11130== LLi miss rate:          0.00%
==11130== 
==11130== D   refs:        537,530,151  (470,253,428 rd   + 67,276,723 wr)
==11130== D1  misses:           14,477  (     12,433 rd   +      2,044 wr)
==11130== LLd misses:            8,336  (      6,817 rd   +      1,519 wr)
==11130== D1  miss rate:           0.0% (        0.0%     +        0.0%  )
==11130== LLd miss rate:           0.0% (        0.0%     +        0.0%  )
==11130== 
==11130== LL refs:              16,320  (     14,276 rd   +      2,044 wr)
==11130== LL misses:            10,030  (      8,511 rd   +      1,519 wr)
==11130== LL miss rate:            0.0% (        0.0%     +        0.0%  )

Я выбрал 32k, 8-way ассоциативный кеш с размером строки в байтах размером 64 байта, чтобы соответствовать общим процессорам Intel, и неоднократно видел одно и то же несоответствие между функциями a и b.

Работа на воображаемой машине с 32k, 128-сторонним ассоциативным кешем с одинаковым размером строки кэша, но эта разница все же не уходит:

valgrind --tool=cachegrind --I1=32768,128,64 --D1=32768,128,64  /tmp/so
==11135== Cachegrind, a cache and branch-prediction profiler
==11135== Copyright (C) 2002-2012, and GNU GPL'd, by Nicholas Nethercote et al.
==11135== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==11135== Command: /tmp/so
==11135== 
--11135-- warning: L3 cache found, using its data for the LL simulation.
a:  6.754838s wall, 6.730000s user + 0.010000s system = 6.740000s CPU (99.8%)
b:  6.827246s wall, 6.800000s user + 0.000000s system = 6.800000s CPU (99.6%)
==11135== 
==11135== I   refs:      2,484,996,642
==11135== I1  misses:            1,816
==11135== LLi misses:            1,718
==11135== I1  miss rate:          0.00%
==11135== LLi miss rate:          0.00%
==11135== 
==11135== D   refs:        537,530,207  (470,253,470 rd   + 67,276,737 wr)
==11135== D1  misses:           14,297  (     12,276 rd   +      2,021 wr)
==11135== LLd misses:            8,336  (      6,817 rd   +      1,519 wr)
==11135== D1  miss rate:           0.0% (        0.0%     +        0.0%  )
==11135== LLd miss rate:           0.0% (        0.0%     +        0.0%  )
==11135== 
==11135== LL refs:              16,113  (     14,092 rd   +      2,021 wr)
==11135== LL misses:            10,054  (      8,535 rd   +      1,519 wr)
==11135== LL miss rate:            0.0% (        0.0%     +        0.0%  )

Так как в 8-стороннем кеше существует меньше пробелов, где могут скрыть потенциально псевдослучайные функции, вы получаете эквивалент адресации для большего количества хеш-коллизий. С машиной, которая имеет различную ассоциативность кэшей, в этом случае вам повезло с тем, где вещи помещаются в объектный файл, и поэтому, если вы не пропустите кеш, вам также не нужно выполнять какую-либо работу, чтобы разрешить, какую строку кэша вы фактически используете необходимо.

Изменить: больше на ассоциативность кеша: http://en.wikipedia.org/wiki/CPU_cache#Associativity

Другое редактирование: я подтвердил это с помощью проверки аппаратных событий с помощью инструмента perf.

Я изменил источник для вызова только a() или b() в зависимости от наличия аргумента командной строки. Тайминги такие же, как в исходном тестовом примере.

sudo perf record -e dTLB-loads,dTLB-load-misses,dTLB-stores,dTLB-store-misses,iTLB-loads,iTLB-load-misses /tmp/so
a:  6.317755s wall, 6.300000s user + 0.000000s system = 6.300000s CPU (99.7%)
sudo perf report 

4K dTLB-loads
97 dTLB-load-misses
4K dTLB-stores
7 dTLB-store-misses
479 iTLB-loads
142 iTLB-load-misses

тогда

sudo perf record -e dTLB-loads,dTLB-load-misses,dTLB-stores,dTLB-store-misses,iTLB-loads,iTLB-load-misses /tmp/so foobar
b:  4.854249s wall, 4.840000s user + 0.000000s system = 4.840000s CPU (99.7%)
sudo perf report 

3K dTLB-loads
87 dTLB-load-misses
3K dTLB-stores
19 dTLB-store-misses
259 iTLB-loads
93 iTLB-load-misses

Показывая, что b имеет меньшее действие TLB, и поэтому кеш не нужно высылать. Учитывая, что функциональность между ними в остальном идентична, ее можно объяснить только с помощью псевдонимов.

Ответ 2

Вы вызываете a и b из test. Поскольку у компилятора нет причин переупорядочивать ваши две функции, a находится дальше, чем b (в оригинале) от test. Вы также используете шаблоны, поэтому фактическое генерирование кода немного больше, чем то, что он смотрит в источнике С++.

Поэтому вполне возможно, что память команд для b попадает в кеш инструкций вместе с test, a, находясь дальше, не попадает в кеш и поэтому занимает больше времени для извлечения из нижних кэшей или Основная память процессора, b.

Следовательно, возможно, что из-за более длительных циклов выборки для a, чем b, a работает медленнее, чем b, хотя фактический код тот же, он еще дальше.

Некоторые архитектуры процессоров (например, серия cortex-A) поддерживают счетчики производительности, которые подсчитывают количество промахов в кэше. Такие инструменты, как perf, могут захватывать эти данные, когда они настроены для работы с соответствующими счетчиками производительности.