Archived

This topic is now archived and is closed to further replies.

Russell

Jump tables

Recommended Posts

Russell    118
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.

Share this post


Link to post
Share on other sites
DrPizza    160
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]

Share this post


Link to post
Share on other sites