Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!caip!sri-spam!mordor!lll-crg!seismo!umcp-cs!chris
From: chris@umcp-cs.UUCP (Chris Torek)
Newsgroups: net.lang.c
Subject: Re: Generating code for the switch statement
Message-ID: <2784@umcp-cs.UUCP>
Date: Thu, 7-Aug-86 17:22:52 EDT
Article-I.D.: umcp-cs.2784
Posted: Thu Aug  7 17:22:52 1986
Date-Received: Sat, 9-Aug-86 07:37:36 EDT
References: <15093@ucbvax.BERKELEY.EDU> <2765@brl-smoke.ARPA> <15120@ucbvax.BERKELEY.EDU> <610@hropus.UUCP> <1171@umd5>
Reply-To: chris@maryland.UUCP (Chris Torek)
Organization: University of Maryland, Dept. of Computer Sci.
Lines: 81

>In article <610@hropus.UUCP> ka@hropus.UUCP (Kenneth Almquist) writes:
>>If the cases are not consecutive, the branch table must be filled with
>>entries for the "missing" cases, making the table larger [; eventually
>>this becomes a waste of space and the compiler uses a different approach].

In article <1171@umd5> zben@umd5.umd.edu (Ben Cranston) writes:
>... In one of an innumerable number of Impress-understanding
>programs I converted an IF nest into a switch statement, and was
>chagrined when the program didn't show a vast efficiency improvement.
>After peeking at the (BSD4.x) C compiler code generator we found
>the 1/3 fudge factor, and that the Impress codes were only two
>short of being dense enough to compile into a jump table.

[... followed by speculation on the effects of adding two cases.]

One can force a consecutive sequence in another, less compiler
dependent, way.  Write a compressing array:

	char	input_class[256] = {
		/* classes for 0-127 */
		is_char, is_char, ..., is_char,
		/* classes for 128 on up */
		is_obj1, is_obj2, is_obj2, is_badobj, is_obj1, ...
	};

Then use

	switch (input_class[input]) {
	case is_char:
		...
	case is_obj1:
		...
	}

Those who are familiar with Knuth's TeX system may have seen some
of the code supplied to convert TeX .DVI files to device-dependent
data (a la Imagen's imPress language).  In these, someone---Knuth
himself most likely---has written code of the form

	/* translated to C for this newsgroup */
	#define two_cases(base) \
			base: case base+1
	#define four_cases(base) \
			two_cases(base): case two_cases(base+2)
	#define eight_cases(base) \
			four_cases(base): case four_cases(base+4)
	#define thirty_two_cases(base) \
			eight_cases(base): case eight_cases(base+8): \
			case eight_cases(base+16): case eight_cases(base+24)
	#define	sixty_four_cases(base) \
			thirty_two_cases(base): case thirty_two_cases(base+32)

then, later in the program, used these as (e.g.)

	#define w0	147
	...
	#define	fntnum0	171
	...

		case four_cases(w0):
			w = p;
			x += w;
			break;
		...

		case sixty_four_cases(fntnum0):
			font = p;
			break;
		...

I originally used rather similar code in my own Imagen and Versatec
DVI conversion programs.  For some reason I decided one day to try
a compressing array like the one above.  To my surprise, the code
was not only clearer to me, but also ran rather faster.  I verified
that the generated code indeed used a vax `casel' instruction in
both versions.  My guess is that the speedup came entirely from
fitting more of the main loop into the cache.
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 1516)
UUCP:	seismo!umcp-cs!chris
CSNet:	chris@umcp-cs		ARPA:	chris@mimsy.umd.edu