Optimal struct layout template?

[KennyTM~]

Don wrote:
> Andrei Alexandrescu wrote:
>> 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!
> 
> Close, but doesn't work in all cases. You sometimes need to insert 
> elements of smaller size.
> 
> Example 1:
> Given real, double, double, short, int:
> real (10 bytes, wants 16 byte alignment) --(only on Windows, 12 byte 
> size on Linux32, 16-byte size on Linux64)
> double (8 bytes, wants 8 byte alignment)
> short (2 bytes, wants 2 byte alignment)
> int (4 bytes, wants 4 byte alignment)
> 
> There are only two solutions:
> { real, short, int, double, double }
> { double, double, real, short, int }
> 
> Example 2:
> struct Foo { double, int } // 12 byte size, wants 8-byte alignment.
> 
> given Foo, Foo, int, int:
> solution is
> { Foo, int, Foo, int }
> 

Greedy algorithm?