Sign in to follow this  
Laval B

Variable size strucs

Recommended Posts

Laval B    12387

Hello everyone

 

I'm trying to optimize the drawitem structure i use for my renderqueue. I use a struct that basically containes the same elements as the one posted by Hodgman in this post http://www.gamedev.net/topic/666419-what-are-your-opinions-on-dx12vulkanmantle/#entry5215127. I'm trying to reduce the footprint of the struct and to get all the members to be contiguous in memory to improve cache efficiency.

 

Replacing the pointers by 16 bits unsigned integers which are indices into arrays will considerably reduce the size of the fixed-length part of the struct (i compile for 64 bits).

 

I don't know how to deal with the variable part of the struct. I though about using variable size structs like the one bellow :

struct DrawItem
{
   u16 shaderPermutationId;
   u16 depthStencilStateId;
   // ...
   u16 textureCount;
   u16 textureIds[];
   // Cannot put more arrays or anything else after that.
};

But like the comment says, it's not possible to have any member after a variable size array.

 

I'm interested to know what could be done.

Edited by Laval B

Share this post


Link to post
Share on other sites
SmkViper    5396

You can write code like this, which adds a small cost to access the pointer:



struct DrawItem
{
   u16 shaderPermutationId;
   u16 depthStencilStateId;
   u16 textureCount;
   u16 cbufferCount;
   u16* TextureIds() { return (u16*)(this+1); }
   u16* CBufferIds() { return (u16*)(TextureIds()+textureCount); }
   u32 Sizeof() const { return sizeof(DrawItem) + sizeof(u16)*textureCount + sizeof(u16)*cbufferCount; }
};
Alignment issues, beware.


I would highly recommend overriding new and delete for any struct that stores data past the end (or use a factory function and hide all the constructors). Not to mention disabling copy and move by deleting the copy and move constructors.

Just because a struct like this is far from a POD and is very easy to misuse.

Share this post


Link to post
Share on other sites
Laval B    12387

 

I would highly recommend overriding new and delete for any struct that stores data past the end (or use a factory function and hide all the constructors). Not to mention disabling copy and move by deleting the copy and move constructors.

Just because a struct like this is far from a POD and is very easy to misuse.

 

 

Yes absolutely. In this case a factory method might be more appropriate since there will be arguments to pass.

Edited by Laval B

Share this post


Link to post
Share on other sites
Laval B    12387

After toying with this a little, i don't think it is possible to do that.

 

The struct i used for testing is the following

struct MultiArray
{

    u16 arr1Count;
    u16 arr2Count;

    u16* arr1()  { return reinterpret_cast<u16*>(this + 1); }
    u16* arr2()  { return reinterpret_cast<u16*>(arr1() + arr2Count); }
};

I allocate the memory using (with arr1Count_ = 2 and arr2Count_ = 3)

::operator new(sizeof(MultiArray) +  sizeof(u16)*arr1Count_ + sizeof(u16)*arr2Count_, std::nothrow) 

which i then cast into a pointer of the type of the struct. Then i can fill the struct using the pointer then access the content without any problem. But when i call ::operator delete(ptr, std::nothrow), i get a runtime check error telling me that i have written pass the end of the heap buffer (which is technically true).

 

The size given by sizeof(MultiArray) + sizeof(u16)*arr1Count_ + sizeof(u16)*arr2Count_ is the same as the one i get if i call sizeof with a struct containig two u16 values, a u16 [2] and a u16[3] (i.e. 14) so alignment shouldn't be the problem.

 

It's ok, the size is 14 but the alignment (for this struct) is 2 so i need to allocated 2 more bytes and it works fine. I just need to take care of the alignment properly (and to find how i can get the proper alignment for a given type).

Edited by Laval B

Share this post


Link to post
Share on other sites
SmkViper    5396
It also occurs to me you'll want your counts to be const - there is no reason they should ever be modified once set via the constructor as you can't resize your arrays.

Share this post


Link to post
Share on other sites
struct MultiArray
{
    u16 arr1Count;
    u16 arr2Count;

    u16* arr1()  { return reinterpret_cast<u16*>(this + 1); }           //vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    u16* arr2()  { return reinterpret_cast<u16*>(arr1() + arr2Count); } //<--- this should be (arr1() + arr1Count).
};                                                                      //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

 

Share this post


Link to post
Share on other sites
Hodgman    51328

arr1() + arr2Count

This is a bug (should be arr1Count to compute the end pointer of arr1); you are writing past the end of your allocation by 2 bytes!
[edit]ninja'd by sotl!

I would highly recommend overriding new and delete for any struct that stores data past the end (or use a factory function and hide all the constructors).

I don't override new/delete because with these kinds of packed/variable-sized structures, I usually want to put more than one of them into a single allocation. So I usually end up with a function that lookw like a simple constructor, but actually just returns the size that's required. You can then loop through all the objects that you want to create, measure their requirements, perform one single big allocation, then do a 2nd pass where you actually construct them in-place.

I also wouldn't include structures like this in any public header files -- the public API would likely just have a forward declaration of the type ("struct DrawItem;"), a factory for creating them, and functions that ise/consume them. That way all this dangerous variable size stuff isn't even visible to the user of the code.

Share this post


Link to post
Share on other sites
Laval B    12387

 

arr1() + arr2Count

This is a bug (should be arr1Count to compute the end pointer of arr1); you are writing past the end of your allocation by 2 bytes!

 

Thank you, for some reason, i totally missed it wacko.png

Share this post


Link to post
Share on other sites
Hodgman    51328

Thank you, for some reason, i totally missed it :wacko:

There's a reason every modern language has forbidden this kind of C-style tomfoolery: you will make more mistakes like this before your project is done! :)
When you think your code is finished, leave it for a month, then come back and audit it with a fine-toothed comb.

Share this post


Link to post
Share on other sites
Laval B    12387

There's a reason every modern language has forbidden this kind of C-style tomfoolery: you will make more mistakes like this before your project is done! smile.png

When you think your code is finished, leave it for a month, then come back and audit it with a fine-toothed comb.

 

Of course i realize that. The thing is i'm not working on production code, i'm just experimenting during my spare time.

Share this post


Link to post
Share on other sites
SmkViper    5396

I would highly recommend overriding new and delete for any struct that stores data past the end (or use a factory function and hide all the constructors).

I don't override new/delete because with these kinds of packed/variable-sized structures, I usually want to put more than one of them into a single allocation. So I usually end up with a function that lookw like a simple constructor, but actually just returns the size that's required. You can then loop through all the objects that you want to create, measure their requirements, perform one single big allocation, then do a 2nd pass where you actually construct them in-place.

I also wouldn't include structures like this in any public header files -- the public API would likely just have a forward declaration of the type ("struct DrawItem;"), a factory for creating them, and functions that ise/consume them. That way all this dangerous variable size stuff isn't even visible to the user of the code.


Yeah, that works too. The less code that has to know about how to specially construct these and what not to do with them the better. smile.png

Share this post


Link to post
Share on other sites
Madhed    4095

Does every draw item really need to store information about shaders, number of textures, assigned textures, etc?

Wouldn't it be better to store an id to a "material" object which contains a pair of shaders and any textures/constants that need to be set for the material to work?

Share this post


Link to post
Share on other sites
Laval B    12387
Yeah, that works too. The less code that has to know about how to specially construct these and what not to do with them the better. smile.png

 

Yes it is very important in production code that is manipulated by many people not to allow such a data structures to be easily or accidentally accident missused. It must not be possible to construct a drawitem on the stack or in a conatiner that would construct an incomplete object.

 

Does every draw item really need to store information about shaders, number of textures, assigned textures, etc?

Wouldn't it be better to store an id to a "material" object which contains a pair of shaders and any textures/constants that need to be set for the material to work?

 

Yes indeed. But then, how do you define the "material" object ? This material object will need to have thoses fields anyway with the arrays.

Edited by Laval B

Share this post


Link to post
Share on other sites
Madhed    4095


Yes indeed. But then, how do you define the "material" object ? This material object will need to have thoses fields anyway with the arrays

 

Well, the main idea is that not every draw item will have a unique combination of shaders and textures, etc. By moving the shared data into a material you will save memory in your main draw queue, it's basically the flyweight pattern.

 

Also you will want to sort your render queue by some criteria which will probably include a material id. Since the number of materials will hopefully be much less than the actual number of draw calls you could use some "heavier" data structures like vectors for the varying length parameters like textures and constants.

Share this post


Link to post
Share on other sites
Laval B    12387

 

Well, the main idea is that not every draw item will have a unique combination of shaders and textures, etc. By moving the shared data into a material you will save memory in your main draw queue, it's basically the flyweight pattern.

 

Also you will want to sort your render queue by some criteria which will probably include a material id. Since the number of materials will hopefully be much less than the actual number of draw calls you could use some "heavier" data structures like vectors for the varying length parameters like textures and constants.

 

 

You mean moving the shaders, the shader parameters and the textures to a material class that could be shared among multiple DrawItems ? Yes it could be done. But what i'm trying to do (and this is only experimentation) is to pack all the data for a draw call into contiguous memory to see if there is something to be gained by being more "cache efficient". Packing arrays is what is actually difficult.

 

Elements of a draw item are of course shared across models.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this