Xref: utzoo comp.lang.c:11353 comp.arch:5524
Path: utzoo!attcan!uunet!lll-winken!lll-lcc!ames!ucsd!chem.ucsd.edu!tps
From: tps@chem.ucsd.edu (Tom Stockfisch)
Newsgroups: comp.lang.c,comp.arch
Subject: Re: Self-modifying code (and space/time complexity)
Keywords: self-modifying code, generate-and-execute
Message-ID: <257@chem.ucsd.EDU>
Date: 16 Jul 88 02:42:37 GMT
References: <3353@cognos.UUCP> <619@goofy.megatest.UUCP> <429@uwovax.uwo.ca> <12360@ut-sally.UUCP> <1744@vaxb.calgary.UUCP> <33652@yale-celray.yale.UUCP>
Reply-To: tps@chem.ucsd.edu (Tom Stockfisch)
Organization: Chemistry Dept, UC San Diego
Lines: 51

In article <33652@yale-celray.yale.UUCP> lisper-bjorn@CS.YALE.EDU (Bjorn Lisper) writes:
>In article <1744@vaxb.calgary.UUCP> radford@calgary.UUCP (Radford Neal) writes:
>>There are interesting cases where on-the-fly generation of code seems
>>to be essential to get good asymptotic space and/or time complexity.
>>
>>     for (i = 0; i<L; i++)
>>     { if (c1) p1();
>>       if (c2) p2();
>>       ...
>>       if (cN) pN();
>>     }
>>[SMC solution follows]
>>     start generating code;
>>     if (c1) generate instruction to call p1;
>>     if (c2) generate instruction to call p2;
>>     ...
>>     if (cN) generate instruction to call pN;
>>     for (i = 0; i<L; i++) execute generated instructions;

Wouldn't the following be "nearly" as efficient, and be portable to boot?
At least it has the same asymptotic complexity.

	enum { END, P1, P2, ..., Pn }	code[MAXCODE], *p;

	p = code;
	if (c1)	*p++ =	P1;
	if (c2)	*p++ =	P2;
	...
	if (cn)	*p++ =	Pn;
	*p =	END;

	for ( pixel = 0; pixel++ < NPIXELS )
		for ( p = code; *p != END; )
			switch (*p++)
			{
			case	P1:
				[p1 instructions]
				break;
			case	P2:
				[p2 instructions]
				break;
			...
			case	Pn:
				[pn instructions]
				break;
			default:
				assert(0);
				/*NOTREACHED*/
			}
-- 

|| Tom Stockfisch, UCSD Chemistry	tps@chem.ucsd.edu