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

    • Improvement
    • Status: Closed
    • Major - P3
    • Resolution: Won't Fix
    • None
    • None
    • Internal Code
    • 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

              backlog-server-platform DO NOT USE - Backlog - Platform Team
              david.storch@mongodb.com David Storch
              Votes:
              0 Vote for this issue
              Watchers:
              10 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: