[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:
Related
is related to SERVER-35693 Parsing of $in takes quadratic time d... Closed
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 SERVER-35693. However, we may also wish to patch our vendorized version of boost in order to avoid future issues of this nature.



 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 SERVER-35693, it feels like upstreaming fixes to boost falls more to the Platform team to triage.

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