Idea for custom thread-safe STL allocator?

[Brian Genisio]

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

 

[tom_usenet]

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

 

[Brian Genisio]

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

 

[Jeff Schwab]

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.

 

[Brian Genisio]

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

 

[Nick Hounsome]

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.

 

[Jonathan Turkanis]

Brian Genisio wrote:

Ok, I figured it out:

std::list<int, my_allocator<int> >

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

 

[tom_usenet]

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

 

[tom_usenet]

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

 

[Nick Hounsome]

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


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.

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.

 

[Jonathan Turkanis]

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.

You are half right (and I am half wrong). By portable I just meant
guaranteed by the standard to work That is why I made the distinction
between being portable and working as expected.

I was not aware that all recent libraries had decided not to take
advantage of the clause I cited, but I did examine Dinkumware before
posting.

I must admit I missed the templated constructor in the example
mentioned, which should transfer the state properly on library
implementations that allow stateful allocators, e.g., when an
allocator for a node is constructed from an int allocator. There still
seems to be a missing copy constructor, though.

Regards,
Jonathan

 

[Jonathan Turkanis]

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

The default is okay here.

Jonathan

 

[tom_usenet]

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.

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.

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

I look forward to it.

You might want to lobby for it...

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.

If you want to tie your code to a single platform, I'd recommend the
Java platform, since it is widely available. Others might recommend
the .NET platform, which is less widely available, but allows more
implementation languages (including C++).

For a portable cross-platform C++ app, you could do worse than to
follow the Mozilla guidelines, which ban templates, namespaces and
exceptions entirely:
http://www.mozilla.org/hacking/portable-cpp.html

If you want to use "Modern C++", then relying on stateful allocators
may be the least of your portability worries.

Tom

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