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


G

gdotone

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");
}
 
Ad

Advertisements

B

Ben Bacarisse

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...

Yup, no memory leak.
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.

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>
 
G

gdotone

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.

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.
 
J

James Dow Allen

(e-mail address removed) might have writ, in
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.

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:
int isThere_Two_Pair_In ( int myHand[][2] )
...
/* look for first pair */
for (int i = 0; i < NUMBEROFCARDSINHAND; i++ )
for ( int j = i + 1; j < NUMBEROFCARDSINHAND; j++ )
... /* looking for the next pair */
for ( int k = j + 1; k < NUMBEROFCARDSINHAND; k++ )
for ( int m = k + 1; m < NUMBEROFCARDSINHAND; m++ )

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
 
G

gdotone

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.
 
G

gdotone

(e-mail address removed) might have writ, in
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.
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:
int isThere_Two_Pair_In ( int myHand[][2] )
/* look for first pair */
for (int i = 0; i < NUMBEROFCARDSINHAND; i++ )
for ( int j = i + 1; j < NUMBEROFCARDSINHAND; j++ )
... /* looking for the next pair */
for ( int k = j + 1; k < NUMBEROFCARDSINHAND; k++ )
for ( int m = k + 1; m < NUMBEROFCARDSINHAND; m++ )
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 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.
 
Ad

Advertisements

J

Jorgen Grahn

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.

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
 
P

Paul

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.

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
 
B

BartC

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.

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?
 
G

gdotone

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.
 
Ad

Advertisements

B

BartC

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.

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.)
 
Ad

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. After that, you can post your question and our members will help you out.

Ask a Question

Top