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!

I can't reproduce with GCC, Clang, or Stock VS 16.2.0. The code itself is well defined so it is either a VS or ICC bug. If you compile the code using cl instead of icl do you get the same results? — NathanOliver, Nov 13 '19 at 21:57
@NathanOliver-ReinstateMonica If I try with _cl_, I always obtain the expected 0..17, whatever the compile switches I use. So you suspect an ICC bug? — dom_beau, Nov 14 '19 at 14:17
Looks that way. I wonder if it is trying to do some sort of vectorization and that is breaking the insertion. — NathanOliver, Nov 14 '19 at 14:21
I smell undefined behavior in your code somewhere. Where exactly? I couldn't tell you. What I can tell you is that your first function is only well defined if `values` is a multiple of 3. Otherwise, it will overrun the buffer. You seem to be doing that here, so you should be okay in **this** example. But it is something to be wary of. — , Dec 10 '19 at 00:27
@Chipster Well actually I posted a snippet that shows the problem. I'm perfectly aware of the weakness you put the emphasis to. If you "smell" something, you're right. The code is perfectly defined and must work. "Must" in the sense "to respect C++"... as far as I know. A bug ticket is opened at Intel for that. — dom_beau, Dec 10 '19 at 16:39
cannot reproduce with ICC on godbolt either (but that's probably ICC for Linux). — n. m. could be an AI, Aug 05 '20 at 07:17
Try printing map size and/or content after each step, perhaps it will clarify something. — n. m. could be an AI, Aug 05 '20 at 10:11

score 1 · Answer 1 · answered Aug 23 '20 at 18:53

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.

Secundi · Answer 2 · 2020-12-07T16:54:29.947

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.

Jarek C · Answer 3 · 2021-02-01T06:03:06.537

-1

Just guessing that there could be an optimization related to for(...; i+=3)

I see that your use-case has the number of items dividable by 3, but anyway I would fix a bug in your code for more general cases:

{
  std::map<int, int>  myMap;
  for (int i = 0; (i + 2) < values.size(); i+=3)  // ignore the possibly incomplete last triplet

I know it is not directly related to your problem, but maybe this fix triggers something in the compiler optimizer to build a correct code.

edited Feb 01 '21 at 06:03

answered Aug 05 '20 at 06:46

Jarek C

1,077
6
18

1

Didn't you mean to say `i+2 < values.size()` ? – v010dya Jan 30 '21 at 06:24
i+3 < values.size(); – OLNG Feb 07 '21 at 22:00

Using std::map should be deterministic or not?

3 Answers3