www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Optimal struct layout template?

reply dsimcha <dsimcha yahoo.com> writes:
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.
Dec 14 2008
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Dec 14 2008
prev sibling next sibling parent reply BCS <ao pathlink.com> writes:
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?
Dec 14 2008
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Dec 14 2008
next sibling parent reply Sergey Gromov <snake.scaly gmail.com> writes:
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.
Dec 15 2008
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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.


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
Dec 15 2008
parent reply Don <nospam nospam.com> writes:
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.


(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 }
 
 Andrei

Dec 16 2008
next sibling parent KennyTM~ <kennytm gmail.com> writes:
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.


(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?
Dec 16 2008
prev sibling parent reply Sergey Gromov <snake.scaly gmail.com> writes:
Tue, 16 Dec 2008 10:09:41 +0100, Don wrote:

 Example 2:
 struct Foo { double, int } // 12 byte size, wants 8-byte alignment.

Foo.sizeof is 16. The thing is, array of Foo's must be properly aligned, and &foo[1] must be cast(byte*) &foo[0] + Foo.sizeof. This means that Foo.sizeof must be itself 8-aligned. The solution is { Foo, Foo, int, int }. The same with your other example. Sizeof cannot be less than alignment. Therefore you can never pack real and short in 16 bytes.
Dec 17 2008
parent reply Sergey Gromov <snake.scaly gmail.com> writes:
Thu, 18 Dec 2008 00:21:58 +0300, Denis Koroskin wrote:

 On Thu, 18 Dec 2008 00:12:18 +0300, Sergey Gromov <snake.scaly gmail.com>  
 wrote:
 
 Tue, 16 Dec 2008 10:09:41 +0100, Don wrote:

 Example 2:
 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. The problem is when you have elements with non-trivial alignment requirements and want to pack them as tightly as possible.
 The thing is, array of Foo's must be properly aligned, and &foo[1] must
 be cast(byte*) &foo[0] + Foo.sizeof.  This means that Foo.sizeof must be
 itself 8-aligned.  The solution is { Foo, Foo, int, int }.

Stop right there. You can't access &foo[1] no matter what align or structure layout is used. Example: align(default): struct Data { int i1; short s2; char c1; int 12; } What is &i1[1]?

i1 is not an array. Sorry I wasn't clear enough. I was talking about an imaginary array of Foo's: Foo[] foo; You must admit that foo[1] and &foo[1] makes perfect sense for such construct. And that cast(byte*) &foo[1] - cast(byte*) &foo[0] == Foo.sizeof must hold.
Dec 17 2008
parent reply Don <nospam nospam.com> writes:
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.




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.
Dec 18 2008
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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.




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
Dec 18 2008
parent reply Don <nospam nospam.com> writes:
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.



about.

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.
Jan 08 2009
next sibling parent Robert Fraser <fraserofthenight gmail.com> writes:
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.



about.

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

Wow; thanks; that's awesome.
Jan 08 2009
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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.



about.

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
Jan 08 2009
next sibling parent reply Don <nospam nospam.com> writes:
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.



about.

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 ?
Jan 09 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Don wrote:
 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.



about.

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 ?

Yah, that's the place. That module quickly becomes one of my faves. Andrei
Jan 09 2009
prev sibling parent reply grauzone <none example.net> writes:
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.



about.

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

But this looks like something that really should be done by the compiler. This is in the compiler's area of responsibility, and using Don's template isn't very elegant either. Just look how the types and field names are separate, unlike in normal struct declarations. And the names are string literals. Instead, this should be implemented directly in the compiler. Some syntax is needed to mark structs, that should use an optimal layout. What about: align("optimal") struct Foo { int[] x; char[13] y; short z; double[5] w; } For classes, the compiler can optimize the field layout by default.
Jan 09 2009
parent reply Don <nospam nospam.com> writes:
grauzone wrote:
 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.



about.

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

But this looks like something that really should be done by the compiler. This is in the compiler's area of responsibility, and using Don's template isn't very elegant either. Just look how the types and field names are separate, unlike in normal struct declarations. And the names are string literals. Instead, this should be implemented directly in the compiler. Some syntax is needed to mark structs, that should use an optimal layout. What about: align("optimal") struct Foo { int[] x; char[13] y; short z; double[5] w; } For classes, the compiler can optimize the field layout by default.

Well, it's very obscure, really. It only makes a difference when you want to reduce the size of the struct, since DMD already assigns padding to give optimal alignment. And you'd only use it in cases when you care about the size AND you don't think it's important enough to order the fields yourself (or where you can't, because you don't know the types) AND where you don't care that the compiler will add a few bytes of padding at the end. So I'm pretty much certain the compiler shouldn't include support for limited-interest stuff like this. I'm not even sure that it's useful enough to be in a standard library. It was a fun exercise though.
Jan 09 2009
parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Don (nospam nospam.com)'s article
 For classes, the compiler can optimize the field layout by default.

want to reduce the size of the struct, since DMD already assigns padding to give optimal alignment. And you'd only use it in cases when you care about the size AND you don't think it's important enough to order the fields yourself (or where you can't, because you don't know the types) AND where you don't care that the compiler will add a few bytes of padding at the end. So I'm pretty much certain the compiler shouldn't include support for limited-interest stuff like this. I'm not even sure that it's useful enough to be in a standard library. It was a fun exercise though.

The thing is, those few bytes of padding really matter when you're working with large arrays of templated structs, and they can turn into tens of megabytes, or possibly even if they can just turn into kilobytes and kill cache performance. A perfect use for it (and the one I had in mind) was to build more space-efficient generic hash tables.
Jan 09 2009
prev sibling parent reply Sergey Gromov <snake.scaly gmail.com> writes:
Thu, 18 Dec 2008 17:08:12 +0100, Don 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.





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.

I think this is not something you can assume or not assume. The set of conditions you mention is required and sufficient to respect alignment requirements of array elements while obeying the rules of pointer math. You cannot change them until you drop either pointer math or alignment guarantees.
 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.

If you want size, you can use align(): struct ReallySmall { int flags; align(2) real value; byte flags2; align(2) real value2; } Now ReallySmall.value.alignof == 2, and sorting will give you struct ReallySmallSorted { int flags; align(2) real value; align(2) real value2; byte flags2; } with ReallySmallSorted.sizeof == 28 and .alignof == 4 on Windows.
 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.

I don't understand this part. Do you say that fields in different elements of the same array should be aligned differently?
Dec 18 2008
next sibling parent Rainer Deyke <rainerd eldwood.com> writes:
Sergey Gromov wrote:
 I think this is not something you can assume or not assume.  The set of
 conditions you mention is required and sufficient to respect alignment
 requirements of array elements while obeying the rules of pointer math.
 You cannot change them until you drop either pointer math or alignment
 guarantees.

You could split the sizeof property into two separate: real.alignof = 16 real.unpaddedsizeof = 12 real.paddedsizeof = 16 T.paddedsizeof = (T.unpaddedsizeof + T.alignof - 1) & ~T.alignof; Arrays would always use paddedsizeof to calculate addresses. Structs could use unpaddedsizeof and squeeze one or more additional variables into the padding space. The same applies to structs: struct C { int a; byte b; } C.alignof = 4 C.unpaddedsizeof = 5 C.paddedsizeof = 8 There is one problem with this technique. Because the padding space of a variable may contain another variable, when the variable is copied, only unpaddedsizeof bytes may be copied or the other variable will be clobbered. I expect that this partially negates the advantage of properly aligning the variable. -- Rainer Deyke
Dec 18 2008
prev sibling parent Don <nospam nospam.com> writes:
Sergey Gromov wrote:
 Thu, 18 Dec 2008 17:08:12 +0100, Don 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.





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.

I think this is not something you can assume or not assume. The set of conditions you mention is required and sufficient to respect alignment requirements of array elements while obeying the rules of pointer math. You cannot change them until you drop either pointer math or alignment guarantees.
 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.

If you want size, you can use align(): struct ReallySmall { int flags; align(2) real value; byte flags2; align(2) real value2; } Now ReallySmall.value.alignof == 2, and sorting will give you struct ReallySmallSorted { int flags; align(2) real value; align(2) real value2; byte flags2; } with ReallySmallSorted.sizeof == 28 and .alignof == 4 on Windows.
 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.

I don't understand this part. Do you say that fields in different elements of the same array should be aligned differently?

No. It only applies in this situation where you have a struct which contains another struct which is align(1). Given align(1): struct Foo { int a; double b; } (A) struct Bar { int c; Foo d; } (B) struct Bar { Foo d; int c; } (A) is better than (B) because it aligns Bar.d.b correctly. It's a trick, really -- it's using the other elements of Bar as padding for Foo. I can't think of any other cases where this trick applies. As you say, an array of Foo[] cannot have all of its elements aligned. So probably, the 'ideal solution' for the proposed template would be probe the insides of each struct to see if the trick can be used. real80 is another case where the trick can be applied. float[4] may also benefit from being aligned to a 16-byte boundary. With Intel's AVX instructions, something as large as float[16] might like to be on a 256-byte boundary, but all such cases are easy, since they involve x.sizeof == pow(2,k). align(1) structs and real80 are the only non-trivial ones.
Dec 19 2008
prev sibling parent reply BCS <ao pathlink.com> writes:
Reply to Andrei,

 BCS wrote:
 
 would "align 1" work?
 

(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
Dec 15 2008
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== 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.
Dec 15 2008
parent Don <nospam nospam.com> writes:
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.
Dec 15 2008
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
BCS wrote:
 Reply to Andrei,
 
 BCS wrote:

 would "align 1" work?

(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
Dec 15 2008
prev sibling next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Thu, 18 Dec 2008 00:12:18 +0300, Sergey Gromov <snake.scaly gmail.com>  
wrote:

 Tue, 16 Dec 2008 10:09:41 +0100, Don wrote:

 Example 2:
 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).
 The thing is, array of Foo's must be properly aligned, and &foo[1] must
 be cast(byte*) &foo[0] + Foo.sizeof.  This means that Foo.sizeof must be
 itself 8-aligned.  The solution is { Foo, Foo, int, int }.

Stop right there. You can't access &foo[1] no matter what align or structure layout is used. Example: align(default): struct Data { int i1; short s2; char c1; int 12; } What is &i1[1]?
Dec 17 2008
prev sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Thu, 18 Dec 2008 01:38:32 +0300, Sergey Gromov <snake.scaly gmail.com>  
wrote:

 Thu, 18 Dec 2008 00:21:58 +0300, Denis Koroskin wrote:

 On Thu, 18 Dec 2008 00:12:18 +0300, Sergey Gromov  
 <snake.scaly gmail.com>
 wrote:

 Tue, 16 Dec 2008 10:09:41 +0100, Don wrote:

 Example 2:
 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. The problem is when you have elements with non-trivial alignment requirements and want to pack them as tightly as possible.

No, there is. You should have structure as follows: align(1): struct Foo { char c; double d; short s; bool b; } it should be reordered to (one of the solutions): align(1): struct Foo { char c; bool b; short s; double d; } so that Foo.d.alignof == 8. Align(1) is still necessary so that Foo.sizeof == 12.
 The thing is, array of Foo's must be properly aligned, and &foo[1] must
 be cast(byte*) &foo[0] + Foo.sizeof.  This means that Foo.sizeof must  
 be
 itself 8-aligned.  The solution is { Foo, Foo, int, int }.

Stop right there. You can't access &foo[1] no matter what align or structure layout is used. Example: align(default): struct Data { int i1; short s2; char c1; int 12; } What is &i1[1]?

i1 is not an array. Sorry I wasn't clear enough. I was talking about an imaginary array of Foo's: Foo[] foo; You must admit that foo[1] and &foo[1] makes perfect sense for such construct. And that cast(byte*) &foo[1] - cast(byte*) &foo[0] == Foo.sizeof must hold.

This will *always* be true no matter what align/data layout is used.
Dec 18 2008