Fast dynamic casting

We describe a scheme for implementing dynamic casts suitable for systems where the performance and predictability of performance is essential. A dynamic cast from a base class to a derived class in an object‐oriented language can be performed quickly by having the linker assign an integer type ID to each class. A simple integer arithmetic operation verifies whether the cast is legal at run time. The type ID scheme presented uses the modulo function to check that one class derives from another. A 64‐bit type ID is sufficient to handle class hierarchies of large size at least nine levels of derivation deep. We also discuss the pointer adjustments required for a C++ dynamic_cast. All examples will be drawn from the C++ language. Copyright © 2005 John Wiley & Sons, Ltd.     

Design and evaluation of C++ open multi-methods

Multiple dispatch-the selection of a function to be invoked based on the dynamic type of two or more arguments-is a solution to several classical problems in object-oriented programming. Open multi-methods generalize multiple dispatch towards open-class extensions, which improve separation of concerns and provisions for retroactive design. We present the rationale, design, implementation, performance, programming guidelines, and experiences of working with a language feature, called open multi-methods, for C++. Our open multi-methods support both repeated and virtual inheritance. Our call resolution rules generalize both virtual function dispatch and overload resolution semantics. After using all information from argument types, these rules can resolve further ambiguities by using covariant return types. Care was taken to integrate open multi-methods with existing C++ language features and rules. We describe a model implementation and compare its performance and space requirements to existing open multi-method extensions and work-around techniques for C++. Compared to these techniques, our approach is simpler to use, catches more user mistakes, and resolves more ambiguities through link-time analysis, is comparable in memory usage, and runs significantly faster. In particular, the runtime cost of calling an open multi-method is constant and less than the cost of a double dispatch (two virtual function calls). Finally, we provide a sketch of a design for open multi-methods in the presence of dynamic loading and linking of libraries.     

An experiment with the interchangeability of processes and monitors

Two styles of operating system implementation based on the use of monitors and processes, respectively, are identified, and arguments for a basic equivalence of these systems despite large stylistic differences are presented. The ‘Lauer-Needham Duality Hypothesis’ states that the two styles are equivalent, both in terms of ease of programming and in efficiency of the resulting systems. A domain for which the first part of this claim holds is outlined, and data affirming the essential equivalence of performance within that domain are presented. An operating system based on the Cambridge CAP system, called SIMOS, was simulated for a wide range of hardware configurations and job loads. SIMOS is written using a module concept that allows an individual module to be interpreted as a monitor in one run and as a process in another. Runs using a monitor to control access to some data can be compared with runs using a process to control access to the same data. The throughput and response time for the two styles of system were found to be identical in most cases. However, a degradation in response time occurred in a process-based system when the job load and the low level scheduling policy were poorly matched.     

‘Long return’: A technique for improving the efficiency of inter-module communication

This paper describes a concept called ‘long return’ for use in inter-module communication systems. First an implementation which implies a simplification of—rather than an extension of—traditional inter-module communication systems is outlined. This implementation allows long returns to be used as an optimization technique without violating the commonly accepted principles of system structuring. Thereafter an experiment that provides an estimate of the improvements in efficiency of a particular operating system is described. In the SIMOS operating systems (based on the Cambridge CAP operating system) about 20 per cent of all inter-process communication operations can be avoided by using long returns, and as a consequence the amount of useful work done in the system is typically increased by about 2.0 per cent.     

《C++程序设计原理与实践》

<正>程序设计是这样一门艺术,它将问题求解方案描述成计算机可以执行的形式。程序设计中很多工作都花费在寻找求解方案以及对其求精上。通常,只有在真正编写程序求解一个问题的过程中才会对问题本身理解透彻。     

Adding classes to the C language: An exercise in language evolution

The C language is a fine tool for writing compact and efficient programs. It is relatively easy to produce good compilers for, and the number of tools available for supporting program- ming in C is large, especially in its ‘home environment’, the UNM system. However, C'S facilities for structuring programs were, until recently, rather limited. To remedy this situation, a data abstraction facility, called classes, was added. The class concept described here has benefitted from the experience gained through a year's use. It is now in use at close to a hundred installations. The guiding principles of the design of C classes were simplicity both in concept and in implementation. Smooth blending of the new facilities into the existing C programming environment was considered essential. Classes can be used without sacrificing the run-time efficiency expected from C. This paper presents some of the reasons why C classes are what they are.     

What is object-oriented programming?

The meaning of the term `object oriented' is examined in the context of the general-purpose programming language C++. This choice is made partly to introduce C++ and partly because C++ is one of the few languages that supports data abstraction, object-oriented programming, and traditional programming techniques. The support of programming paradigms by languages is discussed and four paradigms are examined: procedural, data hiding, data abstraction, and object-oriented programming. The support of the latter two by C++ is discussed in some detail     

Untangling the balancing and searching of balanced binary search trees

A balanced binary search tree can be characterized by two orthogonal issues: its search strategy and its balancing strategy. In this paper, we show how to decouple search and balancing strategies so that they can be expressed independently of each other, communicating only by basic operations such as rotations. Different balancing strategies, such as red–black trees and splay trees, and different search applications, such as key search and rank search, can be combined arbitrarily. As a new result, we show how optimal string search can be expressed as a search application on any balanced binary tree. We implement our framework in C++, with the heavy use of templates and inlining. It keeps balancing and searching separate, while still delivering a performance that compares favorably to widely used binary tree implementations. Common services, such as correctness checks and timing measurements, do not have to be rewritten for each tree implementation. The common framework simplifies experimentation with trees and search algorithms; as a demonstration, we present some simple comparisons of red–black trees, splay trees and treaps. Copyright © 2003 John Wiley & Sons, Ltd.