[SERVER-35712] boost::flat_set constructor should be O(n log n) given an unsorted range Created: 20/Jun/18 Updated: 25/Jun/18 Resolved: 25/Jun/18 |
|
| Status: | Closed |
| Project: | Core Server |
| Component/s: | Internal Code |
| Affects Version/s: | None |
| Fix Version/s: | None |
| Type: | Improvement | Priority: | Major - P3 |
| Reporter: | David Storch | Assignee: | DO NOT USE - Backlog - Platform Team |
| Resolution: | Won't Fix | Votes: | 0 |
| Labels: | None | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Issue Links: |
|
||||||||
| Participants: | |||||||||
| Description |
|
The current implementation has quadratic time complexity rather than O(n log n) time complexity. This is a known issue with boost: see https://svn.boost.org/trac10/ticket/13140. The problem is that the constructor inserts each input element by using a binary search, but the insertion into the middle of the backing vector has to shift elements over to make room. The known performance impact on the MongoDB server code base is being fixed separately under |
| Comments |
| Comment by Gregory McKeon (Inactive) [ 25/Jun/18 ] |
|
We won't do this, since there is some design work to do with boost. We'd prefer to migrate people off of flat-sets and onto the work being done in PM-650. |
| Comment by Ian Whalen (Inactive) [ 22/Jun/18 ] |
|
Now that the perf has been addressed in |