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

  1. #1
    Informer -Adrian's Avatar
    Join Date
    Jan 2013
    Posts
    820

    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?

  2. #2
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    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.

  3. #3
    Informer -Adrian's Avatar
    Join Date
    Jan 2013
    Posts
    820
    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.

  4. #4
    Registered User
    Join Date
    May 2010
    Posts
    4,465
    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

  5. #5
    Informer -Adrian's Avatar
    Join Date
    Jan 2013
    Posts
    820
    What you're seeing is a method and the variables involved are members of the class. I just simplified it to what it effectively does. No other function is running at that time. The input data is identical in size each time and as you can see the first run of the algorithm always leads to the same result, which at least hints at the data being identical up to that point. I'll see if – short of comparing the entire data between program runs – I can create hashes from the contents of each container and compare those.
    Last edited by -Adrian; 05-10-2016 at 06:57 PM.

  6. #6
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    Quote Originally Posted by -Adrian View Post
    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.

  7. #7
    Informer -Adrian's Avatar
    Join Date
    Jan 2013
    Posts
    820
    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.

  8. #8
    Tweaking master Aslaville's Avatar
    Join Date
    Sep 2012
    Location
    Rogueport
    Posts
    528
    Quote Originally Posted by jimblumberg View Post
    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 .

  9. #9
    Informer -Adrian's Avatar
    Join Date
    Jan 2013
    Posts
    820
    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. Checking the container's size alone gave me false assurance. Forcing the same order creates an identical "M" each run. Right now I can only think of the input containing duplicate "keys" (it shouldn't), so that the first non-unique key entered "wins" the spot.

    Quote Originally Posted by Aslaville View Post
    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 .
    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.
    Last edited by -Adrian; 05-11-2016 at 06:01 PM.

  10. #10
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    Quote Originally Posted by -Adrian View Post
    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"?

  11. #11
    Informer -Adrian's Avatar
    Join Date
    Jan 2013
    Posts
    820
    I copied the elements to a vector, sorted that, then ran md5sum on those bytes.

  12. #12
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    Quote Originally Posted by -Adrian View Post
    I copied the elements to a vector, sorted that, then ran md5sum on those bytes.
    Can you show the code for copying the elements to a vector? And I assume you then saved the vector contents to a file and ran md5sum from the command line?

    EDIT:
    Right now I can only think of the input containing duplicate "keys" (it shouldn't), so that the first non-unique key entered "wins" the spot.
    Actually it would be the last duplicate key that wins (overwrites) the spot. Have you checked to see if there are any identical keys? That should be easy.

    Anyway, this shouldn't really affect the original problem since, as I understand it, the data was always being entered in the same order.
    Last edited by algorism; 05-11-2016 at 06:28 PM.

  13. #13
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Has this code been run through valgrind or something similar?

  14. #14
    Informer -Adrian's Avatar
    Join Date
    Jan 2013
    Posts
    820
    Quote Originally Posted by algorism View Post
    EDIT: Actually it would be the last duplicate key that wins (overwrites) the spot.
    I use std::unordered_map::insert to enter new key/value pairs. According to cppreference, keys are inserted only if they don't already exist.

    Have you checked to see if there are any identical keys? That should be easy.
    Yes, I finally did that. I sorted the copied-to vector by first element and printed adjacent identical values. Turns out keys were not unique per se, so I started with a wrong assumption.

    Anyway, this shouldn't really affect the original problem since, as I understand it, the data was always being entered in the same order.
    Yeah, I left that part out in my original post. I have multiple threads writing to "M" (mutex locked) and since they start in sequence with some delay between each and consume the same amount of data, I assumed they would always finish in the exact order they started. Not always so.

    Bottom line, varying input order appears to have affected which keys ended up in "M" which in turn affected how "solve" did its job. I'm just glad I now know what's up. Back to the drawing board.
    Last edited by -Adrian; 05-11-2016 at 08:05 PM.

  15. #15
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    Turns out keys were not unique per se, so I started with a wrong assumption. ... I assumed [the threads] would always finish in the exact order they started
    The assumptions!
    Great that you solved it.
    I was intrigued to know the answer.
    Last edited by algorism; 05-11-2016 at 08:22 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Strange program behavior
    By milli-961227 in forum C++ Programming
    Replies: 5
    Last Post: 04-05-2015, 11:57 AM
  2. Replies: 5
    Last Post: 04-17-2013, 11:32 PM
  3. Replies: 2
    Last Post: 04-17-2013, 12:25 AM
  4. Very strange behavior from very simple program
    By somekid413 in forum C Programming
    Replies: 5
    Last Post: 12-17-2009, 08:53 PM
  5. Program that shows biggest line...
    By i_can_do_this in forum C Programming
    Replies: 6
    Last Post: 07-21-2006, 07:56 AM

Tags for this Thread