aboutsummaryrefslogtreecommitdiff
path: root/src/txdb.cpp
diff options
context:
space:
mode:
authorMartin Ankerl <Martin.Ankerl@gmail.com>2017-12-29 11:36:11 +0100
committerMartin Ankerl <Martin.Ankerl@gmail.com>2017-12-29 11:36:11 +0100
commit1e0ee9095ce87a3cee0b44a120f6297ac672f5d0 (patch)
tree36ac4110adf4859e426474a24cad4a7a69d4bad7 /src/txdb.cpp
parent5180a86c96bc05d2a731f70f36aae28ab5a3fad4 (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/txdb.cpp')
0 files changed, 0 insertions, 0 deletions