[C++] Arrays and contiguity

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Nov 10, 2009 at 12:49

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.

27 Replies

Please log in or register to post a reply.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Nov 10, 2009 at 13:42

@poita

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.

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.

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Nov 10, 2009 at 13:49

Wouldnt it be heaps harder (and run alot slower) to write the programming language if this wasnt true?

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Nov 10, 2009 at 14:00

@rouncer

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 ;))

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Nov 10, 2009 at 14:09

Which makes your choice of compiler important.

5225bc0c3bf66f4c275c332de6388d1f
0
SyntaxError 101 Nov 10, 2009 at 15:33

@poita

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.

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Nov 10, 2009 at 16:05

If the compiler was made less confusing, what he says is true.

Fe8a5d0ee91f9db7f5b82b8fd4a4e1e6
0
JarkkoL 102 Nov 10, 2009 at 17:02

@.oisyn

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 ;)

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Nov 11, 2009 at 00:13

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.

5225bc0c3bf66f4c275c332de6388d1f
0
SyntaxError 101 Nov 11, 2009 at 03:17

@poita

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.

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Nov 11, 2009 at 03:33

Ok, fair enough.

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

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Nov 11, 2009 at 08:28

You pad manually, it doesnt happen automagically…
Imagine what it would be like if we wasted disk space all the time this way.

Fe8a5d0ee91f9db7f5b82b8fd4a4e1e6
0
JarkkoL 102 Nov 11, 2009 at 13:03

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.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Nov 11, 2009 at 14:31

@poita

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 B). 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 B)

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

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.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Nov 11, 2009 at 14:55

@rouncer

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’

Fe8a5d0ee91f9db7f5b82b8fd4a4e1e6
0
JarkkoL 102 Nov 11, 2009 at 15:15

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.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Nov 11, 2009 at 15:25

For the record, I would’ve made the same assumption here as well.

5225bc0c3bf66f4c275c332de6388d1f
0
SyntaxError 101 Nov 11, 2009 at 17:55

@JarkkoL

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.

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Nov 11, 2009 at 18:06

So i gather counting the amount of variables in your structure in no way dictates final memory usage?

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Nov 11, 2009 at 18:57

In the sense that the size of a struct could be more than the sum of the sizes of its members, yes.

Fe8a5d0ee91f9db7f5b82b8fd4a4e1e6
0
JarkkoL 102 Nov 11, 2009 at 19:46

@SyntaxError

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++.

General way compilers pad structures is by adding bytes after each member so that the next member aligns properly, or after the last member so that the next instance of the enclosing type aligns properly. What OP is basically asking is if sizeof(Vec3)==sizeof(float)*3, which in the particular implementation of Vec3 is true in practice, particularly that it’s a POD type, even though not strictly guaranteed by the C++ standard.@SyntaxError

I would hope that not too many programmers are relying on this behavior

Well, if you are programming e.g. for D3D you probably are (: A common use case where knowing the memory layout of a type is useful is when you pass e.g. vertex data to D3D, which returns you void* upon Lock(), which you cast to the structure that defines the vertex. Sure you could pass all vertex atributes by using float*, but it’s just much more convenient to use struct and rely on the memory layout, because it just works in practice.

5225bc0c3bf66f4c275c332de6388d1f
0
SyntaxError 101 Nov 11, 2009 at 19:56

@rouncer

So i gather counting the amount of variables in your structure in no way dictates final memory usage?

Check this out:

#include "stdafx.h"
#include <stdio.h>

struct Vec3 { double x; float y; float z; };
struct Vec4 { float y; double x; float z; };

int main()
{
   printf("sizeof(Vec3)=%d\n",sizeof(Vec3));
   printf("sizeof(Vec4)=%d\n",sizeof(Vec4));
   return 0 ;
}

Results:

sizeof(Vec3)=16
sizeof(Vec4)=24

Now the only difference is the order that members are declared in the structure. So in short the answer is no. However for VC++ you can usually figure it out based on the alignment requirements but then a different complier might rearrange your members to save space. Just don’t rely on it. Over the years I have dealt with stuff like this numerous times when porting code. Alignment issues can cause a lot of problems when you start taking liberties. This isn’t some theoretical C++ nitpick. It does happen all the time so you should be careful.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Nov 11, 2009 at 20:30

@SyntaxError

but then a different complier might rearrange your members to save space.

Actually, no, a conforming compiler may not rearrange them. It is defined that every member of a class or struct within the same public/protected/private section has an address that is greater than the one of the previous member. In your example, a compiler may only rearrange x, y and z if you put a public: in front of each declaration. Nevertheless, I’ve seen compilers do it anyway (the ARM compiler for the Gameboy Advance. It even rearranged bitfields, which was very annoying as I was trying to define structs that were compatible with the hardware layout of things like sprites and such ;))

Of course, as far as padding is concerned all bets are off. But the standard guarantees that offsetof(Vec3, x) < offsetof(Vec3, y).

Fe8a5d0ee91f9db7f5b82b8fd4a4e1e6
0
JarkkoL 102 Nov 11, 2009 at 20:30

@SyntaxError

…a different complier might rearrange your members to save space.

Actually, to my knowledge it’s not allowed for a C++ standard conforming compiler to rearrange the order of a POD member variables at least. Which compiler are you referring to?

Edit: duh, you beat me .oisyn (:

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Nov 12, 2009 at 00:07

@SyntaxError

Possibly the OP could give us a more detailed description of the actual problem being solved.

As I said in the original post, I want to be able to store vertex position data in a std::vector<Vector3> and then pass in the address of the first element into glVertexPointer.

If you aren’t familiar, glVertexPointer accepts a float* – an array of vertex coordinates, laid out such that v[0] = a.x, v[1] = a.y, v[2] = a.z, v[3] = b.x, and so on…

It’s not very convenient to work with vectors in this componentwise manner, hence why I want to store them as an array of Vector3’s. Also, it would be highly inconvenient if I can to convert my Vector3’s into the array of floats every frame (not just inconvenient, but incredibly slow).

I could write a VertexBuffer object that stores them as an array of floats and converts individual triples into Vector3’s upon request – essentially giving it the interface of a std::vector<Vector3>, but it’s still inconvenient, and without good inlining, could be slow.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Nov 12, 2009 at 00:54

Well, I think it’s been established that you can store them as an array of Vector3s and that will be 98% fine - especially if you assert that sizeof(Vector3) == 3 * sizeof(float), so you will get an alert if for some reason that ever isn’t true.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Nov 12, 2009 at 01:07

You could use BOOST_STATIC_ASSERT or C++0x’s static_assert (included in VS 2010 and GCC 4.3). If you do not want to use boost and have a portable compile-time assert (which allows you to catch the error earlier) you could do something like:

char c[sizeof(Vec3) == 3*sizeof(float) ? 1 : -1];
5225bc0c3bf66f4c275c332de6388d1f
0
SyntaxError 101 Nov 12, 2009 at 08:56

@JarkkoL

Actually, to my knowledge it’s not allowed for a C++ standard conforming compiler to rearrange the order of a POD member variables at least. Which compiler are you referring to?

You guys are probably right. I do remember something about the compiler being able to rearrange members but it might have been in an older standard or before the standard specified it. I don’t really follow the standards in detail.

In any case, in general you still can’t count on data being contiguous. However if your structure doesn’t change and this is really for DirectX you aren’t portable anyway so who cares.

Edit: Oh sorry, it’s for openGL so disregard what I wrote, I’m up too late. I guess you do have to worry about it. In any case I’ve seen machines that like to align everything to double so it might be a problem there, but they are probably few and far between. Also glVertexPointer appears to have a stride parameter so I would think you could just take sizeof() and pass it in.