Вопрос о производительности Boost::multi_array
https://stackoverflow.com/questions/446866
-
22-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я пытаюсь сравнить производительность boost::multi_array с собственными динамически распределяемыми массивами с помощью следующей тестовой программы:
#include <windows.h>
#define _SCL_SECURE_NO_WARNINGS
#define BOOST_DISABLE_ASSERTS
#include <boost/multi_array.hpp>
int main(int argc, char* argv[])
{
const int X_SIZE = 200;
const int Y_SIZE = 200;
const int ITERATIONS = 500;
unsigned int startTime = 0;
unsigned int endTime = 0;
// Create the boost array
typedef boost::multi_array<double, 2> ImageArrayType;
ImageArrayType boostMatrix(boost::extents[X_SIZE][Y_SIZE]);
// Create the native array
double *nativeMatrix = new double [X_SIZE * Y_SIZE];
//------------------Measure boost----------------------------------------------
startTime = ::GetTickCount();
for (int i = 0; i < ITERATIONS; ++i)
{
for (int y = 0; y < Y_SIZE; ++y)
{
for (int x = 0; x < X_SIZE; ++x)
{
boostMatrix[x][y] = 2.345;
}
}
}
endTime = ::GetTickCount();
printf("[Boost] Elapsed time: %6.3f seconds\n", (endTime - startTime) / 1000.0);
//------------------Measure native-----------------------------------------------
startTime = ::GetTickCount();
for (int i = 0; i < ITERATIONS; ++i)
{
for (int y = 0; y < Y_SIZE; ++y)
{
for (int x = 0; x < X_SIZE; ++x)
{
nativeMatrix[x + (y * X_SIZE)] = 2.345;
}
}
}
endTime = ::GetTickCount();
printf("[Native]Elapsed time: %6.3f seconds\n", (endTime - startTime) / 1000.0);
return 0;
}
Я получаю следующие результаты:
[Boost] Elapsed time: 12.500 seconds
[Native]Elapsed time: 0.062 seconds
Я не могу поверить, что multi_arrays работают настолько медленнее.Может ли кто-нибудь заметить, что я делаю неправильно?
Я предполагаю, что кеширование не является проблемой, поскольку я выполняю запись в память.
РЕДАКТИРОВАТЬ:Это была отладочная сборка.По предложению Laserallan я сделал сборку релиза:
[Boost] Elapsed time: 0.266 seconds
[Native]Elapsed time: 0.016 seconds
Гораздо ближе.Но 16 к 1 мне все же кажется высоким.
Что ж, однозначного ответа нет, но я собираюсь пойти дальше и пока оставить свой настоящий код с собственными массивами.
Принимаю ответ Лазераллана, потому что это был самый большой недостаток в моем тесте.
Спасибо всем.
Решение
Вы создаете релиз или отладку?
При работе в режиме отладки массив boost может работать очень медленно, поскольку магия их шаблонов не встроена должным образом, что приводит к большим накладным расходам при вызовах функций.Я не уверен, как реализовано несколько массивов, так что это может быть совершенно не так :)
Возможно, существует некоторая разница в порядке хранения, поэтому вы можете хранить изображение столбец за столбцом и записывать его строку за строкой.Это приведет к ухудшению поведения кэша и может замедлить работу.
Попробуйте поменять порядок циклов X и Y и посмотрите, получите ли вы что-нибудь.Здесь есть некоторая информация о заказе хранилища:http://www.boost.org/doc/libs/1_37_0/libs/multi_array/doc/user.html
РЕДАКТИРОВАТЬ:Поскольку вы, похоже, используете двумерный массив для обработки изображений, вам может быть интересно проверить библиотеку обработки изображений Boosts. Гил.
У него могут быть массивы с меньшими накладными расходами, которые идеально подходят для вашей ситуации.
Другие советы
На моей машине, используя
g++ -O3 -march=native -mtune=native --fast-math -DNDEBUG test.cpp -o test && ./test
я получил
[Boost] Elapsed time: 0.020 seconds
[Native]Elapsed time: 0.020 seconds
Однако изменение const int ITERATIONS к 5000 я получил
[Boost] Elapsed time: 0.240 seconds
[Native]Elapsed time: 0.180 seconds
затем с ITERATIONS вернуться к 500 но X_SIZE и Y_SIZE установлен в 400 у меня гораздо более существенная разница
[Boost] Elapsed time: 0.460 seconds
[Native]Elapsed time: 0.070 seconds
наконец, инвертируя внутренний цикл для [Boost] дело так выглядит
for (int x = 0; x < X_SIZE; ++x)
{
for (int y = 0; y < Y_SIZE; ++y)
{
и сохранение ITERATIONS, X_SIZE и Y_SIZE к 500, 400 и 400 я получил
[Boost] Elapsed time: 0.060 seconds
[Native]Elapsed time: 0.080 seconds
Если я инвертирую внутренний цикл также для [Native] случае (поэтому порядок в этом случае неправильный), я получаю, что неудивительно,
[Boost] Elapsed time: 0.070 seconds
[Native]Elapsed time: 0.450 seconds
Я использую gcc (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5 на Убунту 10.10
Итак, в заключение:
- С правильная оптимизация boost::multi_array выполняет свою работу, как и ожидалось
- Порядок доступа к вашим данным имеет значение
Ваш тест ошибочен.
- В сборке DEBUG boost::MultiArray не хватает этапа оптимизации, который ему крайне необходим.(Гораздо больше, чем собственный массив)
- В сборке RELEASE ваш компилятор будет искать код, который можно сразу удалить и большая часть вашего кода находится в этой категории.
То, что вы, вероятно, видите, является результатом того, что ваш оптимизирующий компилятор видит, что большинство или все ваши циклы «родного массива» могут быть удалены.То же самое теоретически верно и для ваших циклов boost::MultiArray, но MultiArray, вероятно, достаточно сложен, чтобы победить ваш оптимизатор.
Внесите это небольшое изменение в свой испытательный стенд и вы увидите более реалистичные результаты:Измените оба появления "= 2.345 " с "*= 2.345 " и снова скомпилируйте с оптимизацией.Это не позволит вашему компилятору обнаружить, что внешний цикл каждого теста является избыточным.
Я сделал это и получил сравнение скоростей ближе к 2:1.
Мне интересно две вещи:
1) проверка границ: определите макрос препроцессора BOOST_DISABLE_ASSERTS перед включением multi_array.hpp в ваше приложение. Это отключает обязательную проверку. не уверен, если это отключено, когда NDEBUG.
2) базовый индекс: MultiArray может индексировать массивы из баз, отличных от 0. Это означает, что multi_array хранит базовое число (в каждом измерении) и использует более сложную формулу для получения точного местоположения в памяти, мне интересно, если это все об этом.
В противном случае я не понимаю, почему многострочный массив должен быть медленнее, чем C-массивы.
Вместо этого рассмотрите возможность использования Blitz++.Я опробовал Blitz, и его производительность находится на уровне массива в стиле C!
Проверьте свой код с добавленным Blitz ниже:
#include <windows.h>
#define _SCL_SECURE_NO_WARNINGS
#define BOOST_DISABLE_ASSERTS
#include <boost/multi_array.hpp>
#include <blitz/array.h>
int main(int argc, char* argv[])
{
const int X_SIZE = 200;
const int Y_SIZE = 200;
const int ITERATIONS = 500;
unsigned int startTime = 0;
unsigned int endTime = 0;
// Create the boost array
typedef boost::multi_array<double, 2> ImageArrayType;
ImageArrayType boostMatrix(boost::extents[X_SIZE][Y_SIZE]);
//------------------Measure boost----------------------------------------------
startTime = ::GetTickCount();
for (int i = 0; i < ITERATIONS; ++i)
{
for (int y = 0; y < Y_SIZE; ++y)
{
for (int x = 0; x < X_SIZE; ++x)
{
boostMatrix[x][y] = 2.345;
}
}
}
endTime = ::GetTickCount();
printf("[Boost] Elapsed time: %6.3f seconds\n", (endTime - startTime) / 1000.0);
//------------------Measure blitz-----------------------------------------------
blitz::Array<double, 2> blitzArray( X_SIZE, Y_SIZE );
startTime = ::GetTickCount();
for (int i = 0; i < ITERATIONS; ++i)
{
for (int y = 0; y < Y_SIZE; ++y)
{
for (int x = 0; x < X_SIZE; ++x)
{
blitzArray(x,y) = 2.345;
}
}
}
endTime = ::GetTickCount();
printf("[Blitz] Elapsed time: %6.3f seconds\n", (endTime - startTime) / 1000.0);
//------------------Measure native-----------------------------------------------
// Create the native array
double *nativeMatrix = new double [X_SIZE * Y_SIZE];
startTime = ::GetTickCount();
for (int i = 0; i < ITERATIONS; ++i)
{
for (int y = 0; y < Y_SIZE; ++y)
{
for (int x = 0; x < X_SIZE; ++x)
{
nativeMatrix[x + (y * X_SIZE)] = 2.345;
}
}
}
endTime = ::GetTickCount();
printf("[Native]Elapsed time: %6.3f seconds\n", (endTime - startTime) / 1000.0);
return 0;
}
Вот результат отладки и выпуска.
ОТЛАЖИВАТЬ:
Boost 2.093 secs
Blitz 0.375 secs
Native 0.078 secs
ВЫПУСКАТЬ:
Boost 0.266 secs
Blitz 0.016 secs
Native 0.015 secs
Для этого я использовал компилятор MSVC 2008 SP1.
Можем ли мы теперь попрощаться с массивом C-style?=р
Я смотрел на этот вопрос, потому что у меня был тот же вопрос. У меня были некоторые мысли, чтобы дать более строгий тест.
<Ол>На Mac следующий код настроен для предоставления более значимых ответов. Здесь есть 4 теста.
#define BOOST_DISABLE_ASSERTS
#include "boost/multi_array.hpp"
#include <sys/time.h>
#include <stdint.h>
#include<string>
uint64_t GetTimeMs64()
{
struct timeval tv;
gettimeofday( &tv, NULL );
uint64_t ret = tv.tv_usec;
/* Convert from micro seconds (10^-6) to milliseconds (10^-3) */
ret /= 1000;
/* Adds the seconds (10^0) after converting them to milliseconds (10^-3) */
ret += ( tv.tv_sec * 1000 );
return ret;
}
void function1( const int X_SIZE, const int Y_SIZE, const int ITERATIONS )
{
double nativeMatrix1add[X_SIZE*Y_SIZE];
for( int x = 0 ; x < X_SIZE ; ++x )
{
for( int y = 0 ; y < Y_SIZE ; ++y )
{
nativeMatrix1add[y + ( x * Y_SIZE )] = rand();
}
}
// Create the native array
double* __restrict const nativeMatrix1p = new double[X_SIZE * Y_SIZE];
uint64_t startTime = GetTimeMs64();
for( int i = 0 ; i < ITERATIONS ; ++i )
{
for( int xy = 0 ; xy < X_SIZE*Y_SIZE ; ++xy )
{
nativeMatrix1p[xy] += nativeMatrix1add[xy];
}
}
uint64_t endTime = GetTimeMs64();
printf( "[Native Pointer] Elapsed time: %6.3f seconds\n", ( endTime - startTime ) / 1000.0 );
}
void function2( const int X_SIZE, const int Y_SIZE, const int ITERATIONS )
{
double nativeMatrix1add[X_SIZE*Y_SIZE];
for( int x = 0 ; x < X_SIZE ; ++x )
{
for( int y = 0 ; y < Y_SIZE ; ++y )
{
nativeMatrix1add[y + ( x * Y_SIZE )] = rand();
}
}
// Create the native array
double* __restrict const nativeMatrix1 = new double[X_SIZE * Y_SIZE];
uint64_t startTime = GetTimeMs64();
for( int i = 0 ; i < ITERATIONS ; ++i )
{
for( int x = 0 ; x < X_SIZE ; ++x )
{
for( int y = 0 ; y < Y_SIZE ; ++y )
{
nativeMatrix1[y + ( x * Y_SIZE )] += nativeMatrix1add[y + ( x * Y_SIZE )];
}
}
}
uint64_t endTime = GetTimeMs64();
printf( "[Native 1D Array] Elapsed time: %6.3f seconds\n", ( endTime - startTime ) / 1000.0 );
}
void function3( const int X_SIZE, const int Y_SIZE, const int ITERATIONS )
{
double nativeMatrix2add[X_SIZE][Y_SIZE];
for( int x = 0 ; x < X_SIZE ; ++x )
{
for( int y = 0 ; y < Y_SIZE ; ++y )
{
nativeMatrix2add[x][y] = rand();
}
}
// Create the native array
double nativeMatrix2[X_SIZE][Y_SIZE];
uint64_t startTime = GetTimeMs64();
for( int i = 0 ; i < ITERATIONS ; ++i )
{
for( int x = 0 ; x < X_SIZE ; ++x )
{
for( int y = 0 ; y < Y_SIZE ; ++y )
{
nativeMatrix2[x][y] += nativeMatrix2add[x][y];
}
}
}
uint64_t endTime = GetTimeMs64();
printf( "[Native 2D Array] Elapsed time: %6.3f seconds\n", ( endTime - startTime ) / 1000.0 );
}
void function4( const int X_SIZE, const int Y_SIZE, const int ITERATIONS )
{
boost::multi_array<double, 2> boostMatrix2add( boost::extents[X_SIZE][Y_SIZE] );
for( int x = 0 ; x < X_SIZE ; ++x )
{
for( int y = 0 ; y < Y_SIZE ; ++y )
{
boostMatrix2add[x][y] = rand();
}
}
// Create the native array
boost::multi_array<double, 2> boostMatrix( boost::extents[X_SIZE][Y_SIZE] );
uint64_t startTime = GetTimeMs64();
for( int i = 0 ; i < ITERATIONS ; ++i )
{
for( int x = 0 ; x < X_SIZE ; ++x )
{
for( int y = 0 ; y < Y_SIZE ; ++y )
{
boostMatrix[x][y] += boostMatrix2add[x][y];
}
}
}
uint64_t endTime = GetTimeMs64();
printf( "[Boost Array] Elapsed time: %6.3f seconds\n", ( endTime - startTime ) / 1000.0 );
}
int main( int argc, char* argv[] )
{
srand( time( NULL ) );
const int X_SIZE = std::stoi( argv[1] );
const int Y_SIZE = std::stoi( argv[2] );
const int ITERATIONS = std::stoi( argv[3] );
function1( X_SIZE, Y_SIZE, ITERATIONS );
function2( X_SIZE, Y_SIZE, ITERATIONS );
function3( X_SIZE, Y_SIZE, ITERATIONS );
function4( X_SIZE, Y_SIZE, ITERATIONS );
return 0;
}
Один с одним одномерным массивом, использующий [] с целочисленной математикой и двойным циклом
Элемент с одним и тем же одномерным массивом с использованием увеличения указателя
многомерный массив C
Boost multi_array
так что запускай из командной строки, запускай
./test_array xsize ysize iterations"
и вы можете получить хорошее представление о том, как будут работать эти подходы. Вот что я получил со следующими флагами компилятора:
g++4.9.2 -O3 -march=native -funroll-loops -mno-avx --fast-math -DNDEBUG -c -std=c++11
./test_array 51200 1 20000
[Native 1-Loop ] Elapsed time: 0.537 seconds
[Native 1D Array] Elapsed time: 2.045 seconds
[Native 2D Array] Elapsed time: 2.749 seconds
[Boost Array] Elapsed time: 1.167 seconds
./test_array 25600 2 20000
[Native 1-Loop ] Elapsed time: 0.531 seconds
[Native 1D Array] Elapsed time: 1.241 seconds
[Native 2D Array] Elapsed time: 1.631 seconds
[Boost Array] Elapsed time: 0.954 seconds
./test_array 12800 4 20000
[Native 1-Loop ] Elapsed time: 0.536 seconds
[Native 1D Array] Elapsed time: 1.214 seconds
[Native 2D Array] Elapsed time: 1.223 seconds
[Boost Array] Elapsed time: 0.798 seconds
./test_array 6400 8 20000
[Native 1-Loop ] Elapsed time: 0.540 seconds
[Native 1D Array] Elapsed time: 0.845 seconds
[Native 2D Array] Elapsed time: 0.878 seconds
[Boost Array] Elapsed time: 0.803 seconds
./test_array 3200 16 20000
[Native 1-Loop ] Elapsed time: 0.537 seconds
[Native 1D Array] Elapsed time: 0.661 seconds
[Native 2D Array] Elapsed time: 0.673 seconds
[Boost Array] Elapsed time: 0.708 seconds
./test_array 1600 32 20000
[Native 1-Loop ] Elapsed time: 0.532 seconds
[Native 1D Array] Elapsed time: 0.592 seconds
[Native 2D Array] Elapsed time: 0.596 seconds
[Boost Array] Elapsed time: 0.764 seconds
./test_array 800 64 20000
[Native 1-Loop ] Elapsed time: 0.546 seconds
[Native 1D Array] Elapsed time: 0.594 seconds
[Native 2D Array] Elapsed time: 0.606 seconds
[Boost Array] Elapsed time: 0.764 seconds
./test_array 400 128 20000
[Native 1-Loop ] Elapsed time: 0.536 seconds
[Native 1D Array] Elapsed time: 0.560 seconds
[Native 2D Array] Elapsed time: 0.564 seconds
[Boost Array] Elapsed time: 0.746 seconds
Итак, я думаю, можно с уверенностью сказать, что boost multi_array работает довольно хорошо. Ничто не сравнится с оценкой одного цикла, но в зависимости от размера массива boost :: multi_array может превзойти стандартный c-массив с двойным циклом.
Еще одна попытка - использовать итераторы вместо прямого индекса для массива надстройки.
Я бы ожидал, что многолинейный массив будет столь же эффективным. Но я получаю похожие результаты на PPC Mac, используя gcc. Я также попробовал multiarrayref, чтобы обе версии использовали одно и то же хранилище без разницы. Это полезно знать, поскольку в некоторых моих кодах я использую несколько массивов и просто предположил, что это похоже на ручное кодирование.
Я думаю, что знаю, в чем проблема ... возможно.
Чтобы реализация Boost имела синтаксис, такой как: matrix [x] [y]. это означает, что matrix [x] должна возвращать ссылку на объект, который действует как одномерный массив column , и в этом случае ссылка [y] дает вам ваш элемент.
Проблема здесь в том, что вы выполняете итерацию в мажоре строк (что типично для c / c ++, поскольку нативные массивы являются мажорными строками IIRC. Компилятор должен повторно выполнить матрицу [x] для в данном случае - y. Если при использовании матрицы повышения вы итерировали в главном порядке столбцов, производительность может быть выше.
Просто теория.
РЕДАКТИРОВАТЬ: в моей системе linux (с некоторыми незначительными изменениями) я проверил свою теорию и показал некоторое улучшение производительности, переключив x и y, но это все же было медленнее, чем собственный массив. Это может быть простой проблемой того, что компилятор не может оптимизировать временный ссылочный тип.
Выполните сборку в режиме выпуска, используйте objdump и посмотрите на сборку. Они могут делать совершенно разные вещи, и вы сможете увидеть, какие оптимизации использует компилятор.
Подобный вопрос был задан и получен ответ здесь:
http://www.codeguru.com/forum /archive/index.php/t-300014.html
Короткий ответ: компилятору проще всего оптимизировать простые массивы, а оптимизировать версию Boost не так просто. Следовательно, конкретный компилятор может не дать версии Boost все те же преимущества оптимизации.
Компиляторы также могут отличаться в зависимости от того, насколько хорошо они будут оптимизироваться, и от того, насколько консервативными они будут (например, с помощью шаблонного кода или других сложностей).
Я тестировал ОС Snow Leopard Mac OS с использованием gcc 4.2.1
Debug:
[Boost] Elapsed time: 2.268 seconds
[Native]Elapsed time: 0.076 seconds
Release:
[Boost] Elapsed time: 0.065 seconds
[Native]Elapsed time: 0.020 seconds
Здесь приведен код (модифицированный таким образом, чтобы его можно было скомпилировать в Unix):
#define BOOST_DISABLE_ASSERTS
#include <boost/multi_array.hpp>
#include <ctime>
int main(int argc, char* argv[])
{
const int X_SIZE = 200;
const int Y_SIZE = 200;
const int ITERATIONS = 500;
unsigned int startTime = 0;
unsigned int endTime = 0;
// Create the boost array
typedef boost::multi_array<double, 2> ImageArrayType;
ImageArrayType boostMatrix(boost::extents[X_SIZE][Y_SIZE]);
// Create the native array
double *nativeMatrix = new double [X_SIZE * Y_SIZE];
//------------------Measure boost----------------------------------------------
startTime = clock();
for (int i = 0; i < ITERATIONS; ++i)
{
for (int y = 0; y < Y_SIZE; ++y)
{
for (int x = 0; x < X_SIZE; ++x)
{
boostMatrix[x][y] = 2.345;
}
}
}
endTime = clock();
printf("[Boost] Elapsed time: %6.3f seconds\n", (endTime - startTime) / (double)CLOCKS_PER_SEC);
//------------------Measure native-----------------------------------------------
startTime = clock();
for (int i = 0; i < ITERATIONS; ++i)
{
for (int y = 0; y < Y_SIZE; ++y)
{
for (int x = 0; x < X_SIZE; ++x)
{
nativeMatrix[x + (y * X_SIZE)] = 2.345;
}
}
}
endTime = clock();
printf("[Native]Elapsed time: %6.3f seconds\n", (endTime - startTime) / (double)CLOCKS_PER_SEC);
return 0;
}
Глядя на сборку, сгенерированную g ++ 4.8.2 с помощью -O3 -DBOOST_DISABLE_ASSERTS и используя способы доступа к элементам как operator(), так и [][], видно, что единственная дополнительная операция по сравнению с собственными массивами и вычислением индекса вручную дополнение базы. Я не измерял стоимость этого все же.
Я изменил приведенный выше код в Visual Studio 2008 v9.0.21022 и применил подпрограммы контейнеров из подпрограмм «Числовой рецепт» для C и C ++
http://www.nrbook.com/nr3/ с использованием их лицензионных подпрограмм dmatrix и MatDoub соответственно
dmatrix использует устаревший синтаксический оператор malloc и не рекомендуется ... MatDoub использует команду New
Скорость в секундах указана в версии выпуска:
Повышение: 0,437
Родной: 0.032
Числовые рецепты C: 0,031
Числовые рецепты C ++: 0,031
Таким образом, блиц выглядит как лучшая бесплатная альтернатива.
Я скомпилировал код (с небольшими изменениями) под VC ++ 2010 с включенной оптимизацией (" Максимизировать скорость " вместе со встроенными функциями " Любой подходящий " и " Любим быстрый код ") и получил раз 0,015 / 0,391. Я сгенерировал листинг сборки, и, хотя я ужасный новичок в сборке, внутри цикла измерения наддува есть одна строка, которая мне не подходит:
call ??A?$multi_array_ref@N$01@boost@@QAE?AV?$sub_array@N$00@multi_array@detail@1@H@Z ; boost::multi_array_ref<double,2>::operator[]
Один из операторов [] не был встроен! Вызванная процедура делает другой вызов, на этот раз multi_array::value_accessor_n<...>::access<...>():
call ??$access@V?$sub_array@N$00@multi_array@detail@boost@@PAN@?$value_accessor_n@N$01@multi_array@detail@boost@@IBE?AV?$sub_array@N$00@123@U?$type@V?$sub_array@N$00@multi_array@detail@boost@@@3@HPANPBIPBH3@Z ; boost::detail::multi_array::value_accessor_n<double,2>::access<boost::detail::multi_array::sub_array<double,1>,double *>
В целом, две процедуры представляют собой достаточно много кода для простого доступа к одному элементу в массиве. У меня сложилось общее впечатление, что библиотека настолько сложна и высокоуровнева, что Visual Studio не может оптимизировать ее столько, сколько мы хотели бы (постеры, использующие gcc, по-видимому, получили лучшие результаты).
ИМХО, хороший компилятор действительно должен был встроить и оптимизировать две процедуры - обе они довольно короткие и простые, не содержат циклов и т. д. Много времени может быть потрачено впустую просто на передачу своих аргументов и результатов.
Как ответил Rodrigob, активация правильной оптимизации (по умолчанию GCC -O0) является ключом для получения хорошей производительности. Кроме того, я также провел тестирование с помощью Blaze DynamicMatrix , что привело к дополнительному Улучшение производительности в 2-х факторах с теми же флагами оптимизации. https://bitbucket.org/account/user/blaze-lib/projects/ BLAZE
