Time and Space Efficient Multi-Method Dispatching

Stephen Alstrup, Gerth Stølting Brodal, Inge Li Gørtz, and Theis Rauhe

Technical Report, ALCOMFT-TR-02-76, ALCOM-FT, 9 pages, May 2002.


The dispatching problem for object oriented languages is the problem of determining the most specialized method to invoke for calls at run-time. This can be a critical component of execution performance. A number of recent results, including [Muthukrishnan and Müller SODA'96, Ferragina and Muthukrishnan ESA'96, Alstrup et al. FOCS'98], have studied this problem and in particular provided various efficient data structures for the mono-method dispatching problem. A recent paper of Ferragina, Muthukrishnan and de Berg [STOC'99] addresses the multi-method dispatching problem.

Our main result is a linear space data structure for binary dispatching that supports dispatching in logarithmic time. Using the same query time as Ferragina et al., this result improves the space bound with a logarithmic factor.

Online version

alcomft-tr-02-76.pdf (152 Kb)

BIBTEX entry

  author = "Stephen Alstrup and Gerth St{\o}lting Brodal and Inge Li G{\o}rtz and Theis Rauhe",
  institution = "ALCOM-FT",
  month = "May",
  number = "ALCOMFT-TR-02-76",
  pages = "9",
  title = "Time and Space Efficient Multi-Method Dispatching",
  year = "2002"