Memory management

Memory management is especially important for immutable data structures. This is mainly due to:

  1. In order to preserve the old value, new memory has to be allocated to store the new data whenever a container is manipulated. Thus, more allocations are performed when changing than with traditional mutable data structures.

  2. In order to support structural sharing transparently, some kind of garbage collection mechanism is required. Passing immutable data structures around is, internally, just passing references, thus the system needs to figure out somehow when old values are not referenced anymore and should be deallocated.

Thus, most containers in this library can be customized via policies in order to use different allocation and garbage collection strategies.

Warning

doxygentypedef: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Warning

doxygentypedef: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Warning

doxygentypedef: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Memory policy

Warning

doxygenstruct: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Example: tracing garbage collection

It is noteworthy that all aspects of a immer::memory_policy are not completely orthogonal.

Let’s say you want to use a tracing garbage collector. Actually, we already provide a heap that interfaces with the Boehm’s conservative garbage collector. Chunks of memory allocated with this heap do not need to be deallocated, instead, after a certain number of allocations, the heap itself will scan the stack and all allocated memory to find references to other blocks of memory. The memory that is not referenced anymore is automatically freed. Thus, no reference counting mechanism is needed, and it makes no sense to use this heap with anything else than the immer::no_refcount_policy. Also, a big object can be separated in parts that contain pointers and parts that do not, which make scanning references faster. So it makes most sense to use prefer_fewer_bigger_objects = false.

Note

There are few considerations to note when using gc_heap with containers. Please make sure to read its documentation section before using it.

#include <immer/heap/gc_heap.hpp>
#include <immer/heap/heap_policy.hpp>
#include <immer/memory_policy.hpp>
#include <immer/refcount/no_refcount_policy.hpp>
#include <immer/vector.hpp>

#include <iostream>

// declare a memory policy for using a tracing garbage collector
using gc_policy = immer::memory_policy<immer::heap_policy<immer::gc_heap>,
                                       immer::no_refcount_policy,
                                       immer::default_lock_policy,
                                       immer::gc_transience_policy,
                                       false>;

// alias the vector type so we are not concerned about memory policies
// in the places where we actually use it
template <typename T>
using my_vector = immer::vector<T, gc_policy>;

int main()
{
    auto v =
        my_vector<const char*>().push_back("hello, ").push_back("world!\n");

    for (auto s : v)
        std::cout << s;
}

Heaps

A heap policy is a metafunction class that given the sizes of the objects that we want to allocate, it returns a heap that can allocate objects of those sizes.

A heap is a type with methods void* allocate(std::size_t) and void deallocate(void*) that return and release raw memory. For a canonical model of this concept check the immer::cpp_heap.

Note

Currently, heaps can only have global state. Having internal state poses conceptual problems for immutable data structures: should a const method of a container modify its internal allocator state? Should every immutable container object have its own internal state, or new objects made from another one just keep a reference to the allocator of the parent?

On the other hand, having some scoped state does make sense for some use-cases of immutable data structures. For example, we might want to support variations of region based allocation. This interface might evolve to support some kind of non-global state to accommodate these use cases.

Why not use the standard allocator interface?

The standard allocator API was not designed to support different allocation strategies, but to abstract over the underlying memory model instead. In C++11 the situation improves, but the new API is stateful, posing various challenges as described in the previous note. So far it was easier to provide our own allocation interface. In the future, we will provide adaptors so standard-compatible allocators can also be used with immer.

Heap policies

Warning

doxygenstruct: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Warning

doxygenstruct: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Standard heap

Warning

doxygenstruct: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Malloc heap

Warning

doxygenstruct: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Garbage collected heap

Warning

doxygenclass: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Heap adaptors

Inspired by Andrei Alexandrescu’s talk on allocators and Emery Berger’s heap layers we provide allocator adaptors that can be combined using C++ mixins. These enable building more complex allocators out of simpler strategies, or provide application specific optimizations on top of general allocators.

Warning

doxygenstruct: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Warning

doxygenstruct: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Warning

doxygenstruct: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Warning

doxygenstruct: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Warning

doxygenstruct: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Warning

doxygenstruct: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Warning

doxygenstruct: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Reference counting

Reference counting is the most commonly used garbage collection strategy for C++. It can be implemented non-intrusively, in a way orthogonal to the allocation strategy. It is deterministic, playing well with RAII.

A memory policy can provide a reference counting strategy that containers can use to track their contents.

Warning

doxygenstruct: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Warning

doxygenstruct: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Warning

doxygenstruct: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Transience

In order to support transients, it is needed to provide a mechanism to track the ownership of the data allocated inside the container. This concept is encapsulated in transience policies.

Note that when reference counting is available, no such mechanism is needed. However, when tracing garbage collection is used instead, a special policy has to be provided. Otherwise, the transient API is still available, but it will perform poorly, since it won’t be able to mutate any data in place.

Warning

doxygenstruct: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml

Warning

doxygenstruct: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml