[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: |
|
||||||||
| 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. |