Thread: Program shows different behavior each time it's run

I have the following program:

1. Container A contains pairs of numbers
2. Container M contains key->value pairs
3. Iterating over A, i check if values in its second column match keys in M.
4. If so, that value in A gets replaced by the value in M.

Code:

std::vector<std::pair<int, int>> A;
std::unordered_map<int, int> M;

size_t solve() // solve is method, has access to A & M
{
    auto m = M.cend();
    size_t changes = 0;
    for(auto& a : A)
    {
        m = M.find(a.second);
        if(m != M.cend()) // match
        {
            a.second = m->second;
            ++changes;
        }
    }
    return changes;
}

Now my problem is as follows: Each time I run the program, the changes value returned by solve is identical on the first call (good), but different on the following ones (WAT!), such that:

Code:

int main()
{
    for(int i = 0; i < N; ++i)
        cout << "#" << i << ": " << solve() << endl;
}

./program:
#1: 25,000,008
#2:     12,000 (finds less, expected)
#3:      5,000 (^...)

./program:
#1: 25,000,008 (same, good)
#2:      7,000 (what the hell!)
#3:      3,400 (...)

./program:
#1: 25,000,008 (same, good)
#2:     63,000 (what in the world!?)
#3:      9,300 (...)

The input data is always the same, and no part of the program intentionally contains random behavior. Any idea what could cause this? Am I mis-using iterators?

The problem seems to be elsewhere in your code. Post a complete runnable program, with input, expected output, and actual output. In constructing such an example you have a very good chance of finding the problem yourself.

Obviously a smaller input file would be good.

Yeah, I'll see if I can do that (and you're right about better problem-formulation often leading to error-discovery by oneself). I just wanted to make sure the function itself isn't erroneous to the trained eye, as the data appears to be consistent up to that point.

How can you tell? Using those global variables will allow the data to change almost anywhere. You really need to learn to pass the required variables to and from your functions as required.


Jim

Originally Posted by jimblumberg

How can you tell? Using those global variables will allow the data to change almost anywhere. You really need to learn to pass the required variables to and from your functions as required.


Jim

Even more so and while at it, make sure to use 'const' on arguments that should not be modified.

On the other paw, not the source of the problem of course but line 6 in the first code snippet is not necessary but of course you already know that .

Originally Posted by Guest

I've narrowed it down somewhat. Looks like the contents of "M" change based on the order in which (the same) data is entered into it.

How did you determine that the contents have "changed"?

I copied the elements to a vector, sorted that, then ran md5sum on those bytes.

Originally Posted by Guest

1. These are non-const class members, so aside from passing them into the solve method (is that common practice?) that won't be possible.
2. If you mean move auto to line 10, wouldn't that cause the compiler to create a new object each iteration or is that irrelevant since find produces one anyway? I usually try to construct re-used variables before the loop, but if that's not the best approach, let me know.

1. I was just noting something general not with reference to your current code.
2. In that case I might be sure which way is best, I guess you could just stick to your current one.

Originally Posted by Guest

I just simplified it to what it effectively does.

If we trust what you are saying then the problem you are describing is essentially impossible. When what you are experiencing seems impossible it usually indicates a false assumption, so we cannot really trust what you say. And with a code snippet that doesn't run and hence cannot reproduce the problem, we have no way of determining the problem.

Yeah, fair enough. As I said, knowing that my example (as written there) doesn't have some apparent undefined behavior helps me forward in narrowing down the problem.

Has this code been run through valgrind or something similar?

Yeah, that's true. However, the order of thread execution wasn't on my radar because it didn't matter to the program I thought I was writing. It only started to matter when finding the source of the problem, which were the duplicate keys in the input.