design high-performance 3d dynamic array

Question

4.00/5 (1 vote)

See more:

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. Therefore, I designed my own array class, the fragment of which
is as follows:

template<class T>
class array
{
public:
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];

for (size_t i=0;i!=d1;++i)
for (size_t j=0;j!=d2;++j)
for (size_t k=0;k!=d3;++k)
p[i][j][k]=T();
}

public:
T& operator()(size_t d1,size_t d2,size_t d3)
{
return p[d1][d2][d3];
}
private:
T ***p;
};

However, since I have to read and write the array elements for more
than ten million times in the computation, the overloaded parentheses
will decrease the efficiency dramatically. To improve the performance,
one way is to make T ***p public and using array.p[i][j][k] to
read/write data. However, I think this design is hideous.

So, does anyone have a better idea to hide the internal pointer p from
users without decrease the efficiency? Or, does anyone have a complete
new idea of a high-performance three-dimensional dynamic array?

Thanks in advance!

Posted 27-Feb-10 20:46pm

endring

Add a Solution

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

AspDotNetDev · Answer 1 · 2010-02-28T03:30:00

Like the other answer mentions, you can use pointer arithmetic with a single-dimension array to simulate a three-dimensional array. Just thought I'd add that the performance of indexing that array can be improved. Rather than using multiplication to calculate the index, you can store pre-calculated values for offsets into each dimension for a given index. Effectively, you are storing the result of multiplications. You would create these offset arrays when the 3-D array gets allocated or resized. To get the pointer offset, you'd do something like this:

C++

int offset = zOffset[z] + yOffset[y] + x;

Those arrays would be filled using code that would go something like this:

C++

for(int i = 0; i < yMax; i++)
{
    yOffset[i] = i * xMax;
}
int xyMax = xMax * yMax;
for(int i = 0; i < zMax; i++)
{
    zOffset[i] = i * xyMax;
}

That way, you perform an array lookup rather than a multiplication. Whether or not this is faster than a multiplication depends on if the specific computer can do array lookups or multiplications faster.

AspDotNetDev · Answer 2 · 2010-02-28T00:59:00

Solution 1

You could make the operator() an inline function.

Posted 28-Feb-10 0:59am

AspDotNetDev

Avi Berger · Answer 3 · 2010-02-28T03:04:00

The overloaded operator() is likely to be expanded in-line, so it may not be the performance issue you believe. Have you checked on this?

To be a devil's advocate, the array.p[i][j][k] approach has the advantage of letting you write with array syntax rather than function syntax. Also instead of making your internal pointer public, you should provide an inline getter that would return a T*** const, so the outside code couldn't actually alter your pointer.

My thought is to do this "old style". It should be close to what the compiler would produce for a built-in 3d array. You could also choose between column major and row major order, which might make a difference in some situations.

Your fragment would be revised like so:

template<class T>
class array
{
public:
    array( size_t d1, size_t d2, size_t d3) : d1_(d1), d2_(d2), d3_(d3)
    {
        p = new T[ d1 * d2 * d3 ];
    }
public:
    T& operator()( size_t x, size_t y, size_t z )
    {
        return p + (( x * d2_ + y ) * d3_ + z );
        //return p + ( x + d1_ * ( y + z * d2_ )); // alternative
    }

private:
    T *p;
    size_t d1_;
    size_t d2_;
    size_t d3_;
};

Addendum:

Applying table lookup here never occurred to me. Thank you for the idea, aspdotnetdev.

Note that an array lookup might typically be implemented as a multiply and an add. I count 3 multiplies and 3 adds for a 3-d array indexing operation whether it is the OP's, aspdotnetdev's, or my approach. However, depending on the size of T, one of those might very well be replaceable by a bit shift in each of those approaches. In addition, the other 2 multiplies could also be turned into shifts for either the OP's or aspdotnetdev's suggestion, but not mine. So for array index calculations my suggestion is the loser when bit shifts are faster than multiplies.

On the other hand, for locality of reference, I believe that mine is best and the OP's the worst. This can have a significant impact, but depends on the platform and how things are used. The only way to determine that would be by measuring actual performance.

Maybe it is time to do some profiling?

design high-performance 3d dynamic array

3 solutions

Solution 3

Solution 1

Solution 2

Add your solution here

Preview 0