что быстрее? «вектор структур» или «ряд векторов»?

Question

Решение 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];

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

У кого-нибудь есть идея? заранее большое спасибо!

Answer 1

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

Answer 2

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

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

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

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

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

Answer 3

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

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

abcabcacb...

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

aaa...bbb..ccc...

..., тогда перейдите к решению № 2.

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

--- EDIT ---

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

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

--- EDIT 2 ---

Для отличного рассмотрения этого предмета я настоятельно рекомендую выступление Херба Саттера «Вещи, на которых язык программирования никогда не говорил вам», по-прежнему доступно по адресу:

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

Answer 4

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

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

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

car & this_car = allcars[12];

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

a = a[12];

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

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

Answer 5

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

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

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

Answer 6

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

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