Понимание 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. Я был бы признателен, если бы вы помогли мне понять поведение. Является ли результат результатом

  1. я неправильно понимаю принципы проектирования, ориентированного на данные, или,
  2. какой-то артефакт этого очень простого примера, такой как области памяти, выделяемые очень близко друг к другу и каким-то образом очень эффективно оптимизируемые компилятором?

Наконец, есть ли способ обойти 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 раза.


person Arda Aytekin    schedule 01.11.2017    source источник
comment
[S]должен обеспечивать более высокую производительность — это почти всегда отвлекающий маневр . Преждевременная оптимизация часто бывает плохой.   -  person Some programmer dude    schedule 01.11.2017
comment
также ваш метод тестирования очень ненадежен. У вас не может быть нескольких таких тестов, потому что простое выполнение одного теста повлияет на результаты следующих тестов. Это связано с кэшированием данных. Вам нужно иметь 1 тест на прогон и запускать один и тот же тест несколько раз.   -  person bolov    schedule 01.11.2017
comment
Спасибо за ваше время, @Someprogrammerdude. Меня интересует, должен ли [S] повысить производительность, это отвлекающий маневр или нет. Вот почему я спрашиваю, следует ли следовать упаковке данных в структуру в этом конкретном случае или почему это не дает преимущества в производительности. Однако я не могу ясно понять, почему это преждевременная оптимизация. Это могло быть приложение для обработки изображений, в котором решение по выбору могло заключаться либо в сохранении значений R, G, B данного пикселя в трех разных контейнерах, либо в объединении их вместе в структуры и сохранении в одном контейнере.   -  person Arda Aytekin    schedule 01.11.2017
comment
Спасибо за ваше время, @bolov. Вы говорите, что я должен скомпилировать две разные программы и запустить их (из сценария оболочки) для каждого N, в этом примере, M раз, а затем получить среднее значение времени? Если да, то я это сделаю и сообщу о новых таймингах. Надеюсь, это объясняет огромную разницу, то есть 2.5x. Спасибо за подсказку!   -  person Arda Aytekin    schedule 01.11.2017
comment
у вас может быть 1 программа с макросом препроцессора или аргументами программы, выбирающими метод и параметры. И да, вам поможет, если вы запустите их из скрипта. В вашем случае у вас есть 6 тестов для запуска: 2 метода (3 вектора и 1 вектор) x 3 размера. Не забудьте запустить каждый тест несколько раз подряд (3-5 раз должно быть достаточно) и получить среднее значение.   -  person bolov    schedule 01.11.2017
comment
@Someprogrammerdude Должно быть, я пропустил ту часть, где OP сказал, что это преждевременная оптимизация. Это похоже на вполне разумную микро-оптимизацию. Термин «красная селедка» здесь неуместен.   -  person Konrad Rudolph    schedule 01.11.2017
comment
Возможно, это потому, что в случае std::transform компилятор может генерировать SIMD-инструкции. Примечание. Ваше решение не должно обеспечивать лучшую производительность. Кэш может предоставлять данные одновременно для обоих решений в вашем случае. Если вы использовали больше потоков данных (больше, чем кэш-путей), возможно, вариант std::transform будет медленнее.   -  person geza    schedule 01.11.2017
comment
Я проверил: для GCC особой разницы нет (и он намного медленнее, чем clang). Clang использует SIMD в обоих случаях, но в вашем случае Packed.comp ему необходимо перемещать данные, чтобы иметь возможность использовать деление SIMD. Может в этом причина разницы. (но у меня на компе с clang 6 разница всего 60%, а не 2х-3х)   -  person geza    schedule 01.11.2017
comment
Спасибо, @geza, за ваше время и объяснение. На самом деле, я проверил сейчас с clang, и поведение у меня похожее. Тем не менее, разница в производительности вызывает беспокойство, но опять же, как вы предполагаете, поведение может превратиться в преимущество упакованного хранилища в более сложных ситуациях, чем эта. Когда я построил этот простой пример, я только что проверил nm a.out | c++filt | grep comp, чтобы увидеть, оптимизируется ли вызов функции (что он и делает), но я не знаю, как наблюдать, должна ли эта штука перемещать данные. Хотите дать ответ на вопрос, который я могу выбрать?   -  person Arda Aytekin    schedule 01.11.2017
comment
Я впечатлен. Вы действительно последовали нашему совету и реализовали его. Отличная работа.   -  person bolov    schedule 01.11.2017
comment
Позвольте представить вам Godbolt, обозреватель компиляторов. Я предлагаю вам использовать его в будущем.   -  person Mgetz    schedule 01.11.2017
comment
Спасибо, @bolov :) Ну, я прошу помощи и должен следовать любому совету, который поможет мне выделить проблему среди других. Еще раз спасибо.   -  person Arda Aytekin    schedule 01.11.2017
comment
@Mgetz, на самом деле я знаю об этом сайте. К сожалению, я не знаю ни одного ассемблера. Может быть, мне следует потратить больше времени на изучение основ, чтобы я мог лучше рассуждать о коде. Я постараюсь использовать его в будущем, я обещаю :)   -  person Arda Aytekin    schedule 01.11.2017
comment
повторите тесты с -mno-sse. Это отключит инструкции SSE (SIMD). Будет интересно посмотреть, будет ли этот способ упаковки быстрее.   -  person bolov    schedule 01.11.2017
comment
@bolov, гм, g++ дает error: SSE register return with SSE disabled, тогда как clang++ компилируется правильно. Однако вывод clang++ -mno-sse скомпилированного кода - это мусор --- я вижу nan и нули.   -  person Arda Aytekin    schedule 01.11.2017
comment
@ArdaAytekin Согласно ABI x86-64 (github.com/hjl-tools/x86-psABI/wiki/x86-64-psABI-r252.pdf) Аргументы типов float, double, _Decimal32, _Decimal64 и __m64 относятся к классу SSE.; что означает передачу их как (по значению) аргументов невстроенной функции или возврат их из такой функции, требует регистров SSE и, следовательно, инструкций. Это затрудняет использование -mno-sse в этой архитектуре.   -  person Arne Vogel    schedule 01.11.2017
comment
Ух ты! Честно говоря, я не ожидал такого количества точек зрения, когда задавал вопрос. Это привело к различным плодотворным обсуждениям/комментариям, касающимся различных областей вычислений/программирования. Спасибо, @ArneVogel, за ваш комментарий о SSE.   -  person Arda Aytekin    schedule 01.11.2017
comment
Предположение, что хранение всех данных в одном месте снижает стоимость доступа к памяти, ошибочно. Данные упаковки могут быть очень полезными, например. при доступе к холодной памяти. Лучше иметь один промах кеша, чем несколько промахов… Однако в этом конкретном случае использования std::transform последовательно проходит некоторые средние и большие векторы (два входа, один выход), и современные процессоры могут легко предсказать последовательный доступ и предварительно выбрать соответствующий кеш. линии. Ограничение на количество векторов, конечно, есть, но уж точно не меньше трех…   -  person Arne Vogel    schedule 01.11.2017
comment
+ArdaAytekin Пожалуйста. :-)   -  person Arne Vogel    schedule 01.11.2017
comment
@ArneVogel, я также вижу, что когда мне нужно использовать такую ​​рекурсию, для которой требуется более двух итераторов ввода, мне нужно будет написать либо (1) цикл for, основанный на том же idx, обращающемся к разным ячейкам памяти, или (2) упаковать их в struct вот так и использовать один доступ к памяти. Я предполагаю, что это сводится к тому, что имел в виду @geza --- SoA против AoS. Однако, по-видимому, этот минимальный рабочий пример слишком прост для этих целей :) Еще раз спасибо за второе пояснение по предсказаниям доступа процессоров.   -  person Arda Aytekin    schedule 01.11.2017


Ответы (2)


Вот скомпилированный цикл случая 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 формате.

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

person geza    schedule 01.11.2017
comment
Нет, вовсе нет! Еще раз спасибо, что нашли время, чтобы объяснить проблему. По крайней мере, теперь я могу понять, что происходит. Когда я задал вопрос, в нем не было особого смысла. Но теперь я могу сделать вывод, что для проблемных установок, где локальность данных важнее, чем этот простой пример, объединение вещей может повысить производительность. Тем не менее, на мой взгляд, объединение вещей в связную структуру лучше для более выразительного и легко отлаживаемого кода. В то же время я должен просто помнить, что для таких простых случаев лучше выбрать первый тип решения. Ваше здоровье! - person Arda Aytekin; 01.11.2017
comment
@ArdaAytekin: На самом деле это большая тема :) Просто поверхностно: en.wikipedia.org/wiki/ AOS_and_SOA - person geza; 01.11.2017
comment
Ну, я очевидно не разбираюсь в теме, но на самом деле этот вопрос возник в ходе обсуждения проекта с моим коллегой. Я уже видел выступление Майка Эктона на CppCon 2014, и у меня есть небольшой опыт программирования на GPU и распределенных вычислений. В случае, который мягко представлен на этом простом примере, речь шла о дизайнерском решении. Обязательно почитаю еще что-нибудь по теме. Спасибо, @geza :) - person Arda Aytekin; 01.11.2017
comment
Даже если не считать лучшей SIMD-совместимости формата SoA, идея о том, что объединение данных повысит локальность данных, не совсем точна. Локальность данных очень хороша в любом случае: представьте, что ваши два значения занимают по 8 байтов каждое, всего 16 байтов для пары. Это 4 пары в каждой строке кэша, если вы упаковываете их в структуру или 8 отдельных элементов, если вы храните их в отдельных массивах. Итак, после того, как вы обработаете 8 пар, вы в любом случае получите доступ к двум строкам кеша: сначала одна строка кеша для 4 структур, а затем следующая для случая структуры... - person BeeOnRope; 04.11.2017
comment
... или две строки кеша сразу для каждого элемента в другом. Потом это повторяется. Хотя вы могли бы возразить, что на микроскопическом уровне первый шаблон немного более локален (одна строка кэша за раз), одновременный доступ к двум строкам кэша существенно не отличается от доступа к одной строке за другой в любой разумной архитектуре, и это не так. что люди имеют в виду, когда говорят о месте ссылки. В частности, предварительная выборка может работать с двумя потоками на половине скорости примерно так же, как с одним потоком (а иногда и лучше из-за эффектов страницы DRAM). @АрдаАйтекин - person BeeOnRope; 04.11.2017
comment
Кроме того, вы говорите и один доступ к памяти структуры даст мне все необходимые мне переменные - ну, не совсем так: даже если мы проигнорируем SIMD, компилятор будет использовать два отдельных доступа, чтобы получить два части структуры, так как они нужны в двух разных регистрах, что будет быстрее, чем однократное чтение и сдвиг и маскирование для извлечения значений. Это не сами инструкции доступа медленные (любой современный x86 может выполнять 2 за цикл), это промахи базового кеша, если таковые имеются: и доступ два против одного к одной и той же структуре не меняет этого. - person BeeOnRope; 04.11.2017
comment
Наконец, данные имеют разные размеры: 32-битный float против 16-битный int16_t. Для создания структуры пары из них потребуется 8 байтов из-за выравнивания, поэтому 2 байта тратятся впустую. Таким образом, объединение их вместе в конечном итоге требует большей пропускной способности и меньшей локальности ссылок, потому что на каждые 6 байтов полезной нагрузки приходится 2 потерянных байта. Отдельные массивы не имеют этой проблемы. - person BeeOnRope; 04.11.2017
comment
Привет, @BeeOnRope. Большое спасибо за содержательные объяснения. Теперь я даже не настроен скептически --- я должен просто избегать упаковки вещей в структуры, или? Видимо, мне нужно еще немного изучить/почитать по теме. Итак, когда я должен использовать эти методы? Есть ли какой-то конкретный случай, или я должен просто профилировать код для конкретной архитектуры после того, как код будет полностью готов, и для этих типов микрооптимизаций? - person Arda Aytekin; 15.11.2017
comment
@ArdaAytekin - хорошо, использовать ли SoA или AoS - это целая тема сама по себе, но можно с уверенностью сказать, что подавляющее большинство кода не будет критично для производительности и не будет подвергаться такой векторизации, поэтому обычно вы должны просто делать то, что больше всего естественный, который почти всегда просто группирует поля в структуру, как вы сделали (AoS). Только после того, как вы профилируете свое приложение и узнаете о горячих точках, рассмотрите способы организации данных, которые могут быть менее естественными и требуют больших затрат на разработку и обслуживание, но быстрее. - person BeeOnRope; 15.11.2017
comment
Одна из проблем с SoA заключается в том, что она имеет тенденцию к вирусному эффекту: если вам нужна SoA в одном месте для повышения производительности, вы можете быть вынуждены использовать ее в других местах, где в противном случае она была бы не нужна, потому что она слишком медленная для преобразования между форматы. Если вам повезет, там есть естественная точка разделения, позволяющая сохранить большую часть вашего кода в чистоте, но это не всегда так. См. также этот вопрос. - person BeeOnRope; 15.11.2017
comment
Еще раз спасибо, @BeeOnRope. Я тоже добавил этот вопрос в закладки. Как я уже говорил в вопросе, я не имею опыта работы с CS и не являюсь штатным разработчиком. Я не был осведомлен об этой теме. Когда я хотел спросить между ними двумя, я не думал, что это сама по себе такая большая тема, если честно :) - person Arda Aytekin; 15.11.2017
comment
FWIW, даже большинство людей, имеющих опыт работы в CS, на самом деле не будут знать о различиях SoA и AoS. В основном вы слышали об этом в высокопроизводительных вычислениях и играх (где это особенно актуально для графических процессоров). В основном вам не нужно беспокоиться: просто используйте структуры, как обычно, и профиль :) - person BeeOnRope; 15.11.2017
comment
@ArdaAytekin: вот эмпирическое правило, которое я использую: если код имеет одинаковую сложность для SoA и AoS, и я ожидаю (из опыта), что SoA будет быстрее, тогда я буду использовать SoA. В противном случае я использую AoS, и я могу преобразовать код в SoA позже, если так скажет профайлер. Например, для системы частиц, где каждая частица имеет множество атрибутов (положение, скорость, размер, цвет и т. д.), а каждый алгоритм работает только с небольшим набором атрибутов, я буду использовать SoA, поскольку он более удобен для кэширования, а сложность кода одинакова для SoA/AoS. - person geza; 15.11.2017

[...] и сбор их в контейнер должен повысить производительность.

Я думаю, что ваша интуиция немного отстает от случаев последовательного доступа. Просто учитывая последовательные циклы на входах нетривиального размера, 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 («распакованный»). Возможно, вы сможете обрабатывать заданный диапазон индексов каждого контейнера SoA в каждом отдельном потоке, по-прежнему используя std::transform в каждом из них.

person Community    schedule 23.12.2017
comment
Спасибо @DrunkCoder за исчерпывающий ответ. Это многое прояснило, особенно когда речь идет о динамике, связанной с операциями SoA и SIMD. Однако, что касается вашего последнего абзаца, я боюсь, что мы не можем подготовить данные для замены деления на умножение, и нам не разрешено пользоваться преимуществами параллелизма. Тем не менее, я еще раз благодарю вас за исчерпывающий ответ с учетом всех точек зрения одновременно! Здоровья и счастливого праздничного периода! :) - person Arda Aytekin; 25.12.2017
comment
Ваше здоровье! Репутация SoA (параллельные массивы, т.е.) имеет тенденцию превосходить, если вы используете шаблоны последовательного доступа, и накладные расходы на поддержку этих параллельных векторов/массивов не являются горячей точкой, а последовательно перебирают данные. Поэтому я бы оставил это представление SoA в вашем случае и, возможно, посмотрел бы, сможете ли вы определить другие возможности оптимизации, если это необходимо, но в противном случае последовательный цикл, выполняющий арифметику через SoA, уже довольно хорош, если алгоритм не может быть применен лучше, чем линейное время сложность. Концептуально вы не можете победить эту оптимизацию на очень микроуровне, ... - person ; 25.12.2017
comment
... поиск возможностей предварительной подготовки данных, если это возможно, для более быстрой обработки, или жертвование некоторой точностью результатов в пользу скорости... или использование совершенно другого оборудования, такого как графический процессор, если это применимо. - person ; 25.12.2017
comment
Что касается того, когда вы должны и не должны использовать AoS (упакованный), обычно я склоняюсь в сторону AoS, поскольку он имеет тенденцию давать более простой код, который легче поддерживать и который достаточно хорошо подходит для всех видов шаблонов доступа. . Однако, если вы заранее или задним числом знаете, что будете тратить большую часть циклов, критически важных для производительности, на последовательное перебор больших объемов данных, тогда могут пригодиться повторения SoA (даже несмотря на то, что результирующий код может быть большую PITA для поддержания). - person ; 25.12.2017
comment
В качестве примера я бы использовал SoA заранее с симуляторами частиц, поскольку они тратят так много времени на последовательное прохождение каждой частицы: for each particle, move it around а количество частиц может исчисляться миллионами. Так что я даже больше не заморачиваюсь с представителями AoS в таких случаях, поскольку может быть сложно переписать представителей AoS в SoA или наоборот. Я всегда обнаруживал, что представитель SoA превосходит AoS в этих случаях достаточно раз после профилирования, чтобы просто использовать SoA заранее, когда я ожидаю сильной потребности в быстрой последовательной обработке. - person ; 25.12.2017
comment
Еще одна вещь, о которой следует подумать, это использование памяти. Для последовательной обработки часто чем меньше памяти требуется для обработки, тем быстрее она выполняется. С представителями AoS вы в конечном итоге тратите немного памяти на заполнение структуры, если последующие поля требуют другого выравнивания, чем они обычно имели бы, если бы одно поле данных сразу же следовало за следующим в памяти. Например, 32-битное float, за которым следует char, за которым следует еще одно float, приведет к потере 3 байтов, поскольку char требует только выравнивания по 1 байту, а float обычно требует 4, поэтому для выравнивания этого третьего поля данных компилятор добавит 3 байта. байт. - person ; 25.12.2017