Efficient multiple and predicated dispatching
Efficient multiple and predicated dispatching
复制标题
高效的多重和预测调度
DOI：
10.1145/320384.320407
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Weimin Chen
中科院分区：
文献类型：
--
作者：
C. Chambers;Weimin Chen
消息调度的速度是影响面向对象程序整体性能的一个重要问题。我们开发了一种构建高效调度函数的算法，该算法结合了高效单调度、多调度和谓词调度的新颖算法。我们的算法首先将通用谓词调度模型（概括了单调度、多调度、谓词类和分类器以及模式匹配）中编写的方法简化为使用更简单的多方法调度模型编写的方法。然后，我们的算法根据单个调度序列计算实现多个调度的策略，将该策略表示为查找 DAG。最后，我们的算法为每个单独的调度分别计算一个实现策略，为每个调度生成一个调度树，它是混合类标识测试、类范围测试和表查找的二元决策树。我们的算法利用任何可用的静态信息（来自类型声明或类分析）来从查找 DAG 中修剪不可达的路径，并使用任何可用的动态配置文件信息来最小化搜索调度树的预期时间。我们在由 Vortex 优化编译器编译的一组大型 Cecil 程序上测量了调度算法的有效性，结果显示比已经经过深度优化的基准版本提高了高达 30%。
The speed of message dispatching is an important issue in the overall performance of object-oriented programs. We have developed an algorithm for constructing efficient dispatch functions that combines novel algorithms for efficient single dispatching, multiple dispatching, and predicate dispatching. Our algorithm first reduces methods written in the general predicate dispatching model (which generalizes single dispatching, multiple dispatching, predicate classes and classifiers, and pattern-matching) into ones written using a simpler multimethod dispatching model. Our algorithm then computes a strategy for implementing multiple dispatching in terms of sequences of single dispatches, representing the strategy as a lookup DAG. Finally, our algorithm computes an implementation strategy separately for each of the single dispatches, producing for each dispatch a dispatch tree, which is a binary decision tree blending class identity tests, class range tests, and table lookups. Our algorithm exploits any available static information (from type declarations or class analysis) to prune unreachable paths from the lookup DAG, and uses any available dynamic profile information to minimize the expected time to search the dispatch trees. We measure the effectiveness of our dispatching algorithms on a collection of large Cecil programs, compiled by the Vortex optimizing compiler, showing improvements of up to 30% over already heavily optimized baseline versions.