memory allocators & proper alignment...

[Chris Thomasson]

Here is some info on a C++ allocator prototype I am working on:

http://groups.google.com/group/comp.lang.c++/browse_frm/thread/beeee1f61fdbb52c

Any tried-and-true techniques for calculating the correct alignment of any
C++ type the user can throw at it? For the initial code, I was assuming that
the alignment(T) == sizeof(T)... Now that I am so close to being able to
release this thing, I wanted to be able to stitch up this loose end.

All of the allocators I have worked on were always uses by entities which
were private to a library implementation... Any they only needed to align
structures on level-2 cache-line boundaries. So, I didn't need to align for
the type, I only align for the cache line.

Now I need to figure out how to get the correct alignment of any C++ type a
user can come up with...

Help!


:^)

 

[Chris Thomasson]

Here is some info on a C++ allocator prototype I am working on:

http://groups.google.com/group/comp.lang.c++/browse_frm/thread/beeee1f61fdbb52c
[...]
Now I need to figure out how to get the correct alignment of any C++ type
a user can come up with...

I think I will just go ahead and post the code today or tomorrow.

 

[John Harrison]

Here is some info on a C++ allocator prototype I am working on:

http://groups.google.com/group/comp.lang.c++/browse_frm/thread/beeee1f61fdbb52c


Any tried-and-true techniques for calculating the correct alignment of
any C++ type the user can throw at it? For the initial code, I was
assuming that the alignment(T) == sizeof(T)... Now that I am so close to
being able to release this thing, I wanted to be able to stitch up this
loose end.

All of the allocators I have worked on were always uses by entities
which were private to a library implementation... Any they only needed
to align structures on level-2 cache-line boundaries. So, I didn't need
to align for the type, I only align for the cache line.

Now I need to figure out how to get the correct alignment of any C++
type a user can come up with...

Help!


:^)

There is no infallible way to compute that in standard C++. I recall
reading about techniques that almost always work. This article seems to
describe one of those (although it doesn't ring any bells for me).

http://www.monkeyspeak.com/alignment/

john

 

[Gianni Mariani]

Here is some info on a C++ allocator prototype I am working on:

http://groups.google.com/group/comp.lang.c++/browse_frm/thread/beeee1...

[...]
Now I need to figure out how to get the correct alignment of any C++ type
a user can come up with...

one way:
template <typename T>
struct alignof_static
{
struct Helper1 { T v; };
struct Helper2 { char c; Helper1 v; };

static const unsigned value = sizeof(Helper2)-sizeof(Helper1);
};


template <typename T>
unsigned alignof()
{
return alignof_static<T>::value;
}

#ifdef __GNUC__
struct X
{
int a;
} __attribute__ ((aligned (8)));
#else
typedef int X;
#endif


#include <iostream>
int main()
{
std::cout << alignof<char>() << "\n";
std::cout << alignof<short>() << "\n";
std::cout << alignof<int &>() << "\n";
std::cout << alignof<char &>() << "\n";
std::cout << alignof<X>() << "\n";
}

 

[Gianni Mariani]

Here is some info on a C++ allocator prototype I am working on:

http://groups.google.com/group/comp.lang.c++/browse_frm/thread/beeee1...

[...]
Now I need to figure out how to get the correct alignment of any C++ type
a user can come up with...

I think I will just go ahead and post the code today or tomorrow.

I'm not sure why my previous attempt at posting this didn't show up -
if this is a second post - apologies in advance.

template <typename T>
struct alignof_static
{
struct Helper1 { T v; };
struct Helper2 { char c; Helper1 v; };

static const unsigned value = sizeof(Helper2)-sizeof(Helper1);
};


template <typename T>
unsigned alignof()
{
return alignof_static<T>::value;
}

#ifdef __GNUC__
struct X
{
int a;
} __attribute__ ((aligned (8)));
#else
typedef int X;
#endif


#include <iostream>
int main()
{
std::cout << alignof<char>() << "\n";
std::cout << alignof<short>() << "\n";
std::cout << alignof<int &>() << "\n";
std::cout << alignof<char &>() << "\n";
std::cout << alignof<X>() << "\n";
}

 

[James Kanze]

Here is some info on a C++ allocator prototype I am working on:
http://groups.google.com/group/comp.lang.c++/browse_frm/thread/beeee1....

[...]

Now I need to figure out how to get the correct alignment
of any C++ type a user can come up with...

one way:
template <typename T>
struct alignof_static
{
struct Helper1 { T v; };
struct Helper2 { char c; Helper1 v; };
static const unsigned value = sizeof(Helper2)-sizeof(Helper1);

Just curious, but why Helper1? I would have expected:

struct Helper { char c; T v ; } ;
static const size_t value = sizeof( Helper ) - sizeof( T ) ;

Word addressed machines will typically require all struct's to
be aligned at word boundaries; only character types are exempt
from the requirement. But since the above seems so obvious, I
presume that there is some reason I haven't seen for not using
it.

 

[Gianni Mariani]

Here is some info on a C++ allocator prototype I am working on:
http://groups.google.com/group/comp.lang.c++/browse_frm/thread/beeee1...
[...]
Now I need to figure out how to get the correct alignment
of any C++ type a user can come up with...

one way:
template <typename T>
struct alignof_static
{
struct Helper1 { T v; };
struct Helper2 { char c; Helper1 v; };
static const unsigned value = sizeof(Helper2)-sizeof(Helper1);

Just curious, but why Helper1? I would have expected:

struct Helper { char c; T v ; } ;
static const size_t value = sizeof( Helper ) - sizeof( T ) ;

Think about what the expression above does when T = char &.

I attached another version which has two alignof methods - one for
dealing with the reference as a type and the other to deal with the
references and the underlying type as the same.

Word addressed machines will typically require all struct's to
be aligned at word boundaries; only character types are exempt
from the requirement. But since the above seems so obvious, I
presume that there is some reason I haven't seen for not using
it.

You can probably do a static assert for this - i.e. safe since it fails
to compile on platforms that don't support it.



template <typename T>
struct noreference
{
typedef T type;
};

template <typename T>
struct noreference<T&>
{
typedef T type;
};



template <typename T>
struct alignof_static
{
struct Helper1 { T v; };
struct Helper2 { char c; Helper1 v; };

static const unsigned value = sizeof(Helper2)-sizeof(Helper1);
};

template <typename T>
struct alignof_noref_static
{
static const unsigned value = alignof_static<typename noreference<T>::type >::value;
};

template <typename T>
unsigned alignof()
{
return alignof_static<T>::value;
}

template <typename T>
unsigned alignof_noref()
{
return alignof_noref_static<T>::value;
}

#ifdef __GNUC__
struct X
{
int a;
} __attribute__ ((aligned (8)));
#else
typedef int X;
#endif


#include <iostream>
int main()
{
std::cout << alignof<char>() << "\n";
std::cout << alignof<short>() << "\n";
std::cout << alignof<int &>() << "\n";
std::cout << alignof<char &>() << " noref=" << alignof_noref<char &>() << "\n";
std::cout << alignof<X>() << "\n";
}

 

[Gianni Mariani]

James Kanze wrote:

....

I forgot to mention - I decided to switch news servers after my last
response didn't show for a few hours. So apologies again for double posts.

 

[James Kanze]

[...]
Now I need to figure out how to get the correct alignment
of any C++ type a user can come up with...
one way:
template <typename T>
struct alignof_static
{
struct Helper1 { T v; };
struct Helper2 { char c; Helper1 v; };
static const unsigned value = sizeof(Helper2)-sizeof(Helper1);

Just curious, but why Helper1? I would have expected:
struct Helper { char c; T v ; } ;
static const size_t value = sizeof( Helper ) - sizeof( T ) ;

Think about what the expression above does when T = char &.

Bingo. That's what I hadn't thought of.

I'm not sure that it's all that useful to ask the alignment of
something that the standard says might not occupy memory. On
the other hand, for most people, the case is probably more
likely to occur in practice that is the case of a word addressed
machine (unless you're a mainframes programmer, and your company
buys from Unisys). A good library should probably handle both
(i.e. word addressed machines, and the alignment of references)
correctly.

(The simplest solution would probably be to use both techniques,
forcing an error if the results weren't equal. That would
probably handle 99% of the cases, and would cause a compile time
error for the cases it didn't handle. Otherwise, I think that
it should be possible to use some metaprogramming tricks to use
one technique for references, and the other otherwise.)

 

[Chris Thomasson]

Thank you all for your time and energy!

Humm... This thread might be of interest to this group. I say this simply
because current C++ has no concept of threads... I can allow you to create a
single-threaded allocator in C++, and transform it into a full-blown
scaleable mulit-threaded one:

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/eb87f9cb2cb62d84


No kidding!


So, all of your single threaded C++ allocators can be transformed into
multi-threaded versions, simply by applying a simple lock-free algorithm I
invented.


Any thoughts? Could the technology/method I invented be of use to you or
your company?

 

[Chris Thomasson]

Here is the caveat!

I need to be able to create an instance of your single-threaded allocator by
using extern "C" Create/Destroy function pointers.

 

[Chris Thomasson]

Here is some updated rough-example code:

http://appcore.home.comcast.net/vzoom/malloc/example.cpp


Notice any problems right off the bat?

 

[Chris Thomasson]

One more quick question...

wrt overloading global new and delete operators...

struct alignchar {
char m_buf;
};

void* :perator new(size_t sz) {
// alloc and align buf on sizeof(alignchar) boundary
char* const buf = ::mymalloc_aligned(sz, sizeof(alignchar));
if (! buf) { throw std::bad_alloc(); }
return buf ;
}

void :perator delete(void *buf) {
::myfree(buf);
}


Is that sufficient alignment? AFAICT, void* :perator new(size_t) does not
have to align for the specific C++ type... It just has to mimic malloc
alignment requirements right?

And, the size variable (e.g., size_t sz) passed to the void* :perator
new(size_t) function when new is called with any type should be large enough
to accommodate the alignment for those types?


Thanks.

 

[James Kanze]

One more quick question...

wrt overloading global new and delete operators...

struct alignchar {
char m_buf;
};

Not sure what you're trying to achieve here, but on all of the
platforms I have access to, sizeof( alignchar ) is 1. About the
only cases where I would expect something different would be on
a word addressed machine.

void* :perator new(size_t sz) {
// alloc and align buf on sizeof(alignchar) boundary
char* const buf = ::mymalloc_aligned(sz, sizeof(alignchar));
if (! buf) { throw std::bad_alloc(); }
return buf ;
}

void :perator delete(void *buf) {
::myfree(buf);
}

Is that sufficient alignment? AFAICT, void* :perator new(size_t) does not
have to align for the specific C++ type... It just has to mimic malloc
alignment requirements right?

The returned address should be sufficiently aligned for any data
type. Just like malloc, yes.

And, the size variable (e.g., size_t sz) passed to the void* :perator
new(size_t) function when new is called with any type should be large enough
to accommodate the alignment for those types?

Run that by me again. There's no relationship between the size
argument and the alignment requirements for operator new.
Although logically... my machine requires an alignment of 8 for
double, but it doesn't make much sense to require operator
new(4) to return memory aligned on an 8 byte boundary, because
there's no way you can write anything larger than a float or an
int into the returned memory, and they only require an alignment
of 4. But the requirement in the standard (§3.7.3.1) is clear:
"The pointer returned shall be suitably aligned so that it can
be converted to a pointer of any complete object type and then
used to access the object or array in the storage allocated."
"Any complete object type", and not "Any complete object type
which will fit in the allocated memory".

The usual way to determine alignment of a type T, I believe, is
something like:

struct AlignOfT { char a ; T b ; } ;
size_t alignOfT() { return offsetof( AlignOfT, b ) ; }

(This only works for POD types, of course.)

If you want to ensure alignment for any possible type, use a
union of all the basic types, plus a few pointers (to char, to a
struct, to a function, etc.) for T in the above. It's not
formally guaranteed by the standard, but it should work on any
real platform.