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

[Gabriel Dos Reis]

"Dan Martens" <address@hidden> writes:

| >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. 

Not necessarily.

| >                                                         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. 

Yes, it might -- that is option (3) in my previous mail.  But, GCC
does not do that. 

[...]

| >| >> > 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,

even int that case, I doubt it would. 

| 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.

   My understanding of Joris' original message is that it may also be
interesting to consider the Visitor Pattern.

| 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?

The key notion I got from his mail is:

   I am interested in the following situation: I have 150 built-in
   TeXmacs tags and a few places in the code where some action has
   to be undertaken which is different for about 10 tags and
   the same for the remaining 140 tags.

I assume those tags actually identify Texmacs entities.  No?

| Virtual function calls and switch statements are meant for 2 totally
| different purposes.  

  Not really.  An illustrative example is the Visitor Deisgn Pattern.

| 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. 

  That is a very restricted and unuseful view of what virtual functions
are about.  There are very few, limited cases where switch statements
are better alternatives to virtual functions.  Note: I'm not saying
virtual functions should be used about every thing in place of every
switch statement.  I'm saying that, basically, when you're switching on
tags, consider whether virtual functions would not offer a better
alternative.  Virtual functions are implementations of switch
statement at the compiler level.  An illustration is the visitor
design pattern.

Cheers,

-- Gaby