The Joy of Tables

CS 301 Lecture, Dr. Lawlor

Tables for Optimization

Arrays are beautiful things. It's just as easy to index into a million-element array as it is into a two-element array--its just a[i] each time. You can use tables to speed up things that would otherwise be really slow.

For example, say you've got a really complicated subroutine that, given an input value from 0 to 99, returns an output int:
    int really_complicated(int i) { ... }

You can make such a routine much faster by computing the values once, and storing the result in a little table:
    int really_fast(int i) {
       int *table=0;
       if (table==0) { /* gotta fill the table the first time around */
          table=new int[100];
          for (int t=0;t<100;t++) table[t]=really_complicated(t);
       }
       return table[i];
    }

"return table[i]" might be a thousand times faster than whatever "..." does!

You can also initialize the array one entry at a time instead of all at once.

You could also figure out the table values when you write the code, and hardcode the values into the array:

    int really_fast_static(int i) {
       static const int table[]={7,9,14,15,1,3};
       return table[i];
    }

Sometimes adding a table like this can make the code much *simpler*, by replacing a static decision by a table lookup.

Switch Statements

The "switch" statement in C can be implemented in one of two ways:

The compiler could put in a test for each "case", and jump to the appropriate chunk of code. This is fine for small "switch"es, but gets slower and slower as you add cases (because you need more and more tests).
```
if (v==case1) {code1();}
if (v==case2) {code2();}
if (v==case3) {code3();}
if (v==case4) {code4();}
if (v==case5) {code5();}
```
The compiler can build a little "jump table" pointing to the code to jump to for each case, and then just do a computed jump, using something like "jmp *the_table(,%edx,4)", which means to jump to the pointer stored in "the_table[%edx]". The advantage of this approach is that it costs the same amount for 10 cases as it does for 1000 cases (because indexing a 10-entry table is about as fast as a 1000-entry table).

In each case, a "break" is always just a "goto end_of_switch".

Check out the disassembly for this C code:

switch (read_input()) {
case 0: return 0xd00dE0;
case 1: return 0x373371;
case 2: return 0xd00d02;
case 3: return 0xd00d03;
case 4: return 0xd00d04;
}
return 0xbaddd;

(executable NetRun Link)

Here's a little assembly example where we build a "jump table", that gives the address where we should keep running:

extern read_input
call read_input
; Return value comes back in eax
; Now jump to entry eax of the jump table:
jmp [jump_table + 4*eax]
mov eax,0xf00bad; <- Should never come back here!
ret

jump_table:
	dd case0; index 0, stores address of case0 (just 4 bytes)
	dd case1
	dd case2

case0:
	mov eax,0xd00dE0;
	ret
case1:
	mov eax,0x373371;
	ret
case2:
	mov eax,0xd00d02;
	ret

(executable NetRun Link)

Function Pointers, and Tables of Function Pointers

You can tell C about a whole group of functions that take the same arguments and return types, and then "point" to one of those functions. This is called a "function pointer", which in assembly is just the address of the code to run. The ugliest part about function pointers (by far!) is the syntax--I recommend you always use a typedef to define a function pointer. For example, here's how you make a new type "fn_ptr_t" that takes a short and returns an int:

typedef int (*fn_ptr_t)(short param);

Now you can declare variables of type "fn_ptr_t", assign compatible functions to them, and finally call them:

int case0(short val) {return 0xd00dE0+val;}
int case1(short val) {return 0x373371;}
int case2(short val) {return 0xd00d02;}

int foo(void) {
	typedef int (*fn_ptr_t)(short param); /* "fn_ptr_t" is a function pointer */
	fn_ptr_t x;
	x=case0;
	if (read_input()) x=case1; 
	int v=x(3); /* call the function pointer */
	return v;
}

(executable NetRun Link)

You can sort of fake a switch-style jump table in C using a table of function pointers:

int case0(void) {return 0xd00dE0;}
int case1(void) {return 0x373371;}
int case2(void) {return 0xd00d02;}

int foo(void) {
	typedef int (*fn_t)(void); /* "fn_t" is a function pointer */
	const static fn_t arr[3]={case0,case1,case2}; /* "arr" is an array of "fn_t"s */
	fn_t fn=arr[read_input()]; /* grab a fn_t from the array */
	return fn(); /* call the function */
}

(executable NetRun Link)

One common use of function pointers is to fake C++-style "virtual methods" in C. This is very similar to how C++ actually implements virtual methods!

struct parent;
typedef void (*fn_parent_bar)(struct parent *this);
struct parent {
	int v;
	fn_parent_bar bar; /* function pointer */
};

void parent_bar(struct parent *this) { printf("I'm the parent (v=%d)\n",this->v); }
void child_bar(struct parent *this) { printf("I'm the child (v=%d)\n",this->v); }

int foo(void) {
	struct parent p;
	p.v=10;
	p.bar=parent_bar; /* set up function pointer */
	p.bar(&p); /* call function pointer */
	
	struct parent c; /* "child class", with different methods */
	c.v=11;
	c.bar=child_bar;
	c.bar(&c);

	return 0;
}

(executable NetRun link)

The only difference between C++ virtual methods and the above "struct field is a function pointer" trick are:

The C++ syntax is nicer--just put "virtual" ahead of the method name, instead of declaring a separate function.
The "this" pointer is automatically passed into C++ class methods, instead of manually like above.
All the function pointers for virtual methods of a particular class type are kept in a second, smaller, readonly struct called the "vtable". The vtable is pointed to by an invisible class member; all instances of a given class point to the same vtable (for the class).

Extra! The Thing that should not be C

Here's the unholy hybrid offspring of a switch statement and a for loop.
(Executable NetRun Link)

int foo(void) {
	int sum=0,j=0;
	switch (sum&0x7) {
	       for (;j<100;j++) { 
	case 7:  sum++;
	case 6:  sum++;
	case 5:  sum++; 
	case 4:  sum++;
	case 3:  sum++;
	case 2:  sum++;
	case 1:  sum++;
	case 0:  sum++; 
	       }
	};
	return (int)sum;
}

Note the returned value--*both* the switch statement *and* the for loop are running!

Can you think of a use for this monstrosity?