A portable way of pointer alignment

[Pavel]

Is there a portable C++-ish way to get a properly aligned pointer to an
object of given type from given arbitrary pointer-to-char? More
precisely, how to implement a template function with this prototype:

template <typename T>
T *
align(char *buf, size_t bufSize);

whose input is a memory buffer and output is either the lowest position
in the buffer at which one can placement-new an object of type T or a
null pointer if it is impossible?

-Pavel

 

[Alf P. Steinbach]

* Pavel:

Is there a portable C++-ish way to get a properly aligned pointer to an
object of given type from given arbitrary pointer-to-char? More
precisely, how to implement a template function with this prototype:

template <typename T>
T *
align(char *buf, size_t bufSize);

whose input is a memory buffer and output is either the lowest position
in the buffer at which one can placement-new an object of type T or a
null pointer if it is impossible?

It depends what you mean by portable.

If you mean "formally portable" then you can just wait a year or two or three
until C++0x, and then you have alignment as part of the standard library.

Until then I'm pretty sure that you'll find this functionality in the Boost
library (disclaimer 1: haven't checked).

But if you absolutely insist on doing it yourself, and the buffer does not stem
from an ordinary 'new' (which produces a pointer suitably aligned for any
ordinary type), and you're happy with a little formal UB, then you might try
something like


<code>
typedef ptrdiff_t Size;

template< typename T >
inline Size alignmentOf()
{
struct X
{
char bah;
T t;
};

return offsetof( X, t );
}

template <typename T>
T* align( char* const buf, Size const bufSize)
{
Size const i = reinterpret_cast<Size>( buf );
Size const j = i + alignmentOf<T>() - 1;
Size const aligned = j - j % alignmentOf<T>();

return (aligned - i >= bufSize - sizeof(T)? 0 : reinterpret_cast<T*>(
aligned ) );
}
</code>

(disclaimer 2: not tested! )


Cheers & hth.,

- Alf

 

[Maxim Yegorushkin]

Is there a portable C++-ish way to get a properly aligned pointer to an
object of given type from given arbitrary pointer-to-char? More
precisely, how to implement a template function with this prototype:

template <typename T>
T *
align(char *buf, size_t bufSize);

whose input is a memory buffer and output is either the lowest position
in the buffer at which one can placement-new an object of type T or a
null pointer if it is impossible?

What would you use such a function for?

 

[Pavel]

* Pavel:

It depends what you mean by portable.

The code that does not have to be changed when changing to a different
Standard-compliant compiler/set of compiler options/hardware platform/OS.

If you mean "formally portable" then you can just wait a year or two or
three until C++0x, and then you have alignment as part of the standard
library.

Looked in there and you are right, thanks! It is funny the prototype has
same name as I made up and the parameters are almost same. They opted
for passing two run-time parameters instead of one template parameter
but I hope this will be reasonably optimized/inlined by most of the
compilers when sizeof/alignof are passed. I wonder though whether this
can be optimized to the code equivalent to the one that could be
achieved with my desired prototype.

If I am still alive, active and involved with C++ when my systems are
built with C++0x-compliant compiler, this alignment support will come
very handy.

Until then I'm pretty sure that you'll find this functionality in the
Boost library (disclaimer 1: haven't checked).

Couldn't find there. They have some discussion of alignment, but in the
context of pools
(http://www.boost.org/doc/libs/1_41_0/libs/pool/doc/implementation/alignment.html);
My case is different.

But if you absolutely insist on doing it yourself,

Absolutely not . Vice versa, I would strongly prefer not to..

and the buffer does
not stem from an ordinary 'new' (which produces a pointer suitably
aligned for any ordinary type), and you're happy with a little formal
UB, then you might try something like

No, I can solve my problem w/o UB it for each particular situation but
it slightly have annoyed me to do it over and over again and the
maintenance have given some headache (more like thinking of it than
actually doing it ); so I just wondered if anyone invented a generic
way.

<code>
typedef ptrdiff_t Size;

I am not sure every pointer fits in ptrdiff_t.. For all my target
systems I could live with C99's intptr_t though as it is supported by
their C++ compilers...

template< typename T >
inline Size alignmentOf()
{
struct X
{
char bah;
T t;
};

return offsetof( X, t );

offsetof only works when T is a POD (18.1-5). e.g. g++ gives warnings on
using it on any non-POD and we cannot allow this warning as a matter of
policy. I am not sure if it is safe even assuming GCC and flat memory
model or gcc may re-order members in non-PODs sometimes.

}

template <typename T>
T* align( char* const buf, Size const bufSize)
{
Size const i = reinterpret_cast<Size>( buf );
Size const j = i + alignmentOf<T>() - 1;

say, pointers are plain integers (flat memory model) and 0-based and (i
= reinterpret_cast<Size>) == 118 and we need to align to the 4-bytes

Size const aligned = j - j % alignmentOf<T>();

(aligned = 118 - 118 % 3) == (118 - 1) == 117.. and we expect 119 if
bufSize is sufficient.

return (aligned - i >= bufSize - sizeof(T)? 0 : reinterpret_cast<T*>(
aligned ) );

But I can see where you are coming from, probably just something like
this (omitting size and null-pointer checks):

return reinterpret_cast<T *>(buf + (((intptr_t)buf - 1) /

}
</code>

(disclaimer 2: not tested! )

Thanks, I did not expect it anyway, just was looking for an idea. In the
above, there are too many assumptions; I guess I will have to stick to
hand-crafting until C++0x.

-Pavel

 

[Pavel]

What would you use such a function for?

At this time, to stuff heterogeneous objects into a memory buffer; but I
needed it before for other reasons, too.

 

[Alf P. Steinbach]

* Pavel:

Absolutely not . Vice versa, I would strongly prefer not to..

No, I can solve my problem w/o UB it for each particular situation but
it slightly have annoyed me to do it over and over again and the
maintenance have given some headache (more like thinking of it than
actually doing it ); so I just wondered if anyone invented a generic
way.

I am not sure every pointer fits in ptrdiff_t.. For all my target
systems I could live with C99's intptr_t though as it is supported by
their C++ compilers...
offsetof only works when T is a POD (18.1-5). e.g. g++ gives warnings on
using it on any non-POD and we cannot allow this warning as a matter of
policy. I am not sure if it is safe even assuming GCC and flat memory
model or gcc may re-order members in non-PODs sometimes.
say, pointers are plain integers (flat memory model) and 0-based and (i
= reinterpret_cast<Size>) == 118 and we need to align to the 4-bytes
boundary (that is, 119 as we count from 0

No, that would be 120.

). Then, alignmentOf<T>() == 3,

No, alignmentOf would be 4 in this case (just test it if you don't believe that).

But you're right that it formally only handles POD type.

To avoid the warning you could always just do the internal formally UB pointer
arithmetic in offsetof directly, like definining your own offsetof.

(j = 118 + 3 - 1) == 120,

j = 118 + 4 - 1 == 121

(aligned = 118 - 118 % 3) == (118 - 1) == 117..

aligned = 121 - 121 % 4 == 121 - 1 = 120

and we expect 119 if bufSize is sufficient.

No, you expect 120 if bufSize is sufficient. ;-)

But I can see where you are coming from, probably just something like
this (omitting size and null-pointer checks):

return reinterpret_cast<T *>(buf + (((intptr_t)buf - 1) /
(alignmentOf<T>() + 1)) * (alignmentOf<T>() + 1)) + 1;
?


Thanks, I did not expect it anyway, just was looking for an idea. In the
above, there are too many assumptions; I guess I will have to stick to
hand-crafting until C++0x.

Cheers & hth.,

- Alf

 

[Pavel]

* Pavel:

No, that would be 120.



No, alignmentOf would be 4 in this case (just test it if you don't
believe that).

But you're right that it formally only handles POD type.

To avoid the warning you could always just do the internal formally UB
pointer arithmetic in offsetof directly, like definining your own offsetof.

That would not be portable :-(

 

[Ian Collins]

At this time, to stuff heterogeneous objects into a memory buffer; but I
needed it before for other reasons, too.

Given that requirement, you want the machine alignment. The first power
of 2 greater than sizeof(long double) will cover most (if not all?) systems.

 

[Pavel]

Given that requirement, you want the machine alignment. The first power
of 2 greater than sizeof(long double) will cover most (if not all?)
systems.

That would be slightly wasteful. Some objects are only 1-2 bytes long,
some are few tens bytes long.

 

[Ian Collins]

That would be slightly wasteful. Some objects are only 1-2 bytes long,
some are few tens bytes long.

You could say the same for malloc!

 

[Andrew Poelstra]

You could say the same for malloc!

True, but supposing you're working with tens of thousands of objects,
hopefully malloc() will not give you the same amount of memory for
a bunch of 20-byte objects (say, 20Kb) as it would for a bunch of
two-byters (2Kb)!

 

[Ian Collins]

True, but supposing you're working with tens of thousands of objects,
hopefully malloc() will not give you the same amount of memory for
a bunch of 20-byte objects (say, 20Kb) as it would for a bunch of
two-byters (2Kb)!

Well no, but the two byte objects will have the same alignment at the 20
byte ones. So assuming an alignment of 16 bytes, each 2 byte block will
be 16 bytes apart and each 22 byte block will be 32 bytes apart. No
different from my suggestion.

If you know you have a lot of small allocations, use a custom allocator.

A silly example:

#include <stdlib.h>
#include <stdio.h>

int main()
{
printf( "%p\n", malloc(2) );
printf( "%p\n", malloc(2) );
printf( "%p\n", malloc(2) );

printf( "%p\n", malloc(20) );
printf( "%p\n", malloc(20) );
printf( "%p\n", malloc(20) );
}

 

[Pavel]

You could say the same for malloc!

Exactly, malloc has same issue (which I believe is solved in practice by
returning memory suitably aligned for any C++ object); I need this
optimized and I am ready to specify the exact C++ type I need; it's just
that malloc() is unable to take advantage of it.

On a side note, malloc has to provide for arbitrary order of
allocation/deallocation whereas I (currently) need sequential allocation
into buffer (e.g. FIFO). Yes, I did not mention it in the original post;
I still don't think it matters for the problem as I stated it.

-Pavel

 

[Ian Collins]

Exactly, malloc has same issue (which I believe is solved in practice by
returning memory suitably aligned for any C++ object); I need this
optimized and I am ready to specify the exact C++ type I need; it's just
that malloc() is unable to take advantage of it.

On a side note, malloc has to provide for arbitrary order of
allocation/deallocation whereas I (currently) need sequential allocation
into buffer (e.g. FIFO). Yes, I did not mention it in the original post;
I still don't think it matters for the problem as I stated it.

The underlying issue and the solution still remain: you have to stick to
the alignment rules of the machine. The alignment for any aggregate
type will have to follow those rules. As I said else thread, if you
want to efficiently allocate many small objects, use a custom allocator.

 

[Öö Tiib]

On a side note, malloc has to provide for arbitrary order of
allocation/deallocation whereas I (currently) need sequential allocation
into buffer (e.g. FIFO). Yes, I did not mention it in the original post;
I still don't think it matters for the problem as I stated it.

Boost has ALIGNOF or alignment_of (somewhere in type traits) that
might be useful until C++0x alignof operator comes out.

 

[Pavel]

The underlying issue and the solution still remain: True.
you have to stick to
the alignment rules of the machine. The alignment for any aggregate type
will have to follow those rules. As I said else thread, if you want to
efficiently allocate many small objects,

Thanks, but this is not the problem I need to solve. Seems like I have
to wait for C++0x for generic solution and live with manual hacks till then.

> use a custom allocator.

-Pavel

 

[Pavel]

Boost has ALIGNOF or alignment_of (somewhere in type traits) that
might be useful until C++0x alignof operator comes out.

Thanks Öö!

I looked into alignment_of. So far I have not figured out how to write
the required align() function using it in general (the difficulty is in
determining in general case at what boundary given char* pointer is
aligned). But, for platforms with flat memory model and a pointer
represented by an integral, the boost implementation of alignment_of
gives a useful idea.

-Pavel

 

[s_tec]

Is there a portable C++-ish way to get a properly aligned pointer to an
object of given type from given arbitrary pointer-to-char?

As others in this thread have pointed out, there are two parts to this
problem. The first is determining what the alignment of T should be in
the first place, and the second is actually aligning a pointer to that
boundary. For the first part, Alf Steinbach provided a nice solution
here on the list, and there is also a slightly different solution is
available at [1].

Solving the second part is a bit trickier, since there is no assurance
that casting a pointer to an int will do anything useful. I believe I
have found a completely-portable solution, though. The solution relies
on two facts:

a) Arithmetic is well-defined between pointers in the same array
b) new[] returns memory which meets the platform's worst-case
alignment requirements

From the problem description, it sounds like the original poster is
allocating a large block of memory and then packing several smaller
items into that block. If that is the case, performing the alignment
relative to the block's starting address should always work. If the
block's starting address comes from new[], it will already meet the
platform's worst-case alignment requirements. Subtracting the start of
the block form a pointer into the block will yield a well-behaved
signed integer, which can then be aligned. Adding the integer back to
the start of the block will yield a pointer, as desired:

#define ALIGN(p, base, align) base + (p - base + (align-1) &
~(align-1))

Here, p is the pointer to align, base is the starting address of the
block, and align is the requested alignment. Both p and base are char
*'s. This macro should work even on platforms with "weird" pointer
representations, since it uses pointer arithmetic rather than directly
twiddling the pointer's bits.

Obviously, on platforms where the pointer representation is known,
casting the pointer to an integer is going to be slightly faster than
this method.

I hope this information is useful to somebody. Sorry to resurrect a
topic that's been dead for a while.

-William "s_tec" Swanson

[1] http://www.monkeyspeak.com/alignment/

 

[Chris M. Thomasson]

What about something like this:

http://pastebin.org/96326

?

 

[James]

Is there a portable C++-ish way to get a properly aligned pointer to an
object of given type from given arbitrary pointer-to-char?

As others in this thread have pointed out, there are two parts to this
problem. The first is determining what the alignment of T should be in
the first place, and the second is actually aligning a pointer to that
boundary. For the first part, Alf Steinbach provided a nice solution
here on the list, and there is also a slightly different solution is
available at [1].

Solving the second part is a bit trickier, since there is no assurance
that casting a pointer to an int will do anything useful. I believe I
have found a completely-portable solution, though. The solution relies
on two facts:

a) Arithmetic is well-defined between pointers in the same array
b) new[] returns memory which meets the platform's worst-case
alignment requirements

From the problem description, it sounds like the original poster is
allocating a large block of memory and then packing several smaller
items into that block. If that is the case, performing the alignment
relative to the block's starting address should always work. If the
block's starting address comes from new[], it will already meet the
platform's worst-case alignment requirements. Subtracting the start of
the block form a pointer into the block will yield a well-behaved
signed integer, which can then be aligned. Adding the integer back to
the start of the block will yield a pointer, as desired:

#define ALIGN(p, base, align) base + (p - base + (align-1) &
~(align-1))

Here, p is the pointer to align, base is the starting address of the
block, and align is the requested alignment. Both p and base are char
*'s. This macro should work even on platforms with "weird" pointer
representations, since it uses pointer arithmetic rather than directly
twiddling the pointer's bits.

I am missing something here. How do I use the macro above to align:


char temp[12287];


on a 4096 byte boundary? Here is what I am trying to do:


#define ALIGN(p, base, align) (base + (p - base + (align-1) & ~(align-1)))


char buffer[12287];
char* align = ALIGN(buffer, buffer, 4096);

if (((size_t)align) % 4096)
{
puts("NOT ALIGNED");
}



I am getting NOT ALIGNED output which means the align pointer to not
aligned. What am I doing wrong?


Thanks!

:^)