Discussion:
C++ proposal to improve allocator interface
(too old to reply)
Marcelo Zimbres
2016-01-18 20:08:58 UTC
Permalink
Hi,

I would like to ask for some feedback on a non-breaking proposal to
the C++ standard, that aims to reduce allocator complexity, support
realtime allocation and improve performance of node-based containers
through the addition
of overloads of the allocate and deallocate member functions. The PDF
can be found here.

https://github.com/mzimbres/rtcpp/blob/master/doc/proposal_allocator.pdf

A previous discussion on the subject can be found here [1].

Best regards,
Marcelo

[1] http://www.open-std.org/pipermail/embedded/2014-December/000335.html
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
David Krauss
2016-01-19 01:43:49 UTC
Permalink
https://github.com/mzimbres/rtcpp/blob/master/doc/proposal_allocator.pdf <https://github.com/mzimbres/rtcpp/blob/master/doc/proposal_allocator.pdf>
I hope you don’t mind me summarizing: The proposal is to add an allocate() method which is equivalent to allocate(1). The benefit is to bless allocators which avoid the complexity of variable-sized allocation blocks.

Why can’t such allocators simply return 1 from max_size()? This would let array-based containers work up to an array size of 1, which should be good enough for std::deque at least. Perhaps allocator_traits::max_size should be constexpr if a.max_size() is a constant expression. (Come to think of it, then deque<T,A> could detect this condition, and drop the MoveAssignable requirement on T.)

Do allocators following the proposal have no allocate(size_type) overload at all, or is it defined as deleted? That would break compatibility with all allocator-aware containers, which seems to level the balance with the fact that max_size currently tends to be ignored.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Marcelo Zimbres
2016-01-19 19:03:53 UTC
Permalink
I hope you don’t mind me summarizing: The proposal is to add an allocate()
method which is equivalent to allocate(1). The benefit is to bless
allocators which avoid the complexity of variable-sized allocation blocks.
Shortly said, that's it, but this is not motivating enough, let me
also shortly explain with a use case, why the currently allocator
interface is not satisfactory, this may be missing in the draft.

Suppose the common situation where I want a linked list with,
say n = 20 elements somewhere in my code. I have two options

A) I simply use std::list<int>.

This is very undesirable for some reasons:
1) Nodes go on the heap. For only 20 elements I would be better
using the stack.
2) The node size is small (~20bytes), it does not make sense allocating
them individually on the heap. Fragmentation begin to play a role
if I have many lists (or bigger n)
3) Big overhead on the heap allocation: all the code inside malloc,
plus system calls and allocation strategies. (I only need 20bytes
of space for a node!)

All this is overkill for a simple list with a couple of elements
(for big n situation gets worser).

B) Use a custom allocator, something like:

std::array<char, 20 * node_size > buffer = {{}};
my_allocator alloc(buffer);

std::list<int, my_allocator<int>> l(alloc);

This is the ideal solution:
1) Nodes on the stack.
2) Buffer is as small as possible.
3) No allocation overhead: I only change some pointers.

This is however not possible in the current allocator interface
due to the fact that allocate(n) may be called with n != 1 and
that means I have to add strategy to handle the many possible
values of n. The size of the buffer is not anymore clear. All the
added complexity is pointless. The proposal tries to "fix" this.
Why can’t such allocators simply return 1 from max_size()? This would let
array-based containers work up to an array size of 1, which should be good
enough for std::deque at least. Perhaps allocator_traits::max_size should be
constexpr if a.max_size() is a constant expression. (Come to think of it,
then deque<T,A> could detect this condition, and drop the MoveAssignable
requirement on T.)
Unordered containers usually need to rebind twice, once for node allocation
and once for array allocation. that means they would need allocate() and
allocate(size_type) as well. I cannot make max_size return 1 for this reason.
Do allocators following the proposal have no allocate(size_type) overload at
all, or is it defined as deleted? That would break compatibility with all
allocator-aware containers, which seems to level the balance with the fact
that max_size currently tends to be ignored.
The allocators can provide both allocate() and allocate(size_type),
but if the typedef
use_node_allocation is defined to std::true_type, then the container should use
allocate() for its node allocations. The proposal is non-breaking.

Marcelo
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Nevin Liber
2016-01-19 19:26:44 UTC
Permalink
Post by Marcelo Zimbres
This is however not possible in the current allocator interface
due to the fact that allocate(n) may be called with n != 1 and
that means I have to add strategy to handle the many possible
values of n.
No you don't. Just assert(n == 1) in your custom allocator. If someone
uses your custom allocator for something other than node based containers,
the assert will fire.
--
Nevin ":-)" Liber <mailto:***@eviloverlord.com> +1-847-691-1404
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Marcelo Zimbres
2016-01-19 19:47:40 UTC
Permalink
Post by Nevin Liber
No you don't. Just assert(n == 1) in your custom allocator. If someone
uses your custom allocator for something other than node based containers,
the assert will fire.
What should I do when the condition n =! 1 is triggered with the client?

If the condition n != 1 holds for a given STL implementation than I either
give up on the custom allocator or add the allocation strategy anyway
(which may be rather complex by the way).

I am aiming for a simple (and efficient) solution, for a simple problem.

Marcelo
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Nevin Liber
2016-01-19 19:54:24 UTC
Permalink
Post by David Krauss
Post by Nevin Liber
No you don't. Just assert(n == 1) in your custom allocator. If someone
uses your custom allocator for something other than node based
containers,
Post by Nevin Liber
the assert will fire.
What should I do when the condition n =! 1 is triggered with the client?
1. Abort. They violated the contract that your allocator should only be
used with node-based containers.

2. Fall back to a different allocator, such as std::allocator. (This may
allow you to use your allocator with almost-node-based containers such as
std::deque; maybe that is what David Krauss was alluding to?)
--
Nevin ":-)" Liber <mailto:***@eviloverlord.com> +1-847-691-1404
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Marcelo Zimbres
2016-01-19 20:25:39 UTC
Permalink
Post by Nevin Liber
1. Abort. They violated the contract that your allocator should only be
used with node-based containers.
Node-based containers can themselves use n != 1. There is no guarantee
for n == 1 in standard, even for node-based containers.
Post by Nevin Liber
2. Fall back to a different allocator, such as std::allocator. (This may
allow you to use your allocator with almost-node-based containers such as
std::deque; maybe that is what David Krauss was alluding to?)
Fall back to std::allocator is undesirable in this simple case for
reasons mentioned
above, specially if I a doing embedded C++. A simple solution should
not require me to
allocate on the heap at all.

There is also the annoying possibility that a node-based container
uses n =! 1 far too often to avoid the overhead of many dynamic
allocations of small blocks (Allocation strategy being built on the container
itself).

Marcelo
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Nevin Liber
2016-01-19 20:58:33 UTC
Permalink
Post by Marcelo Zimbres
Post by Nevin Liber
1. Abort. They violated the contract that your allocator should only be
used with node-based containers.
Node-based containers can themselves use n != 1. There is no guarantee
for n == 1 in standard, even for node-based containers.
IMO that is what we should address. It makes no sense (and can be a
pessimization) for both the container and allocator to be managing space
for nodes, especially since the allocator interface doesn't really give a
way for a container and allocator to negotiate space requests.
--
Nevin ":-)" Liber <mailto:***@eviloverlord.com> +1-847-691-1404
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
David Krauss
2016-01-20 06:19:37 UTC
Permalink
Post by David Krauss
Why can’t such allocators simply return 1 from max_size()? This would let array-based containers work up to an array size of 1, which should be good enough for std::deque at least.
I have no idea what you are talking about with deque. deque is not a node-based container. Could you elaborate?
I’m just considering the effect of passing a node-based allocator to an array-based container. deque could get a bonus feature.

I forgot about the “table of contents” array, though. That’s a fly in the ointment, so node-deque would actually be slightly trickier than an unordered container — ah well.
Post by David Krauss
2. Fall back to a different allocator, such as std::allocator. (This may allow you to use your allocator with almost-node-based containers such as std::deque; maybe that is what David Krauss was alluding to?)
Nah, my max_size suggestion is just the same as your assert suggestion, but without the option of fallback. Fallback is the status quo, anyway, no proposal needed.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Alisdair Meredith
2016-01-20 12:52:25 UTC
Permalink
1) I dislike the idea of narrowing the standard contract, which is wide, but can
throw. If you request more memory than can be supplied by a single request,
throw std::bad_alloc. Otherwise, I agree with the idea that the existing allocator
interface supports allocators optimized for this purpose, and it is no surprise
that they would not work well for ‘vector’, that has contiguous memory requirements.

2) Fall-back allocators may be reasonable. The backing pool must be obtained
from somewhere, and may use a fall-back allocator to grow on demand anyway,
although certainly not all pools would need (or offer) this facility. You can cover
a lot of ground with creative use of the current interface.

Our approach to this issue is to observe that pooling is such a big win, we build
it into our node-based containers (with a generalized pool abstraction build on
top of the allocator interface) so that our containers are pooling, whether or not
the allocator is optimized for this strategy. I know other libraries have looked
into this and stepped back, as the standard containers (other than deque) offer
no interface that would allow the container to give up excessive memory allocated
when a container hits an abnormally high peak size, holding onto that mostly
unused memory until the container is destroyed.

We also have pooling allocators in the Library Fundamentals TS in the polymorphic
memory resources section, and good experience using them over many years at
Bloomberg, which is why we proposed them in the first place! I would be interested
in feedback on how well they work (or not) for others in practice, before inventing
new allocator interfaces to solve the same problem.

AlisdairM
Post by Marcelo Zimbres
Post by Nevin Liber
No you don't. Just assert(n == 1) in your custom allocator. If someone
uses your custom allocator for something other than node based containers,
the assert will fire.
What should I do when the condition n =! 1 is triggered with the client?
1. Abort. They violated the contract that your allocator should only be used with node-based containers.
2. Fall back to a different allocator, such as std::allocator. (This may allow you to use your allocator with almost-node-based containers such as std::deque; maybe that is what David Krauss was alluding to?)
--
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/ <https://groups.google.com/a/isocpp.org/group/std-proposals/>.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Marcelo Zimbres
2016-01-20 20:21:07 UTC
Permalink
1) I dislike the idea of narrowing the standard contract, which is wide, but can throw.
My proposal does not narrow the standard contract. Library
implementors can still use the allocate(size_type) when they want but
are required to support node allocation as well, when it is the user
desire.

I also think that if it were narrow, major libraries like libcxx and
libstd++ (I did not test on VS) would be profiting from
allocate(size_type) which is not the case (n is always 1).
If you request more memory than can be supplied by a single request, throw std::bad_alloc.
I do not like the idea of throwing when I did not run out of memory,
all n != 1 would be throwing. IMO the problem arises as a result of
doing linked allocation with an array allocator. They have distinct
nature.
Otherwise, I agree with the idea that the existing
allocator
interface supports allocators optimized for this purpose, and it is no surprise
that they would not work well for ‘vector’, that has contiguous memory
requirements.
I also think so and therefore I am proposing to have support for node
allocation in addition to array allocation, to bless node-based
containers as well. The split between array and node allocation is not
new [1]
Our approach to this issue is to observe that pooling is such a big win, we
build it into our node-based containers (with a generalized pool abstraction build
on top of the allocator interface) so that our containers are pooling, whether
or not the allocator is optimized for this strategy. I know other libraries have
looked into this and stepped back, as the standard containers (other than deque)
offer no interface that would allow the container to give up excessive memory
allocated when a container hits an abnormally high peak size, holding onto that mostly
unused memory until the container is destroyed.
I see pooling inside the container as undesirable since I may want to
hang many containers on the same allocator, this way its better to
keep container memory use to a minimum i.e. equal to the number of
elements, and let the allocator handle it. A container is not aware of
other containers the allocator yes. Additionally, it is also
restrictive as the pooling strategy cannot be changed by the user. If
it is kept in the allocator, users can change it at will.
We also have pooling allocators in the Library Fundamentals TS in the polymorphic
memory resources section, and good experience using them over many years at
Bloomberg, which is why we proposed them in the first place! I would be interested
in feedback on how well they work (or not) for others in practice, before inventing
new allocator interfaces to solve the same problem.
I will have a look.
AlisdairM
Thanks for the feedback.

Marcelo


[1] The Art of Computer Programming, Vol. 1, section 2.2.3.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
David Krauss
2016-01-20 06:13:43 UTC
Permalink
Post by Marcelo Zimbres
Unordered containers usually need to rebind twice, once for node allocation
and once for array allocation. that means they would need allocate() and
allocate(size_type) as well. I cannot make max_size return 1 for this reason.
In that case, the problem is much different: The template is implementing two completely different (and incompatible) allocators. One rebind produces a node allocator and one produces an array allocator. They can’t be distinguished by the n == 1 test.

Reviewing the Allocator requirements, I don’t see why it shouldn’t work to simply implement the allocators separately. Converting a given allocator between node mode and array mode requires preserving the state of both, but any given object is only in one mode. Only node mode max_size returns 1.

Taking a quick look at the libc++ and libstdc++ implementations, they allocate individual nodes and arrays of pointers. So you can implement array mode as a partial specialization of the allocator template on pointer types.

The proposal certainly doesn’t clarify the two-in-one nature, particularly that the result of allocate(1) couldn’t be passed to deallocate().
Post by Marcelo Zimbres
Post by David Krauss
Do allocators following the proposal have no allocate(size_type) overload at
all, or is it defined as deleted? That would break compatibility with all
allocator-aware containers, which seems to level the balance with the fact
that max_size currently tends to be ignored.
The allocators can provide both allocate() and allocate(size_type),
but if the typedef
use_node_allocation is defined to std::true_type, then the container should use
allocate() for its node allocations. The proposal is non-breaking.
The task is to eliminate allocate(size_type), so it’s begging the question to say they can provide it.

The proposal does introduce allocators without a well-behaved allocate(size_type), no? Though it’s technically non-breaking, these allocators would be incompatible with all existing containers. The max_size approach avoids incompatibilities.

In any case, the proposal needs to define requirements for [de]allocate(size_type) in the case that allocate() is defined.
Post by Marcelo Zimbres
Node-based containers can themselves use n != 1. There is no guarantee
for n == 1 in standard, even for node-based containers.
Does any standard library implementation allocate multiple nodes in the same block? If not, it might be better to simply add that guarantee.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Marcelo Zimbres
2016-01-20 20:47:15 UTC
Permalink
Post by Marcelo Zimbres
Unordered containers usually need to rebind twice, once for node allocation
and once for array allocation. that means they would need allocate() and
allocate(size_type) as well. I cannot make max_size return 1 for this reason.
In that case, the problem is much different: The template is implementing
two completely different (and incompatible) allocators. One rebind produces
a node allocator and one produces an array allocator. They can’t be
distinguished by the n == 1 test.
I cannot pass two allocators to the container and cannot know which
rebound instance will be used for array/node allocation, that is why
in this case, both allocate() and allocate(size_type) must be
available.
Post by Marcelo Zimbres
Reviewing the Allocator requirements, I don’t see why it shouldn’t work to
simply implement the allocators separately. Converting a given allocator
between node mode and array mode requires preserving the state of both, but
any given object is only in one mode. Only node mode max_size returns 1.
Taking a quick look at the libc++ and libstdc++ implementations, they
allocate individual nodes and arrays of pointers. So you can implement array
mode as a partial specialization of the allocator template on pointer types.
The partial specialization trick may work, but it requires me to go
deeper in the internal details of how unordered containers are
implemented, which is unnecessary since I can distinguish allocation
types with allocate overloads.
Post by Marcelo Zimbres
The proposal certainly doesn’t clarify the two-in-one nature, particularly
that the result of allocate(1) couldn’t be passed to deallocate().
I will fix that. It is meant that deallocate(pointer) can be only used
with pointers returned by allocate(),
Post by Marcelo Zimbres
Do allocators following the proposal have no allocate(size_type) overload at
all, or is it defined as deleted? That would break compatibility with all
allocator-aware containers, which seems to level the balance with the fact
that max_size currently tends to be ignored.
The allocators can provide both allocate() and allocate(size_type),
but if the typedef
use_node_allocation is defined to std::true_type, then the container should use
allocate() for its node allocations. The proposal is non-breaking.
The task is to eliminate allocate(size_type), so it’s begging the question
to say they can provide it.
I do not want to eliminate allocate(size_type) I want to have the
option of not using it. Array allocations are still there.
Post by Marcelo Zimbres
The proposal does introduce allocators without a well-behaved
allocate(size_type), no? Though it’s technically non-breaking, these
allocators would be incompatible with all existing containers. The max_size
approach avoids incompatibilities.
allocate(size_type) is untouched. The max_size approach alone does not
solve the problem, specially for unordered containers where I need an
allocate for array allocations and one for node allocation.
Post by Marcelo Zimbres
In any case, the proposal needs to define requirements for
[de]allocate(size_type) in the case that allocate() is defined.
I will do it. Thanks.

Marcelo
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Nevin Liber
2016-01-20 22:35:43 UTC
Permalink
Post by Marcelo Zimbres
I cannot pass two allocators to the container and cannot know which
rebound instance will be used for array/node allocation, that is why
in this case, both allocate() and allocate(size_type) must be
available.
But unless you mandate that node allocations are to be done by calling
allocate() I don't see how this fixes this problem. And if you are going
to mandate that, why not just mandate that they call allocate(1)?
--
Nevin ":-)" Liber <mailto:***@eviloverlord.com> +1-847-691-1404
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Marcelo Zimbres
2016-01-21 19:08:59 UTC
Permalink
Post by Nevin Liber
But unless you mandate that node allocations are to be done by calling
allocate() I don't see how this fixes this problem.
That is what I am proposing. Node allocations are handle by allocate()
whenever the allocator defines a typedef use_node_allocation to
std::true_type,
Post by Nevin Liber
And if you are going to mandate that, why not just mandate that they call allocate(1)?
That would work for pure node-based containers, but not for unordered
ones. In general, there is no way of knowing which rebound type is
used for node/array allocation. They have to be performed on distinct
member functions.

Marcelo
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Ion Gaztañaga
2016-01-21 21:19:27 UTC
Permalink
Post by Marcelo Zimbres
Post by Nevin Liber
But unless you mandate that node allocations are to be done by calling
allocate() I don't see how this fixes this problem.
That is what I am proposing. Node allocations are handle by allocate()
whenever the allocator defines a typedef use_node_allocation to
std::true_type,
Post by Nevin Liber
And if you are going to mandate that, why not just mandate that they call allocate(1)?
That would work for pure node-based containers, but not for unordered
ones. In general, there is no way of knowing which rebound type is
used for node/array allocation. They have to be performed on distinct
member functions.
Marcelo, I think your proposal is interesting. I would like to suggest
some changes to achieve the same goal.

I think we should make this feature a bit more transparent. Hopefully,
now we have a layer between the container and the allocator,
allocator_traits. Instead of "use_node_allocation" my suggestion is to
have two new allocator_traits members:

//Calls a.allocate_node() if possible. Otherwise it
//calls a.allocate(1u). All memory allocated with this
//function must be deallocated with deallocate_node(a, p)
static pointer allocate_node(Alloc &a);

//Requires: p shall be allocated by a call to allocate_node(a)
//Calls a.deallocate_node(p) if possible. Otherwise
//calls a.deallocate(p, 1u).
static void deallocate_node(Alloc &a, pointer p);

Containers allocating a single node can use the new function if desired.
I don't think we should require the use of the new function, it could be
a QOI feature. Calls to a.allocate(n) should continue to work on node
allocators.

There is existing practice in Boost.Container with this approach, (not
using allocator_traits, since it didn't exist when implementing N2045)
which will be helpful to push your proposal forward.

Best,

Ion

PS: Maximum performance is achieved when allocating several nodes at
once, the so called "burst allocation" in N2045. This needs an
alternative interface, though.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Marcelo Zimbres
2016-01-23 12:39:34 UTC
Permalink
Marcelo, I think your proposal is interesting. I would like to suggest some
changes to achieve the same goal.
I think we should make this feature a bit more transparent. Hopefully, now
we have a layer between the container and the allocator, allocator_traits.
Instead of "use_node_allocation" my suggestion is to have two new
//Calls a.allocate_node() if possible. Otherwise it
//calls a.allocate(1u). All memory allocated with this
//function must be deallocated with deallocate_node(a, p)
static pointer allocate_node(Alloc &a);
//Requires: p shall be allocated by a call to allocate_node(a)
//Calls a.deallocate_node(p) if possible. Otherwise
//calls a.deallocate(p, 1u).
static void deallocate_node(Alloc &a, pointer p);
That is what I am doing, with two small differences:

1) Instead of having the two new names in the allocator_traits:
allocate_node/deallocate_node, I am simply overloading
allocate/deallocate. I do not know what is the better approach, but in
essentially, there is no difference.

2) I did not think of falling back to allocate(1), whenever
allocate_node() is not available. This is indeed a good idea as
node-based containers could use allocate_node regardless of whether
the allocator provides allocate_node or not. This helps me cover your
last comment.
Containers allocating a single node can use the new function if desired. I
don't think we should require the use of the new function, it could be a QOI
feature. Calls to a.allocate(n) should continue to work on node allocators.
In my proposal I do not rule out array allocation inside node-based
containers, they remain untouched. But I do need a guarantee that node
allocation is used whenever the user desires so. This allows me to
have simple solutions, for simple problems i.e. do not provide array
allocation at all in my allocator. Think of how simple it would be to
write an allocator for the simple use case:

std::array<char, 20 * node_size > buffer = {{}};
my_allocator alloc(buffer);

std::list<int, my_allocator<int>> l(alloc);

I would need only a couple of lines of code for that. A massive
simplification if compared to the allocators i could find in the
literature.

Additionally, if anyone feels the need of using array + node
allocation together inside node-based containers, it would still be
possible, given your suggestion of falling back to allocate(1) when
allocate_node is not available.
There is existing practice in Boost.Container with this approach, (not using
allocator_traits, since it didn't exist when implementing N2045) which will
be helpful to push your proposal forward.
That would be great. I am already using boost::node_allocator as a
reference in my proposal.

Marcelo
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Ion Gaztañaga
2016-01-24 20:55:55 UTC
Permalink
Post by Marcelo Zimbres
allocate_node/deallocate_node, I am simply overloading
allocate/deallocate. I do not know what is the better approach, but in
essentially, there is no difference.
One reason for a different name (it's a matter of taste) is that
function names should reflect that both operations have different
semantics, apart from the storage size. If memory expansion (realloc) is
added in the future, it should only work with storage allocated with
allocate(n) but not with storage allocated for nodes. This allows node
allocations to avoid extra bookeeping data to mark the storage as
non-expandable (typically simple segregated storage).

In any case, if the proposal goes forward, I guess the committee will
find the best name for the "node" operations.

Best,

Ion
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Marcelo Zimbres
2016-01-27 20:39:35 UTC
Permalink
One reason for a different name (it's a matter of taste) is that function
names should reflect that both operations have different semantics, apart
from the storage size.
I do agree.
If memory expansion (realloc) is added in the future,
it should only work with storage allocated with allocate(n) but not with
storage allocated for nodes. This allows node allocations to avoid extra
bookeeping data to mark the storage as non-expandable (typically simple
segregated storage).
I think this is another good reason for adding support for node allocation.

Marcelo
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Marcelo Zimbres
2016-01-27 20:45:42 UTC
Permalink
I would like to thank you all for the valuable feedback. There are
many points in my proposal that need improvements. I will fix them and
come back for a second round.

Best,
Marcelo
Post by Marcelo Zimbres
One reason for a different name (it's a matter of taste) is that function
names should reflect that both operations have different semantics, apart
from the storage size.
I do agree.
If memory expansion (realloc) is added in the future,
it should only work with storage allocated with allocate(n) but not with
storage allocated for nodes. This allows node allocations to avoid extra
bookeeping data to mark the storage as non-expandable (typically simple
segregated storage).
I think this is another good reason for adding support for node allocation.
Marcelo
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
David Krauss
2016-01-22 02:38:43 UTC
Permalink
Post by Marcelo Zimbres
Post by David Krauss
Taking a quick look at the libc++ and libstdc++ implementations, they
allocate individual nodes and arrays of pointers. So you can implement array
mode as a partial specialization of the allocator template on pointer types.
The partial specialization trick may work, but it requires me to go
deeper in the internal details of how unordered containers are
implemented, which is unnecessary since I can distinguish allocation
types with allocate overloads.
If the library calls a special overload, then the user doesn’t need to arrange for it to be called, yes. Your solution adds complexity to the library implementation and to the Allocator concept specification, though. Also, it doesn’t allow for a gradual transition: If the library doesn’t call allocate(), node allocation will never occur. So, let’s look for a way that fits better with the status quo.

Reliance on library details can be eliminated by an is_node_type predicate, either as a member or a metafunction. For example:

template< typename T, bool = T::is_node_type >
struct my_alloc {
T * allocate( std::size_t n );
void deallocate( T * p, std::size_t n );
};

template< typename T >
struct my_alloc< T, true > {
T * allocate( std::size_t must_be_one );
void deallocate( T * p, std::size_t must_be_one );

constexpr std::size_t max_size() const
{ return 1; }
};

Advantages:
1. Scales to cooperate with unsupporting libraries. The hackish introspection can be #ifdef’ed in.

2. Avoids having member functions that shouldn’t (or can’t) be instantiated. There’s no my_alloc<node>::allocate(std::size_t) or my_alloc<node*>::allocate().

3. Library support is accomplished simply by adding static constexpr bool is_node_type = true to node types, no need for SFINAE to switch between allocate() and allocate(1) (matching the deallocate overload every time).

4. No quietly lurking bugs from library ABI breakage. A dynamic library built without is_node_type support won’t link against a program built with, because the default argument is baked into the allocator type. On the other hand, in your solution the alternative functions always exist, so the implementation will happily generate and call deallocate(p) even though the dynamic library called allocate(1).

However, this still doesn’t look like the best solution. You can’t write a node allocation pool without knowing the node type. The proposal should address getting the node type from the container type. And given that, the allocator can just partially specialize on the node type, no is_node_type needed.

It would be nice to see a complete prototype.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
David Krauss
2016-01-22 04:50:57 UTC
Permalink
Post by David Krauss
It would be nice to see a complete prototype.
I mean, for any proposal in this space, it would be nice to see a complete example, including both the user’s node-friendly allocator and the library support. It’s hard to extrapolate to the big picture, and a prototype shouldn’t be too much to ask.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Marcelo Zimbres
2016-01-23 14:11:07 UTC
Permalink
If the library calls a special overload, then the user doesn’t need to
arrange for it to be called, yes. Your solution adds complexity to the
library implementation and to the Allocator concept specification, though.
Any new feature would demand an increase in complexity. In this case
the added complexity is minimal, the library implementation has to
decide which overload gets called given a typedef be true or false.
Also, it doesn’t allow for a gradual transition: If the library doesn’t call
allocate(), node allocation will never occur.
Yes, I need a way to ensure allocate() gets called.
So, let’s look for a way that
fits better with the status quo.
Reliance on library details can be eliminated by an is_node_type predicate,
template< typename T, bool = T::is_node_type >
struct my_alloc {
T * allocate( std::size_t n );
void deallocate( T * p, std::size_t n );
};
template< typename T >
struct my_alloc< T, true > {
T * allocate( std::size_t must_be_one );
void deallocate( T * p, std::size_t must_be_one );
constexpr std::size_t max_size() const
{ return 1; }
};
The problem I see:

allocate( std::size_t must_be_one ) is not better than
allocate()/allocate_node(): You get a hard-coded 1 that is redundant
and will be ignored inside the function anyway (the function handles
only one node at time, no need to specify that).

But now with a constexpr max_size function, I can avoid a typedef in
the allocator. However, that would demand to change
std::allocator_traits definition of max_size to be constexpr as well
which would be breaking, as far as I can see.
1. Scales to cooperate with unsupporting libraries. The hackish
introspection can be #ifdef’ed in.
2. Avoids having member functions that shouldn’t (or can’t) be instantiated.
There’s no my_alloc<node>::allocate(std::size_t) or
my_alloc<node*>::allocate().
3. Library support is accomplished simply by adding static constexpr bool
is_node_type = true to node types, no need for SFINAE to switch between
allocate() and allocate(1) (matching the deallocate overload every time).
4. No quietly lurking bugs from library ABI breakage. A dynamic library
built without is_node_type support won’t link against a program built with,
because the default argument is baked into the allocator type. On the other
hand, in your solution the alternative functions always exist, so the
implementation will happily generate and call deallocate(p) even though the
dynamic library called allocate(1).
However, this still doesn’t look like the best solution. You can’t write a
node allocation pool without knowing the node type. The proposal should
address getting the node type from the container type. And given that, the
allocator can just partially specialize on the node type, no is_node_type
needed.
Yes, I need the node-type to write portable buffer sizes (actually
only the node size). I was thinking of that as a future proposal
(together with a node allocator itself).

And now, even if the node type is exposed on node based containers, so
that specializations can be easily done, you still need means to tell
the library to call allocate(n) with n = 1 (supposing I cannot make
max_size constexpr).
It would be nice to see a complete prototype.
I do have a prototype in my github. If this proposal gets aligned with
boost containers, than it would not be only a prototype but a well
tested concept, given the wide spread use of boost.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
David Krauss
2016-01-24 04:15:32 UTC
Permalink
Post by Marcelo Zimbres
Any new feature would demand an increase in complexity. In this case
the added complexity is minimal, the library implementation has to
decide which overload gets called given a typedef be true or false.
Adding SFINAE to every node allocation and deallocation is not minimal, if a simpler solution exists.
Post by Marcelo Zimbres
allocate( std::size_t must_be_one ) is not better than
allocate()/allocate_node(): You get a hard-coded 1 that is redundant
and will be ignored inside the function anyway (the function handles
only one node at time, no need to specify that).
A constant argument to an unused parameter in an inlined function is very likely to have zero impact.
Post by Marcelo Zimbres
But now with a constexpr max_size function, I can avoid a typedef in
the allocator. However, that would demand to change
std::allocator_traits definition of max_size to be constexpr as well
which would be breaking, as far as I can see.
Without any proposal regarding constexpr, the user can already specialize an allocator for nodes, as long as it knows about the library’s internal node types.

Still, what would constexpr break? It’s possible to write a program which observes that allocator_traits::max_size is not currently constexpr, but that’s not something that necessarily needs to be preserved. Adding constexpr might not properly even be a proposal, but rather a defect report that std::deque currently can’t respect max_size when it’s smaller than the calculated array extent.

Let’s forget about constexpr, since deque is outside the scope of this discussion, and just say that max_size returns 1, which essentially reflects the same thing as Nevin’s assert.
Post by Marcelo Zimbres
Yes, I need the node-type to write portable buffer sizes (actually
only the node size). I was thinking of that as a future proposal
(together with a node allocator itself).
It would be better for the proposal to provide for users writing their own node allocators. At the least, there should be single-threaded and multithreaded versions. Allocation of the free-block stack is another question.

Exposing the node type itself would also work, and that might better serve portability. The user can map from node types to node sizes, but not vice versa.
Post by Marcelo Zimbres
And now, even if the node type is exposed on node based containers, so
that specializations can be easily done, you still need means to tell
the library to call allocate(n) with n = 1 (supposing I cannot make
max_size constexpr).
Are you aware of an implementation passing n != 1, or any reason to do that? This seems very speculative. Note that n != 1 is different from allocating several nodes at once, in which case they may be deallocated in any order.
Post by Marcelo Zimbres
I do have a prototype in my github.
Ah: https://github.com/mzimbres/rtcpp/tree/master/rtcpp/memory <https://github.com/mzimbres/rtcpp/tree/master/rtcpp/memory>
Post by Marcelo Zimbres
If this proposal gets aligned with
boost containers, than it would not be only a prototype but a well
tested concept, given the wide spread use of boost.
That depends on how many projects are using what particular features in Boost.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Marcelo Zimbres
2016-01-24 22:46:32 UTC
Permalink
Post by David Krauss
Without any proposal regarding constexpr, the user can already specialize an
allocator for nodes, as long as it knows about the library’s internal node
types.
I will add that to my proposal. Knowing the containers node type is
indeed very useful to avoid the tricks I have been doing to guess the
node size.
Post by David Krauss
Still, what would constexpr break? It’s possible to write a program which
observes that allocator_traits::max_size is not currently constexpr, but
that’s not something that necessarily needs to be preserved. Adding
constexpr might not properly even be a proposal, but rather a defect report
that std::deque currently can’t respect max_size when it’s smaller than the
calculated array extent.
If libraries begin to get static information from max_size i.e.
whether its 1 or not, than all custom allocators that implement
max_size as non-constexpr would be broken (static information cannot
be read out of them). That means, as you said, libraries will have to
detect whether max_size is constexpr or not. All custom allocators
that may want constexpr max_size (node allocators for example), will
have to specialize the std::allocator_traits, since the default is
non-constexpr (my proposal does not need that). The whole picture I
see would be something like this

1) Libraries have to begin to pay attention to max_size, which is fair
enough. (They are not doing it now AFAIK)
2) std::allocator_traits specializations may offer a constexpr max_size.
3) Libraries have to detect that feature.
4) If they are constexpr, check if max_size is 1 and call allocate(n)
accordingly.

I do not think it would be reasonable to standardize this. However, I
like pretty much your idea if it were indeed possible to have a
constexpr max_size.
Post by David Krauss
Let’s forget about constexpr, since deque is outside the scope of this
discussion, and just say that max_size returns 1, which essentially reflects
the same thing as Nevin’s assert
Yes, I need the node-type to write portable buffer sizes (actually
only the node size). I was thinking of that as a future proposal
(together with a node allocator itself).
It would be better for the proposal to provide for users writing their own
node allocators. At the least, there should be single-threaded and
multithreaded versions. Allocation of the free-block stack is another
question.
Exposing the node type itself would also work, and that might better serve
portability. The user can map from node types to node sizes, but not vice
versa.
And now, even if the node type is exposed on node based containers, so
that specializations can be easily done, you still need means to tell
the library to call allocate(n) with n = 1 (supposing I cannot make
max_size constexpr).
Are you aware of an implementation passing n != 1, or any reason to do that?
This seems very speculative. Note that n != 1 is different from allocating
several nodes at once, in which case they may be deallocated in any order.
n is a runtime parameter that can take any value, so I cannot simply
assume that n = 1 always, on all c++ libraries. It is definitely not
portable to rely on that. That said, yes, I have never seen anyone
using n != 1.

Marcelo
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
David Krauss
2016-01-28 01:33:57 UTC
Permalink
Post by Marcelo Zimbres
If libraries begin to get static information from max_size i.e.
whether its 1 or not, than all custom allocators that implement
max_size as non-constexpr would be broken (static information cannot
be read out of them).
I suggested constexpr max_size only as an alternative to adding the use_node_allocation member. Both would add the same static information. Both impose the same awareness requirement on libraries. (When I characterized this as a breaking change, you disagreed. But now you’re saying the same thing.)

To be clear, neither should be necessary if node classes are tagged as opposed to node allocators, and we’re allowed the assumption that array allocation of a node class never happens. This approach seems much more economical.
Post by Marcelo Zimbres
n is a runtime parameter that can take any value, so I cannot simply
assume that n = 1 always, on all c++ libraries. It is definitely not
portable to rely on that. That said, yes, I have never seen anyone
using n != 1.
This seems like a pretty critical detail. Things can be a lot simpler if n!=1 is ruled out for node-based containers.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Marcelo Zimbres
2016-01-28 19:41:00 UTC
Permalink
Post by Marcelo Zimbres
If libraries begin to get static information from max_size i.e.
whether its 1 or not, than all custom allocators that implement
max_size as non-constexpr would be broken (static information cannot
be read out of them).
I suggested constexpr max_size only as an alternative to adding the
use_node_allocation member. Both would add the same static information. Both
impose the same awareness requirement on libraries. (When I characterized
this as a breaking change, you disagreed. But now you’re saying the same
thing.)
To be clear, neither should be necessary if node classes are tagged as
opposed to node allocators, and we’re allowed the assumption that array
allocation of a node class never happens. This approach seems much more
economical.
I will implement your ideas on my project before I push my proposal
forward. That way we can compare the better approach.
Post by Marcelo Zimbres
n is a runtime parameter that can take any value, so I cannot simply
assume that n = 1 always, on all c++ libraries. It is definitely not
portable to rely on that. That said, yes, I have never seen anyone
using n != 1.
This seems like a pretty critical detail. Things can be a lot simpler if
n!=1 is ruled out for node-based containers.
This is what I think. If rule out is not possible, I would at least
like to switch off array allocations inside node-based containers. For
reference, my first thoughts on this problem are on this thread in
C++-embedded:

http://www.open-std.org/pipermail/embedded/2014-December/000335.html


Best,
Marcelo
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Nevin Liber
2016-01-19 19:42:44 UTC
Permalink
Post by Marcelo Zimbres
https://github.com/mzimbres/rtcpp/blob/master/doc/proposal_allocator.pdf
I hope you don’t mind me summarizing: The proposal is to add an allocate()
method which is equivalent to allocate(1). The benefit is to bless
allocators which avoid the complexity of variable-sized allocation blocks.
Why can’t such allocators simply return 1 from max_size()? This would let
array-based containers work up to an array size of 1, which should be good
enough for std::deque at least.
I have no idea what you are talking about with deque. deque is not a
node-based container. Could you elaborate?
--
Nevin ":-)" Liber <mailto:***@eviloverlord.com> +1-847-691-1404
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Howard Hinnant
2016-01-19 19:43:06 UTC
Permalink
Post by Marcelo Zimbres
Hi,
I would like to ask for some feedback on a non-breaking proposal to
the C++ standard, that aims to reduce allocator complexity, support
realtime allocation and improve performance of node-based containers
through the addition
of overloads of the allocate and deallocate member functions. The PDF
can be found here.
https://github.com/mzimbres/rtcpp/blob/master/doc/proposal_allocator.pdf
A previous discussion on the subject can be found here [1].
Best regards,
Marcelo
[1] http://www.open-std.org/pipermail/embedded/2014-December/000335.html
Just fyi, here is a link to past work in this area:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html

Howard
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Loading...