Quote: use interval containment and type slicing for space efficient dispatch tables with multiple inheritance; 2.6x less space than the row displacement algorithm

Quotation Skeleton

In this paper we show how to extend … [interval containment for single-inheritance hierarchies] … by a small factor of .kappa. … our dispatching data structure, based on a novel … [dispatching time is] doubly logarithmic in the number of types … In practice dispatching uses one indirect branch and, … [for] dispatching multi-methods. A by-product … is an incremental algorithm for constant-time subtyping tests … [p. 142] In a collection of 35 hierarchies, totaling … second on a modern processor. … In the fast majority of the hierarchies, the … [p. 143] Its space requirement improves those of [the row displacement algorithm] (arguably the best previously published algorithm in this category), in … a factor of 2.6.   Google-1   Google-2

Copyright clearance needed for quotation.

Additional Titles

Quote: incremental algorithm for constant-time subtyping tests for multiple inheritance

Related Topics

Topic: optimization of object-oriented programs (16 items)
Topic: object-oriented data types (29 items)