[C++] Arrays and contiguity

27 replies to this topic

#1poita

Senior Member

• Members
• 322 posts

Posted 10 November 2009 - 12:49 PM

Are objects in an array guaranteed to be stored contiguously in memory?

In particular:

struct Vec3 { float x, y, z; };

Vec3 vs[2];

assert(&(vs[0].z)+1 == &(vs[1].x));

Essentially I want to know if I can reliably pass &vs[0] as an argument for glVertexPointer using this array of vectors. I'm suspecting that I can, but I'm worrying about potential alignment issues.

#2.oisyn

DevMaster Staff

• Moderators
• 1842 posts

Posted 10 November 2009 - 01:42 PM

poita said:

Are objects in an array guaranteed to be stored contiguously in memory?
Well, yes, but I assume you mean "members of an object" rather than "objects in an array"? The point is, Vec3 might contain padding at the end, which means it is officially not layout compatible with an array of floats.

Quote

In particular:

struct Vec3 { float x, y, z; };

Vec3 vs[2];

assert(&(vs[0].z)+1 == &(vs[1].x));

Essentially I want to know if I can reliably pass &vs[0] as an argument for glVertexPointer using this array of vectors. I'm suspecting that I can, but I'm worrying about potential alignment issues.
Theoretically not. Practically, however, I have never seen a compiler in which the assert would trigger. But it's not guaranteed.
-
Currently working on: the 3D engine for Tomb Raider.

#3rouncer

Senior Member

• Members
• 2758 posts

Posted 10 November 2009 - 01:49 PM

Wouldnt it be heaps harder (and run alot slower) to write the programming language if this wasnt true?
you used to be able to fit a game on a disk, then you used to be able to fit a game on a cd, then you used to be able to fit a game on a dvd, now you can barely fit one on your harddrive.

#4.oisyn

DevMaster Staff

• Moderators
• 1842 posts

Posted 10 November 2009 - 02:00 PM

rouncer said:

Wouldnt it be heaps harder (and run alot slower) to write the programming language if this wasnt true?
That's not the point. The point is that C or C++ doesn't guarantee it, so it's up to the compiler implementors how they implement it. Btw, it's not so unthinkable for it to happen: a compiler might align Vec3 on 16 bytes for efficiency reasons. And it could, as the standard doesn't say it's illegal.
(Btw I was originally wrong and have edited my post )
-
Currently working on: the 3D engine for Tomb Raider.

#5rouncer

Senior Member

• Members
• 2758 posts

Posted 10 November 2009 - 02:09 PM

Which makes your choice of compiler important.
you used to be able to fit a game on a disk, then you used to be able to fit a game on a cd, then you used to be able to fit a game on a dvd, now you can barely fit one on your harddrive.

#6SyntaxError

Valued Member

• Members
• 139 posts

Posted 10 November 2009 - 03:33 PM

poita said:

struct Vec3 { float x, y, z; };

Vec3 vs[2];

assert(&(vs[0].z)+1 == &(vs[1].x));

This isn't guaranteed to work. If your machine (and/or machine with a given structure) pads to double it will fail. I wouldn't rely on it.

Edit: As a side note arrays are guaranteed to be contiguous. The problem isn't with the array. The problem is there may be extra padding at the end of each structure. The compiler adds it for performance reasons. There may be flags to turn this off. I believe the Pentium will load a misaligned float or double correctly with some performance penalty however on many architectures a program will throw a bus error. If it lands on you will be crushed.....OK sorry. In any case just avoid it.

#7rouncer

Senior Member

• Members
• 2758 posts

Posted 10 November 2009 - 04:05 PM

If the compiler was made less confusing, what he says is true.
you used to be able to fit a game on a disk, then you used to be able to fit a game on a cd, then you used to be able to fit a game on a dvd, now you can barely fit one on your harddrive.

#8JarkkoL

Senior Member

• Members
• 477 posts

Posted 10 November 2009 - 05:02 PM

.oisyn said:

a compiler might align Vec3 on 16 bytes for efficiency reasons.
Highly unlikely without forcing it explicitly in code. If it would happen in that specific case it would break pretty much all the code in the whole universe ;)

#9poita

Senior Member

• Members
• 322 posts

Posted 11 November 2009 - 12:13 AM

Quote

Well, yes, but I assume you mean "members of an object" rather than "objects in an array"? The point is, Vec3 might contain padding at the end, which means it is officially not layout compatible with an array of floats.

Well, "contiguously" means "without gaps in between". If there was padding in between objects (due to alignment) then they wouldn't be contiguous. I guess it's arguable whether the 4 bytes of padding at the end are part of the object or not, but that's what I was getting at :)

I guess the real question is, should I rely on it? Some of you are saying I should and others that I shouldn't.

#10SyntaxError

Valued Member

• Members
• 139 posts

Posted 11 November 2009 - 03:17 AM

poita said:

Well, "contiguously" means "without gaps in between". If there was padding in between objects (due to alignment) then they wouldn't be contiguous. I guess it's arguable whether the 4 bytes of padding at the end are part of the object or not, but that's what I was getting at :)

I guess the real question is, should I rely on it? Some of you are saying I should and others that I shouldn't.

I don't think it's all that arguable. Although I haven't checked the standard in my experience the padding is not between objects, it's part of the object. Take the sizeof() of your object and you will see this. Therefore the objects themselves are contiguous. As an example I compiled this code in Visual C++:


#include "stdafx.h"

#include <stdio.h>

struct Vec3 { float x, y, z; };

struct Vec4 { double x; float y; };

int main()

{

printf("sizeof(Vec3)=%d\n",sizeof(Vec3));

printf("sizeof(Vec4)=%d\n",sizeof(Vec4));

return 0 ;

}



results are:

sizeof(Vec3)=12
sizeof(Vec4)=16

The space required should be the same but because the compiler does double alignment for the Pentium to avoid bus performance issues, the size of the Vec4 is larger. I worked at intel for over 20 years and we compiled code on a tons of different workstations from different venders. Trust me, you shouldn't use pointers like that if you want things to be portable.

#11poita

Senior Member

• Members
• 322 posts

Posted 11 November 2009 - 03:33 AM

Ok, fair enough.

Well that sucks. Guess I'll just have to write a wrapper for vertex, normal, and UV arrays :/

#12rouncer

Senior Member

• Members
• 2758 posts

Posted 11 November 2009 - 08:28 AM

You pad manually, it doesnt happen automagically...
Imagine what it would be like if we wasted disk space all the time this way.
you used to be able to fit a game on a disk, then you used to be able to fit a game on a cd, then you used to be able to fit a game on a dvd, now you can barely fit one on your harddrive.

#13JarkkoL

Senior Member

• Members
• 477 posts

Posted 11 November 2009 - 01:03 PM

Don't worry, for that case what you had with Vec3, it's perfectly fine in practice. Just add compile-time assert to verify that the size is sizeof(float)*3 and you are safe.

#14.oisyn

DevMaster Staff

• Moderators
• 1842 posts

Posted 11 November 2009 - 02:31 PM

poita said:

Well, "contiguously" means "without gaps in between". If there was padding in between objects (due to alignment) then they wouldn't be contiguous. I guess it's arguable whether the 4 bytes of padding at the end are part of the object or not, but that's what I was getting at
Well, that's just the point. The padding *is* in fact part of the object according to the standard, that's not even debatable . If you do sizeof(Vec3), it includes the padding (very early GCC compilers bugged in this respect). This is why I misinterpreted your post the first time I read it

Quote

I guess the real question is, should I rely on it? Some of you are saying I should and others that I shouldn't.
Given modern day compilers, I'd say you can rely on it. But if you want to be truely and utterly portable for all possible compilers that exist now and will exist in the future, you shouldn't.

JarkkoL said:

Highly unlikely without forcing it explicitly in code. If it would happen in that specific case it would break pretty much all the code in the whole universe
Again, that's besides the point. The point is that a compiler *could* do that. The fact that there are no popular compilers compilers currently doing that changes nothing.
-
Currently working on: the 3D engine for Tomb Raider.

#15.oisyn

DevMaster Staff

• Moderators
• 1842 posts

Posted 11 November 2009 - 02:55 PM

rouncer said:

You pad manually, it doesnt happen automagically...
Imagine what it would be like if we wasted disk space all the time this way.
Disk space has nothing to do with this topic. And yes, we waste memory space all the time for efficiency reasons. That's why sizeof(Vec4) in SyntaxError's post is 16, even though it could have been 12.

struct Foo
{
int a : 1;
short b : 1;
int c : 1;
short d : 1;
};
This Foo is 16 bytes, even though it only uses 4 bits so theoretically it could have been packed into a single byte. In short: yes, it does in fact very much so happen 'automagically'
-
Currently working on: the 3D engine for Tomb Raider.

#16JarkkoL

Senior Member

• Members
• 477 posts

Posted 11 November 2009 - 03:15 PM

Sure, compilers could do many other things too to render tons of C++ code useless which doesn't strictly follow the C++ standard, but there's a difference between theory and practice. It's the interest of compiler developers that existing code actually works on their compilers, so it changes things quite a bit (: Not saying that you should violate the standard just for sake of it (or to drive C++ zealots crazy even though that can be fun too ;)), but sometimes it's just way more practical to do so.

#17.oisyn

DevMaster Staff

• Moderators
• 1842 posts

Posted 11 November 2009 - 03:25 PM

For the record, I would've made the same assumption here as well.
-
Currently working on: the 3D engine for Tomb Raider.

#18SyntaxError

Valued Member

• Members
• 139 posts

Posted 11 November 2009 - 05:55 PM

JarkkoL said:

Sure, compilers could do many other things too to render tons of C++ code useless which doesn't strictly follow the C++ standard, but there's a difference between theory and practice. It's the interest of compiler developers that existing code actually works on their compilers, so it changes things quite a bit (: Not saying that you should violate the standard just for sake of it (or to drive C++ zealots crazy even though that can be fun too ;)), but sometimes it's just way more practical to do so.

In my view writing something that moves pointers between structures in this way is kind of crazy. Change or add one more field and it fails even in everyday VC++ . This is very much a function of the CPU architecture and compiler developers are merely trying to build their compilers to generate efficient code. This isn't really a fringe issue. I would hope that not too many programmers are relying on this behavior. I would personally consider it extremely poor programming practice and I'm somewhat curious why it is even necessary. I'm having trouble imagining a problem where this couldn’t easily be coded in a better way. Possibly the OP could give us a more detailed description of the actual problem being solved.

#19rouncer

Senior Member

• Members
• 2758 posts

Posted 11 November 2009 - 06:06 PM

So i gather counting the amount of variables in your structure in no way dictates final memory usage?
you used to be able to fit a game on a disk, then you used to be able to fit a game on a cd, then you used to be able to fit a game on a dvd, now you can barely fit one on your harddrive.

#20Reedbeta

DevMaster Staff

• 5340 posts
• LocationSanta Clara, CA

Posted 11 November 2009 - 06:57 PM

In the sense that the size of a struct could be more than the sum of the sizes of its members, yes.
reedbeta.com - developer blog, OpenGL demos, and other projects

1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users