Reusing user data block in (de)allocator
Raoul Gough
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! ]
Chris Thomasson
news:c12cbf5c-f861-4fbb...@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?
--
Chris Thomasson
"Chris Thomasson" <cri...@comcast.net> wrote in message
news:PZadnX7vCIZza2ba...@comcast.com...
> "Raoul Gough" <Raoul...@yahoo.co.uk> wrote in message
> news:c12cbf5c-f861-4fbb...@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...
;^)
Raoul Gough
> "Raoul Gough" <RaoulGo...@yahoo.co.uk> wrote in message
>
> news:c12cbf5c-f861-4fbb...@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:
> union node {
> T m_obj;
> node* m_next;
> };
> 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;
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.
Chris Thomasson
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
Chris Thomasson
> "Raoul Gough" <Raoul...@yahoo.co.uk> wrote in message
> news:1a2ee2eb-6db0-4ff2...@s13g2000prd.googlegroups.com...
>> On Apr 9, 4:43 am, "Chris Thomasson" <cris...@comcast.net> wrote:
>>> "Raoul Gough" <RaoulGo...@yahoo.co.uk> wrote in message
>>>
>>> news:c12cbf5c-f861-4fbb...@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
>>>
>>
>> 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?
If forgot to add:
'if not:'
>
> http://groups.google.com/group/comp.arch/browse_frm/thread/24c40d42a04ee855
The exact posts I wanted to cite within that link are:
http://groups.google.com/group/comp.programming.threads/msg/1d3aeaa6ebf5181f
http://groups.google.com/group/comp.programming.threads/msg/bc019dc04362be41
Raoul Gough
> "Chris Thomasson" <cri...@comcast.net> wrote in message
> news:d4mdnRqgEf3bu2La...@comcast.com...
>> "Raoul Gough" <Raoul...@yahoo.co.uk> wrote in message
>> news:1a2ee2eb-6db0-4ff2...@s13g2000prd.googlegroups.com...
>>> On Apr 9, 4:43 am, "Chris Thomasson" <cris...@comcast.net> wrote:
>>>> "Raoul Gough" <RaoulGo...@yahoo.co.uk> wrote in message
>>>>
>>>> news:c12cbf5c-f861-4fbb...@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
>>>>
> [...]
>>>
>>> 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;
>> };
>>
Yes, I think that would work, but it does so my avoiding the re-use of
the same address for different types of object. I was hoping to get an
insight into whether such reuse can be done portably. I think your
union example might solve that problem for pod-like structs, but I'm
not exactly clear on this point after referring to the standard.
The situation is perhaps even less clear in C, because
1) it doesn't have destructors
2) it doesn't have templates
So if you wanted to have a free-list allocator in C that re-used the
user-data space for its own "next" link, you would not be able
explicitly to destroy the user data object, nor could you (in general)
have a union that contained both the allocator's "next" pointer type
and the user data type.
There's some interesting background to this in Krister Walfridsson's
posting to tech...@netbsd.org "Aliasing, pointer casts and gcc 3.3"
http://mail-index.netbsd.org/tech-kern/2003/08/11/0001.html
By the way, I think casting the user-data pointer to char* and using
memcpy to copy the "head of free-list" pointer probably solves the
aliasing problem. Maybe that's the only portable way to do it...
--
Cheers,
Raoul.