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

Question

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

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

РЕДАКТИРОВАТЬ: Это была отладочная сборка. По словам Лазераллана, я выполнил сборку релиза:

[Boost] Elapsed time:  0.266 seconds
[Native]Elapsed time:  0.016 seconds

Намного ближе. Но 16 к 1 все еще кажется мне высоким.

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

Принятие ответа Ласераллана, потому что это был самый большой недостаток в моем тесте.

Спасибо всем.

Answer 1

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

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

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

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

Answer 2

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

Answer 3

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

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

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

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

РЕДАКТИРОВАТЬ: в моей системе Linux (с некоторыми незначительными изменениями) я проверил свою теорию и показал некоторое улучшение производительности при переключении x и y, но оно все еще было медленнее, чем собственный массив. Это может быть простой проблемой того, что компилятор не может оптимизировать временный ссылочный тип.

Answer 4

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

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

Answer 5

Я изменил приведенный выше код в 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

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