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.
Read more about this topic: Branch Table
Famous quotes containing the words generated, branch and/or tables:
“Here [in London, history] ... seemed the very fabric of things, as if the city were a single growth of stone and brick, uncounted strata of message and meaning, age upon age, generated over the centuries to the dictates of some now all-but-unreadable DNA of commerce and empire.”
—William Gibson (b. 1948)
“She saw a dust bearing bee sink into the sanctum of a bloom; the thousand sister calxes arch to meet the love embrace and the ecstatic shiver of the tree from root to tiniest branch creaming in every blossom and frothing with delight. So this was a marriage!”
—Zora Neale Hurston (1891–1960)
“All my life I have said, “Whatever happens there will always be tables and chairs”—and what a mistake.”
—Elizabeth Bowen (1899–1973)