[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Texmacs-dev] Efficiency of C++ switch-statements
From: |
Dan Martens |
Subject: |
Re: [Texmacs-dev] Efficiency of C++ switch-statements |
Date: |
Mon, 10 Nov 2003 19:42:13 -0500 |
--------- 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
Re: [Texmacs-dev] Efficiency of C++ switch-statements, Dan Martens, 2003/11/11
Re: [Texmacs-dev] Efficiency of C++ switch-statements, Gabriel Dos Reis, 2003/11/11