Memory management is especially important for immutable data structures. This is mainly due to:
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.
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
Warning
doxygenstruct: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml
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;
}
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
.
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
doxygenclass: Cannot find file: /tmp/B.ehzfvydb/BUILD/immer-0.8.1/doc/_doxygen/xml/index.xml
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 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
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