Idea for custom thread-safe STL allocator?

Hi all,

I am developing some software, that creates a tree of information. For
each node, currently I am overriding the new operator, because it is a
requirement that after initialization, no new memory may be allocated.

It also needs to be thread safe, and each thread has a context, so any
allocation of nodes currently looks like this:

new (context) Node(...);

My allocator uses the context to keep memory from different threads safe.

I want to use STL, and write a custom allocator template for passing to
the STL containers (map and vector specifically).

The only problem, is that I need to figure out a way to have the STL use
the context as well, when it calls the allocator. I cant figure out a
way to tell the custom STL allocator to have a custom parameter stored
in the class before container initialization.

Any ideas?
Brian

On Mon, 12 Jan 2004 12:25:22 -0500, Brian Genisio
<> wrote:

>Hi all,
>
>I am developing some software, that creates a tree of information. For
>each node, currently I am overriding the new operator, because it is a
>requirement that after initialization, no new memory may be allocated.
>
>It also needs to be thread safe, and each thread has a context, so any
>allocation of nodes currently looks like this:
>
>new (context) Node(...);
>
>My allocator uses the context to keep memory from different threads safe.
>
>I want to use STL, and write a custom allocator template for passing to
>the STL containers (map and vector specifically).
>
>The only problem, is that I need to figure out a way to have the STL use
>the context as well, when it calls the allocator. I cant figure out a
>way to tell the custom STL allocator to have a custom parameter stored
>in the class before container initialization.
>
>Any ideas?

template <class T>
class myallocator
{
Context m_context;
public:
//allocator typedefs

template <class U>
struct rebind
{
typedef myallocator<U> other;
};

myallocator(Context const& context)
:m_context(context)
{
}

template <class U>
myallocator(myallocator<U> const& other)
:m_context(other.m_context)
{
}

template <class U>
myallocator& operator=(myallocator<U> const& other)
{
m_context = other.m_context;
return *this;
}

T* allocate(size_type n, void* hint = 0)
{
return :perator new(n * sizeof(T), m_context);
}

//etc.
};

Tom

C++ FAQ: http://www.parashift.com/c++-faq-lite/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html

tom_usenet wrote:

> On Mon, 12 Jan 2004 12:25:22 -0500, Brian Genisio
> <> wrote:
>
>
>>Hi all,
>>
>>I am developing some software, that creates a tree of information. For
>>each node, currently I am overriding the new operator, because it is a
>>requirement that after initialization, no new memory may be allocated.
>>
>>It also needs to be thread safe, and each thread has a context, so any
>>allocation of nodes currently looks like this:
>>
>>new (context) Node(...);
>>
>>My allocator uses the context to keep memory from different threads safe.
>>
>>I want to use STL, and write a custom allocator template for passing to
>>the STL containers (map and vector specifically).
>>
>>The only problem, is that I need to figure out a way to have the STL use
>>the context as well, when it calls the allocator. I cant figure out a
>>way to tell the custom STL allocator to have a custom parameter stored
>>in the class before container initialization.
>>
>>Any ideas?
>
>
> template <class T>
> class myallocator
> {
> Context m_context;
> public:
> //allocator typedefs
>
> template <class U>
> struct rebind
> {
> typedef myallocator<U> other;
> };
>
> myallocator(Context const& context)
> :m_context(context)
> {
> }
>
> template <class U>
> myallocator(myallocator<U> const& other)
> :m_context(other.m_context)
> {
> }
>
> template <class U>
> myallocator& operator=(myallocator<U> const& other)
> {
> m_context = other.m_context;
> return *this;
> }
>
> T* allocate(size_type n, void* hint = 0)
> {
> return :perator new(n * sizeof(T), m_context);
> }
>
> //etc.
> };
>
> Tom
>
> C++ FAQ: http://www.parashift.com/c++-faq-lite/
> C FAQ: http://www.eskimo.com/~scs/C-faq/top.html

Thanks for the info... I is very useful. The only question I have: How
does m_context ever get set?

Lets say I use a list of ints:

std::list<int, myallocator<int>> myList;

How do I get the context information in to the container's copy of the
allocator?

Thanks a lot,
Brian

Brian Genisio wrote:
> tom_usenet wrote:
>
>> On Mon, 12 Jan 2004 12:25:22 -0500, Brian Genisio
>> <> wrote:
>>
>>
>>> Hi all,
>>>
>>> I am developing some software, that creates a tree of information.
>>> For each node, currently I am overriding the new operator, because it
>>> is a requirement that after initialization, no new memory may be
>>> allocated.
>>>
>>> It also needs to be thread safe, and each thread has a context, so
>>> any allocation of nodes currently looks like this:
>>>
>>> new (context) Node(...);
>>>
>>> My allocator uses the context to keep memory from different threads
>>> safe.
>>>
>>> I want to use STL, and write a custom allocator template for passing
>>> to the STL containers (map and vector specifically).
>>>
>>> The only problem, is that I need to figure out a way to have the STL
>>> use the context as well, when it calls the allocator. I cant figure
>>> out a way to tell the custom STL allocator to have a custom parameter
>>> stored in the class before container initialization.
>>>
>>> Any ideas?
>>
>>
>>
>> template <class T>
>> class myallocator
>> {
>> Context m_context;
>> public:
>> //allocator typedefs
>>
>> template <class U>
>> struct rebind
>> {
>> typedef myallocator<U> other;
>> };
>>
>> myallocator(Context const& context) :m_context(context)
>> {
>> }
>>
>> template <class U>
>> myallocator(myallocator<U> const& other)
>> :m_context(other.m_context)
>> {
>> }
>>
>> template <class U>
>> myallocator& operator=(myallocator<U> const& other)
>> {
>> m_context = other.m_context;
>> return *this;
>> }
>>
>> T* allocate(size_type n, void* hint = 0)
>> { return :perator new(n * sizeof(T), m_context);
>> }
>>
>> //etc.
>> };
>>
>> Tom
>>
>> C++ FAQ: http://www.parashift.com/c++-faq-lite/
>> C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
>
>
> Thanks for the info... I is very useful. The only question I have: How
> does m_context ever get set?
>
> Lets say I use a list of ints:
>
> std::list<int, myallocator<int>> myList;

Careful.

std::list<int, myallocator<int> > myList;

> How do I get the context information in to the container's copy of the
> allocator?
>
> Thanks a lot,
> Brian
>

Brian Genisio wrote:

> tom_usenet wrote:
>
>> On Mon, 12 Jan 2004 12:25:22 -0500, Brian Genisio
>> <> wrote:
>>
>>
>>> Hi all,
>>>
>>> I am developing some software, that creates a tree of information.
>>> For each node, currently I am overriding the new operator, because it
>>> is a requirement that after initialization, no new memory may be
>>> allocated.
>>>
>>> It also needs to be thread safe, and each thread has a context, so
>>> any allocation of nodes currently looks like this:
>>>
>>> new (context) Node(...);
>>>
>>> My allocator uses the context to keep memory from different threads
>>> safe.
>>>
>>> I want to use STL, and write a custom allocator template for passing
>>> to the STL containers (map and vector specifically).
>>>
>>> The only problem, is that I need to figure out a way to have the STL
>>> use the context as well, when it calls the allocator. I cant figure
>>> out a way to tell the custom STL allocator to have a custom parameter
>>> stored in the class before container initialization.
>>>
>>> Any ideas?
>>
>>
>>
>> template <class T>
>> class myallocator
>> {
>> Context m_context;
>> public:
>> //allocator typedefs
>>
>> template <class U>
>> struct rebind
>> {
>> typedef myallocator<U> other;
>> };
>>
>> myallocator(Context const& context) :m_context(context)
>> {
>> }
>>
>> template <class U>
>> myallocator(myallocator<U> const& other)
>> :m_context(other.m_context)
>> {
>> }
>>
>> template <class U>
>> myallocator& operator=(myallocator<U> const& other)
>> {
>> m_context = other.m_context;
>> return *this;
>> }
>>
>> T* allocate(size_type n, void* hint = 0)
>> { return :perator new(n * sizeof(T), m_context);
>> }
>>
>> //etc.
>> };
>>
>> Tom
>>
>> C++ FAQ: http://www.parashift.com/c++-faq-lite/
>> C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
>
>
> Thanks for the info... I is very useful. The only question I have: How
> does m_context ever get set?
>
> Lets say I use a list of ints:
>
> std::list<int, myallocator<int>> myList;
>
> How do I get the context information in to the container's copy of the
> allocator?
>
> Thanks a lot,
> Brian
>

Ok, I figured it out:

std::list<int, my_allocator<int> > myList(my_allocator<int>(context));

Thanks,
Brian

"tom_usenet" <> wrote in message
news:...
> On Mon, 12 Jan 2004 12:25:22 -0500, Brian Genisio
> <> wrote:
>
> >Hi all,
> >
> >I am developing some software, that creates a tree of information. For
> >each node, currently I am overriding the new operator, because it is a
> >requirement that after initialization, no new memory may be allocated.
> >
> >It also needs to be thread safe, and each thread has a context, so any
> >allocation of nodes currently looks like this:
> >
> >new (context) Node(...);
> >
> >My allocator uses the context to keep memory from different threads safe.
> >
> >I want to use STL, and write a custom allocator template for passing to
> >the STL containers (map and vector specifically).
> >
> >The only problem, is that I need to figure out a way to have the STL use
> >the context as well, when it calls the allocator. I cant figure out a
> >way to tell the custom STL allocator to have a custom parameter stored
> >in the class before container initialization.
> >
> >Any ideas?
>
> template <class T>
> class myallocator
> {
> Context m_context;
> public:
> //allocator typedefs
>
> template <class U>
> struct rebind
> {
> typedef myallocator<U> other;
> };
>
> myallocator(Context const& context)
> :m_context(context)
> {
> }

unfortunately the standard (20.1.5 para 4) says that implementations of
standard containers are allowed to assume that
"ALL INSTANCES OF A GIVEN ALLOCATOR TYPE ARE REQUIRED TO BE INTERCHANGEABLE
AND ALWAYS COMPARE EQUAL TO EACH OTHER"

This draconian requirement effectively means that you cannot (usefully) have
non-static data members in an allocator which - as far as I can see - makes
them pretty well useless.

What you could do is look up context in a map<pthread_t,Context> using
pthread_self()

P.S.Another stupid feature of allocators is the optional hint argument of
the allocate method. This is totally useless because the standard template
aren't required to use it.

"Brian Genisio" <> wrote in message
news:...
> Brian Genisio wrote:

>
> Ok, I figured it out:
>
> std::list<int, my_allocator<int> >
myList(my_allocator<int>(context));
>

These solutions are non-portable, and are likely not to work as
expected. The standard allows implementations to make the following
assumption about allocator types:

- All instances of a given allocator type are required to be
interchangeable and always compare equal to
each other. (20.1.5)

Your allocators do not satisfy this requirement. The list you define
above will probably never use the allocator you passed it to allocate
an int. Instead, it will use an allocator of type

my_allocator<int>::rebind< node >:ther

where node is some internal type. The context information will likely
not be preserved.

Jonathan

On Mon, 12 Jan 2004 19:21:23 -0000, "Nick Hounsome"
<> wrote:

>unfortunately the standard (20.1.5 para 4) says that implementations of
>standard containers are allowed to assume that
>"ALL INSTANCES OF A GIVEN ALLOCATOR TYPE ARE REQUIRED TO BE INTERCHANGEABLE
>AND ALWAYS COMPARE EQUAL TO EACH OTHER"
>
>This draconian requirement

I don't think it's considered draconian by implementors!

> effectively means that you cannot (usefully) have
>non-static data members in an allocator which - as far as I can see - makes
>them pretty well useless.

On the contrary, all the common standard library implementations have
waived that clause. In particular, Dinkumware's lib (used all over the
place), libstdc++ and STLport all allow stateful allocators, and that
covers most compilers. SGI (and libcomo) allows them, but doesn't seem
to swap them when swapping containers. I'd be very surprised if
Metrowerks didn't support them fully. Some libraries optimize the
common case of stateless allocators.

As well as the compare-equal clause, there's also the "encapsulate
more general memory models" recommendation, that Dinkumware have taken
up I believe (by not relying on alloc:ointer being T*), but I'm not
sure about others.

The clause exists because not enough was known about allocators when
the standard was written. Experience now leads to the conclusion that
having stateful allocators is a good thing (since it allows use of
arbitrary pools, shared memory, etc.) - I suspect the next standard
will mandate it.

>What you could do is look up context in a map<pthread_t,Context> using
>pthread_self()
>
>P.S.Another stupid feature of allocators is the optional hint argument of
>the allocate method. This is totally useless because the standard template
>aren't required to use it.

And I don't know of an implementation that does use that hint
argument, no. Anyone?

Tom

C++ FAQ: http://www.parashift.com/c++-faq-lite/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html

On Mon, 12 Jan 2004 12:38:20 -0700, "Jonathan Turkanis"
<> wrote:

>
>"Brian Genisio" <> wrote in message
>news:...
>> Brian Genisio wrote:
>
>>
>> Ok, I figured it out:
>>
>> std::list<int, my_allocator<int> >
>myList(my_allocator<int>(context));
>>
>
>These solutions are non-portable, and are likely not to work as
>expected.

They are portable, just not mandated by the standard. Do you know a
recent compiler/library that won't work with the above?

The simple way to force a compiler error on a "dodgy" library is not
to have a default constructor for your allocator.

Tom

C++ FAQ: http://www.parashift.com/c++-faq-lite/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html

"tom_usenet" <> wrote in message
news:...
> On Mon, 12 Jan 2004 19:21:23 -0000, "Nick Hounsome"
> <> wrote:
>
> >unfortunately the standard (20.1.5 para 4) says that implementations of
> >standard containers are allowed to assume that
> >"ALL INSTANCES OF A GIVEN ALLOCATOR TYPE ARE REQUIRED TO BE
INTERCHANGEABLE
> >AND ALWAYS COMPARE EQUAL TO EACH OTHER"
> >
> >This draconian requirement
>
> I don't think it's considered draconian by implementors!
>
> > effectively means that you cannot (usefully) have
> >non-static data members in an allocator which - as far as I can see -
makes
> >them pretty well useless.
>
> On the contrary, all the common standard library implementations have

Please define 'common'.

> waived that clause. In particular, Dinkumware's lib (used all over the
> place), libstdc++ and STLport all allow stateful allocators, and that
> covers most compilers. SGI (and libcomo) allows them, but doesn't seem
> to swap them when swapping containers. I'd be very surprised if

What good is that then? swapping containers is quite common - in fact its
pretty much a standard idiom for freeing the
spare space in a std::vector. What is worse I doubt that this is documented
because it doesn't have to be to be
standard compliant.

> Metrowerks didn't support them fully. Some libraries optimize the

What if it doesn't?
If I tell my boss I've written 100000 lines of portable code and he decides
that we are going to use Metrowerks then I doubt that saying I'm surprised
that they haven't implemented containers that way will keep my job.

> common case of stateless allocators.
>
> As well as the compare-equal clause, there's also the "encapsulate
> more general memory models" recommendation, that Dinkumware have taken
> up I believe (by not relying on alloc:ointer being T*), but I'm not
> sure about others.
>
> The clause exists because not enough was known about allocators when
> the standard was written. Experience now leads to the conclusion that
> having stateful allocators is a good thing (since it allows use of
> arbitrary pools, shared memory, etc.) - I suspect the next standard
> will mandate it.

I look forward to it.

>
> >What you could do is look up context in a map<pthread_t,Context> using
> >pthread_self()
> >
> >P.S.Another stupid feature of allocators is the optional hint argument of
> >the allocate method. This is totally useless because the standard
template
> >aren't required to use it.
>
> And I don't know of an implementation that does use that hint
> argument, no. Anyone?
>

Again - it doesn't matter if its only 1 in 100 libraries doesn't support
it - if that is the one that you have to use
you are going to be in trouble.

Another thing that you should consider is that you are advocating designing
to de facto standards rather than
internationaly agreed ones..
You don't want to go there - suppose Microsoft bring out "MSTL" with plenty
of useful "extra features" that
maybe only work with .NET.
Java was saved because Sun owned it but C++ doesn't have the same legal
status.

> Tom
>
> C++ FAQ: http://www.parashift.com/c++-faq-lite/
> C FAQ: http://www.eskimo.com/~scs/C-faq/top.html