Use best-fit strategy in Arena, now O(log(n)) instead O(n) #12048

1. 
   martinus commented at 10:40 am on December 29, 2017: contributor

   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 O(n) allocation to O(log(n)). Additionally, some previously O(log(n)) operations are now O(1) operations by using hash maps. The end effect is that the benchmark runs about 2.5 times faster on my machine:

   # Benchmark, evals, iterations, total, min, max, median
   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, and increased the number of iterations so that BenchLockedPool takes about 5 seconds again.

2. 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.

   1e0ee9095c
3. fanquake added the label Refactoring on Dec 29, 2017
4. fanquake requested review from laanwj on Dec 29, 2017
5. 
   jonasschnelli commented at 7:16 am on January 4, 2018: contributor

   Context: LockedPool is used for the secure_allocator which is used to allocate memory for private keys (mainly wallet, but also signrawtransactions and some import commands).

   PR makes sense to me. Concept ACK.

6. in src/support/lockedpool.cpp:109 in 1e0ee9095c outdated

   111-    auto next = chunks_free.upper_bound(freed.first);
   112-    auto prev = (next == chunks_free.begin()) ? chunks_free.end() : std::prev(next);
   113-    if (prev == chunks_free.end() || !extend(prev, freed))
   114-        prev = chunks_free.emplace_hint(next, freed);
   115-    if (next != chunks_free.end() && extend(prev, *next))
   116+    // Coalesc freed with previous chunk
   

   ---

   ---

   

   jimpo commented at 7:49 am on January 4, 2018:

   typo: Coalesce

   ---

   

   martinus commented at 8:39 am on January 6, 2018:

   thanks, fixed
7. in src/support/lockedpool.cpp:110 in 1e0ee9095c outdated

   112-    auto prev = (next == chunks_free.begin()) ? chunks_free.end() : std::prev(next);
   113-    if (prev == chunks_free.end() || !extend(prev, freed))
   114-        prev = chunks_free.emplace_hint(next, freed);
   115-    if (next != chunks_free.end() && extend(prev, *next))
   116+    // Coalesc freed with previous chunk
   117+    auto prev = chunks_free_end.find(freed.first);
   

   ---

   ---

   

   jimpo commented at 8:02 am on January 4, 2018:

   Why is the chunks_free_end map required instead of iterating one backwards from next as is done in the current code?

   ---

   

   martinus commented at 9:25 am on January 4, 2018:

   the cunks_free used to be an std::map that was sorted by char*. There it was possible to use std::prev to just find what memory address came before. I have replaced this sorted map with an std::unordered_map, then it’s not possible any more to just find the previous address quickly within the same map. That’s why I have added another map that contains the back links. So this change replaces one O(log(n)) lookup + std::prev() call with two O(1) lookups.
8. in src/support/lockedpool.cpp:72 in 1e0ee9095c outdated

   71-    if (it == chunks_free.end())
   72+    // Pick a large enough free-chunk. Returns an iterator pointing to the first element that is not less than key.
   73+    // This allocation strategy is best-fit. According to "Dynamic Storage Allocation: A Survey and Critical Review",
   74+    // Wilson et. al. 1995, http://www.scs.stanford.edu/14wi-cs140/sched/readings/wilson.pdf, best-fit and first-fit
   75+    // policies seem to work well in practice.
   76+    auto sizePtrIt = size_to_free_chunk.lower_bound(size);
   

   ---

   ---

   

   jimpo commented at 8:04 am on January 4, 2018:

   nit: Variable names are snake_case, per developer guidelines. Fix sizePtrIt, sizeRemaining, itRemaining.

   ---

   

   martinus commented at 8:38 am on January 6, 2018:

   done!
9. 
   jimpo commented at 8:04 am on January 4, 2018: contributor

   Concept ACK
10. fix nits: variable naming, typos 5fbf7c478a
11. 
    laanwj commented at 10:24 pm on March 6, 2018: member

    Concept ACK - this is a great improvement, thanks! will need to review in detail that various data structures stay consistent, though.
12. laanwj added the label Resource usage on Mar 6, 2018
13. laanwj assigned laanwj on Mar 6, 2018
14. 
    eklitzke commented at 8:12 am on March 11, 2018: contributor

    Concept ACK, and the code looks correct to me. I will try to test this locally this week.
15. 
    laanwj commented at 1:26 pm on March 22, 2018: member

    I can find no problems with this, utACK 5fbf7c478a996974502d5d787b2ccf2fcc91ac78
16. laanwj merged this on Mar 22, 2018
17. laanwj closed this on Mar 22, 2018

    ---

18. laanwj referenced this in commit a6926b065d on Mar 22, 2018
19. martinus deleted the branch on May 22, 2018
20. jkczyz referenced this in commit 28928c1c1f on Jun 6, 2019
21. jkczyz referenced this in commit 09f85273a0 on Jun 6, 2019
22. jkczyz referenced this in commit 177ab0e663 on Jun 6, 2019
23. jkczyz referenced this in commit 62789a6c9d on Jun 7, 2019
24. jkczyz referenced this in commit de9b748abc on Nov 16, 2019
25. jkczyz referenced this in commit ad71548822 on Nov 16, 2019
26. fanquake referenced this in commit 76e777df83 on Nov 20, 2019
27. sidhujag referenced this in commit 4c31537b75 on Nov 20, 2019
28. deadalnix referenced this in commit 08f8796875 on Jan 9, 2020
29. HashUnlimited referenced this in commit 3ab6107dce on Apr 17, 2020
30. zkbot referenced this in commit 5ef5d8d268 on Jul 31, 2020
31. PastaPastaPasta referenced this in commit 0aa3aeff12 on Sep 27, 2020
32. zkbot referenced this in commit 7d94064616 on Sep 29, 2020
33. PastaPastaPasta referenced this in commit 162bba0a6c on Oct 22, 2020
34. PastaPastaPasta referenced this in commit c8f7333c93 on Oct 22, 2020
35. PastaPastaPasta referenced this in commit bedce7256a on Oct 27, 2020
36. sidhujag referenced this in commit 39e180866d on Nov 10, 2020
37. backpacker69 referenced this in commit 828cb4dab1 on Mar 28, 2021
38. furszy referenced this in commit cae2e13a03 on Aug 4, 2021
39. MarcoFalke locked this on Sep 8, 2021

Contributors
martinus jonasschnelli jimpo laanwj eklitzke

Review Requested
laanwj

Labels
Refactoring Resource usage