diff options
author | Martin Ankerl <Martin.Ankerl@gmail.com> | 2017-12-29 11:36:11 +0100 |
---|---|---|
committer | Martin Ankerl <Martin.Ankerl@gmail.com> | 2017-12-29 11:36:11 +0100 |
commit | 1e0ee9095ce87a3cee0b44a120f6297ac672f5d0 (patch) | |
tree | 36ac4110adf4859e426474a24cad4a7a69d4bad7 /src/support/lockedpool.h | |
parent | 5180a86c96bc05d2a731f70f36aae28ab5a3fad4 (diff) |
Use best-fit strategy in Arena, now O(log(n)) instead O(n)
This replaces the first-fit algorithm used in the Arena with a best-fit. According to "Dynamic Storage Allocation: A Survey and Critical Review", Wilson et. al. 1995, http://www.scs.stanford.edu/14wi-cs140/sched/readings/wilson.pdf, both startegies work well in practice.
The advantage of using best-fit is that we can switch the slow O(n) algorithm to O(log(n)) operations. Additionally, some previously O(log(n)) operations are now replaced with O(1) operations by using a hash map. The end effect is that the benchmark runs about 2.5 times faster on my machine:
old: BenchLockedPool, 5, 530, 5.25749, 0.00196938, 0.00199755, 0.00198172
new: BenchLockedPool, 5, 1300, 5.11313, 0.000781493, 0.000793314, 0.00078606
I've run all unit tests and benchmarks.
Diffstat (limited to 'src/support/lockedpool.h')
-rw-r--r-- | src/support/lockedpool.h | 19 |
1 files changed, 14 insertions, 5 deletions
diff --git a/src/support/lockedpool.h b/src/support/lockedpool.h index 834f0371e2..3b6f82c6c7 100644 --- a/src/support/lockedpool.h +++ b/src/support/lockedpool.h @@ -10,6 +10,7 @@ #include <map> #include <mutex> #include <memory> +#include <unordered_map> /** * OS-dependent allocation and deallocation of locked/pinned memory pages. @@ -88,11 +89,19 @@ public: */ bool addressInArena(void *ptr) const { return ptr >= base && ptr < end; } private: - /** Map of chunk address to chunk information. This class makes use of the - * sorted order to merge previous and next chunks during deallocation. - */ - std::map<char*, size_t> chunks_free; - std::map<char*, size_t> chunks_used; + typedef std::multimap<size_t, char*> SizeToChunkSortedMap; + /** Map to enable O(log(n)) best-fit allocation, as it's sorted by size */ + SizeToChunkSortedMap size_to_free_chunk; + + typedef std::unordered_map<char*, SizeToChunkSortedMap::const_iterator> ChunkToSizeMap; + /** Map from begin of free chunk to its node in size_to_free_chunk */ + ChunkToSizeMap chunks_free; + /** Map from end of free chunk to its node in size_to_free_chunk */ + ChunkToSizeMap chunks_free_end; + + /** Map from begin of used chunk to its size */ + std::unordered_map<char*, size_t> chunks_used; + /** Base address of arena */ char* base; /** End address of arena */ |