[cc65] Finished product: FAST ShellSort demo for c64 (working :) ) - feedback?

Date view Thread view Subject view

From: Greg Long (greg_at_maneuveringspeed.com)
Date: 2003-03-05 04:09:40 

This same sort, 19,000 random 16bit integers, took 256 minutes in
uncompiled BASIC.  CC65's -Oi code does it in 10minutes, 34 seconds.

(.NET release C++ build on a Pentium III 1ghz CPU - about 1/20th of a
second.)

I wrote the same routine in 6502 assembly but have yet to debug it;)


SO.... we might say a "typical" 1ghz computer today is roughly 13,000
faster than a 1982 Commodore 64 (for Compiled C) or 300,000 times faster
than uncompiled BASIC.

The Shell Sort, invented by Donald Shell, is one of the fastest sorting
routines available. Others, such as the Quick Sort, involve too much
recursion to be practical on the 64. The Merge and Quick sort algorithms
are faster, but waste memory...up to twice the ammount of the original
array.

It can be seen that this routine can be modifed to sort strings without
much difficulty.  (Now how do I overload the < and > operators in C?)

Actual results may vary, see dealer for details.

Known bugs:
-----------
1) cprintf does not appear to work properly :  replace \r with \n and
watch the results.

2) If the code is executed a second time, it crashes.  Don't know
why...It may be due to the writing to RAM beneath the BASIC interpreter.
I went with 19,000 integers because in a BASIC routine, that was the
most that would fit in the standard 38,911 bytes available.  Does CCS65
modify and make calls to the BASIC interpreter?

Greg


//Code below
/***********************************************************************
*****
Shell Sort c64

Demonstration of shell sort

(Much faster selecting "warp mode" on an emulator such as VICE)
************************************************************************
****/


#include <stdlib.h>
#include <time.h>
#include <conio.h>

#define POKE(addr,val)     (*(unsigned char*) (addr) = (val))
#define POKEW(addr,val)    (*(unsigned*) (addr) = (val))
#define PEEK(addr)         (*(unsigned char*) (addr))
#define PEEKW(addr)        (*(unsigned*) (addr))

//Sort routine invented by Donald Shell
void ShellSort(unsigned int *ra, unsigned int size);

//sets TI$="000000" (realtime jiffy clock at addr 160-162)
void stopwatch_reset();

//returns the jiffy clock (60ths of a second)
unsigned long stopwatch();

int main()
{	
	unsigned int size = 19000;
	unsigned int i = size;  
	unsigned int* ra;//Our array
	unsigned char a;//for peek function
	unsigned long sort_time = 0;
	unsigned int secs = 0;

	ra = malloc(size*2);

	//bank out BASIC interpreter
	a = PEEK(1);
	POKE(1,a&254);

	//generate random numbers ranging 0-32767
	while(i)
	{
		ra[i] = rand();
		--i;
	}
	
	//set TI$=0, and call our sort routine.
	stopwatch_reset();
	ShellSort(ra, size);

	sort_time = stopwatch();
	secs = (unsigned int)(sort_time / 60);
	
	//stores # of seconds in locations 1020-1021
	POKEW(1020,secs);
	
	cprintf ("                    Time: %u sec\r", secs);
	//Maybe someone can debug the cprintf calls here in this
block(?):
	for(i=0 ; i<size ; ++i)
	{
		unsigned int num = ra[i];
		cprintf("%u) %u    \r", i, num);
	}

	//re-enable BASIC interpreter
	a = PEEK(1);
	POKE(1,a|1);

	return 0;
}

void stopwatch_reset()
{
	POKE(160,0);
	POKE(161,0);
	POKE(162,0);
}

unsigned long stopwatch()
{
	unsigned long sw_time = 0;

	sw_time += ((unsigned long)PEEK(160)) * 0x10000;
	sw_time += ((unsigned long)PEEK(161)) * 0x100;
	sw_time += (unsigned long)PEEK(162);

	return sw_time;
}


void ShellSort(unsigned int *ra, unsigned int size)
{	
	unsigned int incs[16];

	unsigned int h=1;//increment
	unsigned int i=0;//number of increments)
	char quit=0;

	while(!quit)
	{
		incs[i] = h;
		h = 3*h+1;
		++i;
		
		if(h >= size)
			quit = 1;
	}

	--i;

	while(i)
	{
		unsigned int hCnt = 0;
		unsigned int j = 0;
		unsigned int hCnt2 = 0;
		--i;
		h = incs[i];

		cprintf ("increment: %u     \r", h);

		hCnt2 = 2*h;
		for(hCnt=h ; hCnt<hCnt2 ; ++hCnt)
		{
			for(j = hCnt ; j < size ; j+= h)
			{
				unsigned int temp = ra[j];
				unsigned int k = j;

				while( (h<k) && (temp<ra[k-h]) )
				{
					ra[k] = ra[k-h];
					k-= h;
				}
				ra[k] = temp;
			}
		}
	}
}
---------------------------------------------------------------------- To unsubscribe from the list send mail to majordomo_at_musoftware.de with the string "unsubscribe cc65" in the body(!) of the mail.

Date view Thread view Subject view

This archive was generated by hypermail 2.1.3 : 2003-03-05 15:18:34 CET