View mode: basic / threaded / horizontal-split · Log in · Help
December 14, 2008
Optimal struct layout template?
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
Re: Optimal struct layout template?
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
Re: Optimal struct layout template?
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
Re: Optimal struct layout template?
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
Re: Optimal struct layout template?
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
Re: Optimal struct layout template?
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
Re: Optimal struct layout template?
== 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
Re: Optimal struct layout template?
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
Re: Optimal struct layout template?
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
Re: Optimal struct layout template?
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