Re: N-Dimensional array library submission...

From: rwgk (rwgk_at_[hidden])
Date: 2001-12-28 07:41:09

Attached is a modified version of multiarray.cpp and results
with the following compilers:

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)

multiarray.cpp includes an additional test:

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++;
  //...
}

This performs consistently better than the test that is advertised
so prominently in the multi_array documentation. However, in general
there is still a significant abstraction penalty.

The multi_array interface is very appealing. However, I believe that
acceptance in the general community will also depend to a large degree
on performance considerations. I am wondering if there aren't ways of
making it easier for the compilers to generate faster code.  One idea
would be to provide optional fast access methods for special but
common cases.

Included in the modified multiarray.cpp is a template c_index_1d that
generates the code for converting n-dim indices to a 1-d index, given 
0
bases, and strides 1. This performs consistently better than
multi_array::operator(). Visual C++ removes the (remaining) 
abstraction
penalty entirely. Could specialized access methods like this be
integrated into the library?

Ralf

        cl.exe /nologo /MD /GR /GX /Zm350 /O2 -I"r:\boost" -c 
multiarray.cpp multiarray.cpp
        link.exe /nologo /incremental:no 
multiarray.obj /out:multiarray.exe 

C:\home\rwgk\py211\vc60\cctbx\dev>multiarray
3D C array : 0.156
3D multiarray : 1.594
3D multiarray collection: 0.406
3D multiarray c_index_1d: 0.156
3D C array : 0.156
3D multiarray : 1.578
3D multiarray collection: 0.407
3D multiarray c_index_1d: 0.156
1D C array : 0.312
1D multiarray : 0.266
1D C array : 0.14
1D multiarray : 0.25

        mwcc  -gccinc -prefix UseDLLPrefix.h -warn off -O  -
I"r:\boost" -c multiarray.cpp
        mwld  multiarray.obj -o multiarray.exe 

C:\home\rwgk\py211\cw70\cctbx\dev>multiarray
3D C array : 0.234
3D multiarray : 1.844
3D multiarray collection: 0.844
3D multiarray c_index_1d: 0.562
3D C array : 0.235
3D multiarray : 1.812
3D multiarray collection: 0.875
3D multiarray c_index_1d: 0.547
1D C array : 0.719
1D multiarray : 0.484
1D C array : 0.157
1D multiarray : 0.484

g++  -fPIC -ftemplate-depth-50  -O2 -I"/net/cci/rwgk/boost" -c 
multiarray.cpp
g++  multiarray.o -o multiarray -lm
% multiarray
3D C array : 0.17
3D multiarray : 1.02
3D multiarray collection: 0.68
3D multiarray c_index_1d: 0.44
3D C array : 0.16
3D multiarray : 1.01
3D multiarray collection: 0.59
3D multiarray c_index_1d: 0.44
1D C array : 0.63
1D multiarray : 0.2
1D C array : 0.17
1D multiarray : 0.2

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.483314
3D multiarray : 7.19971
3D multiarray collection: 0.899964
3D multiarray c_index_1d: 0.816634
3D C array : 0.483314
3D multiarray : 7.24971
3D multiarray collection: 0.899964
3D multiarray c_index_1d: 0.8333
1D C array : 1.28328
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.39
3D multiarray : 7.66
3D multiarray collection: 4.15
3D multiarray c_index_1d: 3.35
3D C array : 2.32
3D multiarray : 7.68
3D multiarray collection: 4.15
3D multiarray c_index_1d: 3.25
1D C array : 5.57
1D multiarray : 2.88
1D C array : 2.42
1D multiarray : 2.88

#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>
  std::size_t operator()(const ExtendArrayType& e, const 
IndexArrayType& i) {
    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>
  std::size_t operator()(const ExtendArrayType& e, const 
IndexArrayType& i) {
    return i[0];
  }
};

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) {
// Assign values to the elements
int values = 0;
MultiArray3D::index i, j, k;
for(i = 0; i != size; ++i)
for(j = 0; j != size; ++j)
for(k = 0; k != size; ++k)
A[i][j][k] = values++;

// Verify values
int verify = 0;
for(i = 0; i != size; ++i)
for(j = 0; j != size; ++j)
for(k = 0; k != size; ++k)
assert(A[i][j][k] == 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* d = A.data();
// 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)
{
// Assign values to the elements
int values = 0;
int i, j, k;
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++;

// Verify values
int verify = 0;
for(i = 0; i != size; ++i)
for(j = 0; j != size; ++j)
for(k = 0; k != size; ++k)
assert( A[(((i*size)+j)*size)+k] == 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 );

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;

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