On Fri, 05 Mar 1999 09:17:18 -0600, Thorsten Froehlich 
	<fro### [at] charliecnsiitedu> wrote:
>In article <MPG.1149eb79f78933399896a1@news.povray.org> , eag### [at] telekabelnl
>(Phoenix) wrote:
>
>> In general, the time it takes to read in a jump table is far greater than
>> just using the jump system that gets generated by an if-clause.
>
>That depends a lot on the density of the case conditions you have. Assume
>you write a switch statement for the tokenizer in POV-Ray: You have most of
>the ASCII characters and a high density of the numbers you compare. So the
>compiler generates a jump table. It will most likely be somewhere around 128
>entries. You need two comparisons plus branches (range checking) and one
>jump.

This depends on your compiler.  I've seen modern compilers do one of two 
things when given a switch statement like

switch (i) {
  case 1: foo(); break;
  case 2: bar(); /* fall through */
  case 4: baz(); break;
  default: quux(); break;
}

One compiler would make this look like: 

  mov  esi, ebp+i
  dec  esi
  test esi, FFFFFFFC
  jnz  default
  mov  ebx, table[esi*4]
  jmp  [ebx]
table:
  .dd  case1
  .dd  case2
  .dd  default
  .dd  case4
case1: 
  call foo
  jmp  end
case2: 
  call bar
case4: 
  call baz
  jmp  end
default: 
  call quux
end:
 ...

The other (older, less efficient compiler) would make it look like:

  mov  eax, ebp+i
  dec  eax
  jz   case1
  jl   default
  dec  eax
  jz   case2
  jl   default
  sub  eax, 2
  jz   case4
  jmp  default
case1: 
  (...same code as above...)


Both look no less efficient than what you'd expect from an if-else 
chain.  The jump table might take up space, but it's pretty quick
to execute.  Note the fancy footwork in the first case: it does the 
range checking for you in only three instructions, and only one 
subtraction.  You can always do this when the table is a power-of-two 
size.  If it makes sense to use a jump table in the first place, you 
can always pad it to the next power of two.  All of this is, of 
course, way off topic. :)

Post a reply to this message