Should I pass allocator as a function parameter? (my misunderstanding about allocator)

Question

After I am studying about allocator for a few days by reading some articles
(cppreference and Are we out of memory) ,
I am confused about how to control a data-structure to allocate memory in a certain way.

I am quite sure I misunderstand something,
so I will divide the rest of question into many parts to make my mistake easier to be refered.

Here is what I (mis)understand :-

Snippet

Suppose that B::generateCs() is a function that generates a list of C from a list of CPrototype.
The B::generateCs() is used in B() constructor:-

class C          {/*some trivial code*/};
class CPrototype {/*some trivial code*/};
class B {
    public: 
    std::vector<C> generateCs() {  
        std::vector<CPrototype> prototypes = getPrototypes();
        std::vector<C> result;                     //#X
        for(std::size_t n=0; n < prototypes.size(); n++) {
            //construct real object  (CPrototype->C)
            result.push_back( makeItBorn(prototypes[n]) ); 
        }
        return result;
    }
    std::vector<C> bField;    //#Y
    B() {
        this->bField = generateCs();    //#Y  ; "generateCs()" is called only here
    }
    //.... other function, e.g. "makeItBorn()" and "getPrototypes()"
};

From the above code, std::vector<C> currently uses a generic default std::allocator.

For simplicity, from now on, let's say there are only 2 allocators (beside the std::allocator) ,
which I may code it myself or modify from somewhere :-

• HeapAllocator
• StackAllocator

Part 1 (#X)

This snippet can be improved using a specific type allocator.
It can be improved in 2 locations. (#X and #Y)

std::vector<C> at line #X seems to be a stack variable,
so I should use stack allocator :-

std::vector<C,StackAllocator> result;   //#X

This tends to yield a performance gain. (#X is finished.)

Part 2 (#Y)

Next, the harder part is in B() constructor. (#Y)
It would be nice if the variable bField has an appropriate allocation protocol.

Just coding the caller to use allocator explicitly can't achieve it, because the caller of constructor can only do as best as :-

std::allocator<B> bAllo;   
B* b = bAllo.allocate(1);   

which does not have any impact on allocation protocol of bField.

Thus, it is duty of constructor itself to pick a correct allocation protocol.

Part 3

I can't know whether an instance of B will be constructed as a heap variable or a stack variable.
It is matter because this information is importance for picking a correct allocator/protocol.

If I know which one it is (heap or stack), I can change declaration of bField to be:-

std::vector<C,StackAllocator> bField;     //.... or ....
std::vector<C,HeapAllocator> bField;     

Unfortunately, with the limited information (I don't know which it will be heap/stack, it can be both),
this path (using std::vector) leads to the dead end.

Part 4

Therefore, the better way is passing allocator into constructor:-

MyVector<C> bField; //create my own "MyVector" that act almost like "std::vector"
B(Allocator* allo) {
    this->bField.setAllocationProtocol(allo);  //<-- run-time flexibility 
    this->bField = generateCs();   
}

It is tedious because callers have to pass an allocator as an additional parameter,
but there are no other ways.

Moreover, it is the only practical way to gain the below data-coherence advantage when there are many callers, each one use its own memory chunk:-

class System1 {
    Allocator* heapForSystem1;
    void test(){
        B b=B(heapForSystem1);
    }
};
class System2 {
    Allocator* heapForSystem2;
    void test(){
        B b=B(heapForSystem2);
    }
};

Question

• Where did I start to go wrong, how?
• How can I improve the snippet to use appropriate allocator (#X and #Y)?
• When should I pass allocator as a parameter?

It is hard to find a practical example about using allocator.

Edit (reply Walter)

... using another than std:allocator<> is only rarely recommendable.

For me, it is the core of Walter's answer.
It would be a valuable knowledge if it is reliable.

1. Are there any book/link/reference/evidence that support it?
The list doesn't support the claim. (It actually supports the opposite a little.)
Is it from personal experience?

2. The answer somehow contradict with many sources. Please defense.
There are many sources that recommend not to use std:allocator<>.

• Are we out of memory :
  Can't answer "How much memory are you using for subsystem X?" is a guilty.
• Custom C++ allocators suitable for video games
  It implies that custom allocator is a must for console games.
  _{@ section "Why replace the default allocator?"}
• Memory Management part 1 of 3
  without custom allocator = "every now and then there’s a little lag (in game)"

More specifically, are they just a "hype" that rarely worth using in real world?

Another small question :-
Can the claim be expanded to "Most quality games rarely use custom allocator"?

3. If I am in such rare situation, I have to pay the cost, right?

There are only 2 good ways:-

• passing allocator as template argument, or
• as a function's (including constructor) parameter
• (another bad approach is to create some global flag about what protocol to use)

Is it correct?

Answer 1

In C++, the allocator used for the standard containers is tied to the container type (but see below). Thus, if you want to control the allocation behaviour of your class (including its container members), the allocator must be part of the type, i.e. you must pass it as a template parameter:

template<template <typename T> Allocator>
class B
{
public:
  using allocator = Allocator<C>
  using fieldcontainer = std::vector<C,allocator>;
  B(allocator alloc=allocator{})
  : bFields(create_fields(alloc)) {}
private:
  const fieldcontainer bFields;
  static fieldcontainer create_fields(allocator);
};

Note, however, that there is experimental polymorphic allocator support, which allows you change the allocator behaviour independently of the type. This is certainly preferable to designing your own MyVector<> template.

Note that using another than std::allocator<> is only recommendable if there is a good reason. Possible cases are as follows.

1. A stack allocator may be preferred for small objects that are frequently allocated and de-allocated, but even the heap allocator may not be less efficient.

2. An allocator that provides memory aligned to, say, 64bytes (suitable for aligned loading into AVX registers).

3. A cache-aligned allocator is useful to avoid false sharing in multi-threaded situations.

4. An allocator could avoid default initialising trivially constructible objects to enhance performance in multi-threaded settings.

---

note added in response to additional questions.

The article Are we out of memory dates from 2008 and doesn't apply to contemporary C++ practice (using the C++11 standard or later), when memory management using std containers and smart pointers (std::unique_ptr and std::shared_ptr) avoids memory leaks, which are the main source of increasing memory demand in poorly written code.

When writing code for certain specific applications, there may well be good reasons to use a custom allocator -- and the C++ standard library supports this, so this is a legitimate and appropriate approach. The good reasons include those listed already above, in particular when high performance is required in a multi-threaded environment or to be achieved via SIMD instructions.

If memory is very limited (as it may be on some game consoles), a custom allocator cannot really magically increase the amount of memory. So in this case the usage of the allocator, not the allocator itself, is most critical. A custom allocator may help reducing memory fragmentation, though.

Answer 2

It sounds like you are misunderstanding what a stack allocator is. A stack allocator is just an allocator that uses a stack, the data structure. A stack allocator can manage memory that is either allocated on the stack or the heap. It is dangerous to use if you don't know what you are doing as a stack allocator deallocates all the memory past the specified pointer when deallocate is called. You can use a stack allocator for when the most recently initialized element in a data structure is always the next one destroyed (or if you end up destroying them all at once in the end).

You can look at some of the std collections to see how they allow programmers to supply a specified allocator such as std::vector. They use an optional template argument so the user can choose the allocator class. It also allows you to pass the allocator in as an instance if you want to. If you don't, it instantiates one with the default constructor. If you don't choose an allocator class, then it uses the default allocater which just uses the heap. You could do the same.

template<typename C, typename Allocator = std::allocator<C> >
class B {

   vector<C, Allocator> bField;

   void generateCs() {  
     std::vector<CPrototype> prototypes = getPrototypes();
     for(std::size_t n=0; n < prototypes.size(); n++) {
         //construct real object  (CPrototype->C)
         bField.push_back( makeItBorn(prototypes[n]) ); 
     }
   }

   B(const Allocator& allo = Allocator()) : bField(allo) {
       generateCs();
   }
}

This allows the user to have control over allocation when they want to, but they also ignore it if they don't care