Почему положение функции в файле c ++ влияет на ее производительность
Почему положение функции в файле c ++ влияет на ее производительность? В частности, в приведенном ниже примере у нас есть две идентичные функции, которые имеют разные, согласованные профили производительности. Как можно исследовать это и определить, почему производительность так отличается?
Пример довольно прост в том, что у нас есть две функции: 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:
[me@host:~/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)) а все еще медленнее, чем б:
[me@host:~/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%)
Если мы теперь инвертируем расположение функций в файле C ++ (переместим определение b выше a), результаты инвертируются, и a становится быстрее, чем b!
[me@host:~/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%)
Так что, по сути, какая бы функция не находилась вверху файла c ++, она работает медленнее.
Некоторые ответы на ваши вопросы:
- Скомпилированный код идентичен для 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.
Почему это происходит? Какие инструменты доступны, чтобы исследовать что-то подобное?
Решение
Мне кажется, что это проблема с наложением кэша.
Тестовый пример довольно умен и корректно загружает все в кеш перед синхронизацией. Похоже, что все помещается в кеш — хотя и моделируется, я проверил это, просмотрев выходные данные инструмента cachegrind от valgrind, и, как и следовало ожидать в таком небольшом тестовом примере, нет существенных ошибок в кеше:
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% )
Я выбрал 32-килобайтный 8-сторонний ассоциативный кэш с размером строки в 64 байта, чтобы он соответствовал обычным процессорам Intel, и неоднократно обнаруживал одно и то же расхождение между функциями a и b.
Работа на воображаемой машине с 32-килобайтным, 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, и, следовательно, кэш не должен быть удален. Учитывая, что функциональность между ними в остальном идентична, это можно объяснить только псевдонимами.
Другие решения
Ты звонишь a а также b от test, Так как у компилятора нет причин менять порядок ваших двух функций a еще дальше, что b (в оригинале) от test, Вы также используете шаблоны, поэтому фактическая генерация кода немного больше, чем в исходном коде C ++.
Поэтому вполне возможно, что память команд для b попадает в кеш инструкций вместе с test, a если вы находитесь дальше, то не попадете в кеш, и, следовательно, потребуется больше времени для извлечения из нижних кэшей или основной памяти ЦП, которые b,
Поэтому возможно, что из-за более длинных циклов выборки команд для a чем b, a работает медленнее, чем b хотя фактический код такой же, он еще дальше.
Некоторые архитектуры ЦП (например, серия arm cortex-A) поддерживают счетчики производительности, которые подсчитывают количество пропусков кэша. Инструменты как перфорация, может захватывать эти данные, когда настроен на работу с соответствующими счетчиками производительности.