Skip to main content
GameDev.net gamedev.net
🔒 Locked

Multi-Dimensional Array Storage

Started by Liam M Apr 2, 2007 at 7:56 AM 3 replies 800+ views
Original Post
Liam M
Liam M
Hi there, Quick question: I have a multidimensional array class, and I have recently started optimising parts of my code, using SSE. The array class is used in my matrix library, which is the basis for my entire geometry library. With SSE, I have realised when working with homogenous coordinates, to speed up matrix operations immensely with SSE, it would be convient to store my multidimensional arrays, which are stored as a 1 dimensional array (to improve allocation speeds), in row major order. currently they are stored in column major order. I was very careful when designing it in the first place to make it easy to maintain and upgrade, and I assumed i could simply change my indexing functions (which the entire program uses, to abstract the low level memory management stuff), from this:
 

inline _Real& operator()(const SizeType y,const SizeType x) {return _mData[x * _mYDim + y];};
inline _Real  operator()(const SizeType y,const SizeType x)const {return _mData[x * _mYDim + y];};


To this:
 

inline _Real& operator()(const SizeType y,const SizeType x) {return _mData[y * _mXDim + x];};
inline _Real  operator()(const SizeType y,const SizeType x)const {return _mData[y * _mXDim + x];};


The change of course being from: x * _mYDim + y To: y * _mXDim + x Where x and y are the indices, and mXDim and mYDim are the dimensions of the array. However, this seems to have some rather, err, adverse effects on my program, which as far as I can tell, shouldnt be happening. Is there a problem with the change I have made here, or is there most likely some other odd mistake I've made?
jpetrie
jpetrie
Is that all you've changed? Exactly that? If so, you've just effectively transposed all your matrices. With your original function, operator()(0,2) would yield element (2 * 4 + 0), or 8. With your new function, operator()(0,2) would yield element (0 * 4 + 2), or 2. (I'm assuming a width of four, here, for a 4x4 matrix).

If you view your 16-element array as a 2D 4x4 matrix, you will note that the elements in positions 2 and 8 (zero based) are reflected about the diagonal. In other words, you just transposed everything implicitly.
Liam M
Liam M
No, i don't think you understand what I've done; my fault for not explaining. that _should_ only reorganise the order in which the data is stored in memory. For example, say we have a 3x3 array:

a b c
d e f
g h i

It is currently stored in column major order in memory, so it is stored in the order adgbehcfi. However, I want to make it so that it is stored in row major order, so, when stored as 1 dimensional array, the members of the array are stored in the order abcdefghi.

However, thanks for your reply, because you solved my problem anyway. I realise what you mean, and by transposing it as you put it, would achieve the affect I'm after. I guess I'l just have to keep looking for that elusive bug.
NotAYakk
NotAYakk
Create a class. It should have a private _mData.

Only a handful of functions should directly access this _mData.

Inherit from it in your matrix class to gain access to these functions.

This will let you isolate the functions that directly access the data. In theory, one of them has the bug or an abstraction leak.

...

If you are really paranoid, you can replace your use of _Real& with a pseudo-reference that doesn't allow a direct pointer or reference into the data in the container: in theory, someone could take your reference, turn it into a pointer, and do pointer arithmetic with it outside of your class.

That is an example of an abstraction leak -- your implementation leaks out in the address of the reference you return from your non-const operator().

A well-written pseudo-reference will compile away to nothing when you build in release code, yet prevent you from doing pointer arithmetic.
rockdeity
rockdeity
Many API functions, like those of OpenGL and DirectX, take raw pointers to arrays as input for certain functions. So,if you ever return your matrices' m_data as a pointer, it would affect the data being passed into the API.

Having abstracted access to elements and rows of your matrix is good, but often you need to pass the matrix as a whole and, in those cases, if accessing code assumed a certain order, like the API's I mentioned, then you will start getting weird results.

This is related to what NotAYakk mentions. That Real& return value is dangerous. Not saying you shouldn't do that but you have to realize what it can be used to do. If all you want to do is return one atomic element of the matrix, it doesn't imporve performance either, since a pointer and a float (if your real is a float) are the same size on Intel machines.

If what you posted is your only access to your Matrix class, then it is likely what NotAYakk says, make sure you aren't returning raw access into your data, or if you do, that the client code gets the ordering it expects. If you pass the address of that real as a pointer somewhere, it might expect a row and get a column now instead. Making it const won't help either, as const functions can still use it to get the address of that reference.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.