Re: Aligning on some odd address?

[Brian Budge <brian dot budge at gmail dot com>]

Hi Marek -

I'm trying to see if I understand correctly:  There are 1260 arrays of
different types.  Each type is at least 16 bytes, but needn't
necessarily be 16 byte aligned.  If each array is terminated by an
empty (zeroed) structure, that would be 1260*16 bytes of wasted
memory.  Now if the arrays are large this is probably a very minor
amount of waste, but if the arrays are small, this could be a lot of
waste.  You were using an unsigned char for your length variable,
which makes me think that the lengths could be quite small.  You
almost certainly won't gain anything by using a 1 byte length, as your
inner structs are very unlikely to be 1 byte aligned.  Most likely
they will be at least 4 byte aligned, so you might as well use a 4
byte integer.  An additional benefit is that if you are iterating over
the structure, it should be faster if a memcmp isn't needed, and a
simple counter can just be checked.

If you put the length in front of the memory, how much space is wasted
will depend on the size of your length (you were using char), and the
alignment of the structs in the array.  Although I'm not sure of the
guarantee (I haven't read the standard), I believe every sane compiler
will layout the memory of the structs to reflect the alignment of it's
members.

So in other words, how much space you waste depends on the alignment
of the inner structs, and the outer struct should take on the
alignment of the maximal alignment requirement of it's members.

You stand to save a small amount of space, but also to potentially
make the code more readable and more efficient by having the length
instead of the zeroed-struct terminator.

I usually program on x86/x86-64/powerpc/MIPS, etc... i.e. not embedded
systems, so if I've said anything non-portable, I hope someone
corrects me.

  Brian

On Thu, Apr 16, 2009 at 11:28 PM, Philipp Marek
<philipp.marek@emerion.com> wrote:
> On Donnerstag, 16. April 2009, Brian Budge wrote:
>> Are these structs packed as-in the "packed" attribute? ?Do you expect
>> to have arrays of the outer structs, or will they all be instantiated
>> separately? ?Do you know the alignment of the something_else_t? ?Is
>> this to support something legacy, or is this a new design?
>>
>> I'm not sure there's quite enough information yet to know how to help.
> Sorry, I'll try to expand a bit.
>
> If you look into the linux kernel sources you'll find lots of pci_device_id
> and similar structures, which are used to identify hardware.
> These structures are at least 16 bytes, and there are (as of some quick count
> with perl) 1260 such arrays - all of which are terminated by an empty
> structure, ie. one consisting of zero bytes.
>
> That means that (at most) about 12k are "wasted" (on disk and in memory) by
> the terminating entries.
>
> So I thought about whether it's possible to put a small length description in
> front of them - but if this length gets padded to the same amount as the
> array, this doesn't make sense, as no space is saved.
> The arrays hold up to (again, quick survey with a perl script) 508 entries ...
> so it's not easy to use a few low bits in some pointer.
>
>
> Currently I'm thinking about extending the pci_driver (and similar)
> structures, to add a "id_table_len" member after the "id_table" pointer, to
> hold the number of elements.
>
>
> Regards,
>
> Phil
>
>