Boost :: multi_array вопрос о производительности

Вы собираете релиз или отлаживаете?

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

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

Попробуйте поменять порядок петель X и Y и посмотрите, получите ли вы что-нибудь. Здесь есть некоторая информация о порядке хранения: http://www.boost.org/doc/libs/1_37_0/libs/multi_array/doc/user.html

Обновлено: Поскольку вы, кажется, используете двумерный массив для обработки изображений, вам может быть интересно проверить библиотеку обработки изображений Boosts гил.

У него могут быть массивы с меньшими накладными расходами, которые идеально подходят для вашей ситуации.

Еще одна вещь, которую следует попробовать, - использовать итераторы вместо прямого индекса для массива boost.

Я ожидал, что multiarray будет столь же эффективным. Но я получаю аналогичные результаты на PPC Mac с использованием gcc. Я также пробовал multiarrayref, так что обе версии без разницы использовали одно и то же хранилище. Это полезно знать, поскольку я использую несколько массивов в некоторых частях своего кода и просто предположил, что это похоже на ручное кодирование.

Думаю, я знаю, в чем проблема ... может быть.

Чтобы реализация Boost имела синтаксис вида: matrix [x] [y]. это означает, что матрица [x] должна возвращать ссылку на объект, который действует как одномерный массив столбец, в котором ссылка [y] дает вам ваш элемент.

Проблема здесь в том, что вы выполняете итерацию в порядке ряд основных (что типично для c / C++, поскольку собственные массивы являются строковыми IIRC. В этом случае компилятор должен повторно выполнить матрицу [x] для каждого y. В основном порядке при использовании матрицы повышения вы можете увидеть лучшую производительность.

Просто теория.

Обновлено: в моей системе Linux (с некоторыми незначительными изменениями) я проверил свою теорию и показал улучшение производительности некоторый путем переключения x и y, но он все еще был медленнее, чем собственный массив. Это может быть простая проблема, связанная с тем, что компилятор не может оптимизировать временный ссылочный тип.

Ваш тест ошибочен.

• В сборке DEBUG boost :: MultiArray не хватает прохода оптимизации, в котором он очень нуждается. (Намного больше, чем обычный массив)
• В сборке RELEASE ваш компилятор будет искать код, который можно удалить сразу, и большая часть вашего кода находится в этой категории.

То, что вы, вероятно, видите, является результатом того, что ваш оптимизирующий компилятор видит, что большинство или все ваши циклы «собственного массива» могут быть удалены. Теоретически то же самое верно и для ваших циклов boost :: MultiArray, но MultiArray, вероятно, достаточно сложен, чтобы победить ваш оптимизатор.

Внесите это небольшое изменение в свой тестовый стенд, и вы увидите более реалистичные результаты: замените оба появления «= 2.345» на «*= 2.345» и снова скомпилируйте с оптимизацией. Это не позволит вашему компилятору обнаружить, что внешний цикл каждого теста избыточен.

Я сделал это и получил сравнение скорости ближе к 2: 1.

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

Вместо этого рассмотрите возможность использования 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-stlye? = p

Меня интересуют две вещи:

1) проверка границ: определите макрос препроцессора BOOST_DISABLE_ASSERTS перед включением multi_array.hpp в ваше приложение. Это отключает проверку привязки. не уверен, что это отключает, когда NDEBUG есть.

2) базовый индекс: MultiArray может индексировать массивы из баз, отличных от 0. Это означает, что multi_array хранит базовое число (в каждом измерении) и использует более сложную формулу для получения точного местоположения в памяти, мне интересно, все ли это об этом.

В противном случае я не понимаю, почему multiarray должен быть медленнее, чем C-массивы.

Здесь был задан аналогичный вопрос и дан ответ:

http://www.codeguru.com/forum/archive/index.php/t-300014.html

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

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

Я изменил приведенный выше код в Visual Studio 2008 v9.0.21022 и применил процедуры контейнера из подпрограмм Numerical Recipe для C и C++.

http://www.nrbook.com/nr3/, используя свои лицензионные подпрограммы dmatrix и MatDoub соответственно

dmatrix использует устаревший синтаксис оператора malloc и не рекомендуется ... MatDoub использует команду New

Скорость в секундах в версии Release:

Повышение: 0,437

Собственный: 0,032

Числовые рецепты C: 0,031

Числовые рецепты C++: 0,031

Итак, из вышесказанного блиц выглядит лучшей бесплатной альтернативой.

Я тестировал Mac OS Snow Leopard с использованием 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++ -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 в Ubuntu 10.10

Итак, в заключение:

• С правильная оптимизация boost :: multi_array выполняет свою работу, как ожидалось
• Порядок, в котором вы получаете доступ к своим данным имеет значение

Я скомпилировал код (с небольшими изменениями) под 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, по-видимому, получили лучшие результаты).

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

Глядя на сборку, сгенерированную g ++ 4.8.2 с -O3 -DBOOST_DISABLE_ASSERTS, и используя как operator(), так и [][] способы доступа к элементам, очевидно, что единственной дополнительной операцией по сравнению с собственными массивами и ручным вычислением индекса является добавление базы. Однако я не измерял стоимость этого.

Я смотрел на этот вопрос, потому что у меня был тот же вопрос. У меня были мысли провести более строгий тест.

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

На 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;
}

1. Один только с одномерным массивом с использованием [] с целочисленной математикой и двойным циклом

2. Один с тем же одномерным массивом с использованием увеличения указателя

3. Многомерный массив C

4. Повышение 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-массив с двойным циклом.

Как ответил Родригоб, активация правильной оптимизации (GCC по умолчанию -O0) является ключом к достижению хорошей производительности. Кроме того, я также тестировал Blaze DynamicMatrix, который дал дополнительное улучшение производительности в 2 раза с теми же флагами оптимизации. https://bitbucket.org/account/user/blaze-lib/projects/BLAZE