Keskustelu: Ohjelmointikysymykset: C: Alkeisesimerkki suoritusnopeuden mittauksesta

#include <assert.h> /* assert */
#include <stdio.h> /* printf */
#include <stdlib.h> /* exit, system */
#include <string.h> /* memset */
#include <time.h> /* clock, clock_t */

#ifndef ROWS
#define ROWS 512
#endif

#ifndef COLS
#define COLS 512
#endif

#ifndef BLOCKSIZE
#define BLOCKSIZE 128
#endif

#ifndef SEARCHTESTS
#define SEARCHTESTS 1000
#endif

#ifndef MULTESTS
#define MULTESTS 10
#endif

const double neg_inf = 0.0 / -1.0;

void print_matrix(double mat[ROWS][COLS]) {
	int i, j;
	for (i=0; i<ROWS; ++i) {
		for (j=0; j<COLS; ++j)
			printf ("%f ", mat[i][j]);
		printf ("\n");
	}
	printf ("\n");
}

void fill_matrix1(double mat[ROWS][COLS]) {
	int i, j;
	for (i=0; i<ROWS; ++i)
	for (j=0; j<COLS; ++j)
		mat[i][j]=1.0/((i+j)%10 + 1);
}

void fill_matrix2(double mat[ROWS][COLS]) {
	int i, j;
	for (i=0; i<ROWS; ++i)
	for (j=0; j<COLS; ++j)
		mat[i][j]=2.0/((i*j)%10 + 1);
}


void zero_matrix(double mat[ROWS][COLS]) {
	memset(mat, 0, sizeof(double) * ROWS * COLS);
}

double find_max1(double mat[ROWS][COLS]) {
	int i, j;
	double best = neg_inf;
	for (i=0; i<ROWS; ++i)
	for (j=0; j<COLS; ++j) {
		if (mat[i][j] > best) best = mat[i][j];
	}
	return best;
}

double find_max2(double mat[ROWS][COLS]) {
	int i, j;
	double best = neg_inf;
	for (j=0; j<COLS; ++j)
	for (i=0; i<ROWS; ++i) {
		if (mat[i][j] > best) best = mat[i][j];
	}
	return best;
}

void matrix_mul1(double left[ROWS][COLS],
	double right[ROWS][COLS], double res[ROWS][COLS])
{
	int i, j, k;
	double e;
	const int N = ROWS;
	assert (ROWS==COLS);
	for (i=0; i<N; ++i)
	for (j=0; j<N; ++j) {
		e = 0;
		for (k=0; k<N; ++k)
			e += left[i][k] * right[k][j];
		res[i][j] = e;
	}
}

void matrix_mul2(double left[ROWS][COLS],
	double right[ROWS][COLS], double res[ROWS][COLS])
{
	int i, j, k;
	double e;
	int jb, kb;
	const int N = ROWS;
	#define MIN(x,y) ((x) < (y) ? (x) : (y))
	assert (ROWS==COLS);
	zero_matrix(res);
	for(jb=0; jb<N; jb += BLOCKSIZE)
	for(kb=0; kb<N; kb += BLOCKSIZE)
	for (i=0; i<N; ++i)
	for (j=jb; j<MIN(jb+BLOCKSIZE, N); ++j) {
		e = 0;
		for (k=kb; k<MIN(kb+BLOCKSIZE, N); ++k)
			e += left[i][k] * right[k][j];
		res[i][j] += e;
	}
}


int main (void) {
	static double
		mat1[ROWS][COLS],
		mat2[ROWS][COLS],
		mat3[ROWS][COLS],
		mat4[ROWS][COLS];
	int i, j;
	double max1, max2;
	clock_t start, stop;
	fill_matrix1(mat1);
	fill_matrix2(mat2);

	printf ("Test 1: Matrix search rows first.\n");
	start = clock();
	for (i=0; i<SEARCHTESTS; ++i)
		max1 = find_max1(mat1);
	stop = clock();
	printf ("Test 1 took approximately %f seconds.\n",
		((double)(stop-start)) / CLOCKS_PER_SEC);

	printf ("Test 2: Matrix search columns first. \n");
	start = clock();
	for (i=0; i<SEARCHTESTS; ++i)
		max2 = find_max2(mat1);
	stop = clock();
	printf ("Test 2 took approximately %f seconds.\n",
		((double)(stop-start)) / CLOCKS_PER_SEC);

	if (max1 != max2) {
		printf ("!error: program found different maximums from same matrix");
		exit (1);
	}

	if (ROWS != COLS) {
		printf ("Can't test matrix multiplication. Dumb program "
			"expects square matrices. Sorry.\n");
		exit(0);
	}

	printf ("Test 3: Straight matrix multiplication. \n");
	start = clock();
	for (i=0; i<MULTESTS; ++i)
		matrix_mul1(mat1, mat2, mat3);
	stop = clock();
	printf ("Test 3 took approximately %f seconds.\n",
		((double)(stop-start)) / CLOCKS_PER_SEC);

	printf ("Test 4: Matrix multiplication in blocks of size %d. \n", BLOCKSIZE);
	start = clock();
	for (i=0; i<MULTESTS; ++i)
		matrix_mul2(mat1, mat2, mat4);
	stop = clock();
	printf ("Test 4 took approximately %f seconds.\n",
		((double)(stop-start)) / CLOCKS_PER_SEC);

	for (i=0; i<ROWS; ++i)
	for (j=0; j<COLS; ++j) {
		double diff = mat3[i][j] - mat4[i][j];
		diff = (diff < 0.0) ? -diff : diff;
		if (diff > 0.00001) {
			printf ("!error: diff at %d %d\n", i, j);
			printf ("%f %f\n", mat3[i][j], mat4[i][j]);
			exit(1);
		}
	}
	/* only for use with small matrices
	print_matrix(mat1);
	print_matrix(mat2);
	print_matrix(mat3);
	print_matrix(mat4);
	*/
	/* ring bell (\a) to signal end of long test */
	#ifdef ALERT_FINISHED
	printf ("Done\a\n");
	#endif

	/* prevent IDE from closing console window; for Windows people */
	#ifdef USE_PAUSE
	system("PAUSE");
	#endif

	return 0;
}