Самый быстрый способ доступа к элементам в Boost MultiArray

Что быстрее — получить доступ к элементам многолинейного массива с помощью оператора выбора элементов или обойти многолинейный массив с помощью итераторов?

В моем случае мне нужно сделать полный проход по всем элементам мульти-массива каждый раз.

1

Решение

Самый быстрый способ получить доступ к каждому элементу boost::multi_array через data() а также num_elements(),

С data() Вы получаете доступ к базовому необработанному хранилищу (непрерывному блоку, который содержит данные массива), поэтому нет необходимости в многократных вычислениях индекса (учтите также, что multi_array может индексировать массивы из баз, отличных от 0, и это еще одно осложнение).

Простой тест дает:

g++ -O3 -fomit-frame-pointer -march=native   (GCC v4.8.2)
Writing (index): 9.70651
Writing (data):  2.22353
Reading (index): 4.5973 (found 1)
Reading (data):  3.53811 (found 1)

clang++ -O3 -fomit-frame-pointer -march=native   (CLANG v3.3)
Writing (index): 5.49858
Writing (data):  2.13678
Reading (index): 5.07324 (found 1)
Reading (data):  2.55109 (found 1)

По умолчанию методы расширенного доступа выполняют проверку диапазона. Если предоставленный индекс выходит за пределы диапазона, определенного для массива, утверждение отменяет программу. Чтобы отключить проверку диапазона, вы можете определить BOOST_DISABLE_ASSERTS макрос препроцессора перед включением multi_array.hpp в вашем приложении.

Это значительно уменьшит разницу в производительности:

g++ -O3 -fomit-frame-pointer -march=native   (GCC v4.8.2)
Writing (index): 3.15244
Writing (data):  2.23002
Reading (index): 1.89553 (found 1)
Reading (data):  1.54427 (found 1)

clang++ -O3 -fomit-frame-pointer -march=native   (CLANG v3.3)
Writing (index): 2.24831
Writing (data):  2.12853
Reading (index): 2.59164 (found 1)
Reading (data):  2.52141 (found 1)

Разница в производительности увеличивается (т.е. data() быстрее):

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

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

Источник:

#include <chrono>
#include <iostream>

// #define BOOST_DISABLE_ASSERTS
#include <boost/multi_array.hpp>

int main()
{
using array3 = boost::multi_array<unsigned, 3>;
using index = array3::index;

using clock = std::chrono::high_resolution_clock;
using duration = std::chrono::duration<double>;

constexpr unsigned d1(300), d2(400), d3(200), sup(100);

array3 A(boost::extents[d1][d2][d3]);

// Writing via index
const auto t_begin1(clock::now());
unsigned values1(0);
for (unsigned n(0); n < sup; ++n)
for (index i(0); i != d1; ++i)
for (index j(0); j != d2; ++j)
for (index k(0); k != d3; ++k)
A[i][j][k] = ++values1;
const auto t_end1(clock::now());

// Writing directly
const auto t_begin2(clock::now());
unsigned values2(0);
for (unsigned n(0); n < sup; ++n)
{
const auto sup(A.data() + A.num_elements());

for (auto i(A.data()); i != sup; ++i)
*i = ++values2;
}
const auto t_end2(clock::now());

// Reading via index
const auto t_begin3(clock::now());
bool found1(false);
for (unsigned n(0); n < sup; ++n)
for (index i(0); i != d1; ++i)
for (index j(0); j != d2; ++j)
for (index k(0); k != d3; ++k)
if (A[i][j][k] == values1)
found1 = true;
const auto t_end3(clock::now());

// Reading directly
const auto t_begin4(clock::now());
bool found2(false);
for (unsigned n(0); n < sup; ++n)
{
const auto sup(A.data() + A.num_elements());

for (auto i(A.data()); i != sup; ++i)
if (*i == values2)
found2 = true;
}
const auto t_end4(clock::now());

std::cout << "Writing (index): "<< std::chrono::duration_cast<duration>(t_end1 - t_begin1).count()
<< std::endl
<< "Writing (data):  "<< std::chrono::duration_cast<duration>(t_end2 - t_begin2).count()
<< std::endl
<< "Reading (index): "<< std::chrono::duration_cast<duration>(t_end3 - t_begin3).count()
<< " (found " << found1 << ")" << std::endl
<< "Reading (data):  "<< std::chrono::duration_cast<duration>(t_end4 - t_begin4).count()
<< " (found " << found2 << ")" << std::endl;

return 0;
}
5

Другие решения


По вопросам рекламы [email protected]