std :: sort на контейнере указателей - PullRequest
Новая
       15

std :: sort на контейнере указателей

0 голосов
/ 11 марта 2012

Я хочу изучить различия в производительности для множественной разыменования данных внутри вектора вновь распределенных структур (или классов). 

struct Foo
{
    int val;
    // some variables
}

std::vector<Foo*> vectorOfFoo;

// Foo objects are new-ed and pushed in vectorOfFoo
for (int i=0; i<N; i++)
{
   Foo *f = new Foo;
   vectorOfFoo.push_back(f);
}

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

for (vector<Foo*>::iterator iter1 = vectorOfFoo.begin(); iter!=vectorOfFoo.end(); ++iter1)
{
   int somevalue  = (*iter)->value;

}

Очевидно, что если указатели внутри vectorOfFoo находятся очень далеко, я думаю, что местность ссылок несколько утрачена.

А как насчет производительности, если перед циклом я сортирую вектор перед тем, как итерировать его? Должен ли я иметь более высокую производительность при повторных разыменованиях?

Уверен ли я, что последовательный «new» выделяет указатель, близкий в макете памяти?

Ответы [ 3 ]

2 голосов
/ 11 марта 2012

Если вы хотите улучшить локальность ссылок для ваших объектов, вам следует изучить распределение пула.

Но без профилирования это бессмысленно.

2 голосов
/ 11 марта 2012

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

1 голос
/ 11 марта 2012

Это зависит от многих факторов.

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

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

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

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

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

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

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

В любом случае, вам абсолютно необходимо измерить производительность всего приложения до и после ваших изменений. Подобные оптимизации - сложная задача, и ситуация может ухудшиться, даже если теоретически производительность должна была быть улучшена. Есть много инструментов, которые могут помочь вам профилировать доступ к памяти. Например, cachegrind. Intel VTune делает то же самое. И много других инструментов. Так что не угадывайте, экспериментируйте и проверяйте результаты.

...