\documentclass{amsart} \usepackage{amsfonts} \usepackage{multicol} \usepackage{psfig} \newcommand{\val}[2]{{\mathrm{val}( #1, #2 )}} \newcommand{\keyw}[1]{{\textbf{#1}}} \newenvironment{smallfont}{\begin{trivlist}\scriptsize}{\end{trivlist}} %\newcommand{\fourthirds}{{\left( \frac{4}{3} \right)}} \newcommand{\fourthirds}{{ (4/3) }} \begin{document} % Removed for amsart %\begin{frontmatter} \title{Lucid and Efficient Case Analysis} % Changed for amsart %\author[RPI]{\'Ulfar Erlingsson}, %\author[RPI]{Mukkai Krishnamoorthy}, %\author[CRL]{T. V. Raman} %\address[RPI]{Rensselaer Polytechnic Institute, Troy, NY 12180} %\address[CRL]{Cambridge Research Laboratory, Digital Equipment Corp., %Cambridge, MA 02139} \author[Erlingsson]{\'Ulfar Erlingsson} \author[Krishnamoorthy]{Mukkai Krishnamoorthy} \author[Raman]{T. V. Raman} \address[Erlingsson]{Rensselaer Polytechnic Institute, Troy, NY 12180} \address[Krishnamoorthy]{Rensselaer Polytechnic Institute, Troy, NY 12180} \address[Raman]{Cambridge Research Laboratory, Digital Equipment Corp., Cambridge, MA 02139} \email[Erlingsson]{ulfar@cs.rpi.edu} \email[Krishnamoorthy]{moorthy@cs.rpi.edu} \email[Raman]{raman@crl.dec.com} \begin{abstract} This paper describes a new scheme for building static search trees, using multiway radix search trees. We present this method for code generation of switch statements in imperative languages. We show that, for sparse case sets, the method produces faster code on average than existing methods, requiring $O(1)$ time with a small constant for the average search. We then apply this method to the problem of code generation for generic functions in object-oriented languages, and find that its use improves clarity as well as efficiency. \end{abstract} % Added for amsart \maketitle % Removed for amsart %\begin{keyword} % Added for amsart \textbf{Keywords} Algorithms, Compilers, Switch statements, Code generation, Code optimization, Object-oriented methods. % Removed for amsart %\end{keyword} %\end{frontmatter} \section{Introduction}\label{sec:intro} Switch statements in C, like case statements in Pascal and Ada, are useful conditional control constructs. These statements represent multiway tree control structures, whereas if statements represent binary tree control structures. In this paper we present a new code generation method for switch statements, which on the average generates faster code for sparse sets of cases than existing methods, and apply it to generic function dispatch in object-oriented languages. The method can be thought of as generating a multiway radix search tree on the case labels, and is referred to as the MRST method throughout this paper. Although the MRST method is appropriate for most searches where a static search tree can be generated, only its application to switch statements is considered here. There has been considerable work in the past (\cite{sale}, \cite{hen}, \cite{atk}, \cite{bern} and \cite{kan}) regarding the Pascal case statement and code generation. Generating code for switch statements is discussed in \cite{lcc} and \cite{gcc}. A scheme similar to MRST, but restricted to binary radix search trees, can be found in \cite{patricia}. We begin, in section \ref{sec:mrst}, by describing the MRST method of code generation for switch statements. In section \ref{sec:anal}, we compare it with four other code generation methods. We analyze the methods in terms of storage requirements and time, providing the worst case and expected case scenarios for each method. We then perform an empirical study of the MRST method with a few representative examples. Finally, in section \ref{sec:appl}, we present an implementation mechanism for generic functions in object-oriented languages which exploits the properties of our MRST method. \section{A New Code Generation Method for Switch Statements}\label{sec:mrst} We assume that all case labels, or \emph{cases}, in the switch statement are numeric. Our basic approach is to determine a critical bit sequence for the input set of cases, and hash on it. We do this recursively on non-trivial sets of cases. The resulting MRST (Multiway Radix Search Tree) is traversed at run-time with the input value to the switch statement. \begin{figure}[h] \begin{smallfont} \begin{center} \begin{tabular}{ccc} \begin{tabular}[b]{r|l} Case & Binary \\ \hline 0 & $0\, 00000\, 00_2$ \\ 1 & $0\, 00000\, 01_2$ \\ 129 & $1\, 00000\, 01_2$ \\ 131 & $1\, 00000\, 11_2$ \end{tabular} & & \psfig{figure=stree.eps} \end{tabular} \end{center} \caption{A set of cases and their MRST.} \label{fig:stree} \end{smallfont} \end{figure} In figure \ref{fig:stree} we see an example justifying our approach. The cases 0, 1, 129 and 131 are almost uniquely determined by the value of their last two bits. The exception is the pair 1 and 129, where bit 7 can determine the case. Therefore we can quickly narrow down the candidate cases for a run-time input by hashing first on the last two bits and then, if necessary, on bit 7. Finally, we compare the input value with the unique remaining candidate case. Note that we jump directly to the default handler for any run-time input ending in $10_2$, since no case ends in this bit pattern. The code generation algorithm looks at the input set of cases and finds a short sequence, or \emph{window}, of consecutive bits which distinguishes the cases into several subsets. The algorithm generates code which branches on the value of the window in the run-time input, thus selecting a specific set of candidate cases based on the input value. For empty sets, the branches lead to the default handler; for sets containing one case, to a simple comparison of the case and the input value; and for larger sets, to recursive invocations of the algorithm. It is desirable to find long windows, in order to make the search tree wide and shallow. However, we must limit the length of the windows, since the branches require hash tables which grow exponentially in the window length. We therefore use the simple greedy strategy of finding the longest \emph{critical} window which distinguishes the cases into more than a threshold number of subsets, relative to the window length. \subsection{Definitions} Let $Z$ be the set of all $K$-bit values, where $K$ is a positive integer. Let $C \subset Z$ be a set of cases, $M$ be a set of labels or markers, and $m_d$ be a default label. We assume as input a set $P = \{\, (c_i, m_i) \,\}$ of ordered pairs, such that every $c_i \in C$ is associated with a single label $m_i \in M$. We want to generate code which performs a mapping $\mathcal{F}:Z \rightarrow M \cup \{\,m_d\,\}$ such that an input value $z \in Z$ is mapped onto $m_d$ if $z \not\in C$, otherwise, if $z = c_i$ for some $c_i \in C$, onto the label $m_i \in M$ as defined by $P$. The mapping $\mathcal{F}$ thus performs the function we expect from a switch statement. We denote the bits of our $K$-bit values by $b_{K-1}, \dots, b_0$. We define a \emph{window} $W$ to be a sequence of consecutive bits $b_l, \dots, b_r$ where $K > l \geq r \geq 0$. We also define a special function \emph{val} on windows $W$ and integers $j \in Z$ such that $\val{j}{W}$ is the value of the bits of $j$ visible in the window $W$. Thus if $W = b_5, \dots, b_3$ we have that $\val{41}{W} = \val{101001_2}{W} = 101_2 = 5$. A window $W = b_l, \dots, b_r$ is \emph{critical} on a subset $S$ of $Z$ if the cardinality of the set $\{\, \val{s}{W} \,\mid\, s \in S \,\}$ is greater than $2^{l-r}$. Thus $W$ is critical if a hash table of size $2^{l-r+1}$ is more than half full when we hash on it with the set $\{\, \val{s}{W} \,\mid\, s \in S \,\}$. \subsection{The MRST Code Generation Algorithm} We now present the algorithm. The initial input is the set $P = \{\, (c_i, m_i) \,\}$ defined above, along with the default label $m_d$. The output is code which maps a run-time input value $z \in Z$ onto a label $m \in M \cup \{\, m_d \,\}$ as defined by the mapping $\mathcal{F}$ above. \begin{tabbing} \quad \= \quad\quad \= \quad \= \quad \= \quad \= \kill \keyw{Algorithm} MRST( $m_d$, $P$ ) \\ \>1.\> \keyw{If} $P$ contains only one pair $(c,m)$ \keyw{Then} \\ \> \> \> Generate a jump to $m$ if $z = c$, but a jump to $m_d$ otherwise. \\ \> \> \> \keyw{Return}. \\ \>2.\> Let $C$ be the set $\{\, c_i \,\mid\, (c_i, m_i) \in P \,\}$.\\ \> \> Find $W_\mathrm{max}$, the longest critical window $b_l,\dots, b_r$ on $C$ (see steps 2.1--2.4).\\ \> \> Let $n$ be $l-r+1$, the length of $W_\mathrm{max}$. \\ \>3.\> Generate an assignment of $\val{z}{W_\mathrm{max}}$ to a register $r1$. \\ \> \> Generate a jump to the label indexed by $r1$ in the table of step 4. \\ \>4.\> \keyw{For} $j := 0$ to $2^n-1$ \keyw{Do} \\ \> \> \> Create a new entry label $t_j$. \\ \> \> \> Create a set $P_j$ of all pairs $(c_i,m_i) \in P$ such that $\val{c_i}{W_\mathrm{max}} = j$. \\ \> \> \> \keyw{If} $P_j$ is not empty \keyw{Then} \\ \> \> \> \> Generate $t_j$ as a table entry. \\ \> \> \> \keyw{Else} \\ \> \> \> \> Generate $m_d$ as a table entry. \\ \>5.\> \keyw{For} each $P_j$ which is not empty \keyw{Do} \\ \> \> \> Generate the entry label $t_j$. \\ \> \> \> \keyw{Call} MRST( $m_d$, $P_j$ ). \end{tabbing} Step 2 of the algorithm can be performed with the following simple procedure. The effect of the procedure is to scan repeatedly over the bits with windows of increasing length, choosing the longest and most critical window as $W_\mathrm{max}$. The fact that the prefix of any critical window is also critical allows us to accomplish this in a single scan. Since any two distinct numbers will differ in at least one bit, we will always find a window $W$ of length at least one. \begin{tabbing} \quad \= \quad\quad \= \quad \= \quad \= \quad \= \kill \>2.1.\> Let $C$ be the set $\{\, c_i \,\mid\, (c_i, m_i) \in P\,\}$.\\ \> \> Let $W$ and $W_\mathrm{max}$ be windows, initially empty. \\ \> \> Let $\#W$, $\#W_\mathrm{max}$, $k$ and $n$ be integers, initially zero. \\ \>2.2.\> \keyw{For} $b :=$ bit $b_{K-1}$ to bit $b_0$, one at a time \keyw{Do} \\ \> \> \> Add $b$ to $W$, extending $W$ one bit to the right. \\ \>2.3.\> \> Let $k$ be the length of $W$. \\ \> \> \> Let $\#W$ be the cardinality of $\{\, \val{c_i}{W} \,\mid\, c_i \in C \,\}$. \\ \> \> \> \keyw{If} $W$ is critical on $C$ \keyw{Then} \\ \> \> \> \>\keyw{If} $k > n$ or $\#W > \#W_\mathrm{max}$ \keyw{Then}\\ \> \> \>\>\> Let $W_\mathrm{max}$ become $W$, $\#W_\mathrm{max}$ become $\#W$ and $n$ become $k$.\\ \>2.4.\> \>\keyw{Else} (if $W$ is non-critical on $C$) \\ \> \> \> \> Remove the leftmost bit from $W$. \\ \> \> \> \> Perform step 2.3 once. \end{tabbing} \subsection{Potential Optimizations} Implementations of the algorithm could adopt various strategies for optimizing running time or storage space. Simple optimizations, such as replacing a hash table of size two with a bit test, will provide some speedup. However, the major factor affecting performance is the choice of windows to hash on. By changing the definition of a critical window, so the threshold ratio is not $1/2$ but an arbitrary fraction in $(0,1]$, storage space and running time can be adjusted according to implementation priorities. The search tree can also be made shallower by removing the constraint that windows need to be sequences of consecutive bits, and generating additional code which compacts sparse windows. Using that method, we could generate code for the cases in figure \ref{fig:stree} which branched directly through a hash table of size 8. Several other optimization schemes are feasible. For instance constructing the MRST using a radix other than 2 may provide speedup for some case sets. \subsection{Sample Code Generation} We now show an example of code generated by the MRST algorithm. Below is a small switch statement written in a Pascal-like language. In figure \ref{fig:ltree} we can see the search tree generated by our algorithm for this switch statement. \begin{smallfont} \begin{tabbing} \quad \= \quad \= \kill \> \keyw{Case} $z$ \keyw{Of} \\ \> \> 8, 16, 33, 37, 41, 60: \= Function1; \\ \> \> 144, 264, 291: \> Function2; \\ \> \> 1032: \> Function3; \\ \> \> 2048, 2082: \> Function4; \\ \> \> \keyw{Otherwise} \> Default; \\ \> \keyw{End}; \end{tabbing} \end{smallfont} \begin{figure}[h] \centerline{\psfig{figure=tree.eps}} \caption{A MRST for the switch statement.} \label{fig:ltree} \end{figure} Assembly code generated for the switch statement by our MRST algorithm is shown in figure \ref{fig:code}. The input value is assumed to be in a register $z$ and we use a register $r1$ to index into the hash tables. \begin{figure}[h] \begin{smallfont} \begin{multicols}{4}[][26ex] \begin{tabbing} start: \\ \quad \= \keyw{mov}\ \= $r1$, $z$ \\ \>\keyw{and}\> $r1$, 0038h \\ \>\keyw{shr}\> $r1$, 3 \\ \>\keyw{jmp}\> [table1+$r1$] \\ table1: \>\>\keyw{data}\ case\_000 \\ \>\>\keyw{data}\ case\_001 \\ \>\>\keyw{data}\ case\_010 \\ \>\>\keyw{data}\ Default \\ \>\>\keyw{data}\ case\_100 \\ \>\>\keyw{data}\ case\_101 \\ \>\>\keyw{data}\ Default \\ \>\>\keyw{data}\ case\_111 \\ case\_000: \\ \>\keyw{cmp}\> $z$, 2048 \\ \>\keyw{jeq}\> Function4 \\ \>\keyw{jmp}\> Default \\ case\_001: \\ \>\keyw{mov}\> $r1$, $z$ \\ \>\keyw{and}\> $r1$, 0400h \\ \>\keyw{shr}\> $r1$, 10 \\ \>\keyw{jmp}\> [table2+$r1$] \\ table2: \>\>\keyw{data}\ case\_001\_0 \\ \>\>\keyw{data}\ case\_001\_1 \\ case\_001\_0: \\ \>\keyw{mov}\> $r1$, $z$ \\ \>\keyw{and}\> $r1$, 0100h \\ \>\keyw{shr}\> $r1$, 8 \\ \>\keyw{jmp}\> [table3+$r1$] \\ table3: \>\>\keyw{data}\ case\_001\_0\_0 \\ \>\>\keyw{data}\ case\_001\_1\_1 \\ case\_001\_0\_0: \\ \>\keyw{cmp}\> $z$, 8 \\ \>\keyw{jeq}\> Function1 \\ \>\keyw{jmp}\> Default \\ case\_001\_0\_1: \\ \>\keyw{cmp}\> $z$, 264 \\ \>\keyw{jeq}\> Function2 \\ \>\keyw{jmp}\> Default \\ case\_001\_1: \\ \>\keyw{cmp}\> $z$, 1032 \\ \>\keyw{jeq}\> Function3 \\ \>\keyw{jmp}\> Default \\ case\_010: \\ \>\keyw{mov}\> $r1$, $z$ \\ \>\keyw{and}\> $r1$, 0080h \\ \>\keyw{shr}\> $r1$, 7 \\ \>\keyw{jmp}\> [table4+$r1$] \\ table4: \>\>\keyw{data}\ case\_010\_0 \\ \>\>\keyw{data}\ case\_010\_1 \\ case\_010\_0: \\ \>\keyw{cmp}\> $z$, 16 \\ \>\keyw{jeq}\> Function1 \\ \>\keyw{jmp}\> Default \\ case\_010\_1: \\ \>\keyw{cmp}\> $z$, 144 \\ \>\keyw{jeq}\> Function2 \\ \>\keyw{jmp}\> Default \\ case\_100: \\ \>\keyw{mov}\> $r1$, $z$ \\ \>\keyw{and}\> $r1$, 0006h \\ \>\keyw{shr}\> $r1$, 1 \\ \>\keyw{jmp}\> [table5+$r1$] \\ table5: \>\>\keyw{data}\ case\_100\_00 \\ \>\>\keyw{data}\ case\_100\_01 \\ \>\>\keyw{data}\ case\_100\_10 \\ \>\>\keyw{data}\ Default \\ case\_100\_00: \\ \>\keyw{cmp}\> $z$, 33 \\ \>\keyw{jeq}\> Function1 \\ \>\keyw{jmp}\> Default \\ case\_100\_01: \\ \>\keyw{mov}\> $r1$, $z$ \\ \>\keyw{and}\> $r1$, 0800h \\ \>\keyw{shr}\> $r1$, 11 \\ \>\keyw{jmp}\> [table6+$r1$] \\ table6: \>\>\keyw{data}\ case\_100\_01\_0 \\ \>\>\keyw{data}\ case\_100\_01\_1 \\ case\_100\_01\_0: \\ \>\keyw{cmp}\> $z$, 291 \\ \>\keyw{jeq}\> Function2 \\ \>\keyw{jmp}\> Default \\ case\_100\_01\_1: \\ \>\keyw{cmp}\> $z$, 2082 \\ \>\keyw{jeq}\> Function4 \\ \>\keyw{jmp}\> Default \\ case\_100\_10: \\ \>\keyw{cmp}\> $z$, 37 \\ \>\keyw{jeq}\> Function1 \\ \>\keyw{jmp}\> Default \\ case\_101: \\ \>\keyw{cmp}\> $z$, 41 \\ \>\keyw{jeq}\> Function1 \\ \>\keyw{jmp}\> Default \\ case\_111: \\ \>\keyw{cmp}\> $z$, 60 \\ \>\keyw{jeq}\> Function1 \\ \>\keyw{jmp}\> Default \end{tabbing} \end{multicols} \caption{Assembly code generated by the MRST algorithm.} \label{fig:code} \end{smallfont} \end{figure} \section{Analysis of Methods}\label{sec:anal} There are several different methods of generating code for switch statements, apart from our MRST. Some common ones are: \begin{enumerate} \item Skewed Binary Tree (see \cite{dragon} and \cite{sale}) \item Balanced Binary Tree (see \cite{sale} and \cite{gcc}) \item Balanced Binary Tree to Hash Tables (see \cite{bern}, \cite{kan}, \cite{hen} and \cite{lcc}) \item Jump Table Method (see \cite{dragon} and \cite{sale}) \end{enumerate} We now compare the time complexity of the above methods with that of our MRST method. We assume that we are running a switch statement that has $m$ cases, and that the statement is called $n$ times with inputs from the set of cases. We show both worst case and expected case running times. \begin{description} \item[Skewed Binary Tree] This is essentially a linear search. Therefore it takes $O(m n)$ time in all cases. \item[Balanced Binary Tree] We compare the run-time input with one case at a time in such a way that the search tree is balanced. Hence the running time is $O(n \log m)$ in all cases. \item[Balanced Binary Tree to Hash Tables] We do a balanced binary search to ranges where the case set is dense, and then hash directly on those ranges. Let the number of leaf nodes with hash tables be $r$. The worst case running time occurs when $r = m$ and is $O(n \log m)$, since $\log m$ is the search time for the tree. The expected case running time is $O(n \log r)$. \item[Jump Table Method] This is a direct hash table lookup, giving us a running time of $O(n)$ in all cases. However, the method requires space linear in the \emph{range} of input cases, and is therefore impractical for sparse sets of input cases. Even so, this is usually the optimal method for dense case sets. \item[MRST Method] Here the analysis is slightly different, as the tree is no longer balanced or binary. In the worst case, the MRST is skewed with a maximum depth $K/2$, where $K$ is the word size of the machine. Hence the worst case running time is $O(n K)$. However, in the expected case, the search time for an entry is $\log_h (K)$, where $h$ is the expected size of the hash tables. Empirically, we can expect $h$ to be on the order of $K$, as is shown in the next subsection. Therefore the expected case running time is $O(n)$. \end{description} In the first three methods, the internal nodes in the search tree are comparison instructions, while in our MRST method they are hash table lookups. Even though this is likely to increase the size and storage space requirements of the generated code, it is also likely to improve its running time. The results become even more favorable if we do not restrict the run-time input to the set of cases, since early branches to the default handler then improve running time. This justifies our MRST approach. \subsection{Empirical Analysis} We now examine the empirical performance of the MRST method on several representative input case sets. We consider both switch statements with $m$ distinct cases and switch statements with $r$ dense ranges, where a range can contain anywhere from 1 to 20 cases. In figures \ref{fig:anal}a and \ref{fig:anal}b we show the average number of branches and storage space for different values of $m$ and $r$ respectively. Storage space is the number of hash table entries required. All values shown are averages from 100 runs on randomly generated sets of input cases, taken from the full range of $32$-bit numbers. Our empirical results have very little deviation from the averages shown. \begin{figure}[h] \begin{smallfont} \begin{center} \begin{tabular}{ccccc} \begin{tabular}{r|r|r} \multicolumn{1}{c|}% {$m$} & Branches & \multicolumn{1}{c}{Space} \\ \hline 10 & 2.13 & 17.1 \\ 20 & 2.23 & 35.8 \\ 100 & 2.45 & 175.9 \\ 200 & 2.48 & 359.0 \end{tabular} & \hspace*{-1em} & \begin{tabular}{r|r|r} \multicolumn{1}{c|}% {$r$} & Branches & \multicolumn{1}{c}{Space} \\ \hline 10 & 2.59 & 183.9 \\ 20 & 2.57 & 363.3 \\ 100 & 2.64 & 1769.0 \\ 200 & 2.64 & 3548.9 \end{tabular} & \hspace*{-1em} & \begin{tabular}{r|r|r|r} Ex.\ & Cases & Branches & Space \\ \hline 1 & 6 & 2.57 & 12 \\ 2 & 128 & 2.00 & 128 \\ 3 & 15 & 5.50 & 30 \\ 4 & 2 & 2.00 & 2 \end{tabular} \\ (a) & \hspace*{-1em} & (b) & \hspace*{-1em} & (c) \end{tabular} \end{center} \caption{Performance of the MRST method on several input case sets} \label{fig:anal} \end{smallfont} \end{figure} We also consider four other examples, the results of which are shown in figure \ref{fig:anal}c. The first example converts numbers into Roman numerals. The second arises in the simulation of a finite-state automaton with transition labels in the ASCII character set. The third uses cases that are the distinct powers of two from $2^1$ to $2^{15}$, and thus has the worst case expected running time for our method. The fourth and final example has only two cases, $2^{14}$ and $-2^{14}$. Obviously, we need to branch at least once in any implementation of a switch statement. We can attain this minimum by using the jump table method, but this is unfeasible for sparse sets of cases. Our MRST method, on the average, requires only two to three branches, using storage space linear in the number of input cases. \section{A Weak Worst-Case Upper Bound on MRST Storage Space} We proceed by induction on the height of the generated MRST. We assume the threshold ratio is a fraction $d \in (0,1]$, with $D = d^{-1}$. We show that the storage space required for $m$ distinct cases in an MRST of height $h$ is less than $\fourthirds^{h-1} Dm$. From the MRST algorithm this is trivially true for an MRST of height one, i.e., with only one hash table, we have $dS_m < m$ and thus $S_m < Dm$. We now assume our hypothesis holds for MRSTs of heights 1 to $h-1$ and show it holds for MRSTs of height $h$. We also assume we have a window which distinguishes $m$ input cases into $s$ subsets, with $a$ subsets of cardinality one or two and $b = s-a$ of greater cardinality. There is no extra storage space required for the $a$ small subsets. For each of the larger subsets, however, the space required is less than $\fourthirds^{h-2}D$ times the cardinality, and therefore in total $\fourthirds^{h-2}D(m-a)$ for the $b$ subsets. The space required for the root level hash table is less than $D(a+b)$. Therefore the total space is bounded above by $\fourthirds^{h-2}D(m-a+a+b)$, which we can simplify to $\fourthirds^{h-1} Dm$. \section{A Practical Application Of Switch Optimization}\label{sec:appl} The previous sections outlined and analyzed our MRST techniques for optimizing sparse switch statements in imperative programming languages. We will now look at how we can implement generic function dispatch for object-oriented languages efficiently using switch statements and our MRST method. Performing by hand the case analysis required for a switch statement based implementation of generic function dispatch is inflexible and error-prone. However, switch statements automatically generated for this purpose are likely to be very sparse. By combining the abstraction mechanisms of object-oriented programming with our MRST method we get an implementation with the desirable qualities of being lucid and clear, while generating near-optimal compiled code. \subsection{Object-oriented Generic Functions} Let $L$ denote an object-oriented language with single-inheritance. Consider implementing function $A$, a function of one argument that takes a geometric shape $S$ (e.g., square, triangle or circle) and computes its area. Using conventional case analysis techniques, function $A$ would be implemented as a long if statement, with one conditional clause for each geometric shape that is handled by function $A$. The disadvantages of the above are immediately obvious. Extending $A$ to handle new shapes is hard, since it needs to be modified each time and will quickly become unwieldy. Also, as the number of clauses in $A$ increases, the function becomes inefficient. Given a shape $S$, the implementation simply performs a linear scan of the clauses making up $A$. The first of the above disadvantages is, in fact, often used to justify object-oriented programming. Here, $A$ can be implemented as a \emph{generic function}\footnote{We use the Common Lisp Object System terminology.}. Extending the implementation of $A$ to handle new shapes only requires the definition of new \emph{methods} on $A$. Each clause of the non-object-oriented implementation thus becomes a single method, making the semantics of $A$ clear. \subsection{General Case Generic Dispatch} Overloading of functions and generic dispatch based on argument types are two of the most powerful features of any object-oriented language. We now show how we can implement these features efficiently using switch statements and the MRST method. Consider a generic function $F$ of $n$ arguments in language $L$, with $m$ methods defined on it. Further, assume that there are $T$ distinct types in the type-pool of $L$, each with a unique $K$-bit identifier. The execution of the generic function $F$ is, in fact, a switch statement which, for a given input case from the $T^n$ possible cases, checks whether one of the $m$ methods applies. We can automatically generate efficient code for this switch statement using the following approach. Assume that method $i$ on $F$ requires its $j$th argument to be of type $t_{ij}$. Method $i$ is thus executed with run-time arguments $a_1, \dots, a_n$ if the condition $(\mathrm{type}(a_1)=t_{i1}) \land \dots \land (\mathrm{type}(a_n)=t_{in})$ is true. This condition is represented by one $nK$-bit case in the switch statement, formed by concatenating the $K$-bit type identifiers of $t_{i1}, \dots, t_{in}$. At compile-time, we generate executable code by running the MRST algorithm on resulting set of $m$ case/method pairs. At run-time, we concatenate the run-time argument type identifiers into an $nK$-bit case, and use this case as the input to the switch statement. It should be pointed out that, in any practical application where such case analysis is performed, the resulting set of cases is very sparse, i.e., $m$ is extremely small relative to $2^{nK}$. Since the MRST method is the only method likely to generate an efficient search for such sparse case sets, it is very attractive for this application. \subsection{Using Interpreted Languages} Finally, we would like to point out that these techniques apply equally well in the realm of interpreted scripting languages. If the language preprocesses the script into an intermediary representation, a static scheme such as the MRST method can be used. If not, the following approach may be applicable. TCL is an interpreted scripting language where the primary datatype is the string. A TCL procedure that contains an $n$-way switch statement can become inefficient as $n$ gets large. However, we can provide an efficient and lucid implementation of generic functions in TCL. We first define a table, implemented as a TCL associative array. We index the table by the result of the various tests equivalent to the cases of the switch statement. The entry in the table is the name of a TCL procedure that executes the corresponding branch of the switch statement. Since associative arrays in TCL are implemented as hash tables, the resulting encoding will exhibit efficiency comparable to that of the MRST method. \section{Conclusion}\label{sec:concl} We have presented the MRST method, a new method of generating static search trees on numeric case sets. We have demonstrated the method in the context of generating code for switch statements in imperative languages. There has been considerable previous work on this code generation. We have found that, for sparse case sets, our MRST method generates code which is empirically faster than previous methods. For most non-contrived case sets, the expected number of branches is less than three. Finally, we have applied the MRST method to generic dispatch in object-oriented languages, and found that its use makes the required case analysis lucid as well as efficient. \section{Acknowledgments}\label{sec:ack} The MRST method originated in work done at the University of Iceland. Snorri Agnarsson and Andrew Shapira contributed significantly to the development of the method. The authors would like to thank Ed Green, Snorri Gylfason, Andrew Shapira, David L. Spooner and Kendra Willson for their help in revising this paper. \begin{thebibliography}{9} \bibitem{dragon} A. Aho, R. Sethi, and J. Ullman, \emph{Compilers, Principles, Techniques, and Tools}. Addison-Wesley, Reading, Mass., 1986. \bibitem{atk} L. Atkinson, ``Optimizing Two-state Case Statements in Pascal,'' \emph{Software---Practice and Experience}, Vol.\ 12, 1982, pp.\ 571--581. \bibitem{bern} R. Bernstein, ``Producing Good Code for the Case Statement,'' \emph{Software---Practice and Experience}, Vol.\ 15, 1985, pp.\ 1021--1024. \bibitem{lcc} C. Fraser and D. Hanson, \emph{A Retargetable C Compiler: Design and Implementation}, The Benjamin/Cummings Publishing Company Inc., Redwood City, CA, 1994. \bibitem{hen} J. Hennessy and N. Mendelsohn, ``Compilation of the Pascal Case Statement,'' \emph{Software---Practice and Experience}, Vol.\ 12, 1982, pp.\ 879--882. \bibitem{kan} S. Kannan and T. Proebsting, ``Correction to Producing Good Code for the Case Statement,'' \emph{Software---Practice and Experience}, Vol.\ 24, 1994, pp.\ 233. \bibitem{patricia} D. R. Morrison, ``PATRICIA---Practical Algorithm To Retrieve Information Coded In Alphanumeric,'' \emph{Journal of the Association for Computing Machinery}, Vol.\ 15, 1968, pp.\ 514--534. \bibitem{sale} A. Sale, ``The Implementation of Case Statements in Pascal,'' \emph{Software---Practice and Experience}, Vol.\ 11, 1981, pp.\ 929--942. \bibitem{gcc} R. M. Stallman, ``Using and Porting GNU CC,'' Technical Report, Free Software Foundation, Cambridge, MA, 1992. \end{thebibliography} \end{document}