Using std::map should be deterministic or not?

Question

I'm facing a strange behaviour using Intel C++ compiler 2019 update 5. When I fill a std::map it seems to lead to a non deterministic (?) result. The stl is from VS2019 16.1.6 in which ICC is embedded. I am on Windows 10.0.17134.286.

My code:

#include <map>
#include <vector>
#include <iostream>

std::map<int, int> AddToMapWithDependencyBetweenElementsInLoop(const std::vector<int>& values)
{
    std::map<int, int>  myMap;
    for (int i = 0; i < values.size(); i+=3)
    {
        myMap.insert(std::make_pair(values[i], myMap.size()));
        myMap.insert(std::make_pair(values[i + 1], myMap.size()));
        myMap.insert(std::make_pair(values[i + 2], myMap.size()));
    }
    return myMap;
}

std::map<int, int> AddToMapOnePerLoop(const std::vector<int>& values)
{
    std::map<int, int>  myMap;
    for (int i = 0; i < values.size(); ++i)
    {
        myMap.insert(std::make_pair(values[i], 0));
    }
    return myMap;
}

int main()
{
    std::vector<int> values{ 6, 7,  15, 5,  4,  12, 13, 16, 11, 10, 9,  14, 0,  1,  2,  3,  8,  17 };

    {
        auto myMap = AddToMapWithDependencyBetweenElementsInLoop(values);
        for (const auto& keyValuePair : myMap)
        {
            std::cout << keyValuePair.first << ", ";
        }
        std::cout << std::endl;
    }

    {
        auto myMap = AddToMapOnePerLoop(values);
        for (const auto& keyValuePair : myMap)
        {
            std::cout << keyValuePair.first << ", ";
        }
        std::cout << std::endl;
    }

    return 0;
}

I simply wanted to perform a test so I call directly icl from the command line:

$ icl /nologo mycode.cpp
$ mycode.exe
0, 1, 2, 3, 4, 5, 6, 7, 11, 12, 13, 14, 15, 16, 17,
0, 1, 2, 3, 4, 5, 6, 7, 12, 13, 14, 15, 16, 17

Curious. I expected to have 18 entries and I got 15 and 14 (depending on the insertion method, see the code).

$ icl /nologo /EHsc mycode.cpp
$ mycode.exe
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17,
0, 1, 2, 3, 4, 5, 6, 7, 12, 13, 14, 15, 16, 17

Still curious, now I got 17 and 14 entries rather than 18 and 18!

$ icl /nologo /Od mycode.cpp
$ mycode.exe
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,

Now, with no optimization, I got 18/18, as expected.

My question is two-fold: 1) is it normal to get such results and 2) if it's not (what I suspect) what did I do wrong? I tought a simple call to the compiler would call the std::map::insert() function correctly?

Does the problem lies in the for(){}???

Thanks for helping me understanding this problem and finding a solution!

Answer 1

I cannot reproduce this but in either case, for peace of mind you could populate the map much simpler:

  for (auto i: values) {
    myMap[i] = 0;
  }

There is no need to use myMap.insert(std::make_pair(key, value)) just to add an entry to the map.

Otherwise your code produces the expected output (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 twice, the sequence is obviously sorted because this is the ordered map) if compiled with gcc 8.4.0 under Ubuntu. I suspect this is simply a bug of that particular compiler you use. It would be beneficial to report the bug to the compiler developers so that they could fix it.

Answer 2

Syntactically, your code is fine. I see no possible undefined behavior here (as far as you did no further hidden crazy hacks like redefining size_t/map, modifying standard headers etc.).

But:

Since I experienced loop-optimizer issues with older compilers due to lines like this one

for (int i = 0; i < values.size(); ++i)

where you mixed signed and unsigned integers / data type ranges, I suspect your intel compiler might have an issue with loop-unrolling here. Maybe it's also due to an according issue inside the loop and the subscript operator usage there. Typical fundamental issue here: Misassumption about allowed register usage. Can you try your code again with a strict size_t usage here?

Further idea:

Can you reproduce the issue if your 'static' pre-defined values to print are created in a very dynamic way instead of hard-code construction? That might at least exclude a lot of possible underlying reasons if you cannot.