Выбор наиболее производительного контейнера (массива)

Question

Это мой маленький большой вопрос о контейнерах, в частности, массивах.

Я пишу физический код, который в основном манипулирует большим (> 1 000 000) набором «частиц» (с 6 double координатами каждая). Я ищу лучший способ (с точки зрения производительности) реализовать класс, который будет содержать контейнер для этих данных и который будет предоставлять примитивы манипуляции для этих данных (например, экземпляр, operator[] и т. Д.).

Есть несколько ограничений на использование этого набора:

• его размер считывается из файла конфигурации и не изменяется во время выполнения
• его можно рассматривать как большой двумерный массив из N (например, 1 000 000) строк и 6 столбцов (каждый из которых хранит координаты в одном измерении)
• массив обрабатывается в большом цикле, к каждой "частице / линии" обращаются, и вычисления выполняются с ее координатами, и результаты сохраняются для этой частицы, и так далее для каждой частицы, и так далее для каждой итерация большого цикла.
• новые элементы не добавляются и не удаляются во время выполнения

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

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

Как я понимаю, нет никакого преимущества в использовании динамически распределенного массива вместо std::vector, поэтому такие вещи, как double** array2d = new ..., loop of new, etc, исключены.

Так стоит ли использовать std::vector<double>?

Если я использую std::vector, я должен создать двумерный массив, например std::vector<std::vector<double> > my_array, который можно индексировать как my_array[i][j], или это плохая идея, и было бы лучше использовать std::vector<double> other_array и получить к нему доступ с other_array[6*i+j].

Может быть, это может повысить производительность, особенно если количество столбцов фиксировано и известно с самого начала.

Если вы считаете, что это лучший вариант, можно ли будет обернуть этот вектор таким образом, чтобы к нему можно было обращаться с помощью оператора индекса, определенного как other_array[i,j] // same as other_array[6*i+j], без издержек (например, при вызове функции при каждом доступе)?

Другой вариант, который я использую до сих пор, - это использование Blitz, в частности blitz::Array:

typedef blitz::Array<double,TWO_DIMENSIONS> store_t;
store_t my_store;

Где мои элементы доступны так: my_store(line, column);.

Я думаю, что в моем случае не так уж много преимуществ от использования Blitz, потому что я обращаюсь к каждому элементу один за другим, и что Blitz было бы интересно, если бы я использовал операции непосредственно над массивом (например, умножение матриц), а я нет. 1050 *

Как вы думаете, с Blitz все в порядке или в моем случае бесполезно?

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

Большое спасибо за помощь в решении этой проблемы!

Edit:

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

• Использовать структуру particle (содержащую 6 двойных) или статический массив из 6 двойных (это позволяет избежать использования двумерных динамических массивов)
• Используйте vector или deque этой particle структуры или массива. Тогда хорошо обходить их с помощью итераторов, и это позволит позже перейти от одного к другому.

Кроме того, я также могу использовать Blitz::TinyVector<double,6> вместо структуры.

Answer 1

Так стоит ли использовать std::vector<double>?

Обычно std::vector должен быть первым выбором контейнера. Вы можете использовать либо std::vector<>::reserve(), либо std::vector<>::resize(), чтобы избежать перераспределения при заполнении вектора. Чтобы узнать, лучше ли какой-либо другой контейнер, измеряет . И только путем измерения. Но в первую очередь стоит оптимизировать, в чем состоит содержимое контейнера (заполнение, доступ к элементам).

Если я использую std :: vector, я должен создать двумерный массив, такой как std::vector<std::vector<double> > [...]?

Нет. IIUC, вы получаете доступ к своим данным по частице, а не по строке. Если это так, почему бы не использовать std::vector<particle>, где particle - это структура, содержащая шесть значений? И даже если я неправильно понял, вам лучше написать двумерную оболочку вокруг одномерного контейнера. Затем выровняйте данные в строках или столбцах - что быстрее с вашими шаблонами доступа.

Как вы думаете, с Blitz все в порядке или в моем случае бесполезно?

У меня нет практических знаний о blitz ++ и областях, в которых он используется. Но разве blitz ++ не связан с шаблонами выражений для развертывания операций цикла и оптимизации временных потоков при выполнении матричных манипуляций? ICBWT.

Answer 2

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

struct Particle { /* coords */ };

Тогда мы можем сделать простой одномерный массив из этих Particles.

Я бы, вероятно, использовал deque, потому что это контейнер по умолчанию, но вы можете попробовать vector, просто 1.000.000 частиц означают один кусок из нескольких МБ. Он должен сохраняться, но может привести к перегрузке вашей системы, если она когда-либо возрастет, тогда как deque выделит несколько фрагментов.

ПРЕДУПРЕЖДЕНИЕ

Как заметил Александр С, если вы идете по дороге deque, воздержитесь от использования operator[] и предпочтите использовать стиль итерации. Если вам действительно нужен произвольный доступ и он чувствителен к производительности, vector должен работать быстрее.

Answer 3

Первое правило при выборе из контейнеров - использовать std::vector. Затем, только после того, как ваш код завершен и вы сможете измерить производительность, вы можете попробовать другие контейнеры. Но сначала придерживайтесь вектора. (И используйте reserve() с самого начала)

Тогда вам не следует использовать std::vector<std::vector<double> >. Вы знаете размер ваших данных: это 6 двойных. Не нужно, чтобы оно было динамичным. Он постоянен и фиксирован. Вы можете определить структуру, которая будет содержать членов вашей частицы (шесть двойников), или вы можете просто ввести ее по умолчанию: typedef double particle[6]. Затем используйте вектор частиц: std::vector<particle>.

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

Answer 4

Если вы считаете, что это лучший вариант, можно ли обернуть этот вектор таким образом, чтобы к нему можно было обращаться с помощью оператора индекса, определенного как other_array [i, j] // то же, что other_array [6 * i + j] без издержек (например, вызов функции при каждом доступе)?

(other_array[i,j] не будет работать слишком хорошо, так как i, j использует оператор запятой для оценки значения «i», затем отбрасывает его, вычисляет и возвращает «j», так что это эквивалентно other_array[i]) .

Вам нужно будет использовать одно из:

other_array[i][j]
other_array(i, j)  // if other_array implements operator()(int, int),
                   // but std::vector<> et al don't.
other_array[i].identifier // identifier is a member variable
other_array[i].identifier() // member function getting value
other_array[i].identifier(double) // member function setting value

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

Итак, хороший тест: если вы пишете код, подобный other_array[i][3], где вы решили, что «3» - это двойное число со скоростью, а other_array[i][5], потому что «5» - это ускорение, тогда прекратите это делать и дайте им правильные идентификаторы, чтобы вы могли сказать other_array[i].speed и .acceleration. Тогда другие разработчики смогут прочитать и понять это, и вы гораздо реже будете делать случайные ошибки. С другой стороны, если вы перебираете эти 6 элементов, выполняя одинаковые действия для каждого, то вы, вероятно, хотите, чтобы Particle содержал двойное число [6], или предоставлял operator[](int). Там нет проблем, делая оба:

struct Particle
{
    double x[6];
    double& speed() { return x[3]; }
    double speed() const { return x[3]; }
    double& acceleration() { return x[5]; }
    ...
};

КСТАТИ / причина того, что vector<vector<double> > может быть слишком дорогой, заключается в том, что каждый набор из 6 двойников будет выделяться в куче, а для быстрого выделения и освобождения многие реализации кучи используют блоки фиксированного размера, поэтому ваш маленький запрос будет округляется до следующего размера: это может быть значительным накладным расходом. Внешний вектор также должен будет записать дополнительный указатель на эту память. Кроме того, выделение и освобождение кучи происходит относительно медленно - в вашем случае вы будете делать это только при запуске и завершении работы, но нет особого смысла замедлять вашу программу без какой-либо причины. Еще важнее то, что области в куче могут просто находиться в памяти, поэтому у вашего оператора [] могут возникать сбои в кеше, тянущие больше страниц памяти, чем необходимо, что замедляет работу всей программы. Иными словами, векторы хранят элементы смежно, но указатели на векторы не могут быть смежными.

Answer 5

Вы могли бы пойти несколькими путями. Но в вашем случае не объявляет std::vector<std::vector<double> >. Вы выделяете vector (и копируете его) на каждые 6 дублей. Это слишком дорого.