[std-discussion] How much memory a container requests from the allocator?

[Marcelo Zimbres]

Hi,

I would like to gauge interest on the following idea: When using allocators
with state, I often would like to know how much memory a container requests
from the allocator. For example, say one needs a list with 5 elements:

std::array<char, N> buffer = {{}};
my::allocator<int> alloc(buffer);

std::list<int, my::allocator<int>> tmp(alloc);
tmp = {5, 3, 7, 20, 1};

What value of N I have to use so that I do not run out of memory or waste it?
Knowing the exact size of N allows me to write more efficient programs as
data gets more compact.

To solve this it would be enough to add a static member function that can
be evaluated at compile time, for example

static constexpr std::size_t memory_consumed(size_type n_elements);

What are your thoughts?

Marcelo

[Daniel Krügler]

1) I believe, that your question does not really belong to this group,
because it is not a discussion of the existing standard, but a
proposal of a new feature. For this you better should use the
std-proposals group:

https://groups.google.com/a/isocpp.org/forum/#!forum/std-proposals

2) From your suggestion it did not really became clear to me, to which
class(es) you suggest to add this static member function. You should
clarify that. For the moment I assume you suggest to add this member
to all standard container classes.

3) My personal two cents on this proposal that I do only partially
understand at that moment: If you suggest to add this function to
containers, you impose stronger requirements on these containers. In
fact, you require them not to take advantage of runtime-properties of
the system. This looks like a severe constraint to me for a feature
that is only relevant for a very narrow use-case of a very specific
allocator that requires static information to decide it's optimal
management. If you are interested in such static policies you either
need to provide your own container that is happy with providing such a
static information, or you could hold a set of array instances within
a union and construct the right one for the right size. Furthermore I
believe that your suggestion is a bit of a red herring, because the
suggested function is only useful, if the actual number of elements is
a constant expression and I doubt that this is often the case. To
defend your suggestion I therefore strongly suggest to provide a
reasonable usage-example of your suggested new feature, so that it is
easier to analyze under which conditions it can actually become
useful.

HTH & Greetings from Bremen,

Daniel Krügler

[Marcelo Zimbres]

"1) I believe, that your question does not really belong to this group, because
it is not a discussion of the existing standard, but a proposal of a new
feature. For this you better should use the std-proposals group:"

I thinks the question fits both groups as I want to know how much memory
standard containers requests from its allocator. I can re-post it anyway on
std-proposals if I am wrong.

"2) From your suggestion it did not really became clear to me, to which
class(es) you suggest to add this static member function. You should clarify
that. For the moment I assume you suggest to add this member to all standard
container classes."

Sorry for not making this point clear, my primary interest is having this
member function on node-based containers. However, I think it would a useful
addition for other containers as well.

"If you suggest to add this function to containers, you impose stronger
requirements on these containers."

Yes, this is true and intended.

"In fact, you require them not to take advantage of runtime-properties of the
system."

I do not agree with this statement. You can take advantage of the
runtime-properties either on the container side or on the allocator side. I
think that the allocation logic should be kept on the allocator and not split
between the container and the allocator. The allocator knows the type for which
it is allocating memory and can use this information. If you have a fancy
allocation algorithm why put it into the container instead of the allocator?

"This looks like a severe constraint to me for a feature that is only relevant
for a very narrow use-case of a very specific allocator that requires static
information to decide it's optimal management."

I think that it is a rather common situation that users know how big a
container will grow or at least have an upper bound on it. If this requirement
is too strong I would be also happy with non-constexpr function, so that I can
at least use an std::vector as a buffer instead of an std::array.

"If you are interested in such static policies you either need to provide your

own container that is happy with providing such a static information ..."

That is what I am trying to avoid since I believe this function could be easily
implement. I may be wrong but on libstdc++ for example, I see that std::set and
std::map could have this function implemented as

static constexpr std::size_t memory_consumed(size_type n_elements)

{return (n_elements + 1) * sizeof (node_type);}

where the "+ 1" accounts for the head node in the underlying red-black tree.

"Furthermore I believe that your suggestion is a bit of a red herring, because
the suggested function is only useful, if the actual number of elements is a
constant expression and I doubt that this is often the case."

I think it is very often the case in node based containers. In all cases I am
aware of the memory requested from the allocator is simply the number of
elements times the node size (and perhaps one more node that is used as head in
binary trees for example).

"To defend your suggestion I therefore strongly suggest to provide a reasonable
usage-example of your suggested new feature, so that it is easier to analyze
under which conditions it can actually become useful."

Every allocator that uses pre-allocated buffer is an usage-example. Without this
feature I am either running out of memory or wasting it. What buffer
size should I use?

Greetings from Atibaia,

Marcelo

> --
>
> ---
> You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to std-discussio...@isocpp.org.
> To post to this group, send email to std-dis...@isocpp.org.
> Visit this group at http://groups.google.com/a/isocpp.org/group/std-discussion/.

[David Krauss]

On 2015–04–13, at 4:35 AM, Marcelo Zimbres <mzim...@gmail.com> wrote:

Hi,

I would like to gauge interest on the following idea: When using allocators
with state, I often would like to know how much memory a container requests
from the allocator.

OK, so you want to interpose something between one container (or a set of containers) and a particular, generic allocator.

std::array<char, N> buffer = {{}};
my::allocator<int> alloc(buffer);

What value of N I have to use so that I do not run out of memory or waste it?
Knowing the exact size of N allows me to write more efficient programs as
data gets more compact.

This is different. Now you’re looking for an estimate of the amount of memory available, which is already called max_size(). In this case, though, you would only use max_size in debug mode, to characterize the memory usage before adjusting N to an optimal, production value.

To solve this it would be enough to add a static member function that can
be evaluated at compile time, for example

Well, there’s still the part about setting up the tests and metrics, and estimating a tolerance factor.

static constexpr std::size_t memory_consumed(size_type n_elements);

A static function can only characterize a particular type of allocator over all containers that use it. This function is insufficient for allocators with multiple instances.

What are your thoughts?

Create your own allocator adapter class with the extra function.

template< typename alloc >

class allocator_accountant : public alloc {

    typename alloc::size_type usage = 0;

public:

    typename alloc::size_type usage_max = 0;

    using alloc::alloc;

    void * allocate( typename alloc::size_type n, typename alloc::template rebind< void >::type::const_pointer hint = 0 ) {

        usage += n;

        if ( usage_max < usage ) usage_max = usage;

        return alloc::allocate( n, hint );

    }

    void deallocate( typename alloc::pointer p, typename alloc::size_type n ) {

        usage -= n;

        alloc::deallocate( p, n );

    }

};

my::allocator_accountant< my::allocator<int> > alloc( buffer );

// Do some stress test.

std::clog << "The foo allocator used " << alloc.usage_max << '\n';

To characterize several containers sharing one allocator, you might specialize allocator_accountant on reference types, giving it an interface with forwarding wrappers.

This doesn’t cover code simply using the default allocator, which is of course in the vast majority. However, there are better ways to measure the main free store. It’s most often done by implementing global operator new. Although this unfortunately (essentially) forces you to define it in terms of malloc, which might be less optimal than your default stdlib implementation, that’s still good enough for the behavioral characterization you need.

[David Krauss]

On 2015–04–13, at 10:03 AM, David Krauss <pot...@gmail.com> wrote:

my::allocator_accountant< my::allocator<int> > alloc( buffer );

Oops, allocators need to have value semantics and survive rebinds, so the adapter will need to keep a reference to an object containing usage and usage_max. Still, the general approach seems to cover the stated need better than the proposal.

[Christopher Smith]

On Sun, Apr 12, 2015 at 4:42 PM, Marcelo Zimbres <mzim...@gmail.com> wrote:

"In fact, you require them not to take advantage of runtime-properties of the
system."

I do not agree with this statement. You can take advantage of the
runtime-properties either on the container side or on the allocator side.  I
think that the allocation logic should be kept on the allocator and not split
between the container and the allocator. The allocator knows the type for which
it is allocating memory and can use this information. If you have a fancy
allocation algorithm why put it into the container instead of the allocator?

As I understand it, there is an implicit assumption here though that the amount of memory needed to allocate a container of N elements of a certain type is fixed. If it were, you could use sizeof() (with a lot of work) to get your answers.

At runtime, allocators have to deal with fragmentation, cache lines, etc., and they might answer the same request differently each time it is asked of them. Maybe you could put an upper bound on that, but I'm not sure if that'd be a terribly useful exercise.

 

--

Chris

[Marcelo Zimbres]

"OK, so you want to interpose something between one container (or a set of
containers) and a particular, generic allocator."

I do not understand what you mean here. I want to know how much memory a
container requests from the allocator i.e. account all calls to
std::allocator<T>::allocate(n); That number is usually equal to the number of
elements in the container times sizeof (T), where T is the rebound type.

"This is different. Now you're looking for an estimate of the amount of memory
available, which is already called max_size(). In this case, though, you would
only use max_size in debug mode, to characterize the memory usage before
adjusting N to an optimal, production value."

I do not want to know how much memory is available, neither on free storage nor
on the stack. Once again, I want to know how much memory the container requests
from its allocator instance if I am going to insert n elements in the
container.

"Well, there's still the part about setting up the tests and metrics, and
estimating a tolerance factor."

I can make tests to try to estimate how memory is used, but I cannot guarantee
that my tests followed all possible paths inside the container to give the
right answer. All I would have is an estimate that may be unsafe in production
code.

"A static function can only characterize a particular type of allocator over
all containers that use it. This function is insufficient for allocators with
multiple instances."

I meant the function should be a member in the container, not in the allocator.
Or, what do you mean? I have already written allocators that are shared among
many objects (and therefore use many instances of it). I could certainly
benefit from such function.

Marcelo

[Marcelo Zimbres]

"As I understand it, there is an implicit assumption here though that the amount
of memory needed to allocate a container of N elements of a certain type is
fixed. If it were, you could use sizeof() (with a lot of work) to get your
answers."

I am not assuming it is fixed, I am assuming it is known and can be returned to
the user. It sounds strange to me that it is not possible to know how
much memory
a container is going to use, if I insert n elements into it.

"At runtime, allocators have to deal with fragmentation, cache lines, etc., and
they might answer the same request differently each time it is asked of them."

Yes, I agree. But this is on the allocator side, not on the container side.

"Maybe you could put an upper bound on that, but I'm not sure if that'd be a
terribly useful exercise."

So you do not care about how much memory a container will use? Ok, I am fine
with it, but I do sometimes feel this information is useful and I would like to
know it.


Marcelo

[David Krauss]

On 2015–04–14, at 1:50 AM, Marcelo Zimbres <mzim...@gmail.com> wrote:

I do not want to know how much memory is available, neither on free storage nor

on the stack. Once again, I want to know how much memory the container requests
from its allocator instance if I am going to insert n elements in the
container.

I can make tests to try to estimate how memory is used, but I cannot guarantee
that my tests followed all possible paths inside the container to give the
right answer. All I would have is an estimate that may be unsafe in production
code.

Each container type has a characteristic storage complexity. You can measure your standard library implementation and extrapolate, or inspect its source code.

A function to estimate worst-case usage memory would be extremely niche, and wouldn’t give you particularly good results. For std::vector, the worst case is when the very last push_back causes a reallocation, so it ends up almost half-empty. For std::deque, the worst case is when the subarrays at the beginning and end both contain only one element.

You’re better off learning about how the containers actually work, and constructing the worst-case scenarios for yourself, taking into consideration what your program does. It’s not too complicated, and the general knowledge is very useful.

[Thiago Macieira]

On Monday 13 April 2015 14:58:48 Marcelo Zimbres wrote:
> I am not assuming it is fixed, I am assuming it is known and can be returned
> to the user. It sounds strange to me that it is not possible to know how
> much memory
> a container is going to use, if I insert n elements into it.

It might not be, if we're talking about a generic container. It might have
different allocation strategies based on how it got to that point.

A hash map, for example, may need to rehash; a tree may need to rebalance,
etc.
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
PGP/GPG: 0x6EF45358; fingerprint:
E067 918B B660 DBD1 105C 966C 33F5 F005 6EF4 5358

[David Rodríguez Ibeas]

I have had a similar need in the past, and used hard-coded knowledge of the container.  That is, building a test allocator, extracting the required information, verified the implementation, added tests that would assert if the expectations change and hardcode the information into the binary.

Some clarifications on the use case, regarding previous comments from David Krauss and Thiago Macierira: when I have used this, I was not looking for  a worst case and looking at the growth strategies, but rather efficient building of a data structure for a single use. Say that you have 1000 elements in a vector and you want to build lookup, data does not change during the computation, I can create a unordered_map<K,V>, reserve the desired capacity and insert the elements. I can then new a single chunk of memory and use an allocator pulling memory from there. 1000 elements, 1000 inserts into the map, a single call to the allocator. Another advantage with this form of arena allocator is that allocations/deallocations are cheap (single pointer increment and return statement for allocate, no-op for deallocate as I can throw the whole arena away when I'm done with the container.

This is a niche use case, I don't imagine most people would be doing this, but it is valuable in certain usage patterns.

    David