Memory Management Techniques

[Christopher J. Pisz]

I am still playing with making custom memory management and learning
about it.

Out of the 15 example memory managers I've found Googling things up,
ZERO of them work if you do not know the size of the type you will be
allocating and only allocate that type. In other words, I cannot find a
memory manager that allows me to allocate space for more than one type.
Additionally, the design of the type is coupled to the memory manager,
because it contains an overload of new and delete just for that class type.

The idea of having my own memory management seems lucrative, because
there is often a time where I know I might be allocating some
10,000-1000,000 objects. We'd significantly improve performance if we
allocated a large chuck of space up front.

For example, this simple memory manager I found on IBM's site, that they
used as their first example.

https://www.ibm.com/developerworks/aix/tutorials/au-memorymanager/
(headers only)

//------------------------------------------------------------------------------
class SpecificToSimpleMM : public ComplexNumber
{
public:
SpecificToSimpleMM(double realPart, double SpecificToSimpleMMPart);
SpecificToSimpleMM(const SpecificToSimpleMM & rhs);
~SpecificToSimpleMM();

// These two operators call on a global instance of the memory
manager to allocated and free space
void * operator new(size_t size);
void operator delete(void * pointerToDelete);
};

//------------------------------------------------------------------------------
// Memory Manager that allocates space for multiple objects, of a
specific type, at a time
//
// Customized for objects of type SpecificToSimpleMM and works only in
single-threaded environments.
// Keeps a pool of SpecificToSimpleMM objects available and has future
allocations occur from this pool.
class SimpleMemoryManager : public IMemoryManager
{
// Node in the memory pool
struct FreeStoreNode
{
FreeStoreNode * m_next;
};

void expandPoolSize();
void cleanUp();

// The memory pool
FreeStoreNode * m_freeStoreHead;

public:

SimpleMemoryManager();
virtual ~SimpleMemoryManager();

virtual void * allocate(size_t);
virtual void free(void *);
};


They had two more; A "bitmapped memory manager" and a "freelist memory
manager", but reading over thier article, it seems to me that both can
only handle one type of object.


Can you point me to some memory management techniques that allow for
allocating different amounts of storage and are not designed to work
with one type only?

[Alf P. Steinbach]

On 28.11.2016 04:02, Christopher J. Pisz wrote:
[snip]

>
> Can you point me to some memory management techniques that allow for
> allocating different amounts of storage and are not designed to work
> with one type only?

Andrei's Loki library has a fast small objects allocator, as I recall.

It's open source.


Cheers & hth.,

- Alf

[Paavo Helde]

On 28.11.2016 5:02, Christopher J. Pisz wrote:
> I am still playing with making custom memory management and learning
> about it.
>
> Out of the 15 example memory managers I've found Googling things up,
> ZERO of them work if you do not know the size of the type you will be
> allocating and only allocate that type. In other words, I cannot find a
> memory manager that allows me to allocate space for more than one type.
> Additionally, the design of the type is coupled to the memory manager,
> because it contains an overload of new and delete just for that class type.

What do you mean? A memory allocator often needs to allocate memory for
other types than its "native" type. There is a special rebind mechanism
for that.

In C++ a custom memory allocator is a template, exactly because it needs
to be instantiated for different types. In your example there was no
template, so I assume it was illustrating something else than C++ memory
allocators.

Maybe you are confused what a memory allocator is in C++. It is not
something which you call from some overridden operator new (though it
may be called from there as well). No, a custom memory allocator is
primarily something which you can pass as a template argument for
std::vector or std::allocate_shared, etc.

From what I see in the debugger, my allocator template is often called
through the rebind mechanism for types like 'char' or
std::_Container_proxy, etc.

>
> The idea of having my own memory management seems lucrative, because
> there is often a time where I know I might be allocating some
> 10,000-1000,000 objects. We'd significantly improve performance if we
> allocated a large chuck of space up front.

These are called pooled memory allocators. There are many of them
existing, no need to reinvent wheels.

[...]

>
> Can you point me to some memory management techniques that allow for
> allocating different amounts of storage and are not designed to work
> with one type only?

http://en.cppreference.com/w/cpp/memory/allocator discusses rebind, with
some examples. In C++17 the rebind mechanism seems to be moved over to
allocator_traits, with some cleaner syntax.

hth
Paavo

[Christopher J. Pisz]

On 11/28/2016 2:37 AM, Paavo Helde wrote:
> On 28.11.2016 5:02, Christopher J. Pisz wrote:
>> I am still playing with making custom memory management and learning
>> about it.
>>
>> Out of the 15 example memory managers I've found Googling things up,
>> ZERO of them work if you do not know the size of the type you will be
>> allocating and only allocate that type. In other words, I cannot find a
>> memory manager that allows me to allocate space for more than one type.
>> Additionally, the design of the type is coupled to the memory manager,
>> because it contains an overload of new and delete just for that class
>> type.
>
> What do you mean? A memory allocator often needs to allocate memory for
> other types than its "native" type. There is a special rebind mechanism
> for that.
>
> In C++ a custom memory allocator is a template, exactly because it needs
> to be instantiated for different types. In your example there was no
> template, so I assume it was illustrating something else than C++ memory
> allocators.

Memory Management is not equivalent to C++ std::allocator from what I am
finding, and I have not found any that actually use post C++11 allocator
requirements, that works, beyond simply adding a logging features and
the like.

Most everything I find is a stand alone mememory management scheme that
does not use allocators at all.

> Maybe you are confused what a memory allocator is in C++. It is not
> something which you call from some overridden operator new (though it
> may be called from there as well). No, a custom memory allocator is
> primarily something which you can pass as a template argument for
> std::vector or std::allocate_shared, etc.

Nope. I know what it is. I've read up on it for a week now.
Even if I was to find a working example of an Allocator post C++11 that
worked and did anything beneficial, the actual memory management
technique would be separate from the allocator itself.

> From what I see in the debugger, my allocator template is often called
> through the rebind mechanism for types like 'char' or
> std::_Container_proxy, etc.
>
>>
>> The idea of having my own memory management seems lucrative, because
>> there is often a time where I know I might be allocating some
>> 10,000-1000,000 objects. We'd significantly improve performance if we
>> allocated a large chuck of space up front.
>
> These are called pooled memory allocators. There are many of them
> existing, no need to reinvent wheels.
>

I'd like to reinvent the wheel to learn how the wheel works if nothing
else. There seems to be demand for this kind of thing.

>>
>> Can you point me to some memory management techniques that allow for
>> allocating different amounts of storage and are not designed to work
>> with one type only?
>
> http://en.cppreference.com/w/cpp/memory/allocator discusses rebind, with
> some examples. In C++17 the rebind mechanism seems to be moved over to
> allocator_traits, with some cleaner syntax.

That example doesn't actually accomplish anything though. It just uses
the default. It does not show anyone how they would actually implement
their own allocator, one that contains state, or how to implement the
actual memory management.


Here are examples of what I am finding:

https://www.ibm.com/developerworks/aix/tutorials/au-memorymanager/
http://anki3d.org/cpp-allocators-for-games/
http://www.codinglabs.net/tutorial_memory_pool.aspx
https://jfdube.wordpress.com/2011/10/06/memory-management-part-2-allocations-tracking/

All of these are memory managers that all work with particular types.
None of them are actually put to use in an allocator.

Then I find links on allocator:

http://en.cppreference.com/w/cpp/memory/allocator
http://www.drdobbs.com/the-standard-librarian-what-are-allocato/184403759#1
https://rawgit.com/google/cxx-std-draft/allocator-paper/allocator_user_guide.html#examples

None of which have any memory management working with them, or have one
that actually compiles and works without severe problems.



From what I understand this is a two part problem. Firstly, actually
learning the memory management techniques, then finding one I can use
for various types. Secondly, implementing it in a way that it can be
used with an allocator. Neither endevour is going very well...

[Paavo Helde]

On 28.11.2016 11:59, Christopher J. Pisz wrote:
> On 11/28/2016 2:37 AM, Paavo Helde wrote:
>
> Memory Management is not equivalent to C++ std::allocator from what I am
> finding, and I have not found any that actually use post C++11 allocator
> requirements, that works, beyond simply adding a logging features and
> the like.

If you are interested in how exactly a memory manager works in low level
then I am pretty sure they are just working with bytes of memory, no
object type involved.

For a C++-compliant memory allocator, see e.g.

"https://www.threadingbuildingblocks.org/tutorial-intel-tbb-scalable-memory-allocator"

Their C++-compliant allocator is just a wrapper around C-style interface
using untyped memory blocks: scalable_malloc() and scalable_free(). One
can use these directly as well. Here you have low-level implementation
which does not care about types, and the high-level C++-compliant
allocator template which works for any type (see the rebind member).

Quote from TBB scalable_allocator.h:

//! Meets "allocator" requirements of ISO C++ Standard, Section 20.1.5
/** The members are ordered the same way they are in section 20.4.1
of the ISO C++ standard.
@ingroup memory_allocation */
template<typename T>
class scalable_allocator {
public:
typedef typename internal::allocator_type<T>::value_type value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
template<class U> struct rebind {
typedef scalable_allocator<U> other;
};

scalable_allocator() throw() {}
scalable_allocator( const scalable_allocator& ) throw() {}
template<typename U> scalable_allocator(const
scalable_allocator<U>&) throw() {}

pointer address(reference x) const {return &x;}
const_pointer address(const_reference x) const {return &x;}

//! Allocate space for n objects.
pointer allocate( size_type n, const void* /*hint*/ =0 ) {
return static_cast<pointer>( scalable_malloc( n *
sizeof(value_type) ) );
}

//! Free previously allocated block of memory
void deallocate( pointer p, size_type ) {
scalable_free( p );
}

//! Largest value for which method allocate might succeed.
size_type max_size() const throw() {
size_type absolutemax = static_cast<size_type>(-1) / sizeof
(value_type);
return (absolutemax > 0 ? absolutemax : 1);
}
#if __TBB_ALLOCATOR_CONSTRUCT_VARIADIC
template<typename U, typename... Args>
void construct(U *p, Args&&... args)
{ ::new((void *)p) U(std::forward<Args>(args)...); }
#else // __TBB_ALLOCATOR_CONSTRUCT_VARIADIC
#if __TBB_CPP11_RVALUE_REF_PRESENT
void construct( pointer p, value_type&& value ) { ::new((void*)(p))
value_type( std::move( value ) ); }
#endif
void construct( pointer p, const value_type& value )
{::new((void*)(p)) value_type(value);}
#endif // __TBB_ALLOCATOR_CONSTRUCT_VARIADIC
void destroy( pointer p ) {p->~value_type();}
};

[Richard]

[Please do not mail me a copy of your followup]

"Alf P. Steinbach" <alf.p.stein...@gmail.com> spake the secret code
<o1gh57$q53$1...@dont-email.me> thusly:

>On 28.11.2016 04:02, Christopher J. Pisz wrote:
>[snip]
>>
>> Can you point me to some memory management techniques that allow for
>> allocating different amounts of storage and are not designed to work
>> with one type only?
>
>Andrei's Loki library has a fast small objects allocator, as I recall.

<http://loki-lib.sourceforge.net/>

I thought there was one in EASTL as well, but it doesn't seem to have
any allocators.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Terminals Wiki <http://terminals-wiki.org>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>

[Richard]

[Please do not mail me a copy of your followup]

som...@somewhere.net spake the secret code
<o1gv3f$2ae$1...@dont-email.me> thusly:

>Most everything I find is a stand alone mememory management scheme that
>does not use allocators at all.

Yes, the whole std::allocator thing is confusing because its name
leads you to believe it has responsibilities that it doesn't have.

Basically, std::allocator's raison d'etre is the near/fear memory
pointer model of 16-bit x86 machines.

This is from memory of a talk on allocators. I think it was this one:
<https://www.youtube.com/watch?v=LIb3L4vKZ7U>
std::allocator is to Allocation what
std::vector is to Vexation

[Vir Campestris]

On 28/11/2016 18:28, Richard wrote:
> Basically, std::allocator's raison d'etre is the near/fear memory
> pointer model of 16-bit x86 machines.

Yes, the '286 memory model certainly scared me :)

But the OP's question sounds like calloc - allocate n objects of size m
all in one go (and then zero the lot).

That's a separate issue to running the constructor on every one of those
C++ objects you want to put on there. But I'd be astonished if resize on
a std::vector didn't allocate all in one block, then run all the
constructors... assuming they aren't trivial POD types that don't have one.

Andy

[asetof...@gmail.com]

Allocator? What does it mean? If it is malloc() free() implementation there is K&R2 that says in its pages, where to start, I remember from that custom malloc is possible implement C++ memory operators new() delete() too

[Öö Tiib]

No, it is C++ class interface concept of Allocator.
Standard library provides standard Allocator template
that is named 'std::allocator'. All standard templates that expect
allocator argument have it as default. So for example 'std::vector'
takes two arguments:

template< class T
, class Allocator = std::allocator<T> >
class vector;

[Christopher J. Pisz]

No, the word 'allocator' did not appear in the original post at all.
So it means nothing, because it isn't there to begin with.

[Chris M. Thomasson]

On 11/27/2016 7:02 PM, Christopher J. Pisz wrote:
> I am still playing with making custom memory management and learning
> about it.

[...]

> Can you point me to some memory management techniques that allow for
> allocating different amounts of storage and are not designed to work
> with one type only?

Check out the source of Hoard for an example:

https://github.com/emeryberger/Hoard

[Richard Damon]

On 11/27/16 10:02 PM, Christopher J. Pisz wrote:
> I am still playing with making custom memory management and learning
> about it.
>
> Out of the 15 example memory managers I've found Googling things up,
> ZERO of them work if you do not know the size of the type you will be
> allocating and only allocate that type. In other words, I cannot find a
> memory manager that allows me to allocate space for more than one type.
> Additionally, the design of the type is coupled to the memory manager,
> because it contains an overload of new and delete just for that class type.
>
> The idea of having my own memory management seems lucrative, because
> there is often a time where I know I might be allocating some
> 10,000-1000,000 objects. We'd significantly improve performance if we
> allocated a large chuck of space up front.
>
> For example, this simple memory manager I found on IBM's site, that they
> used as their first example.
>

...

>
> They had two more; A "bitmapped memory manager" and a "freelist memory
> manager", but reading over thier article, it seems to me that both can
> only handle one type of object.
>
>
> Can you point me to some memory management techniques that allow for
> allocating different amounts of storage and are not designed to work
> with one type only?
>
>

The idea of the custom memory manager will generally only really make
sense if there is something about the memory you want to manage that
doesn't fit the 'standard' model. For truly unpredictable/variable
object, the standard malloc is fairly good, and you are unlikely going
to improve on it unless you know something about the objects you will be
allocating.

Generally, they DO make a system call to get the base memory for the
heap in moderately large chunks. This is something you could possibly
tune. You also could just make one big call to expand the heap, then
free the memory and then move on, the heap is unlikely to be shrunken
immediately.

[Richard]

[Please do not mail me a copy of your followup]

Richard Damon <Ric...@Damon-Family.org> spake the secret code
<2LK0A.266835$8F2....@fx42.iad> thusly:

>The idea of the custom memory manager will generally only really make
>sense if there is something about the memory you want to manage that
>doesn't fit the 'standard' model.

The most overwhelming reason to use a custom memory manager is to
control locality of reference to increase the cache hit rate.

This is why most games simply use fixed size arrays and avoid the
heap. If they use the heap, they may use custom memory managers to
get better cache locality for their objects ('pool' allocators) than
that provided by the standard memory allocator, which makes no claims
about locality of reference, or even claims about the maximum amount
of memory obtained from the underlying system. Fragmentation is
another reason to use a custom memory allocator. Hell, even just
using google's malloc/free replacement can often be a big win.
<http://goog-perftools.sourceforge.net/doc/tcmalloc.html>

[Chris M. Thomasson]

Also, don't forget about good ol Reaps:

https://people.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf

A region allocator mixed with a free operation.