Author: Gareth McCaughan
Date: 19:50:21 01/14/02
Go up one level in this thread
On January 14, 2002 at 15:32:19, Andrew Dados wrote: [Robert Hyatt described a jump table and said:] >> The above is the best way to handle a switch (C) or case (pascal) >> type structure. ... >> The alternative is to use a series of if-then-else clauses but as you add >> cases, you add branches and slow things down. Most common case _must_ >> appear first for performance. While with the jump table, the order of >> the cases is totally irrelevant. > > There is another technique requiring max k jumps, where 2^k>=number of > switches (minimum of k-1 jumps). It works with no jump table, but adding > new cases is tedious. [SNIP: binary tree] In fact, there are three basic strategies: - jump table - balanced-ish binary tree - chain of if-then-elses There's nothing that says you can't combine them when compiling a single case/switch statement. For instance, you might have a couple of layers of binary tree and then switch to jump tables when you reach a densely enough filled range. Or a jump table at the start based on the high bits of the key, followed by a short chain of ifs in each non-empty entry. Or a jump table based on the high bits, leading to a jump table based on the low bits for nonempty entries. Hmm, there's a fourth strategy: - hashing. The idea would be: scramble the bits of the key in such a way that you can then take the bottom N bits and make a jump table out of them, and get few "collisions". If you're especially lucky, you may not need to do much scrambling. I suspect this approach is very seldom best, but for very large sparse switches it might be good. The typical case would go: - various bit-scrambling operations (cheap) - one indirect jump (memory reference and pipeline stall) - one comparison (against the expected key) - an almost-never-taken branch, not taken which is actually not too bad. -- g
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.