June 10, 2019 at 20:32

Attention! Dangerous bug in C ++ implementation std :: map :: merge and std :: set :: merge in Visual Studio 2017

    If you use the C ++ 17 standard in MS Visual Studio 2017 - be careful: the current version contains a critical bug in the implementation of std :: map :: merge and std :: set :: merge. Details - under the cut.

    How does a bug manifest?


    1. The complexity of std :: map :: merge and std :: set :: merge instead of the standard N * log (size () + N)), where N is the size of the added part, turns out to be about N squared.
    2. If a container with a sufficiently large number of elements was added with the help of merge, upon destruction of the resulting container we get stack overflow.
    3. The container comes to an incorrect state after merge is running, so other manifestations are possible.

    What does Microsoft say?


    The bugreport was sent by me to Microsoft almost 2 months ago.
    In Visual Studio 2019 Update 2 Preview 2 should have been fixed.

    But in the current version of Visual Studio 2017 15.9.12 has not been fixed so far, and judging by the latest reports, it will take a long time to wait ... The

    bug consists in incorrect color marking of the added nodes in the red-black tree implementation.

    How to reproduce?


    //#include "pch.h"
#include 
#include 
#include 
#include 
#include 
const size_t mainSize = 50'000;
const size_t additionSize = mainSize;
auto getMainMap()
{
  std::map result;
  while( result.size() < mainSize )
    result.emplace(result.size(), "SomeText");
  return result;
}
auto getAdditionMap()
{
  std::map result;
  while ( result.size() < additionSize )
    result.emplace(mainSize + result.size(), "SomeAdditionText");
  return result;
}
int main()
{
  {
    auto mainMap = getMainMap();
    auto addition = getAdditionMap();
    auto start = std::chrono::steady_clock::now();
    for ( auto const &elem : addition )
      mainMap.emplace(elem);
    auto end = std::chrono::steady_clock::now();
    std::cout << "manual insertion with copy: "
              << std::chrono::duration_cast(end - start).count()
              << std::endl;
  }
  {
    auto mainMap = getMainMap();
    auto addition = getAdditionMap();
    auto start = std::chrono::steady_clock::now();
    mainMap.merge(addition);
    auto end = std::chrono::steady_clock::now();
    std::cout << "std::map::merge: "
              << std::chrono::duration_cast(end - start).count()
              << std::endl;
  } // <---- and stack overflow here because of incorrect mainMap after merge
  return 0;
}

    Varying the value of mainSize, you can get different results - either only slow execution, or also crash.

    What to do?


    Revise your code and replace merge calls with manual insertion. Or switch to VS 2019.
    And if the compiled code has already gone to the customer ... Ohhh ...
    Tags:

    Also popular now: