Lockedpool fixes #9070

1. 
   kazcw commented at 11:20 PM on November 2, 2016: contributor

   No description provided.

2. LockedPool: test handling of invalid allocations

   (Currently fails due to bug)

   21b8f3db31
3. LockedPool: fix explosion for illegal-sized alloc

   Check for unreasonable alloc size in LockedPool rather than lancing through new
   Arenas until we improbably find one worthy of the quixotic request or the system
   can support no more Arenas.

   0b59f80625
4. LockedPool: avoid quadratic-time allocation

   Use separate maps for used/free chunks to avoid linear scan through alloced
   chunks for each alloc.

   b3ddc5e76f
5. kazcw force-pushed on Nov 2, 2016
6. MarcoFalke added the label Refactoring on Nov 3, 2016
7. MarcoFalke added the label Resource usage on Nov 3, 2016
8. MarcoFalke added the label Tests on Nov 3, 2016
9. MarcoFalke added this to the milestone 0.14.0 on Nov 3, 2016
10. 
    laanwj commented at 9:02 AM on November 3, 2016: member

    Nice! Thanks for doing this.

    Can you post bench outputs from before/after?

11. 
    kazcw commented at 5:57 PM on November 3, 2016: contributor

    b3ddc5e  LockedPool,56,0.009781777858734,0.020014733076096,0.019629589148930
    b3ddc5e^ LockedPool,16,0.057266950607300,0.066365003585815,0.063355177640915
    

    It's not as much of a performance increase as I expected. The original algorithm is quadratic, but walking the chunk map is very fast. On my test system, total time it takes (in seconds) for a series of n allocs is approximated by (1/30000000)n^2; it reaches 100ms at around 1.7k allocs and 1s at around 5k allocs. The new algorithm should be loglinear for alloc sequences.

12. 
    laanwj commented at 6:26 PM on November 3, 2016: member

    Thanks. Looks very good. utACK b3ddc5e

13. laanwj merged this on Nov 7, 2016
14. laanwj closed this on Nov 7, 2016

    ---

15. laanwj referenced this in commit 7b22e5001a on Nov 7, 2016
16. codablock referenced this in commit 921730d97a on Jan 13, 2018
17. andvgal referenced this in commit ae222db646 on Jan 6, 2019
18. CryptoCentric referenced this in commit ecfd635091 on Feb 15, 2019
19. zkbot referenced this in commit 5ef5d8d268 on Jul 31, 2020
20. zkbot referenced this in commit 7d94064616 on Sep 29, 2020
21. MarcoFalke locked this on Sep 8, 2021

Milestone
0.14.0