Prev: Class & Instance thereof having same Name.
Next: templated virtual functions??
From: Raoul Gough on 8 Apr 2008 07:54
I guess a fairly standard trick when implementing a custom free-list
allocator is to re-use the start of the user-data block for the "next"
pointer of the free list. This could look something like the following

template<typename T>
void allocator<T>::deallocate(void* userData)
{
// Assume T is big enough for a void*. Store the link to the next
// free block
*static_cast<void**>(userData) = freeList_;

// Make this block the head of freeList
freeList_ = userData;
}

I'm not sure if that's the exact signature for a standard allocator,
but I think the idea is clear. Unfortunately, this is nonportable
because it can violate strict aliasing. Assume that we have
allocator<int>, and we do something like this:

int Foo::bar(int* data)
{
int result = *data;
allocator_.deallocate(data);
return result;
}

When the compiler inlines the deallocate function, we end up with
this:

int result = *data;
*static_cast<void **>(data) = allocator_.freeList_;

So we have two aliases to *data, one of which is int& and one of which
is void*&. We're trying to re-use the same location to store an int
*and* a void* at the same time. I remember seeing a case (with g++ and
its strict-aliasing optimizations) where the compiler reordered the
load and store of *data, meaning that the free list pointer overwrites
the user data before the user data gets read.

The example should probably destroy the int object as below, but from
memory this didn't affect the behaviour in the particular case I
saw...

int result = *data;
data->~int();
allocator_.deallocate(data);

So I guess I have a few questions, firstly should the version with the
destructor work portably, and if not, is there a portable way to make
it work? How about if it doesn't call the destructor?

--
Cheers,
Raoul.

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Chris Thomasson on 8 Apr 2008 12:43
"Raoul Gough" <RaoulGough(a)yahoo.co.uk> wrote in message
news:c12cbf5c-f861-4fbb-a5d5-a40298f32dd2(a)q1g2000prf.googlegroups.com...
>I guess a fairly standard trick when implementing a custom free-list
> allocator is to re-use the start of the user-data block for the "next"
> pointer of the free list. This could look something like the following
>
> template<typename T>
> void allocator<T>::deallocate(void* userData)
> {
> // Assume T is big enough for a void*. Store the link to the next
> // free block
> *static_cast<void**>(userData) = freeList_;
>
> // Make this block the head of freeList
> freeList_ = userData;
> }
[...]

Well, you could use "something" like:


<code-sketch which should compile>
_________________________________________________________________
#include <cstdio>


template<typename T>
class allocator {
union node {
T m_obj;
node* m_next;
};

node* m_head;
unsigned m_count;
unsigned const m_maxdepth;

public:
allocator(unsigned maxdepth = 100)
: m_head(NULL), m_count(0), m_maxdepth(100) {
}

~allocator() {
node* n = m_head;
while (n) {
node* next = n->m_next;
std::printf("(%p)-delete\n", (void*)n);
delete n;
n = next;
}
}

public:
T* create() {
node* n = m_head;
if (! n) {
n = new node;
std::printf("(%p)-cache miss\n", (void*)n);
} else {
--m_count;
m_head = n->m_next;
std::printf("(%p)-cache hit\n", (void*)n);
}
return &n->m_obj;
}

void destroy(T* const obj) {
node* const n = reinterpret_cast<node*>(obj);
if (m_count < m_maxdepth) {
n->m_next = m_head;
m_head = n;
++m_count;
std::printf("(%p)-cached\n", (void*)n);
} else {
delete n;
std::printf("(%p)-delete\n", (void*)n);
}
}
};



#define DEPTH() 6
int main() {
{
int i;
char* ptrs[DEPTH()] = { NULL };
allocator<char> alloc;
for (i = 0; i < DEPTH(); ++i) {
ptrs[i] = alloc.create();
}
for (i = 0; i < DEPTH(); ++i) {
alloc.destroy(ptrs[i]);
}
for (i = 0; i < DEPTH(); ++i) {
ptrs[i] = alloc.create();
}
for (i = 0; i < DEPTH(); ++i) {
alloc.destroy(ptrs[i]);
}
}

{
int i;
double* ptrs[DEPTH()] = { NULL };
allocator<double> alloc;
for (i = 0; i < DEPTH(); ++i) {
ptrs[i] = alloc.create();
}
for (i = 0; i < DEPTH(); ++i) {
alloc.destroy(ptrs[i]);
}
for (i = 0; i < DEPTH(); ++i) {
ptrs[i] = alloc.create();
}
for (i = 0; i < DEPTH(); ++i) {
alloc.destroy(ptrs[i]);
}
}

/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
std::puts("\n\n--------------------------------------------\n\
Press <ENTER> to exit...");
std::getchar();
return 0;
}

_________________________________________________________________



Does that help you at all?


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Chris Thomasson on 9 Apr 2008 04:14

"Chris Thomasson" <cristom(a)comcast.net> wrote in message
news:PZadnX7vCIZza2banZ2dnUVZ_ualnZ2d(a)comcast.com...
> "Raoul Gough" <RaoulGough(a)yahoo.co.uk> wrote in message
> news:c12cbf5c-f861-4fbb-a5d5-a40298f32dd2(a)q1g2000prf.googlegroups.com...
>>I guess a fairly standard trick when implementing a custom free-list
>> allocator is to re-use the start of the user-data block for the "next"
>> pointer of the free list. This could look something like the following
>>
>> template<typename T>
>> void allocator<T>::deallocate(void* userData)
>> {
>> // Assume T is big enough for a void*. Store the link to the next
>> // free block
>> *static_cast<void**>(userData) = freeList_;
>>
>> // Make this block the head of freeList
>> freeList_ = userData;
>> }
> [...]
>
> Well, you could use "something" like:
>
>
> <code-sketch which should compile>
> _________________________________________________________________
[...]
> _________________________________________________________________
>
>
>
> Does that help you at all?

That was a very simple sketch I typed in the newsreader; it seems to compile
just fine, but has some problems. One, it does not call any dtor until a
cache overflow, or allocator destruction. It does not call ctors on every
allocation. It has a bug in the ctor:

allocator(unsigned maxdepth = 100)
: m_head(NULL), m_count(0), m_maxdepth(100) {
}

should be:

allocator(unsigned maxdepth = 100)
: m_head(NULL), m_count(0), m_maxdepth(maxdepth) {
}

of course.



Anyway, I think this should hopefully give you a __very_rough__ idea on how
to proceed... I guess the code as-is would be analogous to a cache
allocator...

;^)


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Raoul Gough on 9 Apr 2008 08:56
On Apr 9, 4:43 am, "Chris Thomasson" <cris...(a)comcast.net> wrote:
> "Raoul Gough" <RaoulGo...(a)yahoo.co.uk> wrote in message
>
> news:c12cbf5c-f861-4fbb-a5d5-a40298f32dd2(a)q1g2000prf.googlegroups.com...>I guess a fairly standard trick when implementing a custom free-list
> > allocator is to re-use the start of the user-data block for the "next"
> > pointer of the free list. This could look something like the following
>
> > template<typename T>
> > void allocator<T>::deallocate(void* userData)
> > {
> > // Assume T is big enough for a void*. Store the link to the next
> > // free block
> > *static_cast<void**>(userData) = freeList_;
>
> > // Make this block the head of freeList
> > freeList_ = userData;
> > }
>
> [...]
>
> Well, you could use "something" like:
[snip]
> union node {
> T m_obj;
> node* m_next;
> };
[snip]
> void destroy(T* const obj) {
> node* const n = reinterpret_cast<node*>(obj);
> if (m_count < m_maxdepth) {
> n->m_next = m_head;
> m_head = n;
[snip]

This code has a significant restriction that the original code did
not: it only works for types T that can be stored in a union. From
section 9.5 of the '98 standard:

"An object of a class with a non-trivial constructor (12.1), a non-
trivial copy constructor (12.8), a non-trivial destructor (12.4), or a
non-trivial copy assignment operator (13.5.3, 12.8) cannot be a member
of a union"

Also, I'm not entirely sure that it addresses the fundamental aliasing
problem of reusing the same storage. Effectively, we'd end up with the
following inlined code:

int foo(int* p)
{
int result = *p;
reinterpret_cast<union_type*>(p)->m_next = m_head;

Interestingly perhaps, what we *don't* have is this:

int foo(union_type* p)
{
int result = p->m_obj;
p->m_next = m_head;

where it's clearer that the two expressions reference the same (union)
type and might alias the same (union) object. I'm not sure about the
exact semantics of unions, so I'm a little uncertain whether this
actually solves the basic problem (even for the restricted cases where
it would compile).

--
Cheers,
Raoul.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Chris Thomasson on 11 Apr 2008 02:36
"Raoul Gough" <RaoulGough(a)yahoo.co.uk> wrote in message
news:1a2ee2eb-6db0-4ff2-a82f-b64bd5c5c310(a)s13g2000prd.googlegroups.com...
> On Apr 9, 4:43 am, "Chris Thomasson" <cris...(a)comcast.net> wrote:
>> "Raoul Gough" <RaoulGo...(a)yahoo.co.uk> wrote in message
>>
>> news:c12cbf5c-f861-4fbb-a5d5-a40298f32dd2(a)q1g2000prf.googlegroups.com...>I
>> guess a fairly standard trick when implementing a custom free-list
>> > allocator is to re-use the start of the user-data block for the "next"
>> > pointer of the free list. This could look something like the following
>>
>> > template<typename T>
>> > void allocator<T>::deallocate(void* userData)
>> > {
>> > // Assume T is big enough for a void*. Store the link to the next
>> > // free block
>> > *static_cast<void**>(userData) = freeList_;
>>
>> > // Make this block the head of freeList
>> > freeList_ = userData;
>> > }
>>
>> [...]
>>
>> Well, you could use "something" like:
> [snip]
>> union node {
>> T m_obj;
>> node* m_next;
>> };
> [snip]
>> void destroy(T* const obj) {
>> node* const n = reinterpret_cast<node*>(obj);
>> if (m_count < m_maxdepth) {
>> n->m_next = m_head;
>> m_head = n;
> [snip]
>
> This code has a significant restriction that the original code did
> not: it only works for types T that can be stored in a union. From
> section 9.5 of the '98 standard:
[...]

You could always use:

struct node {
T m_obj;
node* m_next;
};


Are you going for an allocator that is 100% standard?

http://groups.google.com/group/comp.arch/browse_frm/thread/24c40d42a04ee855


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 |  Next  |  Last
Pages: 1 2
Prev: Class & Instance thereof having same Name.
Next: templated virtual functions??