December 14, 2008
According to the spec, data stored in structs is guaranteed to be laid out in the order specified in the source code.  While this is necessary in some low-level code, I have a use case where I need to pack structs as efficiently as possible.  These structs are to be stored in an array, and for efficiency reasons I want to store them directly rather than storing pointers, so using classes is out of the question.  Does anyone know how to write a template that, given a tuple of types, will reorder the tuple so that it will produce the optimal struct layout?  I don't care, at least for now, if it assumes x86-32/DMD instead of handling the more general case.
December 14, 2008
dsimcha wrote:
> According to the spec, data stored in structs is guaranteed to be laid out in
> the order specified in the source code.  While this is necessary in some
> low-level code, I have a use case where I need to pack structs as efficiently
> as possible.  These structs are to be stored in an array, and for efficiency
> reasons I want to store them directly rather than storing pointers, so using
> classes is out of the question.  Does anyone know how to write a template
> that, given a tuple of types, will reorder the tuple so that it will produce
> the optimal struct layout?  I don't care, at least for now, if it assumes
> x86-32/DMD instead of handling the more general case.

I don't have such code, but if anyone wrote something, it sounds like a terrific addition to Phobos.

Andrei
December 14, 2008
Reply to dsimcha,

> According to the spec, data stored in structs is guaranteed to be laid
> out in the order specified in the source code.  While this is
> necessary in some low-level code, I have a use case where I need to
> pack structs as efficiently as possible.  These structs are to be
> stored in an array, and for efficiency reasons I want to store them
> directly rather than storing pointers, so using classes is out of the
> question.  Does anyone know how to write a template that, given a
> tuple of types, will reorder the tuple so that it will produce the
> optimal struct layout?  I don't care, at least for now, if it assumes
> x86-32/DMD instead of handling the more general case.
> 

would "align 1" work?


December 14, 2008
BCS wrote:
> Reply to dsimcha,
> 
>> According to the spec, data stored in structs is guaranteed to be laid
>> out in the order specified in the source code.  While this is
>> necessary in some low-level code, I have a use case where I need to
>> pack structs as efficiently as possible.  These structs are to be
>> stored in an array, and for efficiency reasons I want to store them
>> directly rather than storing pointers, so using classes is out of the
>> question.  Does anyone know how to write a template that, given a
>> tuple of types, will reorder the tuple so that it will produce the
>> optimal struct layout?  I don't care, at least for now, if it assumes
>> x86-32/DMD instead of handling the more general case.
>>
> 
> would "align 1" work?

That could make things excruciatingly slow. What's really needed is (in first approximation) to sort the members in decreasing order of size. Odd-sized arrays of char foil this plan to some extent, which is where the fun begins.

Andrei
December 15, 2008
Sun, 14 Dec 2008 13:17:45 -0800, Andrei Alexandrescu wrote:

> BCS wrote:
>> Reply to dsimcha,
>> 
>>> According to the spec, data stored in structs is guaranteed to be laid out in the order specified in the source code.  While this is necessary in some low-level code, I have a use case where I need to pack structs as efficiently as possible.  These structs are to be stored in an array, and for efficiency reasons I want to store them directly rather than storing pointers, so using classes is out of the question.  Does anyone know how to write a template that, given a tuple of types, will reorder the tuple so that it will produce the optimal struct layout?  I don't care, at least for now, if it assumes x86-32/DMD instead of handling the more general case.
>>>
>> 
>> would "align 1" work?
> 
> That could make things excruciatingly slow. What's really needed is (in first approximation) to sort the members in decreasing order of size. Odd-sized arrays of char foil this plan to some extent, which is where the fun begins.

I would say in decreasing order of field/array element alignment requirement.
December 15, 2008
Reply to Andrei,

> BCS wrote:
> 
>> would "align 1" work?
>> 
> That could make things excruciatingly slow. What's really needed is
> (in first approximation) to sort the members in decreasing order of
> size. Odd-sized arrays of char foil this plan to some extent, which is
> where the fun begins.
> 
> Andrei
> 

??

http://en.wikipedia.org/wiki/Bin_packing_problem


December 15, 2008
== Quote from BCS (ao@pathlink.com)'s article
> >
> ??
> http://en.wikipedia.org/wiki/Bin_packing_problem

Yes, but most structs are small enough that the asymptotic complexity really isn't important.  For structs of maybe 4 or less elements, trying every possible permutation in O(N!) seems perfectly reasonable to me.  For larger structs, using heuristics might be necessary.
December 15, 2008
dsimcha wrote:
> == Quote from BCS (ao@pathlink.com)'s article
>> ??
>> http://en.wikipedia.org/wiki/Bin_packing_problem
> 
> Yes, but most structs are small enough that the asymptotic complexity really isn't
> important.  For structs of maybe 4 or less elements, trying every possible
> permutation in O(N!) seems perfectly reasonable to me.  For larger structs, using
> heuristics might be necessary.

You're only interested in the values of   x.sizeof&(x.alignof-1), and x.alignof is only ever 16,8,4,2, or 1. So there are only 65(?) possible elements.
I'm pretty sure it can be done in linear time, with the calculation maybe even done in constant time.
December 15, 2008
BCS wrote:
> Reply to Andrei,
> 
>> BCS wrote:
>>
>>> would "align 1" work?
>>>
>> That could make things excruciatingly slow. What's really needed is
>> (in first approximation) to sort the members in decreasing order of
>> size. Odd-sized arrays of char foil this plan to some extent, which is
>> where the fun begins.
>>
>> Andrei
>>
> 
> ??
> 
> http://en.wikipedia.org/wiki/Bin_packing_problem
> 

It's not a bin packing problem because the restrictions are very different. Clearly it's not a simple problem either! I wonder if it's NP-hard, and I highly doubt it (in fact I'm almost sure it isn't) because it can be easily decomposed into smaller subproblems.

Andrei
December 15, 2008
Sergey Gromov wrote:
> Sun, 14 Dec 2008 13:17:45 -0800, Andrei Alexandrescu wrote:
> 
>> BCS wrote:
>>> Reply to dsimcha,
>>>
>>>> According to the spec, data stored in structs is guaranteed to be laid
>>>> out in the order specified in the source code.  While this is
>>>> necessary in some low-level code, I have a use case where I need to
>>>> pack structs as efficiently as possible.  These structs are to be
>>>> stored in an array, and for efficiency reasons I want to store them
>>>> directly rather than storing pointers, so using classes is out of the
>>>> question.  Does anyone know how to write a template that, given a
>>>> tuple of types, will reorder the tuple so that it will produce the
>>>> optimal struct layout?  I don't care, at least for now, if it assumes
>>>> x86-32/DMD instead of handling the more general case.
>>>>
>>> would "align 1" work?
>> That could make things excruciatingly slow. What's really needed is (in first approximation) to sort the members in decreasing order of size. Odd-sized arrays of char foil this plan to some extent, which is where the fun begins.
> 
> I would say in decreasing order of field/array element alignment
> requirement.

Sounds indeed right. Even simpler than I thought!

Andrei
« First   ‹ Prev
1 2 3
Top | Discussion index | About this forum | D home