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?

On Mon, 12 Jan 2004 12:25:22 -0500, Brian Genisio
<Br**********@yahoo.com> 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 ::operator 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
<Br**********@yahoo.com> 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 ::operator 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

tom_usenet wrote:

On Mon, 12 Jan 2004 12:25:22 -0500, Brian Genisio
<Br**********@yahoo.com> 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 ::operator 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

On Mon, 12 Jan 2004 12:25:22 -0500, Brian Genisio
<Br**********@yahoo.com> 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)
{
}

Brian Genisio wrote:
Ok, I figured it out:

std::list<int, my_allocator<int> > myList(my_allocator<int>(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
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::pointer 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.

"Brian Genisio" <Br**********@yahoo.com> wrote in message
news:40**************@yahoo.com...

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.

On Mon, 12 Jan 2004 19:21:23 -0000, "Nick Hounsome"
<nh***@blueyonder.co.uk> 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 INTERCHANGEABLEAND 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 - makesthem 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::pointer 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 templatearen'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

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.

allocator for a node is constructed from an int allocator. There still seems to be a missing copy constructor, though.

"tom_usenet" <to********@hotmail.com> wrote in message
news:qi********************************@4ax.com.. .

On Mon, 12 Jan 2004 19:21:23 -0000, "Nick Hounsome"
<nh***@blueyonder.co.uk> 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 BEINTERCHANGEABLE >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'.

I don't know a library that doesn't support it other than SGI's, and I
know about most standard library implementations. STLport is available
for SGI anyway. Stateful allocators work on platforms as obscure as
QNX and Tandem.

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.

They actually document the old behaviour (stateless allocators):
http://www.sgi.com/tech/stl/alloc.html

The code does seem to support stateful allocators to some extent, but
it is unfinished.

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.

STLport works with Metrowerks, so you could always use that. But, like
I said, Metrowerks almost certainly supports that (since they have
quite an advanced library implementation, with type_traits, etc.), I
just don't have copy to check it with. Howard Hinnant might be reading
though...

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::pointer 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.

You might want to lobby for 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 standardtemplate >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.

Yes, if your code is tied closely to the decision. Still, the time
saved using STL rather than some custom containers that could use
stateful allocators (assuming you needed them) can be spent porting
the code.
Another thing that you should consider is that you are advocating designing
to de facto standards rather than
internationaly agreed ones..
Are you suggesting that all compilers comply with international
standards? This particular de facto standard feature (stateful
allocators) is far more portable than many "internationally agreed"
standard features. e.g. template template parameters, two phase name
lookup, template friends, etc. It is even recommended by the
international standard.
You don't want to go there - suppose Microsoft bring out "MSTL" with plenty
of useful "extra features" that
maybe only work with .NET.
In most software products, at least 10% of the code has to rely on
implementation defined behaviour and libraries. If you encapsulate
your use of allocators and containers, then using stateful allocators
isn't going to make that noticeably worse. Or you can take a slight
risk and not encapsulate, it's up to you. I wouldn't lose sleep over
such a decision, since if you do have to port to an obscure platform
with an out of date (or, gulp, no) STL, far bigger problems are going
to rear their heads.
Java was saved because Sun owned it but C++ doesn't have the same legal
status.