mCRL2
Loading...
Searching...
No Matches
aterm_pool_implementation.h
Go to the documentation of this file.
1// Author(s): Maurice Laveaux.
2// Copyright: see the accompanying file COPYING or copy at
3// https://github.com/mCRL2org/mCRL2/blob/master/COPYING
4//
5// Distributed under the Boost Software License, Version 1.0.
6// (See accompanying file LICENSE_1_0.txt or copy at
7// http://www.boost.org/LICENSE_1_0.txt)
8//
9
10#ifndef ATERMPP_DETAIL_ATERM_POOL_IMPLEMENTATION_H
11#define ATERMPP_DETAIL_ATERM_POOL_IMPLEMENTATION_H
12#pragma once
13
14#include <chrono>
15#include "aterm_pool.h"
16#include "aterm_pool_storage_implementation.h" // For store_in_argument_array.
17
18
19namespace atermpp
20{
21namespace detail
22{
23
25 m_int_storage(*this),
26 m_appl_storage(
27 *this,
28 *this,
29 *this,
30 *this,
31 *this,
32 *this,
33 *this,
34 *this
35 ),
36 m_appl_dynamic_storage(*this)
37{
40
42 {
44 }
45
46 // Initialize the empty list.
48}
49
51{
52 const std::size_t arity = sym.arity();
53
54 switch (arity)
55 {
56 case 0:
57 {
58 if (sym == get_symbol_pool().as_int())
59 {
60 m_int_storage.add_deletion_hook(sym, callback);
61 }
62 else
63 {
64 std::get<0>(m_appl_storage).add_deletion_hook(sym, callback);
65 }
66 }
67 break;
68 case 1:
69 std::get<1>(m_appl_storage).add_deletion_hook(sym, callback);
70 break;
71 case 2:
72 std::get<2>(m_appl_storage).add_deletion_hook(sym, callback);
73 break;
74 case 3:
75 std::get<3>(m_appl_storage).add_deletion_hook(sym, callback);
76 break;
77 case 4:
78 std::get<4>(m_appl_storage).add_deletion_hook(sym, callback);
79 break;
80 case 5:
81 std::get<5>(m_appl_storage).add_deletion_hook(sym, callback);
82 break;
83 case 6:
84 std::get<6>(m_appl_storage).add_deletion_hook(sym, callback);
85 break;
86 case 7:
87 std::get<7>(m_appl_storage).add_deletion_hook(sym, callback);
88 break;
89 default:
91 }
92}
93
95{
98}
99
101{
103 m_thread_pools.insert(m_thread_pools.end(), &pool);
104}
105
107{
109
110 auto it = std::find(m_thread_pools.begin(), m_thread_pools.end(), &pool);
111 if (it != m_thread_pools.end())
112 {
113 m_thread_pools.erase(it); // This only removes the pointer, not the underlying data
114 // structure, which only disappears when the thread is removed.
115 }
116}
117
119{
120 m_int_storage.print_performance_stats("integral_storage");
121 std::get<0>(m_appl_storage).print_performance_stats("term_storage");
122 std::get<1>(m_appl_storage).print_performance_stats("function_application_storage_1");
123 std::get<2>(m_appl_storage).print_performance_stats("function_application_storage_2");
124 std::get<3>(m_appl_storage).print_performance_stats("function_application_storage_3");
125 std::get<4>(m_appl_storage).print_performance_stats("function_application_storage_4");
126 std::get<5>(m_appl_storage).print_performance_stats("function_application_storage_5");
127 std::get<6>(m_appl_storage).print_performance_stats("function_application_storage_6");
128 std::get<7>(m_appl_storage).print_performance_stats("function_application_storage_7");
129
130 m_appl_dynamic_storage.print_performance_stats("arbitrary_function_application_storage");
131
132 // Print information for the local aterm pools.
134 {
135 local->print_local_performance_statistics();
136 }
137}
138
139std::size_t aterm_pool::capacity() const noexcept
140{
141 // Determine the total number of terms in any storage.
142 return m_int_storage.capacity()
143 + std::get<0>(m_appl_storage).capacity()
144 + std::get<1>(m_appl_storage).capacity()
145 + std::get<2>(m_appl_storage).capacity()
146 + std::get<3>(m_appl_storage).capacity()
147 + std::get<4>(m_appl_storage).capacity()
148 + std::get<5>(m_appl_storage).capacity()
149 + std::get<6>(m_appl_storage).capacity()
150 + std::get<7>(m_appl_storage).capacity()
152}
153
154std::size_t aterm_pool::size() const
155{
156 // Determine the total number of terms in any storage.
157 return m_int_storage.size()
158 + std::get<0>(m_appl_storage).size()
159 + std::get<1>(m_appl_storage).size()
160 + std::get<2>(m_appl_storage).size()
161 + std::get<3>(m_appl_storage).size()
162 + std::get<4>(m_appl_storage).size()
163 + std::get<5>(m_appl_storage).size()
164 + std::get<6>(m_appl_storage).size()
165 + std::get<7>(m_appl_storage).size()
167}
168
169// private
170
172{
173 // Defer garbage collection when it happens too often.
174 if (m_count_until_collection.load(std::memory_order_relaxed) <= 0)
175 {
176 if (allow_collect)
177 {
179 }
180 }
181 else
182 {
183 m_count_until_collection.fetch_sub(1, std::memory_order_relaxed);
184 }
185
186 if (m_count_until_resize.load(std::memory_order_relaxed) <= 0)
187 {
188 if (allow_collect)
189 {
191 }
192 }
193 else
194 {
195 m_count_until_resize.fetch_sub(1, std::memory_order_relaxed);
196 }
197}
198
200{
202 {
205 {
206 // Another thread has performed garbage collection, so we can ignore it.
207 return;
208 }
209
210 auto timestamp = std::chrono::system_clock::now();
211 std::size_t old_size = size();
212
213 // Mark the terms referenced by all thread pools.
214 for (const auto& pool : m_thread_pools)
215 {
216 pool->mark();
217 }
218
219 assert(std::get<0>(m_appl_storage).verify_mark());
220 assert(std::get<1>(m_appl_storage).verify_mark());
221 assert(std::get<2>(m_appl_storage).verify_mark());
222 assert(std::get<3>(m_appl_storage).verify_mark());
223 assert(std::get<4>(m_appl_storage).verify_mark());
224 assert(std::get<5>(m_appl_storage).verify_mark());
225 assert(std::get<6>(m_appl_storage).verify_mark());
226 assert(std::get<7>(m_appl_storage).verify_mark());
228
229 // Keep track of the duration for marking and reset for sweep.
230 auto mark_duration = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - timestamp).count();
231 timestamp = std::chrono::system_clock::now();
232 // Collect all terms that are not marked.
234 std::get<7>(m_appl_storage).sweep();
235 std::get<6>(m_appl_storage).sweep();
236 std::get<5>(m_appl_storage).sweep();
237 std::get<4>(m_appl_storage).sweep();
238 std::get<3>(m_appl_storage).sweep();
239 std::get<2>(m_appl_storage).sweep();
240 std::get<1>(m_appl_storage).sweep();
241 std::get<0>(m_appl_storage).sweep();
243
244 // Check that after sweeping the terms are consistent.
245 assert(m_int_storage.verify_sweep());
246 assert(std::get<0>(m_appl_storage).verify_sweep());
247 assert(std::get<1>(m_appl_storage).verify_sweep());
248 assert(std::get<2>(m_appl_storage).verify_sweep());
249 assert(std::get<3>(m_appl_storage).verify_sweep());
250 assert(std::get<4>(m_appl_storage).verify_sweep());
251 assert(std::get<5>(m_appl_storage).verify_sweep());
252 assert(std::get<6>(m_appl_storage).verify_sweep());
253 assert(std::get<7>(m_appl_storage).verify_sweep());
255
256 // Print some statistics.
258 {
259 // Update the times
260 auto sweep_duration = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - timestamp).count();
261
262 // Print the relevant information.
263 mCRL2log(mcrl2::log::info) << "g_term_pool(): Garbage collected " << old_size - size() << " terms, " << size() << " terms remaining in "
264 << mark_duration + sweep_duration << " ms (marking " << mark_duration << " ms + sweep " << sweep_duration << " ms).\n";
265 }
266
267 // Garbage collect function symbols.
269
271
272 // Use some heuristics to determine when the next collect should be called automatically.
274
276 {
278 }
279 }
280}
281
282function_symbol aterm_pool::create_function_symbol(const std::string& name, const std::size_t arity, const bool check_for_registered_functions)
283{
284 return m_function_symbol_pool.create(name, arity, check_for_registered_functions);
285}
286
287function_symbol aterm_pool::create_function_symbol(std::string&& name, const std::size_t arity, const bool check_for_registered_functions)
288{
289 return m_function_symbol_pool.create(std::forward<std::string>(name), arity, check_for_registered_functions);
290}
291
292bool aterm_pool::create_int(aterm& term, size_t val)
293{
294 return m_int_storage.create_int(term, val);
295}
296
298{
299 return std::get<0>(m_appl_storage).create_term(term, sym);
300}
301
302template<class ...Terms>
303bool aterm_pool::create_appl(aterm& term, const function_symbol& sym, const Terms&... arguments)
304{
305 if constexpr (sizeof...(Terms) <= 7)
306 {
307 return std::get<sizeof...(Terms)>(m_appl_storage).create_appl(term, sym, arguments...);
308 }
309 else
310 {
311 std::array<unprotected_aterm_core, sizeof...(Terms)> array;
312 store_in_argument_array(array, arguments...);
313 return m_appl_dynamic_storage.create_appl_dynamic(term, sym, array.begin(), array.end());
314 }
315}
316
317template<typename ForwardIterator>
319 const function_symbol& sym,
320 ForwardIterator begin,
321 ForwardIterator end)
322{
323 const std::size_t arity = sym.arity();
324
325 switch(arity)
326 {
327 case 0:
328 return std::get<0>(m_appl_storage).create_term(term, sym);
329 case 1:
330 return std::get<1>(m_appl_storage).template create_appl_iterator<ForwardIterator>(term, sym, begin, end);
331 case 2:
332 return std::get<2>(m_appl_storage).template create_appl_iterator<ForwardIterator>(term, sym, begin, end);
333 case 3:
334 return std::get<3>(m_appl_storage).template create_appl_iterator<ForwardIterator>(term, sym, begin, end);
335 case 4:
336 return std::get<4>(m_appl_storage).template create_appl_iterator<ForwardIterator>(term, sym, begin, end);
337 case 5:
338 return std::get<5>(m_appl_storage).template create_appl_iterator<ForwardIterator>(term, sym, begin, end);
339 case 6:
340 return std::get<6>(m_appl_storage).template create_appl_iterator<ForwardIterator>(term, sym, begin, end);
341 case 7:
342 return std::get<7>(m_appl_storage).template create_appl_iterator<ForwardIterator>(term, sym, begin, end);
343 default:
344 return m_appl_dynamic_storage.create_appl_dynamic(term, sym, begin, end);
345 }
346}
347
348template<typename InputIterator, typename ATermConverter>
350 const function_symbol& sym,
351 ATermConverter converter,
352 InputIterator begin,
353 InputIterator end)
354{
355 const std::size_t arity = sym.arity();
356 switch(arity)
357 {
358 case 0:
359 return std::get<0>(m_appl_storage).create_term(term, sym);
360 case 1:
361 return std::get<1>(m_appl_storage).template create_appl_iterator<InputIterator, ATermConverter>(term, sym, converter, begin, end);
362 case 2:
363 return std::get<2>(m_appl_storage).template create_appl_iterator<InputIterator, ATermConverter>(term, sym, converter, begin, end);
364 case 3:
365 return std::get<3>(m_appl_storage).template create_appl_iterator<InputIterator, ATermConverter>(term, sym, converter, begin, end);
366 case 4:
367 return std::get<4>(m_appl_storage).template create_appl_iterator<InputIterator, ATermConverter>(term, sym, converter, begin, end);
368 case 5:
369 return std::get<5>(m_appl_storage).template create_appl_iterator<InputIterator, ATermConverter>(term, sym, converter, begin, end);
370 case 6:
371 return std::get<6>(m_appl_storage).template create_appl_iterator<InputIterator, ATermConverter>(term, sym, converter, begin, end);
372 case 7:
373 return std::get<7>(m_appl_storage).template create_appl_iterator<InputIterator, ATermConverter>(term, sym, converter, begin, end);
374 default:
375 return m_appl_dynamic_storage.create_appl_dynamic(term, sym, converter, begin, end);
376 }
377}
378
380{
382 if (m_count_until_resize > 0)
383 {
384 // Another thread has resized the tables, so we can ignore it.
385 return;
386 }
387
388 auto timestamp = std::chrono::system_clock::now();
389 std::size_t old_capacity = capacity();
390 std::size_t old_symbols_capacity = m_function_symbol_pool.capacity();
391
392 // Attempt to resize all storages.
394
396 std::get<0>(m_appl_storage).resize_if_needed();
397 std::get<1>(m_appl_storage).resize_if_needed();
398 std::get<2>(m_appl_storage).resize_if_needed();
399 std::get<3>(m_appl_storage).resize_if_needed();
400 std::get<4>(m_appl_storage).resize_if_needed();
401 std::get<5>(m_appl_storage).resize_if_needed();
402 std::get<6>(m_appl_storage).resize_if_needed();
403 std::get<7>(m_appl_storage).resize_if_needed();
405
406 // Attempt to resize ever so often.
407 m_count_until_resize = 10000;
408
409 if (EnableGarbageCollectionMetrics && (old_capacity != capacity() || old_symbols_capacity != m_function_symbol_pool.capacity()))
410 {
411 // Only print if a resize actually took place.
412 auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - timestamp).count();
413
414 mCRL2log(mcrl2::log::info) << "aterm_pool: Resized hash tables from " << old_capacity << " to " << capacity() << " capacity in "
415 << duration << " ms.\n";
416 }
417}
418
420{
421 std::size_t result = 0;
422
423 for (const auto& pool : m_thread_pools)
424 {
425 result += pool->protection_set_size();
426 }
427
428 return result;
429}
430
431} // namespace detail
432} // namespace atermpp
433
434#endif // ATERMPP_DETAIL_ATERM_POOL_IMPLEMENTATION_H
void print_performance_stats(const char *identifier) const
Prints various performance statistics for this storage.
bool create_int(aterm &term, std::size_t value)
Creates a integral term with the given value.
void resize_if_needed()
Resizes the hash table if necessary.
bool verify_sweep()
Check that all arguments of a term application are marked properly.
void add_deletion_hook(function_symbol sym, term_callback callback)
Add a callback that is triggered whenever a term with the given function symbol is destroyed.
bool create_appl_dynamic(aterm &term, const function_symbol &sym, ForwardIterator begin, ForwardIterator end)
Creates a function application with the given function symbol and the arguments as provided by the gi...
std::size_t capacity() const noexcept
bool verify_mark()
Check that all arguments of a term application are marked properly.
void sweep()
sweep Destroys all terms that are not reachable. Requires that mark() was called first.
const function_symbol & as_int() noexcept
Definition aterm_pool.h:118
void created_term(bool allow_collect, mcrl2::utilities::shared_mutex &mutex)
Triggers garbage collection and resizing when conditions are met.
bool create_appl(aterm &term, const function_symbol &sym, const Terms &... arguments)
Creates a function application with the given function symbol and arguments.
std::atomic< bool > m_enable_garbage_collection
Definition aterm_pool.h:216
std::atomic< long > m_count_until_resize
Definition aterm_pool.h:214
void remove_thread_aterm_pool(thread_aterm_pool_interface &pool)
Remove thread specific aterm pool.
std::vector< thread_aterm_pool_interface * > m_thread_pools
The set of local aterm pools.
Definition aterm_pool.h:189
bool create_int(aterm &term, std::size_t val)
Creates a integral term with the given value.
function_symbol_pool m_function_symbol_pool
Storage for the function symbols.
Definition aterm_pool.h:192
void collect_impl(mcrl2::utilities::shared_mutex &mutex)
Collect garbage on all storages.
arbitrary_function_application_storage m_appl_dynamic_storage
Storage for term_appl with a dynamic number of arguments larger than 7.
Definition aterm_pool.h:210
function_symbol create_function_symbol(const std::string &name, const std::size_t arity, const bool check_for_registered_functions=false)
Creates a function symbol pair (name, arity).
aterm_core m_empty_list
Represents an empty list.
Definition aterm_pool.h:222
void print_performance_statistics() const
Prints various performance statistics for the term pool.
std::atomic< long > m_count_until_collection
Track the number of terms destroyed and reduce the freelist.
Definition aterm_pool.h:213
void register_thread_aterm_pool(thread_aterm_pool_interface &pool)
Register a thread specific aterm pool.
bool create_term(aterm &term, const function_symbol &sym)
Creates a term with the given function symbol.
void collect(mcrl2::utilities::shared_mutex &mutex)
Force garbage collection on all storages.
bool create_appl_dynamic(aterm &term, const function_symbol &sym, ForwardIterator begin, ForwardIterator end)
Creates a function application with the given function symbol and the arguments as provided by the gi...
mcrl2::utilities::shared_mutex m_shared_mutex
Garbage collection is enabled.
Definition aterm_pool.h:219
void add_deletion_hook(function_symbol sym, term_callback callback)
Add a callback that is triggered whenever a term with the given function symbol is destroyed.
function_symbol_pool & get_symbol_pool()
Definition aterm_pool.h:132
std::tuple< term_storage, function_application_storage< 1 >, function_application_storage< 2 >, function_application_storage< 3 >, function_application_storage< 4 >, function_application_storage< 5 >, function_application_storage< 6 >, function_application_storage< 7 > > m_appl_storage
Storage for function applications with a fixed number of arguments.
Definition aterm_pool.h:207
integer_term_storage m_int_storage
Storage for integral terms.
Definition aterm_pool.h:195
void resize_if_needed(mcrl2::utilities::shared_mutex &shared)
Resizes all storages if necessary.
std::size_t capacity() const noexcept
The number of terms that can be stored without resizing.
void sweep()
Collect all garbage function symbols.
void resize_if_needed()
Resize the function symbol pool if necessary.
const function_symbol & as_empty_list() noexcept
std::size_t capacity() const noexcept
function_symbol create(const std::string &name, const std::size_t arity, const bool check_for_registered_functions=false)
Creates a function symbol pair (name, arity), returns a pointer to an existing element if this pair i...
A thread specific aterm pool that provides a local interface to the global term pool....
Definition aterm_pool.h:40
std::size_t arity() const
Return the arity (number of arguments) of the function symbol (function_symbol).
An unprotected term does not change the reference count of the shared term when it is copied or moved...
Definition aterm_core.h:32
An exclusive lock guard for the shared_mutex.
This is simply an exclusive lock based on the standard library with the ability to perform no locks w...
Definition mutex.h:23
a pool allocator class
#define mCRL2log(LEVEL)
mCRL2log(LEVEL) provides the stream used to log.
Definition logger.h:395
static constexpr bool EnableGarbageCollectionMetrics
Enable to print garbage collection statistics.
static constexpr bool EnableAggressiveGarbageCollection
Performs garbage collection intensively for testing purposes.
void store_in_argument_array(std::array< unprotected_aterm_core, N > &argument_array, const Args &... args)
The main namespace for the aterm++ library.
Definition algorithm.h:21
void(* term_callback)(const aterm &)
Definition aterm.h:194