It is currently Wed Dec 12, 2018 3:08 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 43 posts ]  Go to page Previous  1, 2, 3
Author Message
PostPosted: Fri Nov 30, 2018 1:05 am 
Offline

Joined: Tue Oct 06, 2015 10:16 am
Posts: 844
Koitsu's example of accessing a multidimensional array linearly is undefined behavior. The compiler is allowed to break that, it is not guaranteed to be allocated linearly. Hit that before.


Top
 Profile  
 
PostPosted: Fri Nov 30, 2018 1:28 am 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7011
Location: Canada
Right, if you actually want a linear 1D array you should just use one. There are some applications where being able to e.g. treat an x coordinate past the edge as the next line down is a useful thing.

You can also split the difference with a convenient inline accessor function that takes (x,y) parameters. Would perform just as well as either the 1D or 2D array in normal circumstances, and you could use it or ignore it as needed.


Top
 Profile  
 
PostPosted: Fri Nov 30, 2018 1:32 am 
Offline
User avatar

Joined: Thu Mar 31, 2016 11:15 am
Posts: 441
calima wrote:
Koitsu's example of accessing a multidimensional array linearly is undefined behavior. The compiler is allowed to break that, it is not guaranteed to be allocated linearly. Hit that before.

Pretty sure arrays are guaranteed to be allocated in a single contiguous storage location and they're guaranteed to be packed (or rather, their size is equal to sizeof(T) * N). Because of this, it should be safe in practice.

The reason it's undefined behavior is because of other rules, like how a pointer to an object can't be incremented past the end of that object, and so on. And type punning, etc.

But yes! If you want to do that, just use a single dimensional array and add the multiplications in yourself.


Top
 Profile  
 
PostPosted: Fri Nov 30, 2018 3:51 am 
Offline
User avatar

Joined: Sun Sep 19, 2004 9:28 pm
Posts: 3722
Location: Mountain View, CA
calima wrote:
Koitsu's example of accessing a multidimensional array linearly is undefined behavior. The compiler is allowed to break that, it is not guaranteed to be allocated linearly. Hit that before.

...which is exactly why I said, quoting myself, "then the answer is yes, assuming the array is declared as described." The array I demonstrated in the example code I gave is absolutely going to consist of a piece contiguous/linear memory. Period -- and I refuse to get into discussing how ld.so and ELF declarations end up being allocated because it's remarkably advanced and I have no interest in blowing time discussing it. The only "bug" in what I listed is one of habit: I should have said, in my final paragraph, memset(&b, '-', sizeof(b[0][0]) * 8 * 1024);, though what I said will work in this case.

OP's question got answered as best I could answer it / as much time as I was willing to put into it. Are there other aspects of multidimensional (or even single-dimensional!) array declarations and accesses/methodologies (generally) where this *won't* work? Absolutely! But not in the example I gave. Nothing else for me to say on this matter.


Top
 Profile  
 
PostPosted: Fri Nov 30, 2018 9:21 am 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7602
Location: Chexbres, VD, Switzerland
koitsu wrote:
The only "bug" in what I listed is one of habit: I should have said, in my final paragraph, memset(&b, '-', sizeof(b[0][0]) * 8 * 1024);, though what I said will work in this case.

My god C is so ugly as a programming language, I can't for the world figure why anyon would use such an ugly language and although I've much used it I've forgotten all those quicks and hope I won't met them ever again. This line above looks like giberrish nonsense and doesn't look like you're iinitalizing a multidimentional array.


Top
 Profile  
 
PostPosted: Fri Nov 30, 2018 10:07 am 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7011
Location: Canada
Bregalad wrote:
koitsu wrote:
The only "bug" in what I listed is one of habit: I should have said, in my final paragraph, memset(&b, '-', sizeof(b[0][0]) * 8 * 1024);, though what I said will work in this case.

My god C is so ugly as a programming language, I can't for the world figure why anyon would use such an ugly language and although I've much used it I've forgotten all those quicks and hope I won't met them ever again. This line above looks like giberrish nonsense and doesn't look like you're iinitalizing a multidimentional array.

Not that I really care whether code is "ugly" but there are other options.

It could have been initialized to 0 during its declaration like this:
Code:
char b[8][1024] = { 0 };


If you need an arbitrary initialization value, even the memset can be ranged more simply like this, so at least you aren't repeating your values, and the & is optional for a static array like this:
Code:
memset(b, v, sizeof(b));


There are other ways too. (C++11 has some 'nice' looking ways to do this, maybe.) koitsu's version isn't surprising or non-idiomatic though, even though it's verbose, I've seen similar many times.


Top
 Profile  
 
PostPosted: Fri Nov 30, 2018 11:46 am 
Offline

Joined: Sun Apr 13, 2008 11:12 am
Posts: 7817
Location: Seattle
koitsu wrote:
...which is exactly why I said, quoting myself, "then the answer is yes, assuming the array is declared as described." The array I demonstrated in the example code I gave is absolutely going to consist of a piece contiguous/linear memory. Period
This behavior is, in fact, described in the C99 standard. §6.5.2.1 Array subscripting


Top
 Profile  
 
PostPosted: Fri Nov 30, 2018 2:42 pm 
Offline
Formerly Espozo
User avatar

Joined: Mon Sep 15, 2014 4:35 pm
Posts: 3404
Location: Richmond, Virginia
Sorry for being ignorant, but a multidimensional array is guaranteed to be contiguous in memory, correct? (I was getting mixed signals from some of the answers.) This is important because, regardless of performance, sometimes it is less complicated (for the programmer) to access a multidimensional array linearly. A random example would be if you wanted to increment every item in a multidimensional array by 1; you'd save yourself from having to write embedded for loops.


Top
 Profile  
 
PostPosted: Fri Nov 30, 2018 4:57 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7011
Location: Canada
No, koitsu was demonstrating that the underlying memory organization is the same. I don't believe he was suggesting that it is a good idea to cast a 2D array to a 1D array.

If you want 1D array access then just use a 1D array. If you want convenient 2 coordinate access to that 1D array, make an inline function or a macro or something to make indexing it like a 2D array easier. It will be functionally and performance-wise equivalent to a 2D array.

Don't go casting types around like this except as a last resort. It can work if you really need it to, but it's semantically wrong enough that an aggressive compiler might break it on you in the wrong situation.

...and again, you're making the assumption that there is a performance advantage for doing this anyway. This is not necessarily true. Depending on the situation accessing a row at a time might be as fast or nearly as fast as having the whole array unrolled into a 1D form. The difference between these two things is not usually a significant performance bottleneck by itself. It can be, but it usually isn't. Like I keep saying: time it if you really want to know, and don't start optimizing until you've started timing things. The answer to this is going to be different for different shapes of array, and different needs.


Top
 Profile  
 
PostPosted: Fri Nov 30, 2018 6:14 pm 
Offline
Formerly Espozo
User avatar

Joined: Mon Sep 15, 2014 4:35 pm
Posts: 3404
Location: Richmond, Virginia
rainwarrior wrote:
...and again, you're making the assumption that there is a performance advantage for doing this anyway.

I was talking about ease for the programmer (not the processor) at this point; I now understand that the compiler is capable of generating efficient code with a multi dimensional array.

There are things that are definately easier for the programmer to conceptualize as a multi dimensional array vs a single dimensional array, so you would make a multi dimensional array, but you would still want the option to access linearly, especially if the compiler will treat it as such in these cases anyway.

As an example, you have a framebuffer stored as a 2D array, because for 99% of cases, it's easier to work with this way. However, if you want to perform an operation on every pixel of the framebuffer, it would be easier for you (not the processor) to start at index 0 and go until index xDimension * yDimension rather than making an embedded for loop for each axis. Not a good example though because there's hardly a difference in difficulty for the programmer either way...


Top
 Profile  
 
PostPosted: Fri Nov 30, 2018 7:00 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7011
Location: Canada
Well, I mentioned it by name, but there are solutions to the convenience problem too, e.g. in C++:
Code:
inline int& pixel(int x, int y)
{
    return array[(y*256)+x];
}

// can use to access the 1D array with 2 coordinates:
pixel(10,35) = v;
v = pixel(99,2);


The "inline" means the compiler is allowed to weave the function directly into the code instead of having to do a subroutine call, and permits all sorts of optimizations to carry through it. It's yet another functionally equivalent way to do the indexing. There are a bunch of other options here too.

I've seen stuff like a "forxy" macro that's a shorthand for a loop that iterates over x and y, instead of having to type two loops.

There are tons of image libraries out there that have both ways of accessing an image built into an image class, or operating on an image structure.

Really there are a lot of ways to accomplish these things. Many of them have zero run-time performance drawback. C and especially C++ are very versatile in this respect, and I think this is one of the big strengths of these languages.


Last edited by rainwarrior on Fri Nov 30, 2018 7:32 pm, edited 1 time in total.

Top
 Profile  
 
PostPosted: Fri Nov 30, 2018 7:23 pm 
Offline
User avatar

Joined: Sun Sep 19, 2004 9:28 pm
Posts: 3722
Location: Mountain View, CA
rainwarrior covered it -- no, I wasn't advocating treating a multidimensional array as a standard/single-dimensional array (you should access the array in the manner of which it was declared if at all possible), I was simply demonstrating that the memory is guaranteed to be contiguous if the array is declared as in my example. Other declarations certainly do not guarantee contiguous layout, and thus you need to trust the language and compiler to do what's optimal. What's optimal depends on the situation; if you're ever worried/deeply concerned, then use a profiler and look at the generated assembly + do cycle counting.

If embedded (nested) for-loops bother you, then you'll probably loathe how one iterate over data structures like JSON, YAML, XML, etc. -- things commonplace today in higher-level PLs. You use nested loops or a helper function which is recursive to help you, or you end up using abstraction frameworks that "hide" it all from you (but in the end, do exactly that -- nested loops or recursive functions). But switching back to C, linked list code or trees will probably bother you -- but they're very common, both in userland (programs/libraries) as well as kernel. Some OSes (ex. Linux, BSDs; not sure about Windows) have helper macros for lists and trees that make such things a bit easier code-wise.


Top
 Profile  
 
PostPosted: Fri Nov 30, 2018 8:24 pm 
Offline
User avatar

Joined: Tue Jun 24, 2008 8:38 pm
Posts: 2124
Location: Fukuoka, Japan
So go for easy of use first and try to achieve your goal then if there is a performance issue, like rainwarrior said, time it (or profile it depending of the tools you have) and check the bottle neck you have.

Corn flakes! (ok, I stop ^^;;;)


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 43 posts ]  Go to page Previous  1, 2, 3

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group