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

[Dan Martens]

--

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

DATE: 11 Nov 2003 03:34:30 +010
From: Gabriel Dos Reis <address@hidden>
To: address@hidden
Cc: address@hidden

>Not always.  The compiler (g++ or gcc) can use a table with entries or a
>series of compares and jumps, that depends on the density of the labels.  
>See  Message-ID: <address@hidden>

Yes, this is true, but as Joris stated previously, his switch statement was 
sparse, with many "fall-throughs" to a single piece of code. This is what I 
experimented with.  I apologize if I did not cover all the different 
implementations of a switch statement (of which there are many), but I was just 
answering the question at hand.

>In your program, the low case is 1 and the highest is 3000000; you
>have 24 labels.  And they aren't dense in the range 1..3000000.  So
>according to the comment
>

See above.  We are not talking about a dense table here.  If many switch 
statemets fall through to the same piece of code, then compares will be 
implemented as only a few compares will be necessary.

>                                                         A branch table
>   is used if there are more than a few labels and the labels are  dense
>   within the range between the smallest and largest case value.
> 

See above. A combination of jump tables and compares may be used for dense 
switch statements with outliers.

>In short, your testcase does not testify that the compiler does not
>generate real branch table tables.  It just concurs on the fact that
>when the case labels are not dense then, the compiler sort the labels
>and generate compares and jumps.

As I said above, this is what Joris was testing.

>As you can see, the compiler does generate actual lookup table with entries
>that correspond to appropriate codes.

Thankyou.  A very nice example of jump tables.

>
>| >> > 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. 
>
>Not really.  See above.

If gcc were to use a hash function on a switch argument, which generated 
offsets into an array (such as a mod), then yes, order would matter, which is 
why it did in earlier compilers. However, newer compilers will sort case 
statements.  Older compilers were almost a high-level assembler however, and 
did not do smart optimizations as they do today. This comment was discussed in 
the previous email were the writer explained that it used to be this way.

>But, a virtual function call may be cheaper than the series of
>compares and jumps.  And in case the compiler would have used a branch
>table, again the virtual function call may be cheaper.  

>compared to a virtual function call, a switch is simpler onnly in a
>very limited cases.
>

I'm sorry, I do not understand the relation of virtual function calls to switch 
statements.  This is a very general statement.  If I were to compare a single 
integer to a 150 possible values and branch to various code, how would virtual 
function calls in an object heirarchy facilitate this?  Virtual function calls 
and switch statements are meant for 2 totally different purposes.  One is for 
quick code executing dependant upons individual values or ranges of variables 
of primitive types, the other is meant for object orientated programming and 
polymorphism.

Dan