Skip to content

Conversation

kazcw
Copy link
Contributor

@kazcw kazcw commented Nov 2, 2016

No description provided.

kazcw added 3 commits November 2, 2016 14:05
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.
Use separate maps for used/free chunks to avoid linear scan through alloced
chunks for each alloc.
@laanwj
Copy link
Member

laanwj commented Nov 3, 2016

Nice! Thanks for doing this.

Can you post bench outputs from before/after?

@kazcw
Copy link
Contributor Author

kazcw commented Nov 3, 2016

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.

@laanwj
Copy link
Member

laanwj commented Nov 3, 2016

Thanks. Looks very good.
utACK b3ddc5e

@laanwj laanwj merged commit b3ddc5e into bitcoin:master Nov 7, 2016
laanwj added a commit that referenced this pull request Nov 7, 2016
b3ddc5e LockedPool: avoid quadratic-time allocation (Kaz Wesley)
0b59f80 LockedPool: fix explosion for illegal-sized alloc (Kaz Wesley)
21b8f3d LockedPool: test handling of invalid allocations (Kaz Wesley)
codablock pushed a commit to codablock/dash that referenced this pull request Jan 13, 2018
b3ddc5e LockedPool: avoid quadratic-time allocation (Kaz Wesley)
0b59f80 LockedPool: fix explosion for illegal-sized alloc (Kaz Wesley)
21b8f3d LockedPool: test handling of invalid allocations (Kaz Wesley)
andvgal pushed a commit to energicryptocurrency/gen2-energi that referenced this pull request Jan 6, 2019
b3ddc5e LockedPool: avoid quadratic-time allocation (Kaz Wesley)
0b59f80 LockedPool: fix explosion for illegal-sized alloc (Kaz Wesley)
21b8f3d LockedPool: test handling of invalid allocations (Kaz Wesley)
CryptoCentric pushed a commit to absolute-community/absolute that referenced this pull request Feb 15, 2019
b3ddc5e LockedPool: avoid quadratic-time allocation (Kaz Wesley)
0b59f80 LockedPool: fix explosion for illegal-sized alloc (Kaz Wesley)
21b8f3d LockedPool: test handling of invalid allocations (Kaz Wesley)
zkbot added a commit to zcash/zcash that referenced this pull request Sep 29, 2020
Locked memory manager

Add a pool for locked memory chunks, replacing `LockedPageManager`.

Cherry-picked from the following upstream PRs:
- bitcoin/bitcoin#8321
- bitcoin/bitcoin#8753
- bitcoin/bitcoin#9063
- bitcoin/bitcoin#9070
- bitcoin/bitcoin#11385
- bitcoin/bitcoin#12048
  - Excludes change to benchmark.
- bitcoin/bitcoin#15117
- bitcoin/bitcoin#16161
  - Excludes Travis CI changes.
  - Includes change from bitcoin/bitcoin#13163
- bitcoin/bitcoin#15600
- bitcoin/bitcoin#18443
- Assorted small changes from:
  - bitcoin/bitcoin#9233
  - bitcoin/bitcoin#10483
  - bitcoin/bitcoin#10645
  - bitcoin/bitcoin#10969
  - bitcoin/bitcoin#11351
- bitcoin/bitcoin#19111
  - Excludes change to `src/rpc/server.cpp`
- bitcoin/bitcoin#9804
  - Only the commit for `src/key.cpp`
- bitcoin/bitcoin#9598
@bitcoin bitcoin locked as resolved and limited conversation to collaborators Sep 8, 2021
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants