Optimal struct layout template?

[Don]

Andrei Alexandrescu wrote:
> Don wrote:
>> Andrei Alexandrescu wrote:
>>> Don wrote:
>>>> Denis Koroskin wrote:
>>>>> On Thu, 18 Dec 2008 01:38:32 +0300, Sergey Gromov
>>>>>> Thu, 18 Dec 2008 00:21:58 +0300, Denis Koroskin wrote:
>>>>>>> On Thu, 18 Dec 2008 00:12:18 +0300, Sergey Gromov
>>>>>>>> Tue, 16 Dec 2008 10:09:41 +0100, Don wrote:
>>>>>>>>> struct Foo { double, int } // 12 byte size, wants 8-byte 
>>>>>>>>> alignment.
>>>>>>>> Foo.sizeof is 16.
>>>>>>> It is 12 with align(1) (I see no problem with it).
>>>>>> With align(1) the Foo.alignof is 1 so there is no problem to talk 
>>>>>> about.
>>>>> No, there is. You should have structure as follows:
>>>>>
>>>>> align(1):
>>>>> struct Foo
>>>>> {
>>>>>     char c;
>>>>>     double d;
>>>>>     short s;
>>>>>     bool b;
>>>>> }
>>>>
>>>> [snip]
>>>>
>>>>> so that Foo.d.alignof == 8. Align(1) is still necessary so that 
>>>>> Foo.sizeof == 12.
>>>>
>>>> Sergey is correct to the extent that in DMD, x.alignof <= x.sizeof 
>>>> for any x, and also x.sizeof is always an integer multiple of 
>>>> x.alignof.
>>>> When you assume that DMD is correct, then the simple ordering by 
>>>> .alignof indeed gives an optimal solution.
>>>> But these values *don't* reflect the machine behaviour.
>>>>
>>>> real.alignof is 2. But it's significantly faster (factor of 2) on 
>>>> most x86 machines to have real aligned to 16.
>>>>
>>>> These effects are not captured by the .alignof property for structs. 
>>>> To capture it in the Foo example, you'd need (for example) a 
>>>> Foo.memberalignof property, and a Foo.memberalignoffsetof property.
>>>> But you could reasonably argue that if you're specifying align(1) 
>>>> then alignment is not important.
>>>> The simple algorithm may well be good enough.
>>>> (And note that you can use radix sort -- alignof can only be 1, 2, 
>>>> 4, 8, or 16 -- so it's in O(n) not O(n lg n)).
>>>>
>>>> Interestingly, this 'internal alignment' applies to function 
>>>> alignment, as well. D allows you to specify that a function be 
>>>> aligned to (for example) a 16-byte boundary. This is hardly ever 
>>>> useful; usually what you want is for the innermost loop to be 
>>>> aligned. And instead of a pile of nops before the loop, you'd like 
>>>> the function start address to be adjusted.
>>>
>>> That's cool! I think the way to the templates AlignForSpeed!(Foo) and 
>>> AlignForSize!(Foo) is paved. Don, now all you have to do is a simple 
>>> matter of coding :o).
>>>
>>> Andrei
>>
>> Here's a very simple implementation that should solve the problem 
>> described in the original post. It doesn't deal with the obscure and 
>> difficult cases of align(1) structs, or 80-bit reals.
>> Implementation includes workarounds for FOUR compiler bugs.
>> Works without modification on both D1 and D2.
>>
>> ----
>> /// Order the provided members to minimize size while preserving 
>> alignment
>> /// BUG: bugzilla 2029 prevents the signature from being (string[] 
>> names...),
>> /// so we need to use an ugly array literal instead.
>> char [] alignForSize(E...)(string[E.length] names)
>> {
>>     // Sort all of the members by .alignof.
>>     // BUG: Alignment is not always optimal for align(1) structs
>>     // or 80-bit reals.
>>     // TRICK: Use the fact that .alignof is always a power of 2,
>>     // and maximum 16 on extant systems. Thus, we can perform
>>     // a very limited radix sort.
>>     int [][] alignlist; // workaround for bugzilla 2569
>>     // alignof = 1, 2, 4, 8, 16, 32, 64
>>     alignlist = [ [],[],[],[],[],[],[]]; // workaround for bugzilla 2562
>>     char[][] declaration;
>>     foreach(int i_bug,T; E) {
>>         int i = i_bug; // workaround for bugzilla 2564 (D2 only)
>>         declaration ~= T.stringof ~ " " ~ names[i].dup ~ ";\n";
>>         int a = T.alignof;
>>         int k = a==2? 1 : a==4? 2 : a==8? 3 : a==16? 4 : a==32? 5 : 
>> a>=64? 6 : 0;
>>         alignlist[k]~=i;
>>     }
>>     char [] s;
>>     foreach_reverse(q; alignlist) {
>>       foreach(int i; q) {
>>         s ~=  declaration[i];
>>       }
>>     }
>>     return s;
>> }
>>
>> // Example:
>>
>> struct Foo {
>>     mixin(alignForSize!(int[], char[13], short, double[5])(["x", 
>> "y","z", "w"]));
>> }
>>
>> is equivalent to:
>>
>> struct Foo{
>>  double[5u] w; // aligned to 8 bytes
>>  int[] x;      // aligned to 4
>>  short z;      // aligned to 2
>>  char[13u] y;   // aligned to 1
>> }
>>
>> which will have a size of 63, followed by 1 byte of padding.
> 
> andrei:~$ grep unittest donscode.d
> andrei:~$ echo $?
> 1
> andrei:~$ _
> 
> 
> Other than that, I'd be glad if you included it in Phobos :o).
> 
> 
> Andrei

I'd really like to see bug 2029 fixed before standardizing it; I hate 
those ugly [] in the parameter list which will appear all over user 
code. It's a trivial change to the library code though.
Where should it go? In typecons.d ?