Multi-dimensional dynamic array - performance

Hi everyone,

I am currently learning c++ (but having programmed in fortran 95 before, it is mostly a case of learning new syntax, and a few new concepts, in order to be familiar with the basics).

For the purposes of a large scientific code that I am preparing to write, I will need to create multi-dimensional arrays dynamically, since the array size in each dimension will be known only at run-time. I will need to create 3D, 6D and 7D arrays.

I have of course looked around a lot to find ways to do this, and have come up with the following (for a 3D array, but I can extend it to 6 and 7D easily):

Code:

---

#include <iostream>

using namespace std;

/* 3D ARRAY CLASS */

class array3d
{
public:
  void allocate(int nx,int ny,int nz); // Allocate the array
  double ***array; // The pointer to the array
};

void array3d::allocate(int nx,int ny,int nz) {


array = new double**[nx];

  for(int i=0;i<nx;i++) {

    array[i] = new double*[ny];
 
    for(int j=0;j<ny;j++) {
 
      array[i][j] = new double[nz];
 
    }

  }

}

/* MAIN PROGRAM */

int main() {

  array3d image;

  /* Allocate the array */

  image.allocate(100,100,100);

  /* Assign values to two elements as an example */

  image.array[33][34][32]=0.6;
  image.array[99][22][10]=0.8;
 
  cout<<image.array[33][34][32]<<endl;
  cout<<image.array[99][22][10]<<endl;


}

---

This way is certainly simple, and works fine. My question is whether this way is the recommended way to do this kind of thing, or whether it will have a very poor performance (since I don't have anything to compare to, I am clueless). Bear in mind that I need a method which works in 6 and 7 dimensions too.

I would welcome any advice as to whether this is good or bad code :-)

Thanks in advance for any help!

One crutial element that you're missing in your class, melkor, is deleting the allocated memory! Create a destructor where this is managed. It might also be worth doing the allocation in a constructor rather than having to call a specific method to do the allocation.
In terms of performance ... one could conceive of a vector of vectors of vectors etc (not mathematical vectors now but a C++ type), but that would be awkward and syntatically disgusting ...

Thanks for your comments!

I decided not to put the allocation inside the constructor, because I want to allocate the array separately from declaring it.

Regarding the destructor, I am wandering into unknown territory (I know what the destructor is, but am not sure how to do it in this case). Would the following be ok:

Code:

---

array3d::~array3d()
{
  for(int i=0;i<nx;i++) {
      for(int j=0;j<ny;j++) {
        array[i][j] = NULL
      }
    array[i] = NULL
  }
  array = NULL
}

---

or is this overkill? Maybe I only need the following?

Code:

---

array3d::~array3d()
{
  array = NULL
}

---

not forgetting semicolons in the above of course...

Well what you're doing there is simply assigning a value. You need to delete it:

for a 2d array:

Code:

---

array2d::~array2d {
  for ( int i=0; i<width; i++ ) {
    delete []mem[i];
  }

  delete []mem;
}

---

where mem is your array.
Here's a 3d-version:

Code:

---

array3d::~array3d {
  for ( int j=0; j<height; j++ ) {
    for ( int i=0; i<width; i++ ) {
      delete []mem[j][i];
    }
    delete []mem[j];
  }
  delete []mem;
}

---

Ok, thanks!

So say that we didn't care about code aesthetics (although I do in reality!), and wrote this using vectors of vectors of vectors etc. as you suggested, what kind of speed gain are we talking about here. Orders of magnitude?

In earnest I don't know. The thing about vectors is that their dimensions are variable. You can set the size (my using one if its public methods). Is speed really that much an issue? The speed difference isn't going to be in the orders of magnitude. I don't think vectors will be faster, will they?

Speed is an issue, but I would not sacrifice code simplicity for only say a factor of 2 or less improvement. And this method does seem pretty simple code-wise.

From what I've read about vectors, they seem overkill. I only need to allocate arrays once and for all, and I don't expect to have to change the size until I destroy them.

As long as this is good c++ code, then I might stick with the above method.

Thanks very much for all your advice :-)

A do it yourself array is going to be quicker than a vector, simply because there is absolutely no checking for doing dumb stuff (out of bound accesses say) with an array.

Though you might want to give vectors a shot first, and then check the performance you're getting. "premature optimisation disease" strikes frequently.

Also, there are far more efficient ways of allocating a 3D (or n-D) array, like so
http://cboard.cprogramming.com/showp...6&postcount=11
As well as taking many fewer alloc calls, you also benefit from improved cache performance since all the data for each dimension is in contiguous memory.

Writing code isn't a beauty contest. It might look ugly (seeing as you're just startin'), but it's probably the most direct way of doing it.

Quote:

---

Originally Posted by melkor445

I decided not to put the allocation inside the constructor, because I want to allocate the array separately from declaring it.

---

This decision is one of the most common mistakes by newbies. It offers the opportunity for the user of your class to forget to initialise it (i.e. create the array), and then to use it despite not having initialised it. For example;

Code:

---

int main()
{
    array2d  some_array;
 
    // lots of operations, including function calls but no attempt to initialise some_array

    do_something_that_assumes_some_array_is_initialised();  // crash and burn
}

---

With VERY few exceptions (and an array class is not one of those exceptions), initialising in the constructor should be viewed as mandatory, IMHO.

If you are worried about memory being allocated and wasted before it is needed, the user can take care of that. If initialisaion happens in a constructor, then all that is needed is to hold off on creating an object until it is needed. For example;

Code:

---

int main()
{

    // lots of operations, including function calls but no usage of some_array

    array2d some_array;    // we need some_array now
    do_something_that_assumes_some_array_is_initialised();  // all happy if array2d's constructor does the initialisation
}

---

> A do it yourself array is going to be quicker than a vector, simply because there is absolutely no checking for
> doing dumb stuff (out of bound accesses say) with an array.

If subscripting is done with [] instead of at(), there's no bounds checking with vectors either. A vector does need to do some extra work such as keep track of its size and capacity, but I doubt it's significant (and using reserve() can avoid reallocation if you have an upper bound for the required capacity). I recently rewrote some of my code which originally used dynamic arrays to use vectors instead. The size of the resulting executable increased slightly, which didn't surprise me, but its speed also increased slightly, which did (making sure to use optimization flags in compiling before and after). I suspect that since vectors automatically handle certain details which have to be dealt with by hand with dynamic arrays, it's easier for the compiler to know what's going on, and optimize accordingly.

Quote:

---

Originally Posted by robatino

I suspect that since vectors automatically handle certain details which have to be dealt with by hand with dynamic arrays, it's easier for the compiler to know what's going on, and optimize accordingly.

---

A std::vector is a type of "dynamic array". It is also one that is designed so it can be implemented in a reasonably efficient manner. The behaviour of templated classes, such as std::vector, can also be optimised by the compiler -- although the precise gains depend on quality of implementation of the compiler -- because the implementation of the template typically needs to be available to the compiler, at least by default. This is not necessarily true for non-templated classes when handled with separate compilation.

Quote:

---

Originally Posted by grumpy

This decision is one of the most common mistakes by newbies. It offers the opportunity for the user of your class to forget to initialise it (i.e. create the array), and then to use it despite not having initialised it.

---

For the purposes of my program, I require several 3D (and 6D) arrays to be globally accessible from a specific class, but I don't know what it's dimensions are until runtime. Once allocated I don't need to change their size (which is why I was suggesting that vectors might be overkill). So I need to declare them in the header of the class before I can allocate them. The two main cricisisms I've seen in your replies is:

• no bounds checking
• danger of using array before allocated

I've come up with the following class where you allocate using:

image.allocate(100,100,100);

and get and put values using

cout<<image.put(23,22,13,0.2);
cout<<image.get(23,22,13);

Once whatever code I am writign is tested and I know there are no out of bounds problems I can always substitute for a similar class without the bounds checking and see if I gain in performance.

Code:

---

#include <iostream>

using namespace std;

class array3d
{
public:

  void allocate(int nx,int ny,int nz);
  double get(int i,int j,int k);
  int put(int i,int j,int k,double value);
  array3d();
  ~array3d();

private:

  double ***array;  // The pointer to the array
  int nx,ny,nz;      // The dimensions of the array
  int allocated;  // Whether the array has been allocated

};

/* CONSTRUCTOR */

array3d::array3d() {
  allocated=0;
}

/* ALLOCATION FUNCTION */

void array3d::allocate(int a,int b,int c) {
  if(!allocated) {
    allocated=1;
    nx=a;
    ny=b;
    nz=c;
    array = new double**[nx];
    for(int i=0;i<nx;i++)
      {
        array[i] = new double*[ny];
        for(int j=0;j<ny;j++)
          {
            array[i][j] = new double[nz];
          }
      }
  } else {
    cout<<"ERROR: array already allocated"<<endl;
    abort();
  }
}

/* DESTRUCTOR */

array3d::~array3d() {
  for(int i=0;i<nx;i++) {
    for(int j=0;j<ny;j++) {
      delete []array[i][j];
    }
    delete []array[i];
  }
  delete []array;
}

/* GET VALUE */

double array3d::get(int i,int j,int k) {
  if(allocated) {
    if(i>=0 && i<=nx && j>=0 && j<=ny && k>=0 && k<=nz)
      {
        return array[i][j][k];
      }
    cout<<"ERROR: indices out of bounds"<<endl;
    abort();
  }
  cout<<"ERROR: array not allocated"<<endl;
  abort();
}

/* PUT VALUE */

int array3d::put(int i,int j,int k,double value) {
  if(allocated) {
    if(i>=0 && i<=nx && j>=0 && j<=ny && k>=0 && k<=nz)
      {
        array[i][j][k] = value;
        return 0;
      }
    cout<<"ERROR: indices out of bounds"<<endl;
    abort();
  }
  cout<<"ERROR: array not allocated"<<endl;
  abort();
}

---

Would the above be considered bad coding, or does it seem like a sensible approach to my problem?

Thanks!

Quote:

---

Originally Posted by melkor445

For the purposes of my program, I require several 3D (and 6D) arrays to be globally accessible from a specific class, but I don't know what it's dimensions are until runtime.

---

This is actually the requirement that I suggest you question most closely. Any need for any data to be globally available (from a class or otherwise) is often a sign of an incomplete design, or significant unnecessary dependencies in your design (and excessive dependencies make your code less efficient, harder to get working correctly -- in other words, you lose out in every respect). If that data that has to be globally available is large (and "several 3D and 6D arrays" will often qualify as large) then that requirement for the data to be globally available needs to be questioned closely.

For example, can your large body of data be created before any instances of your class, and passed as an argument to member functions? A helper class (a struct/class that contains your data) can be useful here: the most you need to pass to your class is a pointer or reference.

Quote:

---

Originally Posted by melkor445

Once allocated I don't need to change their size (which is why I was suggesting that vectors might be overkill).

---

Depends what you mean by overkill. Vectors behave reasonably efficiently if their size can be determined in advance and never needs to be changed after the vector is created: the reserving of space only happens once, which is exactly the same number of times it would need to be done with your hand-rolled class. The effort to use a vector will usually be less than is needed to create a class that creates a subset of the functions offered by a vector.

Quote:

---

Originally Posted by melkor445

So I need to declare them in the header of the class before I can allocate them.

---

As I said above, I would query the requirement for the data to be globally available; if you eliminate that, you can (potentially) eliminate the need for the data arrays to be declared in the header file and initialised (or allocated) later.

Quote:

---

Originally Posted by melkor445

The two main cricisisms I've seen in your replies is:

• no bounds checking
• danger of using array before allocated

---

Bounds checking can be avoided with the right design. Preventing a problem from occurring is more efficient than having to check if the problem has occurred multiple times.

For example, if you have a vector with three elements and indices in the range 0 to 2, ensuring that a loop over indexes for an array only runs from 0 to 2 rather than running -100 to 1000. That eliminates any need for a check when accessing particular array elements .... and will typically be most efficient.

The danger of using an array before it is allocated is a fundamental problem with your code. Particularly if (as happens) you reuse your class in another project, and forget to do the required initialisation. Of is someone comes along and modifies your code, and removes a couple of lines .... one of which, incidentally, is a call to a function that does the initialisation.

Quote:

---

Originally Posted by melkor445

Would the above be considered bad coding, or does it seem like a sensible approach to my problem?

---

Your code is not bad, if one accepts your design constraints. The problem is, your design constraints are, in practice, the cause of lots of real-world problems in terms of getting things working: either correctly or efficiently.

Ok, I think I see what you mean. Thinking about it I don't have a good reason for the arrays to be globally available. And I can easily know the size of the array I will require before the first instance of the class. I need to get into the c++ mindset :-)