Allocating memory aligned on a given boundary

[Eric Sosman]

CBFalconer wrote On 04/27/07 09:44,:

... snip ...



Disagree. Consider an x86 in native mode. The address buss is 20
bits. But the internal code only handles 16 bit quantities.
Addresses are composed of two parts, the segment register and the
offset. Access is equally fast for any 16 bit alignment, because
the data buss is 16 bits. Yet code can be written to handle 32 bit
objects.

Not the prime object of compilation today, but it exists.

None of this seems to have anything to do with alignment
requirements. Maybe that's due to my unfamiliarity with x86,
but I don't see any connection between the way sixteen-bit
quantities are combined into twenty or thirty-two bits, and
the ways all those things must be aligned.

In hopes of clearing things up -- maybe we're using the
same words to talk about different things -- here's what I
mean when I say the alignment requirement for type T is a
divisor of sizeof(T):

Begin with the Standard's definition in Section 3.2:

alignment
requirement that objects of a particular type be
located on storage boundaries with addresses that
are particular multiples of a byte address

This definition has a number of implications. The
reference to "multiples" of a byte address implies that an
address can be multiplied by something. The address might
not be entirely numeric -- we can imagine a machine with
addresses like (Blue,42) and (Red,18) -- but there must
be some way to multiply an address by some quantity.

I am going to assume that the "some quantity" is an
integer, so we can compute 2*(Blue,42) -> (Mauve,84).
If the multiplying quantity is something else -- a complex
number, or a member of the set {Sweet,Sour,Bitter,Salty} --
then my assertion that alignment divides sizeof comes
unglued and I concede your objection. (I'd hate to debug
on such a machine, though!)

So: If we read "multiples" as "integer multiples,"
we are also led to the conclusion that alignment amounts
to a divisibility condition. An object of type T is
properly aligned if it is situated at an address that is
divisible by some integer A(T), written thus to emphasize
that the value may depend on the type T; different types
can have different alignment requirements.

What can we learn about A(T)? Consider an array of
two T objects: `T x[2];'. We know that x[0] is properly
aligned as a T object, and so is x[1]. Therefore, their
byte addresses (char*)&x[0] and (char*)&x[1] are both
multiples of A(T), both divisible by A(T). How far apart
are these two addresses? They are

ptrdiff_t D = (char*)x[1] - (char*)x[0];

bytes apart. And by the way arrays work, this value D is
exactly sizeof(T).

Since the two values (char*)&x[0] and (char*)&x[1]
are both divisible by A(T), their difference D = sizeof(T)
is also divisible by A(T). That is, alignment divides
sizeof -- at least, on machines where "multiples" are of
integers and not of objects from bizarre sets. (The
argument holds even if the addresses themselves are bizarre,
as long as the multipliers are taken to be integers.)

Then there is Vista. See below:

I confess I did not study the four references, but at
a brief glance none of them seemed to concern the alignment
of C data types. The first (which I'd seen before) was an
analysis of the Vista's content protection, the second was
about licensing, the third and fourth were anti-Vista
broadsides. All possibly justifiable, but none seeming to
bear on the question at hand. If there's something about
alignment in these four papers, perhaps you could point out
the specific passages you have in mind.

 

[Eric Sosman]

Eric Sosman wrote On 04/27/07 11:57,:

[...] Consider an array of
two T objects: `T x[2];'. We know that x[0] is properly
aligned as a T object, and so is x[1]. Therefore, their
byte addresses (char*)&x[0] and (char*)&x[1] are both
multiples of A(T), both divisible by A(T). How far apart
are these two addresses? They are

ptrdiff_t D = (char*)x[1] - (char*)x[0];

Drat! I left out the address-of operators:

ptrdiff_t D = (char*)&x[1] - (char*)&x[0];

.... as in the text. Sorry.

 

[Kenneth Brody]

Eric Sosman wrote: [...]

Whatever the alignment requirement and whatever the reason
for imposing it, it must be an exact divisor of sizeof(T).

Disagree. Consider an x86 in native mode. The address buss is 20
bits. But the internal code only handles 16 bit quantities.
Addresses are composed of two parts, the segment register and the
offset. Access is equally fast for any 16 bit alignment, because
the data buss is 16 bits. Yet code can be written to handle 32 bit
objects.

[...]

So, sizeof(long)==4, and the alignment is 2. Two is an exact
divisor of 4. Where's the disagreement?

--
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody | www.hvcomputer.com | #include |
| kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:[email protected]>

 

[Eric Sosman]

CBFalconer wrote On 04/27/07 15:18,:

[... too much ...]

All I am objecting to is the "multiple of sizeof" phrase, and I
illustrated a case. In your example we can assume that a multiple
operates only on the offset value, for example. There is no need
to go any further than whatever minimizes the memory access time,
and possibly not even that if we don't care about speed. All the
thing has to do is work.

Your point still escapes me. I didn't use the phrase
"multiple of sizeof" -- or if I did, it was a typo and I'm
still overlooking it. I said (or meant to say) that the
alignment requirement for a type is a *divisor* of its
sizeof, which is 'tother way about.

 

[Keith Thompson]

Disagree. Consider an x86 in native mode. The address buss is 20
bits. But the internal code only handles 16 bit quantities.
Addresses are composed of two parts, the segment register and the
offset. Access is equally fast for any 16 bit alignment, because
the data buss is 16 bits. Yet code can be written to handle 32 bit
objects.

If 16 bits is no longer an exact divisor of 32 bits, nobody told me
about it. (Perhaps you thought he meant multiple rather than
divisor?)

 

[Keith Thompson]

CBFalconer wrote On 04/27/07 15:18,:

[... too much ...]

All I am objecting to is the "multiple of sizeof" phrase, and I
illustrated a case. In your example we can assume that a multiple
operates only on the offset value, for example. There is no need
to go any further than whatever minimizes the memory access time,
and possibly not even that if we don't care about speed. All the
thing has to do is work.

Your point still escapes me. I didn't use the phrase
"multiple of sizeof" -- or if I did, it was a typo and I'm
still overlooking it. I said (or meant to say) that the
alignment requirement for a type is a *divisor* of its
sizeof, which is 'tother way about.

Your quotation did:

requirement that objects of a particular type be
located on storage boundaries with addresses that
are particular multiples of a byte address

But now I can agree with you

That quotation is the standard's definition of "alignment", C99 3.2p1.
It doesn't say anything about multiple of sizeof, just "multiples of a
byte address" (a phrase that doesn't make a whole lot of sense unless
you already understand what it's *supposed* to mean).