design high-performance 3d dynamic array

[Paul McKenzie]

Hi, everyone:

I am working on a scientific computation program, which needs a very
high-performance three dimensional dynamic array. I tried
std::vector<vector<vector<T> > >, boost::multi_array and blitz::Array,
but the performance of all these libraries couldn't satisfy my
needs.

I didn't use any optimization of the compiler,

Well, that invalidates anything you've stated about things being "too slow" and having to write your own classes. C++ compiler optimizations can be very dramatic. For example, unoptimized code can run 5 to 10 times slower than optimized code when it comes to the Visual C++ compilers.

Also another thing is that the libraries you are saying are slow or not fast enough are created by some of the best C++ programmers in the business. Performance of these libraries is something that these programmers carefully consider, and attempt to accomplish. You need a compelling argument to really state you can do better than these people when it comes to building C++ classes and components.

Therefore, I designed my own array class, the fragment of which
is as follows:

The array class you defined is very simplistic, and not efficient. If your arrays are dynamic, but once created, stay the same size, then what you have written is slow in creation and destruction.

  array(size_t d1,size_t d2,size_t d3)
  {
    p=new T**[d1];
    for(size_t i=0;i!=d1;++i)
      p[i]=new T*[d2];
    for(size_t i=0;i!=d1;++i)
      for(size_t j=0;j!=d2;++j)
	p[i][j]=new T[d3];

You are calling the allocator multiple times in a loop. What if the array is 100x100x100? You are calling "new" thousands of times. That not only is slow, you are fragmenting memory.

You only need to call new 3 times regardless of the size of the dimensions. The first call to new allocates the d1 (which you did). The second call to new allocates all of the second dimension in a pool of pointers. The third call to new allocates the room for the data. Then the loops points the pointers in the right places.

The code below has not been tested, but hopefully I didn't make any mistakes.

     template <typename T>
     T*** Create3DArray(int nLayers, int nRows, int nCols)
     {
          T*** p = new T**[nLayers];
          T** p2 = new T*[nLayers * nRows];
          T* p3 = new T[nLayers * nRows * nCols];

          for (int i = 0; i < nLayers; ++i )
          {
              p[i] = p2 + i * nRows;
              for (int j = 0; j < nRows; ++j )
               p[i][j] = p3 + (i*nRows+j )* nCols;
          }
          return p;
      }
     
      template <typename T>
      void Free3DArray(T ***array)
      {
        delete[] array[0][0];
        delete[] array[0];
        delete[] array;
      }

     int main()
    {
          double ***d3 = Create3DArray<double>(100,100,100);
          d3[56][23][21] = 1234;
          Free3DArray<double>(d3);
     }

This same code calls "new" 3 times, compared to the thousands of times your code called "new". Also, the destruction isn't in a loop -- just three invocations of "delete[]" needs to be done.

Regards,

Paul McKenzie