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

    XMLWordPrintableJSON

Details

    • Icon: Improvement Improvement
    • Resolution: Won't Fix
    • Icon: Major - P3 Major - P3
    • 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

        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: