self studying: this program slows down after repeated runs on my machine.

Discussion in 'C Programming' started by gdotone, Sep 2, 2013.

  1. gdotone

    gdotone Guest

    This program slows down after running it several times. I am not
    allocating any memory, malloc, calloc , I don't believe there is a memory
    leak, but as I'm learning...

    I find if I run the program over and over again it compiles find but it does not
    print as fast as it does over the first few runs. The hand dealt, when finally
    present not have any matching face cards.

    Also, up to this point in the book structures, or unions have not been discussed.

    //
    // main.c
    // fig07_24.c
    //
    // C How to Program by Dietel and Dietel
    // with modification by gdotone

    /* This program comes from the exercises found in Dietel and Dietel
    * C How to program. The execise calls for the modification of a program
    * found in fig. 7.24, of the book. The card dealing function is to deal a 5 card
    * poker hand. The sub-exercises ask for the hand to be evaluated, to
    * find a pair, find two of a kind, three of a kind, four of a kind,
    * straight or flush.
    *
    * This program impliments the first four objectives so far.
    *
    */


    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>

    #define NUMBEROFCARDSINHAND 5

    /* prototypes */

    void shuffle( int wDeck[][ 13 ] );

    void deal( const int wDeck[][ 13], const char *wFace[],
    const char *wSuit[], int myHand[5][2] );


    int isThere_A_Pair_In ( int myHand[][2]);
    int isThere_Two_Pair_In ( int myHand[][2] );
    int isThere_Three_Of_A_Kind_In ( int myHand[][2] );
    int isThere_Four_Of_A_Kind_In ( int myHand[][2] );

    // void printHand( int myHand[5][2], const char *wSuit[], const char *Face[] );

    /***************************** main () ***************************************/

    int main(int argc, const char * argv[])
    {
    /* initialize suit array */
    const char *suit[ 4 ] = { "Hearts", "Dimonds", "Clubs", "Spades" };

    /* initialize face array */
    const char *face[ 13 ] = { "Ace", "Deuce", "Three", "Four",
    "Five", "Six", "Seven", "Eight",
    "Nine", "Ten", "Jack", "Queen", "King" };

    /* initialize deck array */
    int deck[ 4 ] [13 ] = { 0 };


    /* intialize hand */
    int myHand[5][2] = {0};

    srand( (unsigned int) time( 0 ) ); /* seed random-number generator */

    shuffle( deck ); /* shuffle the deck */

    /* deal the deck */
    deal( deck, face, suit, myHand );

    /* check poker hand */
    isThere_A_Pair_In ( myHand );
    isThere_Two_Pair_In ( myHand );
    isThere_Three_Of_A_Kind_In ( myHand );
    isThere_Four_Of_A_Kind_In ( myHand );

    // printHand( myHand, suit, face ); /* use as test to see if hand is dealt */

    return 0;
    }

    /******************************** shuffle () *********************************/

    /* suffle cards in deck */
    void shuffle( int wDeck[][ 13 ] )
    {
    int row; /* row */
    int column; /* colum number */
    int card; /* counter */

    /* for each of the 52 cards, choose slot of deck randomly */
    for ( card = 1; card <= 52; card++ )
    {
    /* choose new random location until unoccupide slot found */
    do {
    row = rand() % 4;
    column = rand() % 13;
    } while ( wDeck[row][column] != 0 ); /* end do ... while */

    /* place card number in chosen slot of deck */
    wDeck[ row ][ column ] = card;

    } /* end for ( card = 1 ... ) */

    } /* end shuffle */

    /********************************* deal() ************************************/

    /* deal cards in deck */
    void deal( const int wDeck[][ 13 ], const char *wFace[],
    const char *wSuit[], int myHand[][2] )
    {
    int card; /* card counter */
    int row; /* row counter */
    int column; /* column counter */
    int t = 0; /* t used as row index for myHand */

    /* deal 5 cards, poker hand */
    for ( card = 1; card <= NUMBEROFCARDSINHAND; card++ )
    {
    /* loop through rows of wDeck */
    for ( row = 0; row <= 3; row++ )
    {
    /* loop through columns of wDeck for current row */
    for ( column = 0; column <= 12; column++ )
    {
    /* if slot contains current card, display card */
    if ( wDeck[row][ column] == card)
    {
    myHand[t][0] = column;
    myHand[t][1] = row;
    printf( "%5s of %-8s%c", wFace[ column ], wSuit[ row ],
    card % 2 == 0 ? '\n' : '\t' );
    t++;
    }

    }/* end for ( column = 0 ...) */

    } /* end for ( row = 0 ...) */

    } /* end for ( card = 1 ...) */

    } /* end void deal(... ) */

    /********************* isThere_A_Pain_In () ******************************/

    int isThere_A_Pair_In ( int myHand[][2] )
    {
    int strenghtOfHand;
    int col = 0;

    for ( int i = 0; i < NUMBEROFCARDSINHAND; i++ )
    for ( int j = i + 1; j < NUMBEROFCARDSINHAND; j++ )
    if ( myHand[col] == myHand[j][col] )
    {
    printf( "\n\nFound a pair\n");
    return strenghtOfHand = 1;
    } /* found a pair */

    return strenghtOfHand = 0; /* no pair found */

    } /* end isThere_A_Pair_In () */


    /********************* isThere_Two_Pair_In () ******************************/

    int isThere_Two_Pair_In ( int myHand[][2] )
    {
    int col = 0;
    int numberOfPairs = 0; /* number of pairs found in hand */
    int strenghtOfHand;

    /* look for first pair */
    for (int i = 0; i < NUMBEROFCARDSINHAND; i++ )
    for ( int j = i + 1; j < NUMBEROFCARDSINHAND; j++ )
    if ( myHand[col] == myHand[j][col] )
    {
    numberOfPairs++;

    /* looking for the next pair */
    for ( int k = j + 1; k < NUMBEROFCARDSINHAND; k++ )
    for ( int m = k + 1; m < NUMBEROFCARDSINHAND; m++ )
    if( ( myHand[k][col] == myHand[m][col])
    && ( myHand[k][col] != myHand[j][col]))
    {
    numberOfPairs++;
    printf( "This hand has two of a kind" );
    return strenghtOfHand = 2;
    }
    } /* end if ( myhand[0] ... ) */

    return strenghtOfHand = 0; /* two pair not found */

    } /* end isThere_Two_Pair_In() */


    /********************* isThere_Three_Of_A_Kind_In () ***********************/

    int isThere_Three_Of_A_Kind_In ( int myHand[][2] )
    {
    int strenghtOfHand;
    int col = 0; /* need not change, only looking at the face of the card */

    for ( int i = 0; i <= NUMBEROFCARDSINHAND; i++ )
    for ( int j = i + 1; j < NUMBEROFCARDSINHAND; j++ )
    if ( myHand[col] == myHand[j][col] )
    {
    /* find next card of same kind */
    for (int k = j + 1; k < NUMBEROFCARDSINHAND; k++)
    {
    if ( myHand[col] == myHand[k][col]) /* found third kind */
    {
    printf( "\nThere are three of a kind in hand\n");
    return strenghtOfHand = 3;
    } /* end if ( myHand[col] ... ) */

    } /* end for ( int k = j + 1; ... */

    } /* end if ( myHand[col]...) */

    return strenghtOfHand = 0; /* no three of a kind */

    } /* end isThere_Three_Of_A_Kind_In () */


    /********************* isThere_Four_Of_A_Kind_In () ************************/

    int isThere_Four_Of_A_Kind_In ( int myHand[][2] )
    {
    int strenghtOfHand;
    int col = 0;

    for ( int i = 0; i <= NUMBEROFCARDSINHAND; i++ )
    for ( int j = i + 1; j < NUMBEROFCARDSINHAND; j++ )
    if ( myHand[col] == myHand[j][col] )
    {
    /* find next card of same kind */
    for (int k = j + 1; k < NUMBEROFCARDSINHAND; k++)
    {
    if ( myHand[col] == myHand[k][col]) /* found third kind */
    {
    /* find next card of same kind */
    for (int m = k + 1; m < NUMBEROFCARDSINHAND; m++ )
    if ( myHand[col] == myHand[m][col] )
    {
    printf( "This hand has four of a kind");
    return strenghtOfHand = 4;
    }

    } /* end if ( myHand[col] ... ) */

    } /* end for (int k = j + 1 ... ) */

    } /* end if ( myHand[col] ... ) */

    return strenghtOfHand = 0; /* four of a kind not found in hand */

    } /* end isThere_Four_Of_A_Kind_In () */


    /***************************** printHand() ***********************************/
    /* used to test hand, check what is dealt */

    void printHand( int myHand[5][2], const char *wSuit[], const char *wFace[] )
    {
    int col = 0; /* column relates to suit of card */

    printf ("\n\n");
    for (int row = 0; row < NUMBEROFCARDSINHAND; row++)
    printf (" %-6s of %-8s\n", wFace[ myHand[row][col] ],
    wSuit[ myHand[row][col + 1] ]);

    printf("\n");
    }
     
    gdotone, Sep 2, 2013
    #1
    1. Advertisements

  2. Yup, no memory leak.
    That's odd and I don't see that behaviour when I run it. Your shuffle
    does have the property that it could, in principle, take an arbitrary
    large amount of time. For example, when the last card is being placed,
    there will be many wasted called to rand() looking for the only possible
    place to put it. However, that's not going to be the explanation for
    the slow-down. That will, most likely, be something else happening on
    you system, or just a mysterious coincidence.

    The main remark I'd make is that the program is working way too hard.
    For all of the main functions -- shuffling the deck, dealing the hand and
    counting the duplicates -- there are much simpler methods.

    Is the representation of the hand and the deck given in the book? I
    think there are simpler ways to represent cards, and the representation
    might have been a factor leading you to derive overly complex
    algorithms.

    I'm not giving any alternatives because it's more fun to dream them up
    yourself, but I'll glady suggest other ways of doing things if you are
    stuck in rut.

    <snip code>
     
    Ben Bacarisse, Sep 2, 2013
    #2
    1. Advertisements

  3. gdotone

    gdotone Guest

    Thanks Ben,
    I will attribute it to something else going on in the machine then.

    The book does use that representation for deck, suit and face.

    The functions are my contributions along with 3 lines of code in
    the function deal(). also, dealing only 5 cards.

    ....
    myHand[t][0] = column;
    myHand[t][1] = row;
    ....
    t++;

    my{Hand][][] array.

    The following problems will probably have me address the deck, etc. Maybe.
    Thanks, yeah don't give it away just yet. I'm enjoying trying to figure it out solution
    to the programming problems.

    Thanks again.
     
    gdotone, Sep 2, 2013
    #3
  4. might have writ, in
    Every time you start-up the program from scratch, it should be presented
    with the same "virgin" tabula rasa (except for difference in random
    seeding, which is unlikely to be your problem). This leads me to
    suspect the problem is external to your code, e.g. your Windows
    environment. I can offer no comment on that as I preferred to use a
    reasonable Operating System (Unix) exclusively.

    I didn't examine your code in detail but this caught my eye:
    I think A A Q Q will be recognized as Two Pair, but A Q A Q will not.

    For a good laugh you can examine my code:
    http://fabpedigree.com/james/holdodds.c
    (The last third of that is specific to Hold'em.)
    The one-pair/full-house/etc. classifier ended up being just
    switch (numpair + numtrip) {
    case 0: /* No pair */ ...
    case 1: /* One pair */ ...
    case 2: /* Two pair */ ...
    case 3: /* Triplets */ ...
    case 4: /* Full house */ ...
    case 5: /* Four-of-kind */ ...
    case 7: /* Five-of-kind */ ...
    }

    James Dow Allen
     
    James Dow Allen, Sep 2, 2013
    #4
  5. gdotone

    gdotone Guest

    Because three may be someone else out there learning too, there is a bug.
    inside function isThere_Two_Pair_In ()
    the line
    for ( int k=j+1; k< NUMBEROFCARDSINHAND; k++)

    should be

    for ( int k=i+1; k<NUMBEROFCARDSINHAND; k++)

    the program as displayed will miss 5, 7, 9, 7, 9 and those like it.
     
    gdotone, Sep 2, 2013
    #5
  6. gdotone

    gdotone Guest

    James Thanks, I found that bug after testing more and before I read your post.
    You are right.
    I think the correction I posted will fix it.
     
    gdotone, Sep 2, 2013
    #6
  7. gdotone

    Jorgen Grahn Guest

    I vote for mysterious coincidence. Or rather, the human tendency to
    see patterns in random data. If the program sometimes, at random,
    takes a long time to run, it's easy to perceive that as "the program
    slows down after the first few rounds".

    /Jorgen
     
    Jorgen Grahn, Sep 2, 2013
    #7
  8. gdotone

    Paul Guest

    I tried a couple things.

    I added a variable to count calls to rand().
    Naturally, the number of calls varies, and it's always
    an even number since you call rand twice in succession.

    I also experimented with time keeping.

    start = clock();
    done = clock() - start;

    That sort of thing. I use DJGPP in Windows for this,
    and clock() wasn't doing anything for me. I switched
    to uclock() and got some numbers with that instead.

    I also tried this page.

    http://www.mcs.anl.gov/~kazutomo/rdtsc.html

    "Pentium class cpu has an instruction to read the
    current time-stamp counter variable ,which is a 64-bit
    variable, into registers (edx:eax). TSC(time stamp counter)
    is incremented every cpu tick (1/CPU_HZ). For example,
    at 1GHz cpu, TSC is incremented by 10^9 per second. It
    allows to measure time activity in an accurate fashion."

    I downloaded rdtsc.h ...

    http://www.mcs.anl.gov/~kazutomo/rdtsc.h

    and put this in my program

    #include "rdtsc.h"

    Then

    unsigned long long a,b,c ;
    a = rdtsc(); /* start time */
    b = rdtsc(); /* place this after last line of functional code */
    sleep(100);
    c = rdtsc(); /* calibration time stamp */

    If you take c - b and scale by the number of seconds
    you were asleep, you get the CPU clock frequency. (If I
    use a 100 second measurement, I get closer to 3GHz. You
    can remove the calibration step when you're happy with it.)
    That's so you have some idea what to scale (b - a) with.
    You can print a,b,c with %lld when debugging.

    I'm getting around 55 milliseconds for the code on
    average (i.e. the last run on my screen). And the count
    of calls to rand(), the usleep and rdtsc() derived measures,
    all delightfully don't correlate. Because measuring time
    on a (Windows) computer, is hard.

    So all I know is, your program has a short execution
    time. The number of calls to rand() is variable (430, 382, 522).
    And yet the time measurement functions do a poor job
    of reflecting that. And the time measurement functions
    don't agree (usleep is not the same as RDTSC).

    Perhaps if I'd put the time measurement functions
    just around shuffle(), I would have got a better
    correlation between call count and execution time.
    Maybe the printf calls are at fault.

    I also tried the timeit.exe program that comes
    with a certain Windows resource kit, and it could
    not attach to my DJGPP executable. ("Unable to
    query process times")

    There is no visible slowdown, from run to run.
    Not into the seconds range at least. If I believe
    my RDTSC based measurements, it's around 55 milliseconds.
    (E8400 Core2 dual core 3GHz, 4GB RAM)

    Paul
     
    Paul, Sep 2, 2013
    #8
  9. gdotone

    BartC Guest

    It what way does it appear slow? I've tried it, and it only prints two or
    three lines, not enough to notice. What timings do you have and what are the
    differences between runs?

    You have a srand() call in there; try passing a constant value (eg.
    srand(12345)) and seeing if successive runs are still slower even when
    performing the same calculations.

    Are you recompiling/relinking each time? You might try turning off any
    anti-virus software briefly (I know mine, every few hours, adds 20 seconds
    to the runtime of a newly linked executable. Assuming it is the
    anti-virus...)

    What about your OS? Are you running off a slow disk, flash memory, or have
    other apps in the background that are affecting the timings? (If you have a
    process monitor try to see what it's up to in the periods when it's slow,
    assuming it's slow enough to allow you to do that.)

    You try setting up a script to repeatedly run your program, and show the
    timings, to see the pattern of how they change. What is it that resets the
    timing to make the program fast again; a new build?
     
    BartC, Sep 2, 2013
    #9
  10. gdotone

    gdotone Guest

    Bartc,

    I believe that it maybe something in the background running.
    As Ben noted, about the deal function, so too does the author write about
    the inefficient of the shuffle() and deal() in the next few exercises.

    Reading through the exercise that has "Card Shuffling and Dealing Modification",
    as it's title, the author talks, writes, about indefinite postponement as part of
    the inefficient shuffling algorithm.

    In this exercise, "Card Shuffling and Dealing Modification" the author ask that
    a high-performance shuffling algorithm be created that avoids indefinite
    postponement.

    From text:
    "This shuffling algorithm could execute indefinitely if cards that have already been
    shuffled are repeatedly selected at random. This phenomenon is know as indefinite
    postponement" (Dietel and Dietel, C How to Program, p.281, my book.)

    So, it's possible that the phenomenon is occurring, but I do recompile. I do believe
    each time it is being linked...

    So I would expect it to be fast then slow then perhaps fast
    again at some point but I don't see that, just slower and slower. Perhaps I haven't
    tested it enough times.

    I am using Xcode, 4.6.3 and there are other applications running in the background.
    Applications like safari, iTunes, etc. ,of course, I've closed those and still noticed the
    slow down. (maybe some house keeping in the OS, or Xcode??)
    I have noticed a little spool in XCode after some time has passed while it is compiling
    or running. Sorry I don't know XCode beyond clicking the run button.

    Thanks a lot,

    g.
     
    gdotone, Sep 3, 2013
    #10
  11. gdotone

    BartC Guest

    You have the srand() call. I suggested using a fixed srand argument.

    But you can also print out the value that is passed to srand, ie. time(0),
    on each run. (That will also confirm any delay is during the runtime of the
    program, and not while loading.)

    When the program becomes slow, take a note of that srand argument, and next
    time give that exact same value to srand(). If it is to do with algorithm,
    then it will be consistently slow on each run. (In which case you might need
    a different algorithm, and could do with some profiling to find out the
    problem bit of code.)

    (I have just tried this, and found a couple of problems:

    * The resolution of time(0) is too low (one second it seems), so you will
    get the same hand if run again within one second.

    * Even with exactly the same argument to srand(), it was hanging the second
    time I tried. This was a problem with shuffle() because wDeck is not cleared
    to zero. I don't know if this is what you mean by 'slower' (I didn't have
    the patience to wait too long) or whether it has already been pointed out.
    But fix that first.)
     
    BartC, Sep 3, 2013
    #11
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.