What are the benefits of pseudo multidimensional arrays and are they more relevant in some languages than others?

Question

For quite some time, I've been aware of pseudo-multidimensional arrays, whereby a multidimensional array is stored in a single dimensional array.

Rather than accessing a value via multiple indexes:

arr[row][col] //Standard Approach

The value is retrieved using a single calculated index:

arr[row * col + 1] //Pseudo Approach

Both approaches make sense. However, I've always assumed the pseudo approach to be a practice more common in C and/or C++ for reasons I've not explored. TBH, I've never felt compelled to use this pseudo approach in C#, Java, Javascript, PHP, OBJ-C, Swift, Kotlin, Python, Ruby, or even in C or C++.

My understanding is both methods reserve the same blocks of contiguous memory and therefore are actually 1D arrays under the hood anyway.

On that note, what are the benefits of one method over the other and do these apply to all languages? Also, is one method considered a better practice over the other or is this a matter of preference?

Answer 1

to my own little understanding as a n00b, using the standard approach is way more easier to use but kind of difficult when you want to allocate a memory for it contiguously, while pseudo method is easy to use with just slight calculations and also easy to allocate memory, thats from my n00b perspective, in relation to C

Answer 2

~ swim ~ As always, you provide such satisfying answers that trigger my mind into a deeper, richer understanding.

Here are my thoughts on your numbered points.

#1 and #2: Is this link a good illustration of what you are referring to with array dereferencing and additions?

https://stackoverflow.com/a/16013550

#3 - #5: Based on these points, you may have indirectly clarified something for me. It has been my understanding that multidimensional arrays are allocated across a block of contiguous memory addresses. Am I wrong on this? If so, I wonder why multidimensional arrays must be uniform sizes for each respective dimension.

Answer 3

Before the grown-ups talk about this, let me quickly show my reason for doing this a while ago:

In Python, it allows you to slice yourself conveniently through the array.

pseudo = [
1, 2, 3,
4, 5, 6,
7, 8, 9,
10, 11, 12
]

diagonal1 = pseudo[0::4]
diagonal2 = pseudo[2:7:2]
middlecol = pseudo[1::3]
middlerow = pseudo[3:6]

The slice values can be controlled with height and width variables (+1 or -1 for diagonals).

Applications of mine:

https://code.sololearn.com/c1U3g759GaMc/?ref=app
https://code.sololearn.com/cOgBIKfp377h/?ref=app
https://code.sololearn.com/cbnX3Z7htKZV/?ref=app

Answer 4

HonFu I must admit, the slice usage in this example is cool. 😉 It's a bit terse compared to using numpy arrays and related functions.

However, I imagine when the dimension lengths aren't guaranteed to be consistent, the slice [start : stop : step] values would need to be calculated, which might increase the code a little more with the pseudo approach.

I also think the slice option here might be a bit more difficult to read and quickly troubleshoot with larger datasets.

In this context for clearer readability, I'd prefer the standard approach.

I put together this code to compare the differences.

Also, there was an issue with the diagonal2 slice in your example. I adjusted it from [2::2] to [2:7:2] 😉👌.

https://code.sololearn.com/cd5hBM6PIxCJ/

Answer 5

Apparently in C, when dynamically allocated, a pseudo multidimensional array avoids some overhead in memory allocation/deallocation (malloc/free). Also when using pointers, the pseudo multidimensional array in C apparently guarantees that all the memory comes from one contiguous block that is more amenable to caching.

https://stackoverflow.com/questions/43311367/why-always-avoid-multi-dimensional-arrays-in-c-c-for-numerical-calculations

Answer 6

~ swim ~ and HonFu and Schindlabua

I wish we had the ability to meet up, have drinks, eat food, and geek out over dinner. I swear, I get a little smarter everytime you share your deep understanding based on your knowledge, experiences, and point of views.

A sincere thanks for all you contribute, for expanding my mind, and always challenging me to see familiar concepts in a new light. 🙏

Answer 7

The benefit is clarity. The dereference is made at compilation time, so the final object code is optimized.

For example:
We have this C code:

int main() {
int array[3][3];
array[1][2] = 123;
}

The resultant assembler code is:

main:
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-28], 123
mov eax, 0
pop rbp
ret

In the assembly code local variables do not exists, they are an offset over the base pointer (a microprocessor register). We can see that the final code does not calculate the position of the element [1][2] because this was already done at compile time.

Answer 8

Ha, David Carroll, you're right, the diagonal end is needed!

Also I missed commas in my list, so thanks - I have corrected it.

Nice to see the two methods side by side!

I have never used numpy so far, so it is a bit confusing for me naturally.

I must confess, that I find my own pseudo 2d array code examples not very readable. As soon as you want to generalize the method and use variables for the dimensions, well...

It's maybe not all that readable.

Answer 9

zemiak I'm not sure I would have put it quite like that, but I think I get your meaning. 🤔

I did tag C# and Java to see if anyone working primarily with these languages have ever seen or used the pseudo approach.

As someone who has far more experience in these other languages and less so with C/C++, I'm trying to figure out if this is a language specific practice.

Answer 10

My usescases for 2D arrays in general are either images and 3x3 or 4x4 matrices.

Image-type classes built into standard libraries are usually 1D (like System.Drawing.Bitmap in C# or ImageData in Javascript) and it is practical for writing to files. 2D arrays there would just complicate things and I find 1D easier to handle.

For 3x3 and 4x4 matrices it is common practice to implement for example matrix multiplication by unrolling both loops and just writing it all out by hand, so it really doesn't make sense to allocate anything else other than an `int[9]` or `int[16]` (or `int[6]` for 2D affine ones).
I guess a 4x4 1D array containing 32 bit ints also fits neatly into an L1 cache line which is an added speed bonus, though I usually don't pay attention to that.

I can't recall when or if I ever thought that true multidimensional arrays are appropriate but it probably just hasn't come up in my programming.
It's either large blocks of memory or super small ones for me :)

Answer 11

Thanks to David Carroll for a question post worth reading with worth learning replies. Finally, something enjoyable amongst the mess. Somehow my dinner taste better as I scrolled through this thread. Really, I am grateful for this, wish more of the likes would come more often, hats off to the contributors! this could be the question of the day, yeah 👍

Thanks everyone, this made my day 👏

Answer 12

That's true.
Given the next code:

int main() {
for(int i=0; i<3; ++i)
for(int j=0; j<3; ++j)
array[i][j] = i+j;
}

The assembler code shows this line:

mov DWORD PTR [rbp-48+rax*4], ecx

Where ecx <- i + j
and
rax is the linear nth element in the array.

To see the full assembly code you can go to godbolt compiler explorer and write down the C source code there, then the page will translate to assembly.

Answer 13

I'll bring a multi socket. :P

Answer 14

yeah Jay Matthews

Answer 15

(you tag it java) in java, allocation of memory is not so important aspect,
code readability is more important

Answer 16

Hi ,I’m Nancy from the city Dallas - USA and I study MCA. I love to make things work, make things move or make things blink. I am really happy to be a part of this community full of explorers, tinkerers, pioneers .

Answer 17

Eslam.nage