Что быстрее? "вектор структур" или "число векторов"?

Решение 1: Если у меня есть класс,

class car{ public: int a; string b; bool c;};

Я могу построить вектор из 200 автомобилей:

std::vector<car>   allcas;  
allcars.resize(200)

во время выполнения, я просто делаю:

this_car=allcars[102];

тогда....

Решение 2:

У меня есть

std::vector<int> a; a.resize(200);
std::vector<string>b; b.resize(200);
std::vector<bool> c; c.resize(200);

this_car_a = a[102];
this_car_b = b[102];
this_car_c = c[102];

Вопрос: Какой из них быстрее?

Есть ли у кого-нибудь идеи? спасибо много заблаговременно!

Ответы

Ответ 1

"Структура векторов" имеет несколько преимуществ перед "вектором структур":

  • Если ваш внутренний цикл не использует каждый элемент структуры, то структурные векторы могут сэкономить на пропускной способности памяти, так как неиспользуемые векторы элементов не будут загружаться в кеш.
  • Легче векторизовать. Структурированные векторы могут позволить вам использовать инструкции векторной обработки вашего процессора (через сборку, встроенные или умные компиляторы), чтобы ускорить ваши внутренние циклы.

С другой стороны, преждевременная оптимизация - это корень всего зла:

  • Использование структуры векторов сложнее, неудобно и неясно.
  • Обычно вы не знаете, где ваши узкие места в производительности, пока вы не заработаете свой код. Стоит ли сделать ваш код более подробным, хрупким и сложным? Вы не узнаете, пока не выполните его.
  • Преимущества программирования в виде векторов различаются в каждом конкретном случае. Это не всегда дает ускорение; вы могли бы в итоге получить худшую производительность.
  • В частности, если ваш шаблон доступа является случайным (в отличие от последовательного или иначе локализованного), организация структур-векторов может в конечном итоге загрузить гораздо больше бесполезных данных из памяти, если каждая строка кэша включает элементы из нескольких соседних объектов...

Итак, моя рекомендация заключается в использовании vector-of-struct по умолчанию, но в качестве альтернативы учесть структуру векторов (т.е. убедитесь, что вы можете переключиться позже, если вы ожидаете последовательные/локальные шаблоны доступа и не стоит больших усилий). Как только ваша программа запущена, вы можете просмотреть ее, чтобы увидеть, где находятся критически важные для вас параметры, и попробовать структурированные векторные и векторизованные операции, где они будут наиболее эффективными.

Ответ 2

Если a, b и c принадлежат вместе и образуют вместе объект, почему, черт возьми, вы бы разделили их? Для большей ясности и удобочитаемости. После этого происходит что-то еще. Кроме того, я думаю, что v2 будет медленнее. Больше доступа к вектору. Однако не время. Как всегда для вопросов о скорости, времени.

Ответ 3

Процессоры любят предварительную выборку.

Если вы собираетесь линейно перемещать свои данные в следующем шаблоне...

abcabcacb...

... тогда вам лучше (с точки зрения производительности) с решением # 1. Если вы хотите получить к ним доступ:

aaa...bbb..ccc...

... затем перейдите к решению # 2.

Однако, если вы не собираетесь выполнять линейный обход или если вы фактически не тестировали свой код и пришли к выводу, что вам действительно нужно выжать каждую последнюю каплю производительности из этой части кода, сделайте свою поддержку и пользуйтесь решением № 1.

--- EDIT ---

В многопоточной среде физическое расположение данных может привести к ложному обмену. По существу, слишком близкие части данных, которые одновременно доступны для разных потоков, могут привести к конфликту с кешем и разрушить масштабируемость.

Итак, если вы одновременно получаете доступ к a из одного потока и b из другого, может стоить разделить их физически и реализовать решение №2. Если, с другой стороны, вы получаете доступ к двум "sibling" a s, придерживайтесь решения # 1.

--- EDIT 2 ---

За отличное отношение к этой теме я горячо рекомендую говорить Herb Sutter "Вещи, которые ваш язык программирования никогда не говорил вам", по-прежнему доступны по адресу:

http://video.google.com/videoplay?docid=-4714369049736584770  http://www.nwcpp.org/Downloads/2007/Machine_Architecture_-_NWCPP.pdf

Ответ 4

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

Во-вторых, вы только утроили ваше время распределения (три распределения вместо одного), время освобождения (то же самое) и уничтожили местность ссылок (возможно, замедление).

В-третьих, единственное преимущество было бы, если бы вы только читали одного члена для всех автомобилей снова и снова и редко меняли автомобили.

Ответ 5

Это зависит от того, как вы хотите использовать свои данные. Например, если вы хотите получить доступ к одному полю:

car this_car = allcars[12];
cout << this_car.a;

Затем это приведет к созданию копии this_car. В этом случае вы будете бесполезно копировать поля b и c. Конечно, вы можете исправить это, получив по ссылке:

car & this_car = allcars[12];

Это потенциально еще медленнее, чем просто делать

a = a[12];

Однако, если вы хотите получить доступ к нескольким свойствам своего класса, то почти наверняка лучше хранить их вместе. На данный момент вы, вероятно, получите более высокую производительность из-за локальности ссылки, однако все это действительно зависит от компилятора, диспетчера памяти и т.д.

В конце концов, ответ на который является лучшей производительностью: это зависит. Это, безусловно, не будет решением узких мест, и определенно лучше держать их в одной структуре для удобочитаемости кода/собственного здравомыслия.

Ответ 6

Это зависит от размера элементов структуры и от доступа к шаблону. Один односторонний доступ не имеет значения, но считайте, что вы выполняете итерацию по вектору, и вас интересует только член a. Чем шире структура, тем меньше элементов структуры будет вписываться в строку кэша, и чем больше промахов в кеше будет происходить. Перемещение всех членов a, разделенных в векторе, увеличивает плотность строки кеша и, таким образом, увеличивает производительность. Это может быть довольно значительным (1,5x, 2x, даже больше).

Однако гораздо важнее сосредоточиться на ремонтопригодности кода, сделать его читаемым, отлажимым и легким для рефакторинга. Код должен четко выражать намерение. Такие микро оптимизации, о которых вы просите, должны рассматриваться только для измерения узких мест. Получите копию Поваренная книга по оптимизации программного обеспечения.