1 | // |
2 | // immer: immutable data structures for C++ |
3 | // Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente |
4 | // |
5 | // This software is distributed under the Boost Software License, Version 1.0. |
6 | // See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt |
7 | // |
8 | |
9 | #pragma once |
10 | |
11 | #include <immer/heap/debug_size_heap.hpp> |
12 | #include <immer/heap/free_list_heap.hpp> |
13 | #include <immer/heap/split_heap.hpp> |
14 | #include <immer/heap/thread_local_free_list_heap.hpp> |
15 | #include <immer/config.hpp> |
16 | |
17 | #include <cstdlib> |
18 | #include <algorithm> |
19 | |
20 | namespace immer { |
21 | |
22 | /*! |
23 | * Heap policy that unconditionally uses its `Heap` argument. |
24 | */ |
25 | template <typename Heap> |
26 | struct heap_policy |
27 | { |
28 | using type = Heap; |
29 | |
30 | template <std::size_t> |
31 | struct optimized |
32 | { |
33 | using type = Heap; |
34 | }; |
35 | }; |
36 | |
37 | template <typename Deriv, typename HeapPolicy> |
38 | struct enable_optimized_heap_policy |
39 | { |
40 | static void* operator new (std::size_t size) |
41 | { |
42 | using heap_type = typename HeapPolicy |
43 | ::template optimized<sizeof(Deriv)>::type; |
44 | |
45 | return heap_type::allocate(size); |
46 | } |
47 | |
48 | static void operator delete (void* data, std::size_t size) |
49 | { |
50 | using heap_type = typename HeapPolicy |
51 | ::template optimized<sizeof(Deriv)>::type; |
52 | |
53 | heap_type::deallocate(size, data); |
54 | } |
55 | }; |
56 | |
57 | /*! |
58 | * Heap policy that returns a heap with a free list of objects |
59 | * of `max_size = max(Sizes...)` on top an underlying `Heap`. Note |
60 | * these two properties of the resulting heap: |
61 | * |
62 | * - Allocating an object that is bigger than `max_size` may trigger |
63 | * *undefined behavior*. |
64 | * |
65 | * - Allocating an object of size less than `max_size` still |
66 | * returns an object of `max_size`. |
67 | * |
68 | * Basically, this heap will always return objects of `max_size`. |
69 | * When an object is freed, it does not directly invoke `std::free`, |
70 | * but it keeps the object in a global linked list instead. When a |
71 | * new object is requested, it does not need to call `std::malloc` but |
72 | * it can directly pop and return the other object from the global |
73 | * list, a much faster operation. |
74 | * |
75 | * This actually creates a hierarchy with two free lists: |
76 | * |
77 | * - A `thread_local` free list is used first. It does not need any |
78 | * kind of synchronization and is very fast. When the thread |
79 | * finishes, its contents are returned to the next free list. |
80 | * |
81 | * - A global free list using lock-free access via atomics. |
82 | * |
83 | * @tparam Heap Heap to be used when the free list is empty. |
84 | * |
85 | * @rst |
86 | * |
87 | * .. tip:: For many applications that use immutable data structures |
88 | * significantly, this is actually the best heap policy, and it |
89 | * might become the default in the future. |
90 | * |
91 | * Note that most our data structures internally use trees with the |
92 | * same big branching factors. This means that all *vectors*, |
93 | * *maps*, etc. can just allocate elements from the same free-list |
94 | * optimized heap. Not only does this lowers the allocation time, |
95 | * but also makes up for more efficient *cache utilization*. When |
96 | * a new node is needed, there are high chances the allocator will |
97 | * return a node that was just accessed. When batches of immutable |
98 | * updates are made, this can make a significant difference. |
99 | * |
100 | * @endrst |
101 | */ |
102 | template <typename Heap, |
103 | std::size_t Limit = default_free_list_size> |
104 | struct free_list_heap_policy |
105 | { |
106 | using type = debug_size_heap<Heap>; |
107 | |
108 | template <std::size_t Size> |
109 | struct optimized |
110 | { |
111 | using type = split_heap< |
112 | Size, |
113 | with_free_list_node< |
114 | thread_local_free_list_heap< |
115 | Size, |
116 | Limit, |
117 | free_list_heap< |
118 | Size, Limit, |
119 | debug_size_heap<Heap>>>>, |
120 | debug_size_heap<Heap>>; |
121 | }; |
122 | }; |
123 | |
124 | /*! |
125 | * Similar to @ref free_list_heap_policy, but it assumes no |
126 | * multi-threading, so a single global free list with no concurrency |
127 | * checks is used. |
128 | */ |
129 | template <typename Heap, |
130 | std::size_t Limit = default_free_list_size> |
131 | struct unsafe_free_list_heap_policy |
132 | { |
133 | using type = Heap; |
134 | |
135 | template <std::size_t Size> |
136 | struct optimized |
137 | { |
138 | using type = split_heap< |
139 | Size, |
140 | with_free_list_node< |
141 | unsafe_free_list_heap< |
142 | Size, Limit, |
143 | debug_size_heap<Heap>>>, |
144 | debug_size_heap<Heap>>; |
145 | }; |
146 | }; |
147 | |
148 | } // namespace immer |
149 | |