"Look Ma, No Hashing, And No Arrays Neither"

Abstract

It is generally assumed that hashing is essential to many algorithms related to efficient compilation; e.g., symbol table formation and maintenance, grammar manipulation, basic block optimization, and global optimization.This paper questions this assumption, and initiates development of an efficient alternative compiler methodology without hashing or sorting.Underlying this methodology are several generic algorithmic tools, among which special importance is given to Multiset Discrimination, which partitions a multiset into blocks of duplicate elements.We show how multiset discrimination, together with other tools, can be tailored to rid compilation of hashing without loss in asymptotic performance.Because of the simplicity of these tools, our results maybe of practical as well as theoretical interest.The various applications presented culminate with a new algorithm to solve iterated strength reduction folded with useless code elimination that runs in worst case asymptotic time and auxiliary space linear in the maximum text length of the initial and optimized programs.1. Introduction.with linear search time and a hash table.They also pro-An important practical and theoretical question in Computer Science is whether there are algorithms whose worst case performance can match the expected performance of solutions that utilize hashing.In the context of this broader question, we initiate an investigation of efficient compilation without hashing and, consequently, raise some doubts about the prevailing view that hashing (e.g., universal hashing [5]) is essential to the various 2. The research of this author was partiatly