About.Com’s C/C++/C# programmeringstävling nummer elva

Nu har programmeringstävling nummer 11 hos About.com blivit avgjord. Tävlingen handlade om att programmera spelet "set" i något av språken C, C++ eller C# och sedan spela spelet 10000 gånger så fort som möjligt. Det snabbaste programmet skrevs av Chris Runyan, han hade löst uppgiften i C++ med en snygg processor-parallellisering av spelen. Hans tid för 10000 spel var drygt 0.1 sekunder. Jag tycker hans källkod verkligen var imponerande enkel och snygg, därför återger jag den här nedan till allmänhetens nytta.

 
/*
AUTHOR:	Chris Runyan
Copyright (c) 2008
lobetrotter@gmail.com
 
USE:
There are no restrictions on the use or publication of this work.
 
OVERVIEW:
Plays Set Match game
 
Plays one game for display followed by 10000 games.
 
DISCLAIMER:
 
This software is provided by Chris Runyan on an "AS IS" basis.
THERE ARE NO WARRANTIES, EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION
THE IMPLIED WARRANTIES OF NON-INFRINGEMENT, MERCHANTABILITY AND FITNESS FOR A
PARTICULAR PURPOSE, REGARDING THE SOFTWARE OR ITS USE AND OPERATION ALONE OR
IN COMBINATION WITH ANY PRODUCTS.
 */
 
#include <stdio.h>
#include
<process.h>
 
#include "hr_time.h"
 
#define CACHE_LINE  32
#define CACHE_ALIGN __declspec(align(CACHE_LINE))
 
#define VALUE int
 
struct CARD
{
  VALUE number;
  VALUE color;
  VALUE shape;
  VALUE shade;
};
 
CACHE_ALIGN CARD factoryDeck[84] =
{
  '1','r','d','f',	'2','r','d','f',	'3','r','d','f',
  '1','g','d','f',	'2','g','d','f',	'3','g','d','f',
  '1','p','d','f',	'2','p','d','f',	'3','p','d','f',
 
  '1','r','s','f',	'2','r','s','f',	'3','r','s','f',
  '1','g','s','f',	'2','g','s','f',	'3','g','s','f',
  '1','p','s','f',	'2','p','s','f',	'3','p','s','f',
 
  '1','r','o','f',	'2','r','o','f',	'3','r','o','f',
  '1','g','o','f',	'2','g','o','f',	'3','g','o','f',
  '1','p','o','f',	'2','p','o','f',	'3','p','o','f',
 
  '1','r','d','e',	'2','r','d','e',	'3','r','d','e',
  '1','g','d','e',	'2','g','d','e',	'3','g','d','e',
  '1','p','d','e',	'2','p','d','e',	'3','p','d','e',
 
  '1','r','s','e',	'2','r','s','e',	'3','r','s','e',
  '1','g','s','e',	'2','g','s','e',	'3','g','s','e',
  '1','p','s','e',	'2','p','s','e',	'3','p','s','e',
 
  '1','r','o','e',	'2','r','o','e',	'3','r','o','e',
  '1','g','o','e',	'2','g','o','e',	'3','g','o','e',
  '1','p','o','e',	'2','p','o','e',	'3','p','o','e',
 
  '1','r','d','c',	'2','r','d','c',	'3','r','d','c',
  '1','g','d','c',	'2','g','d','c',	'3','g','d','c',
  '1','p','d','c',	'2','p','d','c',	'3','p','d','c',
 
  '1','r','s','c',	'2','r','s','c',	'3','r','s','c',
  '1','g','s','c',	'2','g','s','c',	'3','g','s','c',
  '1','p','s','c',	'2','p','s','c',	'3','p','s','c',
 
  '1','r','o','c',	'2','r','o','c',	'3','r','o','c',
  '1','g','o','c',	'2','g','o','c',	'3','g','o','c',
  '1','p','o','c',	'2','p','o','c',	'3','p','o','c',
 
  '-','-','-','-',	'-','-','-','-',	'-','-','-','-', };
 
inline void swapCards(CARD &p1,CARD &p2)
{
  CARD tmpCard(p1);
  p1 = p2;
  p2 = tmpCard;
}
 
inline bool isMatchedAttribute(const VALUE a, const VALUE b, const VALUE c)
{
  return ((a == b && b == c) || (a != b && a != c && c != b));
}
 
inline bool isMatchedSet(const CARD &c1, const CARD &c2, const CARD &c3)
{
  bool rval = isMatchedAttribute(c1.number,c2.number,c3.number);
  rval = rval && isMatchedAttribute(c1.color,c2.color,c3.color);
  rval = rval && isMatchedAttribute(c1.shape,c2.shape,c3.shape);
  rval = rval && isMatchedAttribute(c1.shade,c2.shade,c3.shade);
 
  return rval;
}
 
inline void printSet(const CARD &c1, const CARD &c2, const CARD &c3)
{
  printf("Match: %c %c %c %c : %c %c %c %c : %c %c %c %c\r\n",
      c1.number,c1.color,c1.shape,c1.shade,
      c2.number,c2.color,c2.shape,c2.shade,
      c3.number,c3.color,c3.shape,c3.shade);
}
 
// memcpy was too slow
void _fastcall memcpyUINT(void *d, const void *s, size_t c)
{
  UINT *pS = (UINT *) s;
  UINT *pD = (UINT *) d;
  UINT *pE = (UINT *) ((BYTE *)s + c);
 
  while (pS < pE)
    *(pD++) = *(pS++);
}
 
// declare default function call - playGame()
void _fastcall playGame(bool print = false);
 
void _fastcall playGame(bool print)
{
  CACHE_ALIGN CARD deck[84];
  CACHE_ALIGN CARD table[21];
 
  // create a new deck
  memcpyUINT(deck,factoryDeck,sizeof(deck));
 
  // get random bits for the shuffle
  __int64 rbits = rand() | ((__int64)rand() << 32);
 
  // shuffle
  register unsigned int i = 0;
  register unsigned int j = 80;
 
  do
  {
    if ((rbits & (1i64 << i)) != 0)  // as we shuffle randomly swap cards
    {
      swapCards(deck[i],deck[j]); // interleave cards
      --j;
    }
  } while (++i < 64);
 
  int topOfDeck = 0;
  int cardsOnTable = 0;
 
  // play - deal out 12 cards
  for (int cd = 0; cd < 12; ++cd)
    table[cardsOnTable++] = deck[topOfDeck++];
 
  register int a,b,c;
  do
  {
    // look for a match on the table
    for (a= 0; a < cardsOnTable-2; ++a)
    {
      for (b= a+1; b < cardsOnTable-1; ++b)
      {
        for (c= b+1; c < cardsOnTable; ++c)
        {
          if (isMatchedSet(table[a],table[b],table[c]))
          {
            // we have a set
            if (print)
              printSet(table[a],table[b],table[c]);
 
            // replace set with new cards
            table[a] = deck[topOfDeck++];
            table[b] = deck[topOfDeck++];
            table[c] = deck[topOfDeck++];
            goto FOUND;  // using evil goto for speed
          }
        }
      }
    }
 
    // No match deal three more cards
    table[cardsOnTable++] = deck[topOfDeck++];
    table[cardsOnTable++] = deck[topOfDeck++];
    table[cardsOnTable++] = deck[topOfDeck++];		
 
FOUND: ;
 
  } while (topOfDeck < 84);
}
 
unsigned __stdcall PlayGames_Thread(void *pParam)
{
  LARGE_INTEGER li;
  QueryPerformanceCounter(&li);
 
  // seed the random numbers
  srand( li.LowPart );
 
  int numberToPlay = (int)(pParam);
 
  while (numberToPlay--)
    playGame();
  return 0;
}
 
const int maxCPUs = 64;
 
int getNumberOfProcessors()
{
  int rval = 1;
  SYSTEM_LOGICAL_PROCESSOR_INFORMATION buffer[maxCPUs];
  DWORD len = sizeof(buffer);
 
  BOOL success = GetLogicalProcessorInformation(buffer,&len);
 
  if (success)
  {
    PSYSTEM_LOGICAL_PROCESSOR_INFORMATION ptr;
 
    int processorCount = 0;
    DWORD byteOffset = 0;
    ptr = buffer;
    while (byteOffset < len)
    {
      switch (ptr->Relationship)
      {
        case RelationNumaNode:
        case RelationProcessorCore:
          processorCount++;
          break;
        default:
          break;
      }
      byteOffset += sizeof(SYSTEM_LOGICAL_PROCESSOR_INFORMATION);
      ptr++;
    }
    rval = processorCount;
  }
  if (rval > maxCPUs)
    rval = maxCPUs;
 
  return rval;
}
 
int main(int argc, char* argv[])
{
  const int games = 10000;
 
  int numThreads = getNumberOfProcessors();
 
  // create a thread for each processor
  unsigned threadID[maxCPUs];
  HANDLE hThreads[maxCPUs];
  for (int i=0; i < numThreads; i++)
  {
    int games_per_thread = games/numThreads;
    // handle remainder
    if (i == 0)
      games_per_thread += games % numThreads;
 
    hThreads[i]= (HANDLE)_beginthreadex(NULL,0,
        PlayGames_Thread,			// thread handler
        (void *)(games/numThreads),	// pass in number of games
        CREATE_SUSPENDED,&threadID[i]); // don't start yet
  }
 
  // step up the priority for our threads
  for (int i=0; i < numThreads; i++)
    SetPriorityClass(hThreads[i],HIGH_PRIORITY_CLASS);
 
  for (int i=0; i < numThreads; i++)
    SetThreadPriority(hThreads[i],THREAD_PRIORITY_TIME_CRITICAL);
 
  // be sure each thread runs on its own processor
  for (int i=0; i < numThreads; i++)
    SetThreadAffinityMask(hThreads[i],1<<i);
 
  // play one game for display...not counted in the timing
  srand( GetTickCount() );
  playGame(true);
 
  // time the execution
  CStopWatch sw;
  sw.startTimer();
 
  for (int i=0; i < numThreads; i++)
    ResumeThread(hThreads[i]);
 
  // wait for all of the threads to complete
  WaitForMultipleObjects(numThreads,hThreads,TRUE,INFINITE);
 
  sw.stopTimer();
 
  printf("%d Games played in: %f seconds\r\n",games,sw.getElapsedTime());
 
  return 0;
}
 

En klass för tidtagning var given i tävlingen och den används i koden ovan (inkluderad som hr_time.h);

 
#include <windows.h>
 
typedef struct {
  LARGE_INTEGER start;
  LARGE_INTEGER stop;
} stopWatch;
 
class CStopWatch {
 
  private:
    stopWatch timer;
    LARGE_INTEGER frequency;
    double LIToSecs( LARGE_INTEGER & L);
  public:
    CStopWatch();
    void startTimer( );
    void stopTimer( );
    double getElapsedTime();
};
 
double CStopWatch::LIToSecs( LARGE_INTEGER & L) {
  return ((double)L.QuadPart /(double)frequency.QuadPart);
}
 
CStopWatch::CStopWatch(){
  timer.start.QuadPart=0;
  timer.stop.QuadPart=0;
  QueryPerformanceFrequency( &frequency );
}
 
void CStopWatch::startTimer( ) {
  QueryPerformanceCounter(&timer.start);
}
 
void CStopWatch::stopTimer( ) {
  QueryPerformanceCounter(&timer.stop);
}
 
double CStopWatch::getElapsedTime() {
  LARGE_INTEGER time;
  time.QuadPart = timer.stop.QuadPart - timer.start.QuadPart;
  return LIToSecs( time) ;
}