Re: Optimization of "switch" stmt in C

mayur_naik@my-deja.com wrote:


> GNU CC generates a switch table, a binary search, or a linear
> search for a switch stmt. I want to understand the exact algorithm.
> Any help is greatly appreciated.
>


GNU CC has a simple heuristic which is mainly (there are many hints too)
the following


      if number of cases < 5 (or 4 if machine has special insn to jump
through dispatch table, including bounds checking)
                                or range of case values > 10 * number of cases, then
            the binary search is used which becomes a linear search if there
are few cases.


      otherwise
              the jump table is used.


When gcc uses binary search, it believes that all cases have equal
probability. The algorithm could be improved if we use profile
information.


Another drawback of Gcc switch generation is that gcc uses binary search
if we have several dense regions of case values but the range of case
values is large, e.g.


                      case 1:
                      case 2:
                      ....
                      case 100001:
                      case 100002:


Some combination binary search and jump table would be helpful to
improve the code.


Actually, there are some works in improving GNU CC switch generation.

Return to the comp.compilers page.
Search the comp.compilers archives again.