performance measurements
Each table row shows performance measurements for this C++ g++ program with a particular command-line input value N.
| N | CPU secs | Elapsed secs | Memory KB | Code B | ≈ CPU Load |
|---|---|---|---|---|---|
| 2,098 | 0.04 | 0.04 | ? | 2620 | 0% 0% 0% 100% |
Read the ↓ make, command line, and program output logs to see how this program was run.
Read meteor-contest benchmark to see what this program should do.
notes
gcc (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3
meteor-contest C++ g++ #6 program source code
/* The Computer Language Benchmarks Game http://benchmarksgame.alioth.debian.org/ contributed by Stefan Westen loosely based on Ben St. John's and Kevin Barnes' implementation Main improvements: - Check for isolated cells instead of bad islands - Pre-calculate lists based on availability of 3 neighbouring cells - OpenMP tasks */ #include <stdio.h> #include <omp.h> const int nPieceCount = 10; const int pieces[10][5][2] = { {{0, 0}, {1, 0}, {2, 0}, {3, 0}, {3, 1}}, {{0, 0}, {0, 1}, {-2, 2}, {-1, 2}, {-3, 3}}, {{0, 0}, {1, 0}, {2, 0}, {-1, 1}, {-1, 2}}, {{0, 0}, {1, 0}, {2, 0}, {1, 1}, {1, 2}}, {{0, 0}, {0, 1}, {1, 1}, {-1, 2}, {1, 2}}, {{0, 0}, {1, 0}, {-2, 1}, {-1, 1}, {0, 1}}, {{0, 0}, {1, 0}, {0, 1}, {-1, 2}, {-1, 3}}, {{0, 0}, {2, 0}, {-1, 1}, {0, 1}, {1, 1}}, {{0, 0}, {0, 1}, {0, 2}, {1, 2}, {1, 3}}, {{0, 0}, {0, 1}, {0, 2}, {-1, 3}, {0, 3}} }; unsigned int g_AllMasks[8192]; unsigned int *g_MaskStart[50][8]; unsigned char g_min_solution[50], g_max_solution[50]; unsigned int g_solutions; unsigned int EvenRowsLookup[50]; unsigned int LeftBorderLookup[50]; bool GoodPiece(unsigned int mask, unsigned int pos) { bool bOK(true); const unsigned long long even_rows = 0xf07c1f07c1f07c1f; const unsigned long long odd_rows = ~even_rows; const unsigned long long left_border = 0x1084210842108421; const unsigned long long right_border = left_border >> 1; unsigned long long a,b,a_old,s1,s2,s3,s4,s5,s6,s7,s8; b = (((unsigned long long)mask) << pos) | 0xFFFC000000000000ULL; b = ~b; while (b) { a = b&-b; do { s1 = a << 5; s2 = a >> 5; s3 = (a << 1)&(~left_border); s4 = (a >> 1)&(~right_border); s5 = ((a & even_rows) >> 6) &(~right_border); s6 = ((a & even_rows) << 4) &(~right_border); s7 = ((a & odd_rows) >> 4) & (~left_border); s8 = ((a & odd_rows) << 6) &(~left_border); a_old = a; a = (a|s1|s2|s3|s4|s5|s6|s7|s8)&b; } while (a_old!=a); if (__builtin_popcountll(a)%5!=0) { bOK = false; break; } b = b ^ a; } return bOK; } void Initialise() { for (int i=0;i<50;i++) { EvenRowsLookup[i] = 0xF07C1F07C1F07C1FULL >> i; LeftBorderLookup[i] = 0x1084210842108421ULL >> i; } int nTotalCount(0); int x[5], y[5]; for (int nYBase=2;nYBase<4;nYBase++) { for (int nXBase=0;nXBase<5;nXBase++) { int nPos = nXBase+5*nYBase; g_MaskStart[nPos][0] = &g_AllMasks[nTotalCount]; for (int nPiece=0;nPiece<nPieceCount;nPiece++) { for (int j=0;j<5;j++) { x[j] = pieces[nPiece][j][0]; y[j] = pieces[nPiece][j][1]; } int nCurrentRotation=0; for (nCurrentRotation=0;nCurrentRotation<12;nCurrentRotation++) { if (nPiece!=3||(nCurrentRotation/3)%2==0) { int nMinX = x[0]; int nMinY = y[0]; for (int i=1;i<5;i++) { if (y[i]<nMinY||(y[i]==nMinY&&x[i]<nMinX)) { nMinX=x[i]; nMinY=y[i]; } } unsigned int mask = 0; bool bFit(true); for (int i=0;i<5;i++) { int nX = (x[i]-nMinX+(nXBase-nYBase/2)) +(y[i]-nMinY+nYBase)/2; int nY = y[i]-nMinY+nYBase; if (nX>=0&&nX<5) { int nBit = nX-nXBase+5*(nY-nYBase); mask |= (1<<nBit); } else { bFit = false; } } if (bFit) { if (GoodPiece(mask,nPos)) { g_AllMasks[nTotalCount++] = mask|(1<<(nPiece+22)); } } } for (int i=0;i<5;i++) { int xnew = x[i]+y[i]; int ynew = -x[i]; x[i] = xnew; y[i] = ynew; if (nCurrentRotation==5) { int xnew = x[i]+y[i]; int ynew = -y[i]; x[i] = xnew; y[i] = ynew; } } } } g_AllMasks[nTotalCount++] = 0; } } // copy rows 2 and 3 to other rows for (int nYBase=0;nYBase<10;nYBase++) { if (nYBase!=2&&nYBase!=3) { for (int nXBase=0;nXBase<5;nXBase++) { int nPos = nXBase+5*nYBase; int nOrigPos = nXBase+5*(nYBase%2+2); g_MaskStart[nPos][0] = &g_AllMasks[nTotalCount]; unsigned int *pMask = g_MaskStart[nOrigPos][0]; unsigned int bottom = (0xFFFC000000000000ULL>>nPos) &0x003FFFFF; unsigned int last_row = (0xFFFC000000000000ULL>>(nPos+5)) &0x003FFFFF; while (*pMask) { unsigned int mask=*pMask; pMask++; if ((mask&bottom)==0) { if (nYBase==0||(mask&last_row)) { if (!GoodPiece(mask&0x003FFFFF,nPos)) { continue; } } g_AllMasks[nTotalCount++] = mask; } } g_AllMasks[nTotalCount++] = 0; } } } for (int nFilter=1;nFilter<8;nFilter++) { for (int nPos=0;nPos<50;nPos++) { g_MaskStart[nPos][nFilter] = &g_AllMasks[nTotalCount]; unsigned int filter_mask; filter_mask = ((nFilter&1)<<1)|((nFilter&6)<< (4-(EvenRowsLookup[nPos]&1))); unsigned int *pMask = g_MaskStart[nPos][0]; while (*pMask) { unsigned int mask=*pMask; if ((mask&filter_mask)==0) { g_AllMasks[nTotalCount++] = mask; } pMask++; } g_AllMasks[nTotalCount++] = 0; } } } void CompareSolution(unsigned char* board, unsigned char* min_solution, unsigned char* max_solution) { int i,j; for (i=0;i<50;i++) { if (board[i]<min_solution[i]) { for (j=0;j<50;j++) { min_solution[j] = board[j]; } break; } else if (board[i]>min_solution[i]) { break; } } for (i=0;i<50;i++) { if (board[i]>max_solution[i]) { for (j=0;j<50;j++) { max_solution[j] = board[j]; } break; } else if (board[i]<max_solution[i]) { break; } } } void PrintBoard(unsigned char *board) { int i; for (i=0;i<50;i++) { printf ("%d ", board[i]); if (i%5==4) { printf("\n"); if ((i&1)==0) { printf (" "); } } } printf ("\n"); } void RecordSolution(unsigned int current_solution[]) { unsigned char board[50], flip_board[50]; int i; unsigned long piece; unsigned int mask, pos, current_bit, b1; unsigned long count; b1 = 0; pos = 0; for (i=0;i<10;i++) { mask = current_solution[i]; piece = __builtin_ctz(mask>>22); mask &= 0x003FFFFF; b1 |= mask; while (mask) { current_bit = mask&-mask; count = __builtin_ctz(current_bit); board[count+pos] = piece; flip_board[49-count-pos] = piece; mask ^= current_bit; } count = __builtin_ctz(~b1); pos+=count; b1 >>= count; } if (g_solutions==0) { for (i=0;i<50;i++) { g_min_solution[i] = g_max_solution[i] = board[i]; } } else { CompareSolution(board, g_min_solution, g_max_solution); CompareSolution(flip_board, g_min_solution, g_max_solution); } g_solutions+=2; } void searchLinear(unsigned int board, unsigned int pos, unsigned int used, unsigned int placed, unsigned int current_solution[]) { unsigned long count; unsigned int even_rows, odd_rows, left_border, right_border, s1, s2, s3, s4, s5, s6, s7, s8; if (placed==10) { #pragma omp critical RecordSolution(current_solution); } else { even_rows = EvenRowsLookup[pos]; odd_rows = ~even_rows; left_border = LeftBorderLookup[pos]; right_border = left_border>>1; s1 = (board << 1) | left_border; s2 = (board >> 1) | right_border; s3 = (board << 4) | ((1<<4)-1) | right_border; s4 = (board >> 4) | left_border; s5 = (board << 5) | ((1<<5)-1); s6 = (board >> 5); s7 = (board << 6) | ((1<<6)-1) | left_border; s8 = (board >> 6) | right_border; if (~board&s1&s2&s5&s6&((even_rows&s4&s7)|(odd_rows&s3&s8))) { return; } count = __builtin_ctz(~board); pos+=count; board >>= count; unsigned int f; f = ((board>>1)&1)|((board>>(4-(EvenRowsLookup[pos]&1)))&6); unsigned int board_and_used = board|used; unsigned int *masks = g_MaskStart[pos][f]; unsigned int mask; while (*masks) { while ((*masks)&board_and_used) { masks++; } if (*masks) { mask = *masks; current_solution[placed] = mask; searchLinear(board|((mask&0x003FFFFF)), pos, used|(mask&0xFFC00000), placed+1, current_solution); masks++; } } } } void searchParallel(unsigned int board, unsigned int pos, unsigned int used, unsigned int placed, unsigned int first_piece) { unsigned long count; count = __builtin_ctz(~board); pos+=count; board >>= count; unsigned int board_and_used = board|used; unsigned int *masks = g_MaskStart[pos][0]; unsigned int mask; if (placed==0) { while (*masks) { while ((*masks)&board_and_used) { masks++; } if (*masks) { mask = *masks++; { searchParallel(board|((mask&0x003FFFFF)), pos, used|(mask&0xFFC00000), placed+1, mask); } } } } else { // placed==1 while (*masks) { while ((*masks)&board_and_used) { masks++; } if (*masks) { mask = *masks++; #pragma omp task default(none) firstprivate(board, mask, pos, used, placed, first_piece) { unsigned int current_solution[10]; current_solution[0] = first_piece; current_solution[placed] = mask; searchLinear(board|((mask&0x003FFFFF)), pos, used|(mask&0xFFC00000), placed+1, current_solution); } } } } } int main(int argc, char* argv[]) { if (argc > 2) return 1; Initialise(); g_solutions = 0; #pragma omp parallel { #pragma omp single { searchParallel(0,0,0,0,0); } } printf ("%d solutions found\n\n",g_solutions); PrintBoard(g_min_solution); PrintBoard(g_max_solution); return 0; }
make, command-line, and program output logs
Tue, 30 Apr 2013 05:33:55 GMT
MAKE:
/usr/bin/g++ -c -pipe -O3 -fomit-frame-pointer -march=native meteor.gpp-6.c++ -o meteor.gpp-6.c++.o && \
/usr/bin/g++ meteor.gpp-6.c++.o -o meteor.gpp-6.gpp_run
rm meteor.gpp-6.c++
0.34s to complete and log all make actions
COMMAND LINE:
./meteor.gpp-6.gpp_run 2098
PROGRAM OUTPUT:
2098 solutions found
0 0 0 0 1
2 2 2 0 1
2 6 6 1 1
2 6 1 5 5
8 6 5 5 5
8 6 3 3 3
4 8 8 9 3
4 4 8 9 3
4 7 4 7 9
7 7 7 9 9
9 9 9 9 8
9 6 6 8 5
6 6 8 8 5
6 8 2 5 5
7 7 7 2 5
7 4 7 2 0
1 4 2 2 0
1 4 4 0 3
1 4 0 0 3
1 1 3 3 3