Jump tables

Started by
2 comments, last by Russell 20 years, 6 months ago
I have used switch statements and arrays of function pointers in the past to achieve a little speed boost in situations where there were potentially many unpredictable branches, replacing those many unpredictable branches with one unpredictable branch (the jump table). I was wondering if there are limits to this approach. For instance, is there a point at which adding more elements to the jump table would begin causing a slow down? Even if it is a large, seemingly ridiculous limit, I''m still interested in knowing what it is. The only thing I can think of is that if the jump table gets so large that the table can no longer fit in the cpu cache, then a slowdown could occur.
Advertisement
nope.

The upper limit is somewhere around not being able to fit the table into memory.
The compiler ought to turn switch statements into jump tables, that''s why switch''s only work on integral values.
- The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara
quote:Original post by Magmai Kai Holmlor
The compiler ought to turn switch statements into jump tables, that's why switch's only work on integral values.

It depends entirely on the nature of the switch statement. Chained if/elses (small switches), jump tables (large dense switches), or binary trees (large sparse switches) may be best in any given circumstance. Or a combination of all three (e.g. a large range with several dense parts may use a binary search to find the right dense part and then jump tables).



[edited by - DrPizza on October 12, 2003 9:38:37 PM]
char a[99999],*p=a;int main(int c,char**V){char*v=c>0?1[V]:(char*)V;if(c>=0)for(;*v&&93!=*v;){62==*v&&++p||60==*v&&--p||43==*v&&++*p||45==*v&&--*p||44==*v&&(*p=getchar())||46==*v&&putchar(*p)||91==*v&&(*p&&main(0,(char**)(--v+2))||(v=(char*)main(-1,(char**)++v)-1));++v;}else for(c=1;c;c+=(91==*v)-(93==*v),++v);return(int)v;}  /*** drpizza@battleaxe.net ***/

This topic is closed to new replies.

Advertisement