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

[Gabriel Dos Reis]

Joris van der Hoeven <address@hidden> writes:

| Hi *,
| 
| Can anyone provide me with some information on how well
| the C++ switch-statement is being optimized?
| 
| 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. So I use a switch with
| a "default:". My question is: does C++ use table lookup for
| immediately jumping to the right location (the tables would
| clearly be quite sparse)?

Hi,

As is generally the case and I'm sure you know, the C++ language does not
mandate any particular form of implementation of switches (nor does it
for any particular feature). 

   Switch implementation varies from one compiler to another.  So any
statement about the internal implementation of switch may be valid for
one compiler and fails for another.  However, it seems that good
optimizing compilers tend to use
  (1) a table lookup when the switch-cases are large and dense; 
  (2) if-else branches when the switch-cases are small;
  (3) a mixture of (1) and (2) for "interesting" cases.


  As far as GCC/g++ is conerned, g++ shares the same middle-end and
back-end as the C front-rend (and Fortran and other supported
languages). Here is what the GCC source says (gcc/stmt.c):

   Switch statements can be output in one of two forms.  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.  If a
   branch table is used, no further manipulations are done with the case
   node chain.

   The alternative to the use of a branch table is to generate a series
   of compare and jump insns.  When that is done, we use the LEFT, RIGHT,
   and PARENT fields to hold a binary tree.  Initially the tree is
   totally unbalanced, with everything on the right.  We balance the tree
   with nodes on the left having lower case values than the parent
   and nodes on the right having higher values.  We then output the tree
   in order.  */


This is to be taken with a grain of salt.  This may change in the
future as the compiler is improving and more optimizations are being
implemented (e.g. tree-ssa branch).  Other compiler may implement a
better strategy.

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

  Not, as far as GCC is concerned, see the comment above.  And what
appears inefficient today may be very efficient tomorrow given that the
compiler is rapidly improving.  My rule of thumb in this are is:
design the algroithm, code, measure, optimize. Most of the time, I
consider large switches as last resorts (my experience is that large
switches poses inordinate amount of maintainance problems, but surely
GCC is different from Texmacs ;-)

-- Gaby