What is the best way to create multi-dimensional array?

Question

I have a really very basic doubt regarding STL containers. My requirement is that i want to store double values in the form of multi-dimensional array. I will be performing various algebraic operations directly on them i.e.

myvector[4] = myvector[3] - 2 * myvector[2];

for this I am itterating using for loops & using the [] operator. I am not using STL itterator's. I found 2 basic approaches here. I prefer speed over memory efficiency. Since I am accessing these variables frequently I think vector would be slow for me. So what is your humble opinion on this matter? I know that the answers would be based on your previous experience, that is why I am asking this question. I am sorry if this question is too basic to be discussed here.

`Since I am accessing these variables frequently I think vector would be slow for me.` Why's that? BTW this is not a "forum". — Lightness Races in Orbit, Nov 04 '12 at 13:13
I am storing the values in the array in a method. Then I am accessing those values many times in other methods by use of pointers. — Cool_Coder, Nov 04 '12 at 13:15
Sorry but I can't come up with an answer from you as all this is too vague. Try to come up with a more concrete problem description. — Lightness Races in Orbit, Nov 04 '12 at 13:30

Synxis · Accepted Answer · 2012-11-04T17:13:45.140

The link you gave listed 2 methods, which creates "real" 2d arrays. In general, 2d arrays are not that efficient, because they require a lot of allocations. Instead, you can use a faked 2d array:

// Array of length L and width W
type* array1 = new type[L * W]; // raw pointers
std::vector<type> array2(L * W); // STL Vector

// Accessing a value. You have to use a convention for indices, and follow it.
// Here the convention is: lines are contiguous (index = x + y * W)
type value = array[x + y * W]; // raw pointer array & vector

Here is a simple benchmark (windows only, except if you change the timer part):

#include <vector>
#include <ctime>
#include <iostream>
#include <stdlib.h>

#include <Windows.h>
typedef LARGE_INTEGER clock_int;

void start_timer(clock_int& v)
{
    QueryPerformanceCounter(&v);
}

void end_timer(clock_int v, const char* str)
{
    clock_int e;
    QueryPerformanceCounter(&e);
    clock_int freq;
    QueryPerformanceFrequency(&freq);
    std::cout << str << 1000.0 * ((double)(e.QuadPart-v.QuadPart) / freq.QuadPart) << " ms\n";
}

void test_2d_vector(unsigned int w, unsigned int h)
{
    std::vector<std::vector<double> > a;
    a.resize(h);
    for(unsigned int t = 0; t < h; t++)
        a[t].resize(w);

    clock_int clock;
    start_timer(clock);
    // Benchmark random write access
    for(unsigned int t = 0; t < w * h; t++)
        a[rand() % h][rand() % w] = 0.0f;
    end_timer(clock,"[2D] Random write (STL) : ");

    start_timer(clock);
    // Benchmark contiguous write access
    for(unsigned int y = 0; y < h; y++)
        for(unsigned int x = 0; x < w; x++)
            a[y][x] = 0.0f;
    end_timer(clock,"[2D] Contiguous write (STL) : ");
}

void test_2d_raw(unsigned int w, unsigned int h)
{
    double** a = new double*[h];
    for(unsigned int t = 0; t < h; t++)
        a[t] = new double[w];

    clock_int clock;
    start_timer(clock);
    // Benchmark random write access
    for(unsigned int t = 0; t < w * h; t++)
        a[rand() % h][rand() % w] = 0.0f;
    end_timer(clock,"[2D] Random write (RAW) : ");

    start_timer(clock);
    // Benchmark contiguous write access
    for(unsigned int y = 0; y < h; y++)
        for(unsigned int x = 0; x < w; x++)
            a[y][x] = 0.0f;
    end_timer(clock,"[2D] Contiguous write (RAW) : ");
}

void test_1d_raw(unsigned int w, unsigned int h)
{
    double* a = new double[h * w];

    clock_int clock;
    start_timer(clock);
    // Benchmark random write access
    for(unsigned int t = 0; t < w * h; t++)
        a[(rand() % h) * w + (rand() % w)] = 0.0f;
    end_timer(clock,"[1D] Random write (RAW) : ");

    start_timer(clock);
    // Benchmark contiguous write access
    for(unsigned int y = 0; y < h; y++)
        for(unsigned int x = 0; x < w; x++)
            a[x + y * w] = 0.0f;
    end_timer(clock,"[1D] Contiguous write (RAW) : ");
}

void test_1d_vector(unsigned int w, unsigned int h)
{
    std::vector<double> a(h * w);

    clock_int clock;
    start_timer(clock);
    // Benchmark random write access
    for(unsigned int t = 0; t < w * h; t++)
        a[(rand() % h) * w + (rand() % w)] = 0.0f;
    end_timer(clock,"[1D] Random write (STL) : ");

    start_timer(clock);
    // Benchmark contiguous write access
    for(unsigned int y = 0; y < h; y++)
        for(unsigned int x = 0; x < w; x++)
            a[x + y * w] = 0.0f;
    end_timer(clock,"[1D] Contiguous write (STL) : ");
}

int main()
{
    int w=1000,h=1000;
    test_2d_vector(w,h);
    test_2d_raw(w,h);
    test_1d_vector(w,h);
    test_1d_raw(w,h);
    system("pause");
    return 0;
}

Compiled with msvc2010, release /Ox /Ot, it outputs for me (Win7 x64, Intel Core i7 2600K):

[2D] Random write (STL) : 32.3436 ms
[2D] Contiguous write (STL) : 0.480035 ms
[2D] Random write (RAW) : 32.3477 ms
[2D] Contiguous write (RAW) : 0.688771 ms
[1D] Random write (STL) : 32.1296 ms
[1D] Contiguous write (STL) : 0.23534 ms
[1D] Random write (RAW) : 32.883 ms
[1D] Contiguous write (RAW) : 0.220138 ms

You can see the STL is equivalent to raw pointers. But 1D is much faster than 2D.

i thought of this method previously. but the problem with this method is that for accessing every single element, there should be some calculation to identify the memory location. in my case handling 20 x 20 arrays repetitively would be a cause of concern for speed. that is why it is best to access using the [] operator. — Cool_Coder, Nov 04 '12 at 13:41
I don't think this will really impact your performances if you design your loops properly (first on `y`, then on `x`, according to my answer). The better thing to do is to benchmark those 3 methods. — Synxis, Nov 04 '12 at 13:44
Such difference between RAW and STL feels extremely wrong, since in my experience accessing elements of an `std::vector` is *exactly* as fast as accessing those of a raw array... did you enable the optimizations? — Matteo Italia, Nov 04 '12 at 14:26
This is one interesting benchmark. I compiled it on a unix machine and got similar results to what Synxis reported. I tend to avoid STL for various reasons, but put it through a profiler and it seems to spend a lot of time in call std::vector — camelccc, Nov 04 '12 at 15:13
Actually I re-run the tests on my Linux machine (compiling with -O3, with bigger arrays and repeating each benchmark twice to avoid cache effects) and I got almost the same results for STL and RAW (actually, STL was slightly faster). http://pastebin.com/nybcmakB — Matteo Italia, Nov 04 '12 at 15:47
@Synxis hey i just noticed that you edited your answer. Man thats exactly what i wanted to know!!! Thanks a lot! :) — Cool_Coder, Nov 04 '12 at 16:56
@MatteoItalia hey you are contradicting synxis's claim! Whom should i trust? — Cool_Coder, Nov 04 '12 at 16:59
@Synxis what would you like to comment regarding matteo's claim? — Cool_Coder, Nov 04 '12 at 17:00
@CAD_coding: perform the benchmark on your machine (*enabling the optimizations*) and check it by yourself. Notice that I'm not advocating about the "fake 2D array" (it's actually the fastest way), I'm only saying that using "raw arrays" instead as `std::vector` as backing storage gives no performance advantage. — Matteo Italia, Nov 04 '12 at 17:09
My bad, it was on debug... I've re-run this in release, and edited the results. Yes, I expect the STL to be almost as fast as raw pointers. There might be a small overhead for the stl, depending on the compiler and optimizations it can make. But stl code can be much easier to manipulate. — Synxis, Nov 04 '12 at 17:15
found something over here : http://stackoverflow.com/questions/2740020/c-stl-array-vs-vector-raw-element-accessing-performance — Cool_Coder, Nov 04 '12 at 17:35

What is the best way to create multi-dimensional array?

1 Answers1