Понимание std:: transform и как его бить
Я пытаюсь понять ориентированный на данные дизайн по простой, конкретной проблеме. Приносим извинения заранее людям, ориентированным на данные, если я делаю что-то очень глупое, но мне трудно понять, почему и где мои рассуждения терпят неудачу.
Предположим, что у меня простая операция, т.е. float_t result = int_t(lhs) / int_t(rhs). Если я сохраняю все переменные в своих соответствующих контейнерах, например, std::vector<float_t> и std::vector<int_t>, и я использую std::transform, я получаю правильный результат. Затем для конкретного примера, где using float_t = float и using int_t = int16_t, я предполагаю, что упаковка этих переменных внутри struct, в 64-битной архитектуре, и сбор их внутри контейнера должен обеспечить лучшую производительность.
Я думаю, что struct составляет 64-битный объект, и один доступ к памяти для struct даст мне все переменные, которые мне нужны. С другой стороны, когда все эти переменные собираются в разных контейнерах, мне понадобится три разных доступа к памяти для получения необходимой информации. Ниже описано, как я настроил среду:
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std::chrono;
template <class float_t, class int_t> struct Packed {
float_t sinvl;
int_t s, l;
Packed() = default;
Packed(float_t sinvl, int_t s, int_t l) : sinvl{sinvl}, s{s}, l{l} {}
void comp() { sinvl = float_t(l) / s; }
};
using my_float = float;
using my_int = int16_t;
int main(int argc, char *argv[]) {
constexpr uint32_t M{100};
for (auto N : {1000, 10000, 100000}) {
double t1{0}, t2{0};
for (uint32_t m = 0; m < M; m++) {
std::vector<my_float> sinvl(N, 0.0);
std::vector<my_int> s(N, 3), l(N, 2);
std::vector<Packed<my_float, my_int>> p1(
N, Packed<my_float, my_int>(0.0, 3, 2));
// benchmark unpacked
auto tstart = high_resolution_clock::now();
std::transform(l.cbegin(), l.cend(), s.cbegin(), sinvl.begin(),
std::divides<my_float>{}); // 3 different memory accesses
auto tend = high_resolution_clock::now();
t1 += duration_cast<microseconds>(tend - tstart).count();
if (m == M - 1)
std::cout << "sinvl[0]: " << sinvl[0] << '\n';
// benchmark packed
tstart = high_resolution_clock::now();
for (auto &elem : p1) // 1 memory access
elem.comp();
tend = high_resolution_clock::now();
t2 += duration_cast<microseconds>(tend - tstart).count();
if (m == M - 1)
std::cout << "p1[0].sinvl: " << p1[0].sinvl << '\n';
}
std::cout << "N = " << N << ", unpacked: " << (t1 / M) << " us.\n";
std::cout << "N = " << N << ", packed: " << (t2 / M) << " us.\n";
}
return 0;
}
Скомпилированный код с g++ -O3 дает на моей машине
sinvl[0]: 0.666667
p1[0].sinvl: 0.666667
N = 1000, unpacked: 0 us.
N = 1000, packed: 1 us.
sinvl[0]: 0.666667
p1[0].sinvl: 0.666667
N = 10000, unpacked: 5.06 us.
N = 10000, packed: 12.97 us.
sinvl[0]: 0.666667
p1[0].sinvl: 0.666667
N = 100000, unpacked: 52.31 us.
N = 100000, packed: 124.49 us.
В принципе, std::transform превосходит упакованный доступ 2.5x. Я был бы признателен, если бы вы помогли мне понять поведение. Является результатом результата
- Я не правильно понимаю принципы, ориентированные на данные, или
- некоторый артефакт этого очень простого примера, такого как места памяти, которые распределяются очень близко друг к другу и каким-то образом оптимизируются с помощью компилятора очень эффективно?
Наконец, есть ли способ превзойти std::transform в этом примере или просто ли он достаточно хорош, чтобы стать подходящим решением? Я не эксперт ни в оптимизации компилятора, ни в ориентированном на данные проекте, и поэтому сам не мог ответить на этот вопрос.
Спасибо!
EDIT. Я изменил способ проверки обоих методов в соответствии с предложением @bolov в комментариях.
Теперь код выглядит так:
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std::chrono;
template <class float_t, class int_t> struct Packed {
float_t sinvl;
int_t s, l;
Packed() = default;
Packed(float_t sinvl, int_t s, int_t l) : sinvl{sinvl}, s{s}, l{l} {}
void comp() { sinvl = float_t(l) / s; }
};
using my_float = float;
using my_int = int16_t;
int main(int argc, char *argv[]) {
uint32_t N{1000};
double t{0};
if (argc == 2)
N = std::stoul(argv[1]);
#ifndef _M_PACKED
std::vector<my_float> sinvl(N, 0.0);
std::vector<my_int> s(N, 3), l(N, 2);
// benchmark unpacked
auto tstart = high_resolution_clock::now();
std::transform(l.cbegin(), l.cend(), s.cbegin(), sinvl.begin(),
std::divides<my_float>{}); // 3 different memory accesses
auto tend = high_resolution_clock::now();
t += duration_cast<microseconds>(tend - tstart).count();
std::cout << "sinvl[0]: " << sinvl[0] << '\n';
std::cout << "N = " << N << ", unpacked: " << t << " us.\n";
#else
std::vector<Packed<my_float, my_int>> p1(N,
Packed<my_float, my_int>(0.0, 3, 2));
// benchmark packed
auto tstart = high_resolution_clock::now();
for (auto &elem : p1) // 1 memory access
elem.comp();
auto tend = high_resolution_clock::now();
t += duration_cast<microseconds>(tend - tstart).count();
std::cout << "p1[0].sinvl: " << p1[0].sinvl << '\n';
std::cout << "N = " << N << ", packed: " << t << " us.\n";
#endif
return 0;
}
с соответствующей оболочкой (рыбой) script
g++ -Wall -std=c++11 -O3 transform.cpp -o transform_unpacked.out
g++ -Wall -std=c++11 -O3 transform.cpp -o transform_packed.out -D_M_PACKED
for N in 1000 10000 100000
echo "Testing unpacked for N = $N"
./transform_unpacked.out $N
./transform_unpacked.out $N
./transform_unpacked.out $N
echo "Testing packed for N = $N"
./transform_packed.out $N
./transform_packed.out $N
./transform_packed.out $N
end
который дает следующее:
Testing unpacked for N = 1000
sinvl[0]: 0.666667
N = 1000, unpacked: 0 us.
sinvl[0]: 0.666667
N = 1000, unpacked: 0 us.
sinvl[0]: 0.666667
N = 1000, unpacked: 0 us.
Testing packed for N = 1000
p1[0].sinvl: 0.666667
N = 1000, packed: 1 us.
p1[0].sinvl: 0.666667
N = 1000, packed: 1 us.
p1[0].sinvl: 0.666667
N = 1000, packed: 1 us.
Testing unpacked for N = 10000
sinvl[0]: 0.666667
N = 10000, unpacked: 5 us.
sinvl[0]: 0.666667
N = 10000, unpacked: 5 us.
sinvl[0]: 0.666667
N = 10000, unpacked: 5 us.
Testing packed for N = 10000
p1[0].sinvl: 0.666667
N = 10000, packed: 17 us.
p1[0].sinvl: 0.666667
N = 10000, packed: 13 us.
p1[0].sinvl: 0.666667
N = 10000, packed: 13 us.
Testing unpacked for N = 100000
sinvl[0]: 0.666667
N = 100000, unpacked: 64 us.
sinvl[0]: 0.666667
N = 100000, unpacked: 66 us.
sinvl[0]: 0.666667
N = 100000, unpacked: 66 us.
Testing packed for N = 100000
p1[0].sinvl: 0.666667
N = 100000, packed: 180 us.
p1[0].sinvl: 0.666667
N = 100000, packed: 198 us.
p1[0].sinvl: 0.666667
N = 100000, packed: 177 us.
Надеюсь, я правильно понял правильный метод тестирования. Тем не менее, разница составляет 2-3 раза.
Ответы
Ответ 1
Здесь скомпилированный цикл случая std::transform:
400fd0: f3 41 0f 7e 04 47 movq xmm0,QWORD PTR [r15+rax*2]
400fd6: 66 0f 61 c0 punpcklwd xmm0,xmm0
400fda: 66 0f 72 e0 10 psrad xmm0,0x10
400fdf: 0f 5b c0 cvtdq2ps xmm0,xmm0
400fe2: f3 0f 7e 0c 43 movq xmm1,QWORD PTR [rbx+rax*2]
400fe7: 66 0f 61 c9 punpcklwd xmm1,xmm1
400feb: 66 0f 72 e1 10 psrad xmm1,0x10
400ff0: 0f 5b c9 cvtdq2ps xmm1,xmm1
400ff3: 0f 5e c1 divps xmm0,xmm1
400ff6: 41 0f 11 04 80 movups XMMWORD PTR [r8+rax*4],xmm0
400ffb: f3 41 0f 7e 44 47 08 movq xmm0,QWORD PTR [r15+rax*2+0x8]
401002: 66 0f 61 c0 punpcklwd xmm0,xmm0
401006: 66 0f 72 e0 10 psrad xmm0,0x10
40100b: 0f 5b c0 cvtdq2ps xmm0,xmm0
40100e: f3 0f 7e 4c 43 08 movq xmm1,QWORD PTR [rbx+rax*2+0x8]
401014: 66 0f 61 c9 punpcklwd xmm1,xmm1
401018: 66 0f 72 e1 10 psrad xmm1,0x10
40101d: 0f 5b c9 cvtdq2ps xmm1,xmm1
401020: 0f 5e c1 divps xmm0,xmm1
401023: 41 0f 11 44 80 10 movups XMMWORD PTR [r8+rax*4+0x10],xmm0
401029: 48 83 c0 08 add rax,0x8
40102d: 48 83 c1 02 add rcx,0x2
401031: 75 9d jne 400fd0 <main+0x570>
В каждом цикле цикла он обрабатывает 8 элементов (есть две инструкции divps, каждая из которых состоит из 4 делений).
Здесь другой случай:
401190: f3 0f 6f 42 04 movdqu xmm0,XMMWORD PTR [rdx+0x4]
401195: f3 0f 6f 4a 14 movdqu xmm1,XMMWORD PTR [rdx+0x14]
40119a: 66 0f 70 c9 e8 pshufd xmm1,xmm1,0xe8
40119f: 66 0f 70 c0 e8 pshufd xmm0,xmm0,0xe8
4011a4: f2 0f 70 d0 e8 pshuflw xmm2,xmm0,0xe8
4011a9: 66 0f 6c c1 punpcklqdq xmm0,xmm1
4011ad: 66 0f 72 e0 10 psrad xmm0,0x10
4011b2: 0f 5b c0 cvtdq2ps xmm0,xmm0
4011b5: f2 0f 70 c9 e8 pshuflw xmm1,xmm1,0xe8
4011ba: 66 0f 62 d1 punpckldq xmm2,xmm1
4011be: 66 0f 61 ca punpcklwd xmm1,xmm2
4011c2: 66 0f 72 e1 10 psrad xmm1,0x10
4011c7: 0f 5b c9 cvtdq2ps xmm1,xmm1
4011ca: 0f 5e c1 divps xmm0,xmm1
4011cd: f3 0f 11 02 movss DWORD PTR [rdx],xmm0
4011d1: 0f 28 c8 movaps xmm1,xmm0
4011d4: 0f c6 c9 e5 shufps xmm1,xmm1,0xe5
4011d8: f3 0f 11 4a 08 movss DWORD PTR [rdx+0x8],xmm1
4011dd: 0f 28 c8 movaps xmm1,xmm0
4011e0: 0f 12 c9 movhlps xmm1,xmm1
4011e3: f3 0f 11 4a 10 movss DWORD PTR [rdx+0x10],xmm1
4011e8: 0f c6 c0 e7 shufps xmm0,xmm0,0xe7
4011ec: f3 0f 11 42 18 movss DWORD PTR [rdx+0x18],xmm0
4011f1: 48 83 c2 20 add rdx,0x20
4011f5: 48 83 c1 fc add rcx,0xfffffffffffffffc
4011f9: 75 95 jne 401190 <main+0x730>
В каждом цикле цикла он обрабатывает 4 элемента (существует одна инструкция divps).
В первом случае данные находятся в хорошем формате, инструкции SIMD могут работать на них (почти) без каких-либо перемещений данных, и результат может быть легко написан (4 результата написаны с одной инструкцией).
Во втором случае, однако, это не так. Компилятор должен был испустить много операций перемещения данных (перемешивания), и каждый результат записывается отдельной инструкцией. Таким образом, вход/выход не находится в дружественном формате SIMD.
У меня нет времени для анализа этой проблемы дальше, но если вы просто принимаете тот факт, что оба этих фрагмента имеют одинаковый размер, аналогичные инструкции, но первые процессы в два раза больше, чем элементы второго, вы может возникнуть идея, почему вторая медленнее. Извините за небрежное объяснение.
Ответ 2
[...] и сбор их внутри контейнера должен лучше производительность.
Я думаю, что ваша интуиция немного отстала для случаев последовательного доступа. Рассматривая последовательные циклы на входах нетривиального размера, SoA почти всегда будет быстрее или быстрее, чем AoS для последовательного доступа.
Во многих случаях SoA будет на самом деле меньше меньше промахов в кэше, чем AoS, потому что он избегает добавления структуры (не сталкивается с требованиями к выравниванию чередующихся неоднородных полей), и вы можете избежать загрузки холодных полей для данного (например: физический симулятор мог бы избежать загрузки поля color частицы, используемой только для рендеринга при применении физики). Ваш случай не выгоден ни от одного из них, но это что-то иметь в виду.
Где AoS имеет тенденцию выделяться для случайного доступа. В этом случае, если вы загружаете, скажем, 4096-й элемент, вам может потребоваться только одна строка кеша с AoS для получения всех трех полей. Если вы используете SoA, вам потребуется 3, и он может загружать множество данных для соседних элементов (данные для элементов 4097, 4098, 4099 и т.д.), Ни одна из которых не используется до выселения из-за произвольного доступа шаблон доступа к памяти. Но для последовательного доступа все такие соседние данные обычно будут использоваться даже с репутацией SoA до выселения.
Таким образом, с точки зрения пропусков кэша в случаях, когда вы последовательно перебираете нетривиальные размеры ввода, SoA обычно либо связывает, либо выигрывает.
Но кроме того, в таких последовательных шаблонах доступа, где все соседние данные будут использоваться до выселения, когда вы рассматриваете динамику, когда данные загружаются из кэша в регистр SIMD, SoA предоставляет однородные данные. Он может загружать память в виде, например, float, float, float, float, ... и int16, int16, int16, int16, ..., а не float, int16, int16, float, int16, int16 ... с вертикальными/симметричными операциями, выполняемыми через регистры SIMD. Такие случаи, как правило, предлагают гораздо больше возможностей для оптимизации как для человека, так и для компилятора, и вероятность того, что ваш конкретный случай принесет пользу больше всего, как указывает Геза.
Наконец, есть способ превзойти std:: transform в этом примере или это просто достаточно хорошо, чтобы быть готовым решением?
Я думаю, что попытка превзойти std::transform при выполнении одинаковых требований - это неправильный способ взглянуть на него, но вы можете сжать некоторые приросты производительности, слегка изменив их. Например, вместо std::divides вы можете заранее подготовить данные, чтобы превратить это в умножение. Самое главное, что я хотел бы найти в вашем случае, - проверить, может ли код быть выполнен параллельно с более быстрым представлением SoA ( "unpacked" ). Вы можете обрабатывать заданный диапазон индексов каждого контейнера SoA в каждом отдельном потоке, все еще используя std::transform в каждом из них.
