Boost::multi_array 性能问题

StackOverflow https://stackoverflow.com/questions/446866

题

我试图使用以下测试程序来比较 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 对我来说似乎仍然很高。

好吧，没有明确的答案，但我将继续前进，暂时将我的真实代码保留在本机数组中。

接受Laserallan的答案，因为这是我测试中最大的缺陷。

谢谢大家。

有帮助吗？

解决方案

您正在构建发布版还是调试版？

如果在调试模式下运行，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 在 Ubuntu 10.10 上

所以结论是：

  • 和 适当的优化 boost::multi_array 按预期完成其工作
  • 您访问数据的顺序 确实很重要

你的测试有缺陷。

  • 在 DEBUG 构建中，boost::MultiArray 缺乏它迫切需要的优化过程。（比本机数组要多得多）
  • 在 RELEASE 版本中，您的编译器将查找可以完全删除的代码，并 你的大部分代码都属于该类别.

您可能看到的是优化编译器的结果，发现大多数或全部“本机数组”循环都可以被删除。理论上，boost::MultiArray 循环也是如此，但 MultiArray 可能足够复杂，足以击败您的优化器。

对您的测试平台进行这个小更改 你会看到更真实的结果：更改两次出现的“= 2.345 “ 和 ”*= 2.345 " 并通过优化再次编译。这将防止编译器发现每个测试的外循环是多余的。

我做到了，速度比较接近 2:1。

我想知道两件事情：

1）的边界检查： 定义之前，包括在应用程序multi_array.hpp的BOOST_DISABLE_ASSERTS预处理宏。这将关闭边界检查。不知道这是否是此时禁用NDEBUG是

2）基指数：  的MultiArray可以从从0不同碱基索引数组这意味着，的multi_array存储碱值（在每个维度中），并使用一个更复杂的公式，得到在存储器中的确切位置，我想知道如果它是所有关于这一点。

否则，我不理解为什么多阵列应该比C-阵列慢。

考虑使用闪电++代替。我尝试了闪电战，其性能堪与C数组！

看看下面加有闪电您的代码：

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

这里的结果在调试和释放。

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

我用MSVC此2008 SP1编译器。

我们能不能现在说再见C-stlye阵列？ = P

我正在看这个问题，因为我也有同样的问题。我有一些想法要进行更严格的测试。

  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. 升压多数组

所以从命令行运行，运行

./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，使两个版本采用无差异的同一存储。这是很好的了解，因为我在我的一些代码中使用多阵列，并且只是认为这是类似于手工编码。

我想我知道问题是什么？也许吧。

为了用于升压实施为具有语法，如：矩阵[X] [Y]。这意味着，矩阵[X]具有对参考返回到其作用像一维数组的对象的列，在该点参考[Y]向你元件。

这里的问题是，你是在的行主要顺序（迭代这是在C典型/ C ++，因为天然阵列行主要IIRC，编译器必须重新执行矩阵[X]为每个y在这种情况下，如果在使用升压矩阵时在列主顺序重复，可能会看到更好的性能。

只是一种理论。

编辑：在我的Linux系统（有一些小的变化）我测试我的理论，并没有示出的一些性能通过切换x和y，但它仍比天然阵列较慢的改善。这可能是不能够优化掉临时参照型编译器的一个简单的问题。

构建在释放模式中，使用objdump的，并期待在组件。他们可能会做完全不同的事情，你就可以看到编译器使用其优化。

有一个类似的问题被问和在这里找到答案：

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

简单的回答是，它是最简单的编译器优化简单阵列，以及不那么容易优化升压版本。因此，一个特定的编译器可能不会给升压版本的所有相同的优化的好处。

编译器也可以改变在他们如何将优化对他们将如何保守是（例如，与模板化代码或其他并发症）。

我使用gcc 4.2.1上的雪豹的Mac OS测试

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使用新的命令

以秒为单位的速度是在发布版本：

升压：0.437

本机：0.032

数字食谱C：0.031

数值食谱C ++：0.031

因此，从上述的突击看起来最好的自由选择。

我2010 VC ++下与导通优化编译的代码（略有修改）（“最大化速度”与内联在一起“的任何合适的”功能和“快，赞成代码”），并得到时间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）是获得良好性能的关键。此外，我还与布拉DynamicMatrix 测试，其产生的附加因素2完全相同的优化参数的性能提升。 https://bitbucket.org/account/user/blaze-lib/projects/ BLAZE

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top