Boost logo

Boost :

Date view Thread view Subject view Author view

From: rwgk (rwgk_at_[hidden])
Date: 2002-01-03 17:01:12

When looking at the performance test code again it stood out to me
that the C array test is very unrealistic because the compiler
knows that size is a constant:

for(i = 0; i != size; ++i)
for(j = 0; j != size; ++j)
for(k = 0; k != size; ++k)
A[(((i*size)+j)*size)+k] = values++;

I changed the code such that all tests use the same loop of the
form:

for(i[0] = 0; i[0] != size; ++i[0])
for(i[1] = 0; i[1] != size; ++i[1])
for(i[2] = 0; i[2] != size; ++i[2])
A[(((i[0]*e[1])+i[1])*e[2])+i[2]] = values++;

With:

boost::array<MultiArray3D::index,3> e = {size,size,size};
boost::array<MultiArray3D::index,3> i;

This makes a big difference. The new results are attached.

My conclusions:

  - Overall the multi_array performance using A()-style indexing
    compares well with direct access to a C array.

  - In general performance could be improved somewhat by using the
    c_index_1d template trick. (I figure that the multi_array
    interface would not change if this trick would be integrated.)

  - In the documentation it should be made absolutely clear that
    the A()-style indexing is in general much more efficient than
    the A[]-style indexing.

Ralf

Note another difference to the previously posted test code:
There are full specializations for c_index_1d<2> and c_index_1d<3>.
The results below are shown for
1. without these specializations,
2. with SPECIALIZED_C_INDEX_1D defined.
With some compilers it is better to provide the specializations.
With others it does not make a difference.

Compilers used:

Visual C++ 6.0 (probably Service Pack 5)
Win32 CodeWarrior 7.0
gcc 3.0.2 under RedHat 7.1 (Intel Xeon)
Compaq cxx (EDG 2.40) (Tru64 Unix, Alpha chip)
IRIX CC (EDG 2.38) (MIPS R5000 chip)

cl.exe /nologo /MD /GR /GX /Zm350 /O2 -I"r:\boost" -c multiarray.cpp
link.exe /nologo /incremental:no multiarray.obj /out:multiarray.exe
multiarray
3D C array : 0.171
3D multiarray : 1.704
3D multiarray collection: 0.421
3D multiarray c_index_1d: 0.141
3D C array : 0.156
3D multiarray : 1.719
3D multiarray collection: 0.406
3D multiarray c_index_1d: 0.157
1D C array : 0.313
1D multiarray : 0.265
1D C array : 0.157
1D multiarray : 0.25
cl.exe /nologo /MD /GR /GX /Zm350 /O2 -I"r:\boost" /D
SPECIALIZED_C_INDEX_1D -c multiarray.cpp
link.exe /nologo /incremental:no multiarray.obj /out:multiarray.exe
multiarray
3D C array : 0.171
3D multiarray : 1.704
3D multiarray collection: 0.421
3D multiarray c_index_1d: 0.141
3D C array : 0.156
3D multiarray : 1.719
3D multiarray collection: 0.406
3D multiarray c_index_1d: 0.157
1D C array : 0.313
1D multiarray : 0.265
1D C array : 0.157
1D multiarray : 0.25

mwcc -gccinc -prefix UseDLLPrefix.h -warn off -O -I"r:\boost" -c
multiarray.cpp
mwld multiarray.obj -o multiarray.exe
multiarray
3D C array : 0.422
3D multiarray : 1.859
3D multiarray collection: 0.907
3D multiarray c_index_1d: 0.578
3D C array : 0.406
3D multiarray : 1.859
3D multiarray collection: 0.844
3D multiarray c_index_1d: 0.547
1D C array : 0.719
1D multiarray : 0.5
1D C array : 0.156
1D multiarray : 0.5
mwcc -gccinc -prefix UseDLLPrefix.h -warn off -O -I"r:\boost" -
DSPECIALIZED_C_INDEX_1D -c multiarray.cpp
mwld multiarray.obj -o multiarray.exe
multiarray
3D C array : 0.422
3D multiarray : 1.875
3D multiarray collection: 0.843
3D multiarray c_index_1d: 0.438
3D C array : 0.406
3D multiarray : 1.875
3D multiarray collection: 0.859
3D multiarray c_index_1d: 0.422
1D C array : 0.594
1D multiarray : 0.5
1D C array : 0.156
1D multiarray : 0.5

g++ -fPIC -ftemplate-depth-50 -O2 -I"/net/cci/rwgk/cctbx" -
I"/net/cci/rwgk/boost" -I/usr/local_cci/Python-
2.1.1/include/python2.1 -c multiarray.cpp
g++ multiarray.o -o multiarray -lm
multiarray
3D C array : 0.43
3D multiarray : 1.04
3D multiarray collection: 0.74
3D multiarray c_index_1d: 0.44
3D C array : 0.41
3D multiarray : 1.04
3D multiarray collection: 0.61
3D multiarray c_index_1d: 0.43
1D C array : 0.6
1D multiarray : 0.21
1D C array : 0.15
1D multiarray : 0.2
g++ -fPIC -ftemplate-depth-50 -O2 -I"/net/cci/rwgk/cctbx" -
I"/net/cci/rwgk/boost" -I/usr/local_cci/Python-
2.1.1/include/python2.1 -DSPECIALIZED_C_INDEX_1D -c multiarray.cpp
g++ multiarray.o -o multiarray -lm
multiarray
3D C array : 0.43
3D multiarray : 1.05
3D multiarray collection: 0.7
3D multiarray c_index_1d: 0.42
3D C array : 0.41
3D multiarray : 1.04
3D multiarray collection: 0.67
3D multiarray c_index_1d: 0.41
1D C array : 0.62
1D multiarray : 0.21
1D C array : 0.17
1D multiarray : 0.19

cxx -I"/net/cci/rwgk/boost"/boost/compatibility/cpp_c_headers -std
strict_ansi -msg_display_number -msg_disable 186,450,1115 -O3 -
I"/net/cci/rwgk/boost" -c multiarray.cpp
cxx multiarray.o -o multiarray -lm
multiarray
3D C array : 0.966628
3D multiarray : 7.04972
3D multiarray collection: 0.899964
3D multiarray c_index_1d: 0.799968
3D C array : 0.949962
3D multiarray : 7.08305
3D multiarray collection: 0.899964
3D multiarray c_index_1d: 0.816634
1D C array : 1.26662
1D multiarray : 0.949962
1D C array : 0.466648
1D multiarray : 0.949962
cxx -I"/net/cci/rwgk/boost"/boost/compatibility/cpp_c_headers -std
strict_ansi -msg_display_number -msg_disable 186,450,1115 -O3 -
I"/net/cci/rwgk/boost" -DSPECIALIZED_C_INDEX_1D -c multiarray.cpp
cxx multiarray.o -o multiarray -lm
multiarray
3D C array : 0.966628
3D multiarray : 7.08305
3D multiarray collection: 0.883298
3D multiarray c_index_1d: 0.933296
3D C array : 0.966628
3D multiarray : 7.08305
3D multiarray collection: 0.899964
3D multiarray c_index_1d: 0.933296
1D C array : 1.38328
1D multiarray : 0.966628
1D C array : 0.449982
1D multiarray : 0.966628

CC -LANG:std -n32 -mips4 -
I"/net/cci/rwgk/boost"/boost/compatibility/cpp_c_headers -woff
1001,1234,1682 -O2 -I"/net/cci/rwgk/boost" -c multiarray.cpp
CC -LANG:std -n32 -mips4 -LD_MSG:off=15,84 multiarray.o -o
multiarray -lm
multiarray
3D C array : 2.58
3D multiarray : 8.15
3D multiarray collection: 4.15
3D multiarray c_index_1d: 3.26
3D C array : 2.6
3D multiarray : 8.06
3D multiarray collection: 4.15
3D multiarray c_index_1d: 3.26
1D C array : 5.67
1D multiarray : 2.88
1D C array : 2.32
1D multiarray : 2.89
CC -LANG:std -n32 -mips4 -
I"/net/cci/rwgk/boost"/boost/compatibility/cpp_c_headers -woff
1001,1234,1682 -O2 -I"/net/cci/rwgk/boost" -DSPECIALIZED_C_INDEX_1D -
c multiarray.cpp
CC -LANG:std -n32 -mips4 -LD_MSG:off=15,84 multiarray.o -o
multiarray -lm
multiarray 3D C array : 2.57
3D multiarray : 8.14
3D multiarray collection: 4.15
3D multiarray c_index_1d: 2.93
3D C array : 2.6
3D multiarray : 8.06
3D multiarray collection: 4.15
3D multiarray c_index_1d: 2.93
1D C array : 5.25
1D multiarray : 2.89
1D C array : 2.32
1D multiarray : 2.89

#include <boost/multi_array.hpp>
#include <boost/timer.hpp>
#include <iostream>
#include <cassert>

template <std::size_t N>
struct c_index_1d {
  template <typename ExtendArrayType, typename IndexArrayType>
  inline
  std::size_t operator()(const ExtendArrayType& e, const
IndexArrayType& i) const {
    return c_index_1d<N-1>()(e, i) * e[N-1] + i[N-1];
  }
};

template<>
struct c_index_1d<1> {
  template <typename ExtendArrayType, typename IndexArrayType>
  inline
  std::size_t operator()(const ExtendArrayType& e, const
IndexArrayType& i) const {
    return i[0];
  }
};

#ifdef SPECIALIZED_C_INDEX_1D

template<>
struct c_index_1d<3> {
  template <typename ExtendArrayType, typename IndexArrayType>
  inline
  std::size_t operator()(const ExtendArrayType& e, const
IndexArrayType& i) const {
    return (i[0] * e[1] + i[1]) * e[2] + i[2];
  }
};

template<>
struct c_index_1d<2> {
  template <typename ExtendArrayType, typename IndexArrayType>
  inline
  std::size_t operator()(const ExtendArrayType& e, const
IndexArrayType& i) const {
    return i[0] * e[1] + i[1];
  }
};

#endif // SPECIALIZED_C_INDEX_1D

static const int size = 100;
static const int total_1D_size = size*size*size;

typedef boost::multi_array<double, 1> MultiArray1D;
typedef boost::multi_array<double, 3> MultiArray3D;

int multiarray_1D(MultiArray1D& A) {

// Assign values to the elements
int values = 0;
MultiArray1D::index i;
for(i = 0; i != total_1D_size; ++i) A[i] = values++;

int verify = 0;
for(i = 0; i != total_1D_size; ++i) assert(A[i] == verify++);

return 0;
}

int carray_1D(double* A)
{
// Assign values to the elements
int values = 0;
int i;
for(i = 0; i != total_1D_size; ++i) A[i] = values++;

// Verify values
int verify = 0;
for(i = 0; i != total_1D_size; ++i) assert( A[i] == verify++ );

return 0;
}

int multiarray_3D (MultiArray3D& A) {
boost::array<MultiArray3D::index,3> i;
// Assign values to the elements
int values = 0;
for(i[0] = 0; i[0] != size; ++i[0])
for(i[1] = 0; i[1] != size; ++i[1])
for(i[2] = 0; i[2] != size; ++i[2])
A[i[0]][i[1]][i[2]] = values++;

// Verify values
int verify = 0;
for(i[0] = 0; i[0] != size; ++i[0])
for(i[1] = 0; i[1] != size; ++i[1])
for(i[2] = 0; i[2] != size; ++i[2])
assert(A[i[0]][i[1]][i[2]] == verify++);

return 0;
}

int multiarray_3D_collection (MultiArray3D& A) {
boost::array<MultiArray3D::index,3> i;
// Assign values to the elements
int values = 0;
for(i[0] = 0; i[0] != size; ++i[0])
for(i[1] = 0; i[1] != size; ++i[1])
for(i[2] = 0; i[2] != size; ++i[2])
A(i) = values++;

// Verify values
int verify = 0;
for(i[0] = 0; i[0] != size; ++i[0])
for(i[1] = 0; i[1] != size; ++i[1])
for(i[2] = 0; i[2] != size; ++i[2])
assert(A(i) == verify++);

return 0;
}

int multiarray_3D_c_index_1d (MultiArray3D& A) {
boost::array<MultiArray3D::index,3> e = {size,size,size};
boost::array<MultiArray3D::index,3> i;
c_index_1d<3> i1d;
MultiArray3D::element* dd = A.data();
double* d = dd;
// Assign values to the elements
int values = 0;
for(i[0] = 0; i[0] != size; ++i[0])
for(i[1] = 0; i[1] != size; ++i[1])
for(i[2] = 0; i[2] != size; ++i[2])
d[i1d(e, i)] = values++;

// Verify values
int verify = 0;
for(i[0] = 0; i[0] != size; ++i[0])
for(i[1] = 0; i[1] != size; ++i[1])
for(i[2] = 0; i[2] != size; ++i[2])
assert(d[i1d(e, i)] == verify++);

return 0;
}

int carray_3D(double* A)
{
boost::array<MultiArray3D::index,3> e = {size,size,size};
boost::array<MultiArray3D::index,3> i;
// Assign values to the elements
int values = 0;
for(i[0] = 0; i[0] != size; ++i[0])
for(i[1] = 0; i[1] != size; ++i[1])
for(i[2] = 0; i[2] != size; ++i[2])
A[(((i[0]*e[1])+i[1])*e[2])+i[2]] = values++;

// Verify values
int verify = 0;
for(i[0] = 0; i[0] != size; ++i[0])
for(i[1] = 0; i[1] != size; ++i[1])
for(i[2] = 0; i[2] != size; ++i[2])
assert( A[(((i[0]*e[1])+i[1])*e[2])+i[2]] == verify++ );

return 0;
}

int main()
{
boost::timer t;

{ // 3D tests
MultiArray3D multiarray(boost::extents[size][size][size]);
double* carray = new double[size*size*size];
assert( carray != 0 );

for (int pass=0;pass<2;pass++) {

int i;
t.restart();
for(i = 0; i < 10 ; ++i ) carray_3D(carray);
std::cout << "3D C array : " << t.elapsed() << std::endl;

t.restart();
for(i = 0; i < 10 ; ++i ) multiarray_3D(multiarray);
std::cout << "3D multiarray : " << t.elapsed() << std::endl;

t.restart();
for(i = 0; i < 10 ; ++i ) multiarray_3D_collection(multiarray);
std::cout << "3D multiarray collection: " << t.elapsed() << std::endl;

t.restart();
for(i = 0; i < 10 ; ++i ) multiarray_3D_c_index_1d(multiarray);
std::cout << "3D multiarray c_index_1d: " << t.elapsed() << std::endl;

}

delete carray;
}

{
MultiArray1D multiarray(boost::extents[total_1D_size]);
double* carray = new double[total_1D_size];

int i;
for(i = 0; i < 10 ; ++i ) carray_1D(carray);
std::cout << "1D C array : " << t.elapsed() << std::endl;

t.restart();
for(i = 0; i < 10 ; ++i ) multiarray_1D(multiarray);
std::cout << "1D multiarray : " << t.elapsed() << std::endl;

t.restart();
for(i = 0; i < 10 ; ++i ) carray_1D(carray);
std::cout << "1D C array : " << t.elapsed() << std::endl;

t.restart();
for(i = 0; i < 10 ; ++i ) multiarray_1D(multiarray);
std::cout << "1D multiarray : " << t.elapsed() << std::endl;

delete carray;
}

return 0;
}

Date view Thread view Subject view Author view

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk