Boost :: pergunta desempenho multi_array

https://stackoverflow.com/questions/446866

22-07-2019
|

Pergunta

Eu estou tentando comparar o desempenho de boost :: multi_array para matrizes alocadas dinamicamente nativas, com o seguinte programa de teste:

#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;
}

Eu recebo os seguintes resultados:

[Boost] Elapsed time: 12.500 seconds
[Native]Elapsed time:  0.062 seconds

Eu não posso acreditar multi_arrays são que muito mais lento. Can qualquer ponto que eu estou fazendo errado?

Eu assumo caching não é um problema desde que eu estou fazendo gravações para memória.

EDIT: Esta foi uma compilação de depuração. Per de Laserallan sugere que eu fiz uma compilação de lançamento:

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

Muito mais perto. Mas 16-1 ainda parece alto para mim.

Bem, nenhuma resposta definitiva, mas eu vou seguir em frente e deixar o meu código real com matrizes nativas para agora.

Aceitar a resposta de Laserallan porque era a maior falha no meu teste.

Obrigado a todos.

Solução

Você está construindo lançamento ou de depuração?

Se estiver executando no modo de depuração, a matriz impulso pode ser muito lento, porque a sua magia modelo não é inlined dando adequadamente muita sobrecarga em chamadas de função. Eu não tenho certeza de como array multi é implementado embora então isso pode ser totalmente fora:)

Talvez haja alguma diferença na ordem de armazenamento, bem assim você pode estar tendo sua imagem coluna armazenada por coluna e escrevê-lo linha por linha. Isso daria comportamento do cache pobres e pode abrandar as coisas.

Tente mudar a ordem do circuito X e Y e ver se você ganha nada. Há algumas informações sobre a ordenação de armazenamento aqui: http://www.boost.org/doc/libs /1_37_0/libs/multi_array/doc/user.html

EDIT: Desde que você parece estar usando a matriz bidimensional para processamento de imagem que você pode estar interessado em verificar para fora aumenta biblioteca de processamento de imagem gil .

Ele pode ter arrays com menos sobrecarga que funciona perfeitamente para a sua situação.

Outras dicas

Na minha máquina usando

g++ -O3 -march=native -mtune=native --fast-math -DNDEBUG test.cpp -o test && ./test

I get

[Boost] Elapsed time:  0.020 seconds
[Native]Elapsed time:  0.020 seconds

No entanto mudando const int ITERATIONS para 5000 I get

[Boost] Elapsed time:  0.240 seconds
[Native]Elapsed time:  0.180 seconds

depois com ITERATIONS volta para 500 mas X_SIZE e conjunto Y_SIZE para 400 eu recebo uma diferença muito mais significativa

[Boost] Elapsed time:  0.460 seconds
[Native]Elapsed time:  0.070 seconds

finalmente inverter o loop interno para o caso [Boost] de modo que parece

    for (int x = 0; x < X_SIZE; ++x)
    {
        for (int y = 0; y < Y_SIZE; ++y)
        {

e mantendo ITERATIONS, X_SIZE e Y_SIZE para 500, 400 e 400 I get

[Boost] Elapsed time:  0.060 seconds
[Native]Elapsed time:  0.080 seconds

Se eu inverter o loop interno também ao caso [Native] (por isso é na ordem errada para esse caso), eu recebo, sem surpresa,

[Boost] Elapsed time:  0.070 seconds
[Native]Elapsed time:  0.450 seconds

Eu estou usando gcc (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5 no Ubuntu 10.10

Portanto, em conclusão:

com otimização adequada boost :: multi_array faz o seu trabalho como esperado
A ordem na qual você acessa seus dados não importa

Seu teste é falho.

Em uma compilação de depuração, boost :: multiarray não tem a passagem de otimização que intensamente necessidades. (Muito mais do que uma matriz nativa seria)

Em uma compilação de lançamento, o compilador vai olhar para o código que pode ser removido a título definitivo e a maioria de seu código é nessa categoria .

O que é provável que você ver é o resultado de seu compilador otimizar vendo que a maioria ou todos os seus loops "de matriz nativa" pode ser removido. O mesmo é teoricamente verdadeira do seu boost :: laços multiarray, mas multiarray é provavelmente o suficiente complexa para derrotar o seu otimizador.

Faça esta pequena alteração no seu testbed e você verá mais verdadeiro para a vida resultados: mudar tanto ocorrências de "= 2.345" com "*= 2.345" e compilar novamente com otimizações. Isso vai evitar que seu compilador de descobrir que o loop externo de cada teste é redundante.

Eu fiz isso e tem uma comparação de velocidade mais perto de 2: 1.

Eu estou querendo saber duas coisas:

1) limites verificar: definir as BOOST_DISABLE_ASSERTS pré-processador macro antes de incluindo multi_array.hpp na sua aplicação. Isso desativa a verificação de limite. não sei se isso é desativa quando NDEBUG é.

2) índice de base: Multiarray matrizes índice pode a partir de bases diferentes de 0. Isso significa que as lojas multi_array um número base (em cada dimensão) e utiliza uma fórmula mais complicada para obter a localização exata na memória, eu estou querendo saber se é tudo sobre isso.

Caso contrário, eu não entendo por que multiarray deve ser mais lento do que C-matrizes.

Considere o uso Blitz ++ vez. Eu tentei Blitz, e seu desempenho está a par com matriz estilo C!

Confira o seu código com Blitz adicionado abaixo:

#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; }

Aqui está o resultado na depuração e liberação.

DEBUG:

Boost 2.093 secs Blitz 0.375 secs Native 0.078 secs

RELEASE:

Boost 0.266 secs Blitz 0.016 secs Native 0.015 secs

Eu costumava MSVC 2008 compilador SP1 para isso.

Podemos agora dizer adeus à série C-stlye? = P

Eu estava olhando para essa pergunta, porque eu tinha a mesma pergunta. Eu tinha algumas idéias para dar um teste mais rigoroso.

rodrigob apontou, há falhas na ordem circuito de tal forma que qualquer resultado no código que você originalmente ligados vai dar enganosa dados

Além disso, há bastante pequenas matrizes porte que estão sendo criados usando constantes. O compilador pode ser otimizar os loops, quando na realidade o compilador não vai saber o tamanho das matrizes. Os tamanhos das matrizes e número de iterações deve ser entradas de tempo de execução para o caso.

Em um Mac, o código a seguir está configurado para dar respostas mais significativas. Existem 4 testes aqui.

#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; }

Um com apenas uma única matriz dimensional usando o [] com matemática inteiro e um laço duplo

Um único com a mesma matriz dimensional usando ponteiro incrementado

Uma matriz multidimensional C

Um impulso multi_array

para executar a partir de uma linha de comando, execute

./test_array xsize ysize iterations"

e você pode ter uma boa idéia de como essas abordagens irá executar. Aqui está o que eu tenho com as bandeiras seguinte compilador:

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

Então, eu acho que é seguro dizer que o impulso realiza multi_array muito bom. Nada bate uma única avaliação loop, mas, dependendo da dimensão da matriz, o boost :: multi_array pode bater um c-array padrão com um duplo loop.

Outra coisa é tentar usar iteradores em vez de um índice direto para a matriz impulso.

Eu teria esperado multiarray ser tão eficiente. Mas eu estou obtendo resultados semelhantes em um PPC Mac usando gcc. Eu também tentei multiarrayref, de modo que ambas as versões estavam usando o mesmo armazenamento sem diferença. Isso é bom saber, desde que eu uso multiarray em alguns de meu código, e apenas assumiu que era semelhante ao de codificação mão.

Eu acho que sei qual é o problema ... talvez.

Para que a implementação impulso para ter uma sintaxe como: matriz [x] [y]. isso significa que a matriz [x] tem para retornar uma referência a um objeto que age como uma matriz 1D coluna , em que ponto de referência [y] dá-lhe o seu elemento.

O problema aqui é que você é a iteração em remar importante ordem (o que é típico em C / C ++ desde matrizes nativas são remar grande IIRC. O compilador tem de voltar a executar matriz [x] para cada y neste caso. Se você iteração de maior ordem da coluna ao usar a matriz de impulso, você pode ver um melhor desempenho.

Apenas uma teoria.

EDIT: no meu sistema linux (com algumas pequenas alterações) eu testei minha teoria, e mostrou alguns melhoria do desempenho por comutação x e y, mas ainda mais lento do que uma matriz nativa era. Esta poderia ser uma simples questão do compilador não ser capaz de otimizar longe o tipo de referência temporária.

Construir no modo de versão, uso objdump, e olhar para a montagem. Eles podem estar fazendo coisas completamente diferentes, e você será capaz de ver que otimizações do compilador está usando.

Uma pergunta semelhante foi feita e respondida aqui:

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

A resposta curta é que é mais fácil para o compilador para otimizar as matrizes simples, e não tão fácil de otimizar a versão Boost. Assim, um compilador particular pode não dar a versão impulso todos os mesmos benefícios de otimização.

compiladores também pode variar na forma como eles vão optimizar vs como conservadora que vai ser (por exemplo, com o código modelada ou outras complicações).

I testado em um Mac OS Snow Leopard usando 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

Aqui, é o código (modificado de forma que ele pode ser compilado em 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; }

Olhando para o conjunto gerado pelo g ++ 4.8.2 com -O3 -DBOOST_DISABLE_ASSERTS e usando tanto a operator() e as formas [][] para elementos de acesso, é evidente que a única operação adicional em comparação com as matrizes nativas e cálculo do índice manual é a adição da base. Eu não medir o custo deste embora.

Eu modifiquei o código acima no visual studio 2008 v9.0.21022 e aplicadas as rotinas recipiente das rotinas Receita numéricos para C e C ++

http://www.nrbook.com/nr3/ usando suas rotinas dmatrix licenciado e MatDoub respectivamente

dmatrix usa o fora da sintaxe da data operador malloc e não é recomendado ... MatDoub usa o comando Novo

A velocidade em segundos estão na versão de lançamento:

Boost: 0,437

Nativo: 0,032

Numerical Recipes C: 0,031

Numerical Recipes C ++: 0,031

Assim, a partir da aparência de blitz acima como a melhor alternativa livre.

Eu compilei o código (com ligeiras modificações) sob VC ++ 2010 com otimização ligado ( "maximizar a velocidade", juntamente com inlining "Quaisquer adequados" funções e "Favorecer o código rápido") e os tempos começaram 0,015 / 0,391. Eu gerado montagem listagem e, embora eu sou um noob montagem terrível, há uma linha dentro do ciclo de medição de impulso que não parece bom para mim:

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[]

Um dos operadores [] não se inline! O procedimento chamado faz uma outra chamada, desta vez para 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 *>

Ao todo, os dois procedimentos são bastante um monte de código para simplesmente acessar um único elemento na matriz. Minha impressão geral é que a biblioteca é tão complexo e de alto nível que Visual Studio é incapaz de otimizá-lo tanto quanto gostaríamos (cartazes usando gcc, aparentemente, tem melhores resultados).

IMHO, um bom compilador deveria ter embutido e otimizado os dois procedimentos - ambos são bastante curto e direto, não contêm qualquer lote laços etc. Um de tempo pode ser desperdiçado simplesmente em passar seus argumentos e resultados.

Como respondida por rodrigob, ativando a otimização adequada (padrão do GCC é -O0) é a chave para obter um bom desempenho. Além disso, também testado com chama DynamicMatrix , que produziu um adicional melhoria de desempenho fator 2 com exatamente as mesmas opções de otimização. https://bitbucket.org/account/user/blaze-lib/projects/ BLAZE

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow