Branch Table - Compiler Generated Branch Tables

Compiler Generated Branch Tables

Programmers frequently leave the decision of whether or not to create a branch table to the compiler, believing that it is perfectly capable of making the correct choice from the known search keys. This may be true for optimizing compilers for relatively simple cases where the range of search keys is limited. However, compilers are not as intelligent as humans and cannot have a deep knowledge of 'context', believing that a range of possible search key integer values such as 1, 2, 4, 6, 7, 20, 23, 40, 42, 50 & 1000 would generate a branch table with an excessively large number of empty entries (900+) for very little advantage. (A good optimizing compiler may then presort the values and generate code for a binary chop search, as a 'second best' option.) In fact, the application may be highly "time critical" and memory requirement may not really be an issue at all .

However, a little 'common sense' can transform this particular case, and many other similar cases, to a simple two-step process with very large potential savings – while still eventually leaving the ultimate choice to the compiler – but 'assisting its decision' considerably:

• First, test for search key=1000 and perform appropriate branch.
• Allow the compiler to 'choose' to generate a branch table on the remaining search keys (1-50).

Variations along similar lines can be used in cases where there are two sets of short ranges with a large gap between ranges.