检索结果-内蒙古大学图书馆

Perfect Hashing as an Almost Perfect Subtype Test

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 2008年第6期30卷 1–56页

作者： Ducournau, Roland LIRMM CNRS F-34392 Montpellier 5 France Univ Montpellier 2 Montpellier France

Subtype tests are an important issue in the implementation of object-oriented programming languages. Many techniques have been proposed, but none of them perfectly fulfills the five requirements that we have identified: constant-time, linear-space, multiple inheritance, dynamic loading and inlining. In this article, we propose a subtyping test implementation that involves a combination of usual hashtables and Cohen's display, which is a well-known technique for single inheritance hierarchies. This novel approach is based on perfect hashing, that is, an optimized and truly constant-time variant of hashing that applies to immutable hashtables. We show that the resulting technique closely meets all five requirements. Furthermore, in the framework of JAVA-like languages-characterized by single inheritance of classes and multiple subtyping of interfaces-perfect hashing also applies to method invocation when the receiver is typed by an interface. The proposed technique is compared to some alternatives, including the proposal by Palacz and Vitek [2003]. Time-efficiency is assessed at the cycle level in the framework of Driesen's pseudo-code and the linear-space criterion is validated by statistical simulation on benchmarks consisting of large-scale class hierarchies.

关键词： Experimentation Languages Measurement Performance Casting coloring downcast dynamic loading interfaces method tables multiple inheritance multiple subtyping perfect hashing single inheritance subtype test virtual function tables

来源：评论

学校读者我要写书评

暂无评论

Implementing Statically Typed Object-Oriented Programming Languages

引用

ACM COMPUTING SURVEYS 2011年第3期43卷 1–48页

作者： Ducournau, Roland LIRMM CNRS F-34392 Montpellier 5 France Univ Montpellier 2 F-34095 Montpellier 5 France

Object-oriented programming represents an original implementation issue due to its philosophy of making the program behavior depend on the dynamic type of objects. This is expressed by the late binding mechanism, aka message sending. The underlying principle is that the address of the actually called procedure is not statically determined at compile-time, but depends on the dynamic type of a distinguished parameter known as the receiver. A similar issue arises with attributes, because their position in the object layout may also depend on the object's dynamic type. Furthermore, subtyping introduces another original feature (i.e., runtime subtype checks). All three mechanisms need specific implementations and data structures. In static typing, late binding is generally implemented with so-called virtual function tables. These tables reduce method calls to pointers to functions via a small fixed number of extra indirections. It follows that object-oriented programming yields some overhead, as compared to the usual procedural languages. The different techniques and their resulting overhead depend on several parameters. First, inheritance and subtyping may be single or multiple, and even a mixing is possible, as in JAVA and. NET which present single inheritance for classes and multiple subtyping for interfaces. Multiple inheritance is a well-known complication. Second, the production of executable programs may involve various schemes, from global compilation, which implies the closed-world assumption (CWA), as the whole program is known at compile time, to separate compilation and dynamic loading, where each program unit is compiled and loaded independently of any usage, hence under the open-world assumption (OWA). Global compilation is well-known to facilitate optimization. This article reviews the various implementation techniques available in static typing and in the three cases of single inheritance, multiple inheritance, and multiple subtyping. This language-indepe

关键词： Languages Measurement Performance Binary tree dispatch casting coloring downcast dynamic loading genericity late binding linking message sending method dispatch multiple inheritance pointer adjustment single inheritance static typing type analysis separate compilation virtual function tables C plus C# Eiffel Java PRM Theta

来源：评论

学校读者我要写书评

暂无评论

Empirical Assessment of Object-Oriented Implementations with Multiple Inheritance and Static Typing 09

Empirical Assessment of Object-Oriented Implementations with...

引用

24th Annual ACM Conference on Object-Oriented Programming, Systems, Languages and Applications

作者： Ducournau, Roland Morandat, Floreal Privat, Jean Univ Montpellier 2 LIRMM F-34095 Montpellier 5 France Univ Quebec Montreal Montreal PQ Canada

ISBN: (纸本)9781605587660

Object-oriented languages involve a threefold tradeoff between runtime efficiency, expressiveness (multiple inheritance), and modularity, i.e. open-world assumption (OWA). Runtime efficiency is conditioned by both the implementation technique and compilation scheme. The former specifies the data structures that support method invocation, attribute access and subtype testing. The latter consists of the production line of an executable from the source code. Many implementation techniques have been proposed and several compilation schemes can be considered from fully global compilation under the closed-world assumption (CWA) to separate compilation with dynamic loading under the OWA, with midway solutions. This article reviews a significant subset of possible combinations and presents a systematic, empirical comparison of their respective efficiencies with all other things being equal. The testbed consists of the PRM compiler that has been designed for this purpose. The considered techniques include C++ subobjects, coloring, perfect hashing, binary tree dispatch and caching. A variety of processors were considered. Qualitatively, these first results confirm the intuitive or theoretical abstract assessments of the tested approaches. As expected, efficiency increases as CWA strengthens. From a quantitative standpoint, the results are the first to precisely compare the efficiency of techniques that are closely associated with specific languages like C++ and EIFFEL. They also confirm that perfect hashing should be considered for implementing JAVA and. NET interfaces.

关键词： Experimentation Languages Measurement Performance binary tree dispatch closed-world assumption coloring downcast dynamic loading interfaces late binding method tables multiple inheritance multiple subtyping open-world assumption perfect hashing single inheritance subtype test type analysis virtual function tables

来源：评论

学校读者我要写书评

暂无评论

Coloring, a versatile technique for implementing object-oriented languages

引用

SOFTWARE-PRACTICE & EXPERIENCE 2011年第6期41卷 627-659页

作者： Ducournau, Roland Univ Montpellier 2 LIRMM F-34000 Montpellier France CNRS F-34000 Montpellier France

Late binding and subtyping create run-time overhead for object-oriented languages. Dynamic typing and multiple inheritance create even more overhead. Static typing and single inheritance lead to two major invariants, of reference and position, that make the implementation as efficient as possible. Coloring is a technique that preserves these invariants for dynamic typing or multiple inheritance at minimal spatial cost. Coloring has been independently proposed for method invocation under the name of selector coloring, for subtype tests under the name of pack encoding, and for attribute access and object layout. This paper reviews a number of uses of coloring for optimizing object-oriented programming, generalizes them, and specifies several variations, such as bidirectional and n-directional coloring. Coloring is NP-hard, hence compilers that use it depend on heuristics. The paper describes two families of heuristics and presents some experimental results which indicate that coloring is both efficient and tractable and that bidirectional coloring gives the best results. Copyright (C) 2010 John Wiley & Sons, Ltd.

关键词： object-oriented programming multiple inheritance late binding object layout subtype testing virtual function tables

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：