Я пытаюсь понять ориентированный на данные дизайн простой конкретной проблемы. Заранее извиняюсь перед людьми, занимающимися дизайном, ориентированным на данные, если я делаю что-то очень глупое, но мне трудно понять, почему и где мои рассуждения терпят неудачу.
Предположим, у меня есть простая операция, то есть, 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;
}
с соответствующим shell (fish) скриптом
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 раза.
N
, в этом примере,M
раз, а затем получить среднее значение времени? Если да, то я это сделаю и сообщу о новых таймингах. Надеюсь, это объясняет огромную разницу, то есть2.5x
. Спасибо за подсказку! - person Arda Aytekin   schedule 01.11.2017std::transform
компилятор может генерировать SIMD-инструкции. Примечание. Ваше решение не должно обеспечивать лучшую производительность. Кэш может предоставлять данные одновременно для обоих решений в вашем случае. Если вы использовали больше потоков данных (больше, чем кэш-путей), возможно, вариантstd::transform
будет медленнее. - person geza   schedule 01.11.2017Packed.comp
ему необходимо перемещать данные, чтобы иметь возможность использовать деление SIMD. Может в этом причина разницы. (но у меня на компе с clang 6 разница всего 60%, а не 2х-3х) - person geza   schedule 01.11.2017nm a.out | c++filt | grep comp
, чтобы увидеть, оптимизируется ли вызов функции (что он и делает), но я не знаю, как наблюдать, должна ли эта штука перемещать данные. Хотите дать ответ на вопрос, который я могу выбрать? - person Arda Aytekin   schedule 01.11.2017-mno-sse
. Это отключит инструкции SSE (SIMD). Будет интересно посмотреть, будет ли этот способ упаковки быстрее. - person bolov   schedule 01.11.2017g++
даетerror: SSE register return with SSE disabled
, тогда какclang++
компилируется правильно. Однако выводclang++ -mno-sse
скомпилированного кода - это мусор --- я вижуnan
и нули. - person Arda Aytekin   schedule 01.11.2017-mno-sse
в этой архитектуре. - person Arne Vogel   schedule 01.11.2017std::transform
последовательно проходит некоторые средние и большие векторы (два входа, один выход), и современные процессоры могут легко предсказать последовательный доступ и предварительно выбрать соответствующий кеш. линии. Ограничение на количество векторов, конечно, есть, но уж точно не меньше трех… - person Arne Vogel   schedule 01.11.2017for
, основанный на том жеidx
, обращающемся к разным ячейкам памяти, или (2) упаковать их вstruct
вот так и использовать один доступ к памяти. Я предполагаю, что это сводится к тому, что имел в виду @geza --- SoA против AoS. Однако, по-видимому, этот минимальный рабочий пример слишком прост для этих целей :) Еще раз спасибо за второе пояснение по предсказаниям доступа процессоров. - person Arda Aytekin   schedule 01.11.2017