Re: [Texmacs-dev] Efficiency of C++ switch-statements

[Dan Martens]

--------- Original Message ---------

DATE: Mon, 10 Nov 2003 22:58:15
From: Joris van der Hoeven <address@hidden>
To: <address@hidden>
Cc: 

>> Yes, it does use a table.
>>

This is somewhat misleading.  The compiler does not use a real "table" (ie, an 
array with entries), rather the binary search is implemented using compare 
instructions.  Ie.

a = 5

switch(a){
  case -1:
  case 0:
  case 5:
  case 10:
  case 11:
  default:
}

if(a > 11)
 goto default;
else if(a == 11)
 goto dosomething;
else if(a < -1)
 goto default;
else if(a == -1)
 goto dosomething;
else{
 goto five;
}

five:
if(a == 0)
  goto zero;
.
.
.
.

(Sorry about the bad pseudocode)

So, no jump table is created, just a series of "smart" compare instructions to 
mimic a binary search and narrow decisions. This means that any search is O(log 
n). Much better than cascading if statements.

I have made a very small test program:

#include <stdlib.h>

int main(){

  int test;

  test = rand();

  switch(test){
  case 1: 
  case 10: 
  case 100: 
  case 1000: 
  case 10000: 
  case 100000: 
  case 1000000: test++; break;
  case 2: 
  case 20: 
  case 200: 
  case 2000: 
  case 20000:
  case 200000: 
  case 2000000: test++; break;
  case 3: 
  case 30: 
  case 300: 
  case 3000: 
  case 30000: 
  case 300000: 
  case 3000000: test++; break;
  case 4: test++; break;
  case 40: test++; break;
  default: break;
  }
}

This is the assembly listing from g++:

        .file   "switchtest.cpp"
        .text
        .align 2
.globl main
        .type   main,@function
main:
.LFB2:
        pushl   %ebp
.LCFI0:
        movl    %esp, %ebp
.LCFI1:
        subl    $8, %esp
.LCFI2:
        andl    $-16, %esp
        movl    $0, %eax
        subl    %eax, %esp
        movl    $5000000, -4(%ebp)
        movl    -4(%ebp), %eax
        movl    %eax, -8(%ebp)
        cmpl    $1000, -8(%ebp) ------>Start comparisons
        je      .L9 ----->Jump to code if equal
        cmpl    $1000, -8(%ebp)
        jg      .L28 ------->Jump to next decision tree if greater
        cmpl    $20, -8(%ebp)
        je      .L16
        cmpl    $20, -8(%ebp)
        jg      .L29
        cmpl    $3, -8(%ebp)
        je      .L23
        cmpl    $3, -8(%ebp)
        jg      .L30
        cmpl    $1, -8(%ebp)
        je      .L9
        cmpl    $2, -8(%ebp)
        je      .L16
        jmp     .L2 --------------->The default jump
.L30: --------------------=----->Decision tree for > 3
        cmpl    $4, -8(%ebp)
        je      .L24
        cmpl    $10, -8(%ebp)
        je      .L9
        jmp     .L2
.L29: -------------------------->Decision tree if greater than 20
        cmpl    $100, -8(%ebp)
        je      .L9
        cmpl    $100, -8(%ebp)
        jg      .L31
        cmpl    $30, -8(%ebp)
        je      .L23
        cmpl    $40, -8(%ebp)
        je      .L25
        jmp     .L2
.L31:---------------------------->More decisions...continues for a while
        cmpl    $200, -8(%ebp)
        je      .L16
        cmpl    $300, -8(%ebp)
        je      .L23
        jmp     .L2
.L28:
        cmpl    $100000, -8(%ebp)
        je      .L9
        cmpl    $100000, -8(%ebp)
        jg      .L32
        cmpl    $10000, -8(%ebp)
        je      .L9
        cmpl    $10000, -8(%ebp)
        jg      .L33
        cmpl    $2000, -8(%ebp)
        je      .L16
        cmpl    $3000, -8(%ebp)
        je      .L23
        jmp     .L2
.L33:
        cmpl    $20000, -8(%ebp)
        je      .L16
        cmpl    $30000, -8(%ebp)
        je      .L23
        jmp     .L2
.L32:
        cmpl    $1000000, -8(%ebp)
        je      .L9
        cmpl    $1000000, -8(%ebp)
        jg      .L34
        cmpl    $200000, -8(%ebp)
        je      .L16
        cmpl    $300000, -8(%ebp)
        je      .L23
        jmp     .L2
.L34:
        cmpl    $2000000, -8(%ebp)
        je      .L16
        cmpl    $3000000, -8(%ebp)
        je      .L23
        jmp     .L2
.L9: ----------------------------->Code to increment variable if case if found 
from above decisions, just look for L9 jumps to see discovery
        leal    -4(%ebp), %eax
        incl    (%eax)
        jmp     .L2
.L16: ---------------------------->Same as above, only non-optimized assembly, 
optimizing would most likely elminate the redundant code below.
        leal    -4(%ebp), %eax
        incl    (%eax)
        jmp     .L2
.L23:
        leal    -4(%ebp), %eax
        incl    (%eax)
        jmp     .L2
.L24:
        leal    -4(%ebp), %eax
        incl    (%eax)
        jmp     .L2
.L25:
        leal    -4(%ebp), %eax
        incl    (%eax)
.L2:
        movl    -4(%ebp), %eax
        leave
        ret
.LFE2:
.Lfe1:
        .size   main,.Lfe1-main
        .ident  "GCC: (GNU) 3.2.2 20030222 (Red Hat Linux 3.2.2-5)"

>
>> > Another question: if I do not put the cases in the same order
>> > as the enumeration, does this alter the efficiency?

No, and the above explains why.  If an array of jump instructions were used, 
then order would matter because the entries of the array would be incremental.

>> Also consider using the STL hash_map object, which gives you O(1)
>> lookups and does not waste space when your table is sparse.
>

This is way more overhead than a switch statement.  Much more code is executed 
in the map object.  You have to remember that a switch just does assembly 
compare instructions.  No method calls are made (which are expensive), also the 
cmp instruction is fairly atomic and is not a CISC feature (on RISC also), so 
no microcode is used as is the mul and div instructions which are not atomic. 
As well, dependant upon how the hash table is implemented, the complexity may 
be more than O(1).  Things such as open hashing with chaining, or hash buckets 
would alter this time complexity dependant upon key collisions.

>This might also cause some overhead. I would like something which
>just does table lookup. If necessary, I can put 150 cases,
>but I would prefer to know how many cases are necessary and
>whether the order is really important (for g++).

As you can see above, holes in the cases make no difference.  A switch is by 
far the most efficent method to use, C++ supports over 16000+ cases so 150 is a 
drop in the bucket.  It would be interested to see how the compiler deals with 
very large numbers of cases such as this.  I do not have time to make something 
this big. :)

Hope this helps.

Dan