Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-35712

boost::flat_set constructor should be O(n log n) given an unsorted range

    XMLWordPrintable

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major - P3
    • Resolution: Won't Fix
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: Internal Code
    • Labels:
      None

      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.

        Attachments

          Issue Links

            Activity

              People

              • Votes:
                0 Vote for this issue
                Watchers:
                10 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: