Dynamically allocated 2 dimensional array

[recluse]

Is it possible to possible to use a dynamically allocated 2 dimensional array in C++. I'm having trouble finding info on how to do it. Or maybe I'm just using the wrong search terms.

[Strike]

Sure, just use a vector of vectors. STL is gooooooood.

[jamessan]

Or you can use the new operator and memset(). If you want to see an example, here's a link to a program I wrote that needed to do that. http://coderforums.net/showthread.ph...0865#post10865

[Pointy]

//char example

char** hello_jpg;

hello_jpg = new char*[x_dim];

for(int n=0;n<x_dim;n++)
{
    hello_jpg[n] = new char[ y_dim ];
}

I'd use vector of vectors though stl is good

[skidooer]

You can also use:

char *array = new char[x * y];  // equivalent to array[x][y]
char v = array[(x * i) + j)];   // equivalent to array[i][j]

[DrPizza]

No. C++ doesn't have arrays with more than one dimension.

It does have arrays of array and arrays of pointer, which can both be used to fabricate structures roughly equivalent to multidimensional arrays.

Arrays of array are limited as all but one of the dimensions must be fixed at compile-time. They are, however, efficient. A one-dimensional array takes a multiply, an add, and a dereference to access an element; a two dimensional array takes two multiplies, two adds, and a dereference, and so on, and so forth. They also require only a single allocation to be made.

Arrays of pointer are expensive; they require multiple allocations (probably one per dimension, minimum); they require multiple dereferences.

The latter problem is experienced by vectors of vectors -- the use of vectors eliminates the possibility to perform certain useful efficiency optimizations, which makes vectors of vectors slow.

Better, in general, is to create a one-dimensional array and wrap it in a class with an overloaded operator() to access elements.

[sedarious]

What benifits/loses (if any) are gained by coding a 2 dim. array in a single dimension?

char array1[x][y];
char array2[x*y];

The main benifit I see here is that array1 is easier to handle codewise (IMO). I would guess that the compiled code would be very similar for both cases as your code progessed further. Anyone know any specifics?

[DrPizza]

Originally posted by sedarious
What benifits/loses (if any) are gained by coding a 2 dim. array in a single dimension?

When the array's size is fixed at compile time, none. Element access ought to be identical; the single dimension will require one to manually determine the offset, the array of array will do it automagically.

The difference is when the size is determined at runtime. You can't do something like:

int i, j;
// get i and j
int** myArrayOfArray = new int[i][j];

Arrays of pointers can sort of simulate it, but then you need a separate dereference for every dimension.

A single array allows one to use only a single dereference.

[sedarious]

But a single array also requires an i,j multiplication - which isn't an speedy operation. You may have to wait a couple clocks for a reference return from memory or cache, but it takes many clocks for a multiplication. I would say on a cache efficient system, an array of ptrs would be faster than a 2-D array made 1-D.

[bwkaz]

Originally posted by sedarious
it takes many clocks for a multiplication.

Not with a decent compiler, if your row length is a power of two. Heck, even if it isn't.

If your row length is 64, then you don't have to multiply by 64, you can just shift left 6 bits, which had better only take one clock.

If your row length is 96, you can shift left 6, and shift left 5, and add them together (x*96 = x*(64+32) = x*64+x*32 = x<<6+x<<5), which is three clocks.

[DrPizza]

Originally posted by sedarious
But a single array also requires an i,j multiplication - which isn't an speedy operation. You may have to wait a couple clocks for a reference return from memory or cache, but it takes many clocks for a multiplication. I would say on a cache efficient system, an array of ptrs would be faster than a 2-D array made 1-D. [/b]

It's not faster on any system I've seen (in practice, there are no straight multiplies -- the multiply-adds are turned into leas) -- and waiting on memory takes more than "a couple clocks".

[sedarious]

edit: This is all a big edit. I was a bit brief before and decided to explain it better...

DrPizza:
I am pretty sure LEA only works with constants for that sort of multiplication (and I think they have to be 2,4,8 and maybe 16 - I can't find the info in any tech docs right now). Since, i and j are runtime dependant, they can't be utilized in an LEA multiplication scheme.

bwkaz:
For bit shift multiplication subsitutions, you need to know the values at runtime in order for the compiler to optimize it. Something like char *array=new char[i*10] is fine and dandy. char *array=new char[i*j] on the other hand is not. You would have to have a multiplication lookup table for substitutions (which is a cool idea), but would most likely end up being more costly that a slow ass mul operation due to the jumps and condition branching required.

[DrPizza]

Originally posted by sedarious
I am pretty sure LEA only works with constants for that sort of multiplication (and I think they have to be 2,4,8 and maybe 16 - I can't find the info in any tech docs right now). Since, i and j are runtime dependant, they can't be utilized in an LEA multiplication scheme.

Well, it depends how many degrees of freedom you have.

But, of course, you don't always need to perform the multiplication. To iterate through the array, for instance, requires only pointer increments (or additions if you're going in the other sense).

[bwkaz]

I see. No, it wouldn't work very well if any more than one dimension could be varied...

However, it is still the case that the memory read (if the cache misses -- if the cache hits, then you're OK) will take much, much longer than the piddly little multiply. On the 686 core, according to my Computer Architecture, A Quantitative Approach textbook, a cache miss takes around 70 cycles to satisfy (now this obviously depends a bit on memory and processor clock speeds, but that seems pretty close). Now the processor can still get some work done in that time if the cache is non-blocking and hit under miss (or something like that), because it's superscalar and speculative, but probably not much.

By the same token, if the multiply stalls the processor for some reason (actually, it won't, it'll just get executed on a different execution unit, and only stall dependent machine language instructions), other instructions can still be executed in the meantime. I don't have any numbers for how long it takes to multiply, but I wouldn't think it could possibly be more than about 20... right?

Of course, a cache hit is 1 cycle.

[sedarious]

LEA, regardless of the situation, will not multiply two registers together. ANd if you are talking about iteration, it doesn't matter which method is used (2-D or 1-D) since you can just increment the pointer by the size of the element (excluding row changes since you many not be guarenteed the next spot in memory).

This is what I break the calls down to for a random element:

Array of ptrs to arrays:
2 memory calls (99% chance of cache hit in this case I would say) and an LEA op.

Single dim array:
1 memory call (cache) added to I*J MUL (slow)


Another major factor to consider is the pipeline length. The major difference is that the second case will take more time (the MUL) as the size grows. The first method will always take the same amount of time.

edit:
About the multipy - this is from 386 documentation... its probably not too much better now...

8bit - 70-77
16bit - 118-133
32bit - ???

I would say 32bit would take near 200 clock cycles...

[bwkaz]

Umm, the 386 is definitely not a good processor to pick. Sure it had protected mode, and it had a PMMU, but the similarities with current Intel-compatible processors end there.

It was single-issue, maybe pipelined but I'm not sure on that one, had in-order execution, had no software cache/TLB control support (INVLPG was a 486 instruction), which makes me want to say it had no cache -- though I could be wrong, as I don't remember that processor quite that well.

Where did you find those numbers, though? Might there be anything similar for the 586 or 686 core (the Pentium or PPro/2/3 cores)? I remember that my 80x86 assembly book (the one that shipped with Borland's Turbo Assembler) had clock cycles per instruction in it, but as far as I remember, it only went up to the 386 anyway, so that would be useless. :eh:

I'm not sure on that 99% cache hit number either. We ran some simulations of 8KB, direct-mapped, 64-bit line size caches for our architecture class, on a gcc tracefile, and I remember numbers closer to an 80-90% hit rate. Which isn't bad, but no one got 99%...

[DrPizza]

About the multipy - this is from 386 documentation... its probably not too much better now...

The Pentium 4 takes approximately 14 clock cycles for a 32-bit multiply. So, yeah, it is much better now.

I say "approximately" because one can't make exact measurements given its OOO pipelined nature.

[stuka]

<minor hijack> What does "OOO pipelined nature" mean - or at least the OOO part?

[DrPizza]

Out Of Order.

That is, the processor reorders instructions (well, microops really) in an effort to keep itself as busy as possible and avoid stalls.

[sedarious]

Well, I guess it did get better. P4 also have a monster ALU which is INTERNALLY double pumped. So is it 14 CPU cycles or 14 ALU cycles? I am guessing its cpu cycles, since that is the major reference. Assuming AMD chips and p3's use the same logic, you are looking at a 28 cycle multiply.

OOO - out of order execution...

In reference to the 99% - that was just a number i threw out there. Since the i and j variable are stack located, there is no reason that they should be dropped from cache since the stack is going to be hit all the time.

If someone has the time today, can they toss together 2 little app that creates a 1000x1000 element matrix using both methods and retrieves say 10,000,000 RANDOM elements from the matrix and report a time? I don't have a C/C++ compiler at work and I can't SSH/Telnet out. If not, I will do it when I get home.

edit: Where did you find the info on the 14 clock cycles???