[SERVER-34008] ensure LockManager complexity is not O(n**2) for n taken locks Created: 20/Mar/18  Updated: 02/Oct/19  Resolved: 02/Oct/19

Status: Closed
Project: Core Server
Component/s: Concurrency, Storage
Affects Version/s: None
Fix Version/s: None

Type: Improvement Priority: Major - P3
Reporter: Dianna Hohensee (Inactive) Assignee: Daniel Gottlieb (Inactive)
Resolution: Won't Do Votes: 0
Labels: execution_intern, neweng
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
related to SERVER-33316 Remove limit on number of locks a sin... Closed
Sprint: Execution Team 2019-07-01, Execution Team 2019-09-09, Execution Team 2019-09-23, Execution Team 2019-10-07
Participants:

 Description   

Currently we do linear scans to look up locks, which leads to quadratic complexity for taking many locks. C++17 introduces map features that will allow us to replace our custom FastMapNoAlloc with a standard container while maintaining the reduced allocation benefits reaped from the custom container.



 Comments   
Comment by Daniel Gottlieb (Inactive) [ 02/Oct/19 ]

Doing some basic profiling on my machine shows that a transaction operating on 10,000 collections will spend ~1 second walking locks. geert.bosch and I consider that inconsequential. The main motivation for adding an optimization here would be if the walk time was 10x+ more expensive.

Comment by Geert Bosch [ 04/Sep/19 ]

Ah, now I see what you're asking for. The problem with the existing map was that it's too slow because it would cause amalloc/free for every lock acquisition. However, with C++17, we now have extract and merge, which would allow moving freed nodes to a freelist (map) with a zeroed out key.

It would be good to verify that the behavior can actually show up today, so the first step would probably be to try some transaction that accesses 10,000 collections or so, and see how things break down or not. The goal would be to not lose too much perf in the normal case of few locks while avoiding terrible perf in the weird case.

Comment by Daniel Gottlieb (Inactive) [ 04/Sep/19 ]

Yes that's why the current implementation can be considered quadratic. I'm unsure what was introduced in C++17 that lets us use a different data structure (std::map?) to verify that it would be a correct substitute.

Comment by Geert Bosch [ 03/Sep/19 ]

Because the map is implemented as a std::deque, any insert of a key walks all entries to find it.

Comment by Daniel Gottlieb (Inactive) [ 30/Aug/19 ]

geert.bosch, I believe you wrote the current version of this description. Do you happen to know the name of the map feature?

Comment by Eric Milkie [ 29/Nov/18 ]

Putting in 4.3 Required to re-examine the work for this after C++17 is available for use.

Generated at Thu Feb 08 04:35:16 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.