immer::free_list_heap_policy< Heap, Limit > Struct Template Reference

#include <heap_policy.hpp>

Classes
struct	optimized

Public Types
using	type = debug_size_heap< Heap >

Detailed Description

template<typename Heap, std::size_t Limit = default_free_list_size>
struct immer::free_list_heap_policy< Heap, Limit >

Heap policy that returns a heap with a free list of objects of max_size = max(Sizes...) on top an underlying Heap. Note these two properties of the resulting heap:

• Allocating an object that is bigger than max_size may trigger undefined behavior.
• Allocating an object of size less than max_size still returns an object of max_size.

Basically, this heap will always return objects of max_size. When an object is freed, it does not directly invoke std::free, but it keeps the object in a global linked list instead. When a new object is requested, it does not need to call std::malloc but it can directly pop and return the other object from the global list, a much faster operation.

This actually creates a hierarchy with two free lists:

• A thread_local free list is used first. It does not need any kind of synchronization and is very fast. When the thread finishes, its contents are returned to the next free list.
• A global free list using lock-free access via atomics.

Template Parameters

Heap	Heap to be used when the free list is empty.

.. tip:: For many applications that use immutable data structures significantly, this is actually the best heap policy, and it might become the default in the future.

Note that most our data structures internally use trees with the same big branching factors. This means that all vectors, maps, etc. can just allocate elements from the same free-list optimized heap. Not only does this lowers the allocation time, but also makes up for more efficient cache utilization. When a new node is needed, there are high chances the allocator will return a node that was just accessed. When batches of immutable updates are made, this can make a significant difference.

Definition at line 104 of file heap_policy.hpp.

Member Typedef Documentation

type

template<typename Heap , std::size_t Limit = default_free_list_size>

using immer::free_list_heap_policy< Heap, Limit >::type = debug_size_heap<Heap>

Definition at line 106 of file heap_policy.hpp.

---

The documentation for this struct was generated from the following file:

• src/immer/heap/heap_policy.hpp