From 8a639cb06e75d496a33f609b049dbf9e6145befc Mon Sep 17 00:00:00 2001 From: Matt Turner Date: Wed, 12 Nov 2008 04:53:46 +0000 Subject: Clean up numsort.c git-svn-id: svn://mattst88.com/svn/cleanbench/trunk@11 0d43b9a7-5ab2-4d7b-af9d-f64450cef757 --- Makefile | 32 +++---- nbench1.h | 13 --- numsort.c | 321 ++++++++++++++++++++++++++++---------------------------------- 3 files changed, 160 insertions(+), 206 deletions(-) diff --git a/Makefile b/Makefile index 024a4d7..0bfa36a 100644 --- a/Makefile +++ b/Makefile @@ -19,15 +19,15 @@ default: nbench # You should leave -static in the CFLAGS so that your sysinfo can be # compiled into the executable. -CCC=gcc +ICC=icc GCC=gcc # generic options for gcc #CFLAGS=-O3 -mcpu=ev67 -mieee -funroll-loops -ftree-vectorize -fprefetch-loop-arrays -pipe -static -msmall-data -msmall-text #CFLAGS=-O3 -mcpu=ev67 -mieee -pipe -msmall-data -msmall-text -funroll-loops -ftree-vectorize -static -GCCFLAGS=-O3 -march=k8 -msse3 -ftree-vectorize -funroll-loops -pipe -#CCCFLAGS=-fast -unroll 0 -inline speed -CCCFLAGS=${GCCFLAGS} +GCCFLAGS=-O3 -march=k8 -msse3 -ftree-vectorize -funroll-loops -pipe -static +#GCCFLAGS=-fast -unroll 0 -inline speed +ICCFLAGS=-O2 -ip -xP -gcc -static LINKFLAGS= # if your gcc lets you do it, then try this one @@ -120,33 +120,33 @@ nbench0.o: nbench0.h nbench0.c nmglobal.h hardware.h Makefile sysinfo.c sysinfoc # Segfault before first test emfloat.o: emfloat.h emfloat.c nmglobal.h Makefile - $(CCC) $(DEFINES) $(CCCFLAGS) -c emfloat.c + $(GCC) $(DEFINES) $(GCCFLAGS) -c emfloat.c randnum.o: randnum.c Makefile - $(CCC) $(DEFINES) $(CCCFLAGS) -c randnum.c + $(GCC) $(DEFINES) $(GCCFLAGS) -c randnum.c numsort.o: numsort.c - $(CCC) $(DEFINES) $(CCCFLAGS) -c numsort.c + $(GCC) $(DEFINES) $(GCCFLAGS) -c numsort.c # gcc - 2.95 # ccc - 5.08 stringsort.o: stringsort.c - $(CCC) $(DEFINES) $(CCCFLAGS) -c stringsort.c + $(GCC) $(DEFINES) $(GCCFLAGS) -c stringsort.c # gcc - 6.77 # ccc - 7.24 bitfield.o: bitfield.c - $(CCC) $(DEFINES) $(CCCFLAGS) -c bitfield.c + $(GCC) $(DEFINES) $(GCCFLAGS) -c bitfield.c # gcc - 4.93, 4.90, 4.93, 4.93 # ccc - 4.79, 4.85, 4.81, fpemulation.o: fpemulation.c - $(CCC) $(DEFINES) $(CCCFLAGS) -c fpemulation.c + $(GCC) $(DEFINES) $(GCCFLAGS) -c fpemulation.c # gcc - 13.90 # ccc - 13.90 fourier.o: fourier.c - $(CCC) $(DEFINES) $(CCCFLAGS) -c fourier.c + $(GCC) $(DEFINES) $(GCCFLAGS) -c fourier.c # gcc - 15.96 # ccc - 19.30 @@ -156,14 +156,14 @@ assignment.o: assignment.c # ccc - 7.98 idea.o: idea.c - $(CCC) $(DEFINES) $(CCCFLAGS) -c idea.c + $(GCC) $(DEFINES) $(GCCFLAGS) -c idea.c # gcc - 8.79 # ccc - 9.10 huffman.o: huffman.c $(GCC) $(DEFINES) $(GCCFLAGS) -c huffman.c -# $(CCC) $(DEFINES) -O1 -host -unroll 0 -inline speed -c huffman.c -g3 -# $(CCC) $(DEFINES) $(CCCFLAGS) -c huffman.c -g3 +# $(GCC) $(DEFINES) -O1 -host -unroll 0 -inline speed -c huffman.c -g3 +# $(GCC) $(DEFINES) $(GCCFLAGS) -c huffman.c -g3 # gcc - 6.94 # ccc - segfault # ccc -O1 -host - 5.14 @@ -171,12 +171,12 @@ huffman.o: huffman.c # ccc -O1 -host -unroll 0 -inline speed - 5.95 neural.o: neural.c - $(CCC) $(DEFINES) $(CCCFLAGS) -c neural.c + $(GCC) $(DEFINES) $(GCCFLAGS) -c neural.c # gcc - 12.00 # ccc - 14.20 linear.o: linear.c - $(CCC) $(DEFINES) $(CCCFLAGS) -c linear.c + $(GCC) $(DEFINES) $(GCCFLAGS) -c linear.c # gcc - 16.38 # ccc - 23.29 diff --git a/nbench1.h b/nbench1.h index 77f2bb5..7d53d5a 100644 --- a/nbench1.h +++ b/nbench1.h @@ -72,19 +72,6 @@ extern double TicksToFracSecs(unsigned long tickamount); ** PROTOTYPES */ void DoNumSort(void); -static unsigned long DoNumSortIteration(long *arraybase, - unsigned long arraysize, - unsigned int numarrays); -static void LoadNumArrayWithRand(long *array, - unsigned long arraysize, - unsigned int numarrays); -static void NumHeapSort(long *array, - unsigned long bottom, - unsigned long top); -static void NumSift(long *array, - unsigned long i, - unsigned long j); - /**************** ** STRING SORT ** diff --git a/numsort.c b/numsort.c index 5756a31..6337037 100644 --- a/numsort.c +++ b/numsort.c @@ -1,11 +1,7 @@ #include -#include -/* #include -#include -#include -#include -*/ +#include + #include "nmglobal.h" #include "nbench1.h" @@ -15,110 +11,91 @@ ** This test implements a heapsort algorithm, performed on an ** array of longs. */ +static unsigned long DoNumSortIteration(long *arraybase, unsigned long arraysize, unsigned int numarrays); +static void LoadNumArrayWithRand(long *array, unsigned long arraysize, unsigned int numarrays); +static inline void NumHeapSort(long *array, unsigned long bottom, unsigned long top); +static inline void NumSift(long *array, unsigned long min, unsigned long max); /************** ** DoNumSort ** *************** ** This routine performs the CPU numeric sort test. -** NOTE: Last version incorrectly stated that the routine -** returned result in # of longword sorted per second. -** Not so; the routine returns # of iterations per sec. */ void DoNumSort(void) { /* Error context string pointer */ - const char *errorcontext = "CPU:Numeric Sort"; + const char *context = "CPU:Numeric Sort"; /* Local pointer to global struct */ SortStruct * numsortstruct = &global_numsortstruct; long accumtime; /* Accumulated time */ double iterations; /* Iteration counter */ - long *arraybase; /* Base pointers of array */ - int systemerror; /* For holding error codes */ - -/* -** See if we need to do self adjustment code. -*/ -if(numsortstruct->adjust==0) -{ - /* - ** Self-adjustment code. The system begins by sorting 1 - ** array. If it does that in no time, then two arrays - ** are built and sorted. This process continues until - ** enough arrays are built to handle the tolerance. - */ - numsortstruct->numarrays=1; - while(1) - { - /* - ** Allocate space for arrays - */ - arraybase=(long *)AllocateMemory(sizeof(long) * - numsortstruct->numarrays * numsortstruct->arraysize, - &systemerror); - if(systemerror) - { ReportError(errorcontext,systemerror); - FreeMemory((void *)arraybase, - &systemerror); - } - - /* - ** Do an iteration of the numeric sort. If the - ** elapsed time is less than or equal to the permitted - ** minimum, then allocate for more arrays and - ** try again. - */ - if(DoNumSortIteration(arraybase, - numsortstruct->arraysize, - numsortstruct->numarrays)>global_min_ticks) - break; /* We're ok...exit */ + long *arraybase = NULL; /* Base pointers of array */ + + /* + ** See if we need to do self adjustment code. + */ + if(numsortstruct->adjust==0) { + /* + ** Self-adjustment code. The system begins by sorting 1 + ** array. If it does that in no time, then two arrays + ** are built and sorted. This process continues until + ** enough arrays are built to handle the tolerance. + */ + numsortstruct->numarrays=1; + while(1) { + arraybase = realloc(arraybase, numsortstruct->numarrays * numsortstruct->arraysize * sizeof(long)); + if (!arraybase) { + fprintf(stderr, "Error in %s, could not allocate memory. Exitting...\n", context); + exit(1); + } - FreeMemory((void *)arraybase,&systemerror); - if(numsortstruct->numarrays++>NUMNUMARRAYS) - { printf("CPU:NSORT -- NUMNUMARRAYS hit.\n"); - } - } -} -else -{ /* - ** Allocate space for arrays - */ - arraybase=(long *)AllocateMemory(sizeof(long) * - numsortstruct->numarrays * numsortstruct->arraysize, - &systemerror); - if(systemerror) - { ReportError(errorcontext,systemerror); - FreeMemory((void *)arraybase, - &systemerror); - } + /* + ** Do an iteration of the numeric sort. If the + ** elapsed time is less than or equal to the permitted + ** minimum, then allocate for more arrays and + ** try again. + */ + if ( DoNumSortIteration(arraybase, numsortstruct->arraysize, numsortstruct->numarrays)>global_min_ticks ) { + break; + } -} -/* -** All's well if we get here. Repeatedly perform sorts until the -** accumulated elapsed time is greater than # of seconds requested. -*/ -accumtime = 0L; -iterations = 0.0; + if(numsortstruct->numarrays > NUMNUMARRAYS) { + printf("CPU:NSORT -- NUMNUMARRAYS hit.\n"); + } + ++numsortstruct->numarrays; + } + } else { + arraybase = malloc(numsortstruct->numarrays * numsortstruct->arraysize * sizeof(long)); + if (!arraybase) { + fprintf(stderr, "Error in %s, could not allocate memory. Exitting...\n", context); + exit(1); + } + } -do { - accumtime+=DoNumSortIteration(arraybase, - numsortstruct->arraysize, - numsortstruct->numarrays); - iterations+=(double)1.0; -} while(TicksToSecs(accumtime)request_secs); + /* + ** All's well if we get here. Repeatedly perform sorts until the + ** accumulated elapsed time is greater than # of seconds requested. + */ + accumtime = 0L; + iterations = 0.0; -/* -** Clean up, calculate results, and go home. Be sure to -** show that we don't have to rerun adjustment code. -*/ -FreeMemory((void *)arraybase,&systemerror); + do { + accumtime += DoNumSortIteration(arraybase, numsortstruct->arraysize, numsortstruct->numarrays); + iterations += 1.0; + } while ( TicksToSecs(accumtime) < numsortstruct->request_secs ); -numsortstruct->sortspersec=iterations * - (double)numsortstruct->numarrays / TicksToFracSecs(accumtime); + /* + ** Clean up, calculate results, and go home. Be sure to + ** show that we don't have to rerun adjustment code. + */ + free(arraybase); -if(numsortstruct->adjust==0) - numsortstruct->adjust=1; + numsortstruct->sortspersec=iterations * (double)numsortstruct->numarrays / TicksToFracSecs(accumtime); + if ( numsortstruct->adjust == 0 ) { + numsortstruct->adjust = 1; + } } /*********************** @@ -128,34 +105,33 @@ if(numsortstruct->adjust==0) ** sort benchmark. It returns the number of ticks ** elapsed for the iteration. */ -static unsigned long DoNumSortIteration(long *arraybase, - unsigned long arraysize, - unsigned int numarrays) -{ -unsigned long elapsed; /* Elapsed ticks */ -unsigned long i; -/* -** Load up the array with random numbers -*/ -LoadNumArrayWithRand(arraybase,arraysize,numarrays); - -/* -** Start the stopwatch -*/ -elapsed=StartStopwatch(); - -/* -** Execute a heap of heapsorts -*/ -for(i=0;i0; --i) - NumSift(array,i,top); + /* + ** First, build a heap in the array + */ + for (i = (top / 2L); i > 0; i-- ) { + NumSift(array, i, top); + } -/* -** Repeatedly extract maximum from heap and place it at the -** end of the array. When we get done, we'll have a sorted -** array. -*/ -for(i=top; i>0; --i) -{ NumSift(array,bottom,i); - temp=*array; /* Perform exchange */ - *array=*(array+i); - *(array+i)=temp; -} -return; + /* + ** Repeatedly extract maximum from heap and place it at the + ** end of the array. When we get done, we'll have a sorted + ** array. + */ + for ( i = top; i > 0; i-- ) { + NumSift(array, bottom, i); + + temp = *array; + *array = *(array + i); + *(array + i) = temp; + } } /************ @@ -236,28 +206,25 @@ return; ** Peforms the sift operation on a numeric array, ** constructing a heap in the array. */ -static void NumSift(long *array,/* Array of numbers */ - unsigned long i, /* Minimum of array */ - unsigned long j) /* Maximum of array */ -{ +static inline void NumSift(long *array, unsigned long min, unsigned long max) { unsigned long k; unsigned long temp; /* Used for exchange */ - while ( ( i + i ) <= j ) { - k = i + i; - if ( k < j ) { + while ( ( min * 2 ) <= max ) { + k = min * 2; + if ( k < max ) { if ( array[k] < array[k+1L] ) { ++k; } } - if ( array[i] < array[k] ) { + if ( array[min] < array[k] ) { temp = array[k]; - array[k] = array[i]; - array[i] = temp; - i = k; + array[k] = array[min]; + array[min] = temp; + min = k; } else { - i = j + 1; + min = max + 1; } } } -- cgit v1.2.3