A comparative evaluation of generic programming in Java and C++

Generic programming has been defined as ‘programming with concepts’ where a concept refers to a family of abstractions. The criteria for generic programming include independence of collections from data types, independence of algorithms that operate on the collection, and the adaptability of the collections. This paper examines and evaluates the support for generic programming in the Java Development Kit (JDK) in comparison to C++'s Standard Template Library (STL). The evaluation will consider both the ‘qualitative’ factors as well as certain ‘quantitative’ factors (i.e. factors that can be measured). The qualitative factors that are considered include: 1. a comparison of the structure and APIs; 2. homogeneity versus heterogeneity; and 3. ease of use (including ease of converting to collection classes, ease of changing collection type, and ease of error handling). The quantitative factors include: 1. compiled size; 2. runtime memory usage; and 3. performance. The results of our evaluative comparisons based on the above factors and certain other criteria are presented at the end. Based on the results, we conclude that the support provided for generic programming in C++'s STL is superior to that provided by JDK. Copyright © 2003 John Wiley & Sons, Ltd.     

Programming with C++ concepts

This paper explores the definition, applications, and limitations of concepts and concept maps in C++, with a focus on library composition. We also compare and contrast concepts to adaptation mechanisms in other languages.Efficient, non-intrusive adaptation mechanisms are essential when adapting data structures to a library’s API. Development with reusable components is a widely practiced method of building software. Components vary in form, ranging from source code to non-modifiable binary libraries. The Concepts language features, slated to appear in the next version of C++, have been designed with such compositions in mind, promising an improved ability to create generic, non-intrusive, efficient, and identity-preserving adapters.We report on two cases of data structure adaptation between different libraries, and illustrate best practices and idioms. First, we adapt GUI widgets from several libraries, with differing APIs, for use with a generic layout engine. We further develop this example to describe the run-time concept idiom, extending the applicability of concepts to domains where run-time polymorphism is required. Second, we compose an image processing library and a graph algorithm library, by making use of a transparent adaptation layer, enabling the efficient application of graph algorithms to the image processing domain. We use the adaptation layer to realize a few key algorithms, and report little or no performance degradation.     

Dense and Sparse Matrix Classes Using the C++ Standard Template Library

The C++ programming language has undergone significant changes since its inception in the 1980s, but has now reached a relatively steady state. Standard C++ now includes a general library of container classes, the Standard Template Library (STL). These developments are rapidly changing the styles used in C++ class programming. The paper has dual purposes: it provides an introduction to STL for C++ programmers, and it develops an efficient matrix class library, built upon STL, which provides functionality useful in areas such as computational economics, finance, mathematical programming and statistics. This library, which is freely available, comprises a full set of vector and matrix operations using both dense and sparse implementations. The paper discusses approaches towards and pitfalls in constructing C++ concrete data types, and has references for further on-line information.     

CL_ARRAY: A new generic library of multidimensional containers for c++ compilers with extension for OpenCL framework

This paper presents a new metaprogramming library, CL_ARRAY, that offers multiplatform and generic multidimensional data containers for C++ specifically adapted for parallel programming. The CL_ARRAY containers are built around a new formalism for representing the multidimensional nature of data as well as the semantics of multidimensional pointers and contiguous data structures. We also present OCL_ARRAY_VIEW, a concept based on metaprogrammed enveloped objects that supports multidimensional transformations and multidimensional iterators designed to simplify and formalize the interfacing process between OpenCL APIs, standard template library (STL) algorithms and CL_ARRAY containers. Our results demonstrate improved performance and energy savings over the three most popular container libraries available to the developer community for use in the context of multi-linear algebraic applications.     

STXXL: standard template library for XXL data sets

We present the software library STXXL that is an implementation of the C++ standard template library (STL) for processing huge data sets that can fit only on hard disks. It supports parallel disks, overlapping between disk I/O and computation and it is the first I/O‐efficient algorithm library that supports the pipelining technique that can save more than half of the I/Os. STXXL has been applied both in academic and industrial environments for a range of problems including text processing, graph algorithms, computational geometry, Gaussian elimination, visualization, and analysis of microscopic images, differential cryptographic analysis, etc. The performance of STXXL and its applications are evaluated on synthetic and real‐world inputs. We present the design of the library, how its performance features are supported, and demonstrate how the library integrates with STL. Copyright © 2007 John Wiley & Sons, Ltd.     

MultiArray: a C++ library for generic programming with arrays

In C++, multi‐dimensional arrays are often used but the language provides limited native support for them. The language, in its Standard Library, supplies sophisticated interfaces for manipulating sequential data, but relies on its bare‐bones C heritage for arrays. The MultiArray library, a part of the Boost library collection, enhances a C++ programmer's tool set with versatile multi‐dimensional array abstractions. It includes a general array class template and native array adaptors that support idiomatic array operations and interoperate with C++ Standard Library containers and algorithms. The arrays share a common interface, expressed as a generic programming concept, in terms of which generic array algorithms can be implemented. We present the library design, introduce a generic interface for array programming, demonstrate how the arrays integrate with the C++ Standard Library, and discuss the essential aspects of their implementation. Copyright © 2004 John Wiley & Sons, Ltd.     

Smart Containers and Skeleton Programming for GPU-Based Systems

In this paper, we discuss the role, design and implementation of smart containers in the SkePU skeleton library for GPU-based systems. These containers provide an interface similar to C++ STL containers but internally perform runtime optimization of data transfers and runtime memory management for their operand data on the different memory units. We discuss how these containers can help in achieving asynchronous execution for skeleton calls while providing implicit synchronization capabilities in a data consistent manner. Furthermore, we discuss the limitations of the original, already optimizing memory management mechanism implemented in SkePU containers, and propose and implement a new mechanism that provides stronger data consistency and improves performance by reducing communication and memory allocations. With several applications, we show that our new mechanism can achieve significantly (up to 33.4 times) better performance than the initial mechanism for page-locked memory on a multi-GPU based system.     

Dynamic verification of C++ generic algorithms

Dynamic verification is a new approach to formal verification, applicable to generic algorithms such as those found in the Standard Template Library (STL, part of the Draft ANSI/ISO C++ Standard Library). Using behavioral abstraction and symbolic execution techniques, verifications are carried out at an abstract level such that the results can be used in a variety of instances of the generic algorithms without repeating the proofs. This is achieved by substituting for type parameters of generic algorithms special data types that model generic concepts by accepting symbolic inputs and deducing outputs using inference methods. By itself, this symbolic execution technique supports testing of programs with symbolic values at an abstract level. For formal verification one also needs to generate multiple program execution paths and use assertions (to handle while loops, for example), but the authors show how this can be achieved via directives to a conventional debugger program and an analysis database. The assertions must still be supplied, but they can be packaged separately and evaluated as needed by appropriate transfers of control orchestrated via the debugger. Unlike all previous verification methods, the dynamic verification method thus works without having to transform source code or process it with special interpreters. They include an example of the formal verification of an STL generic algorithm     

面向对象的并行消息传递库的设计与实现分析

MPI是并行程序设计中广泛使用的一个消息传递库,虽然标准MPI-2定义了C 绑定,但它并不严格符合面向对象的观点。在分析各类已有面向对象消息传递系统的基础上,用C 设计并实现了一个面向对象的、易于传递对象(包括用户自定义类型和STL容器)的、MPI一致的、类型安全的、基于MPI的并行消息传递库,并给出了相应的使用实例及性能分析。     

An embeddable mobile agent platform supporting runtime code mobility,interaction and coordination of mobile agents and host systems

Agent technology is emerging as an important concept for the development of distributed complex systems. A number of mobile agent systems have been developed in the last decade. However, most of them were developed to support only Java mobile agents. In order to provide distributed applications with code mobility, this article presents a library, the Mobile-C library, that allows a mobile agent platform, Mobile-C, to be embeddable in an application to support mobile C/C++ codes carried by mobile agents. Mobile-C uses a C/C++ interpreter as its Agent Execution Engine (AEE). Through the Mobile-C library, Mobile-C can be embedded into an application to support mobile C/C++ codes carried by mobile agents. Using mobile C/C++ codes, it is easy to interface a variety of low-level hardware devices and legacy systems. Through the Mobile-C library, Mobile-C can run on heterogeneous platforms with various operating systems. The Mobile-C library has a small footprint to meet the stringent memory capacity for applications in mechatronic and embedded systems. The Mobile-C library contains different categories of Application Programming Interfaces (APIs) in both binary and agent spaces to facilitate the design of mobile agent based applications. In addition, a rich set of existing APIs for the C/C++ interpreter employed as the AEE allows an application to have complete information and control over the mobile C/C++ codes residing in Mobile-C. With the synchronization mechanism provided by the Mobile-C library for both binary and agent spaces, simultaneous processes across both spaces can be coordinated to get correct runtime order and avoid unexpected race condition. The study of performance comparisons indicates that Mobile-C is about two times faster than JADE in agent migration. The application of the Mobile-C library is illustrated by dynamic runtime control of a mobile robot’s behavior using mobile agents.     

Mobile agent‐based computational steering for distributed applications

The mobile agent‐based computational steering (MACS) for distributed applications is presented in this article. In the MACS, a mobile agent platform, Mobile‐C, is embedded in a program through the Mobile‐C library to support C/C++ mobile agent code. Runtime replaceable algorithms of a program are represented as agent services in C/C++ source code and can be replaced with new ones through mobile agents. In the MACS, a mobile agent created and deployed by a user from the steering host migrates to computing hosts successively to replace algorithms of running programs that constitute a distributed application without the need of stopping the execution and recompiling the programs. The methodology of dynamic algorithm alteration in the MACS is described in detail with an example of matrix operation. The Mobile‐C library enables the integration of Mobile‐C into any C/C++ programs to carry out computational steering through mobile agents. The source code level execution of mobile agent code facilitates handling issues such as portability and secure execution of mobile agent code. In the MACS, the network load between the steering and computing hosts can be reduced, and the successive operations of a mobile agent on multiple computing hosts are not affected whether the steering host stays online or not. The employment of the middle‐level language C/C++ enables the MACS to accommodate the diversity of scientific and engineering fields to allow for runtime interaction and steering of distributed applications to match the dynamic requirements imposed by the user or the execution environment. An experiment is used to validate the feasibility of the MACS in real‐world mobile robot applications. The experiment replaces a mobile robot's behavioral algorithm with a mobile agent at runtime. Copyright © 2009 John Wiley & Sons, Ltd.     

C++ lambda expressions and closures

A style of programming that uses higher-order functions has become common in C++, following the introduction of the Standard Template Library (STL) into the standard library. In addition to their utility as arguments to STL algorithms, function parameters are useful as callbacks on GUI events, defining tasks to be executed in a thread, and so forth. C++’s mechanisms for defining functions or function objects are, however, rather verbose, and they often force the function’s definition to be placed far from its use. As a result, C++ frustrates programmers in taking full advantage of its own standard libraries. The effective use of modern C++ libraries calls for a concise mechanism for defining small one-off functions in the language, a need that can be fulfilled with lambda expressions.This paper describes a design and implementation of language support for lambda expressions in C++. C++’s compilation model, where activation records are maintained in a stack, and the lack of automatic object lifetime management make safe lambda functions and closures challenging: if a closure outlives its scope of definition, references stored in a closure dangle. Our design is careful to balance between conciseness of syntax and explicit annotations to guarantee safety. The presented design is included in the draft specification of the forthcoming major revision of the ISO C++ standard, dubbed C++0x. In rewriting typical C++ programs to take advantage of lambda functions, we observed clear benefits, such as reduced code size and improved clarity.     

函数对象及其在STL中的应用

STL是采用泛型编程思想设计的C 通用组件库。函数对象在STL中具有重要作用,它可以进一步提高算法的通用性,增强核心组件的功能。本文在简要介绍函数对象的基础上,讨论了它在STL中的应用。     

The design of the Boost interval arithmetic library

We present the design of the Boost interval arithmetic library, a C++$++$ library designed to handle mathematical intervals efficiently and in a generic way. Interval computations are an essential tool for reliable computing. Increasingly a number of mathematical proofs have relied on global optimization problems solved using branch-and-bound algorithms with interval computations; it is therefore extremely important to have a mathematically correct implementation of interval arithmetic. Various implementations exist with diverse semantics. Our design is unique in that it uses policies to specify three independent variable behaviors: rounding, checking, and comparisons. As a result, with the proper policies, our interval library is able to emulate almost any of the specialized libraries available for interval arithmetic, without any loss of performance nor sacrificing the ease of use. This library is openly available at www.boost.org.     

Implicit matrix multiplication with maximum accuracy on various transputer networks

The majority of numerical algorithms employs floating-point vector and matrix operations. On a parallel computer these algorithms should be solved fastand reliably in order to avoid a time-consuming error analysis. The XSC-languages (high-level language extensions for eXtended Scientific Computation) are well-suited for this purpose since they support the design of numerical algorithms delivering correct and automatically verified results. This goal is attained by an arithmetic with maximum accuracy (especially for vector and matrix operations), highly accurate standard functions, and exact evaluation of dot product expressions. Within theESPRIT Parallel Computing Action, one XSC-language, PASCAL-XSC, was implemented on a Supercluster Transputer System under the operating system HELIOS. Parallel algorithms for computationally intensive and maximally accurate matrix operations were implemented and tested on various transputer architectures. We will sketch some features of these architectures and present some benchmarks for the algorithms used. These algorithms form a parallel C runtime library of PASCAL-XSC (or any other XSC-language that uses a C runtime library) and are called automatically. This can be considered a basis for implicit parallelization in an XSC-language.     

Data Parallel Algorithmic Skeletons with Accelerator Support

Hardware accelerators such as GPUs or Intel Xeon Phi comprise hundreds or thousands of cores on a single chip and promise to deliver high performance. They are widely used to boost the performance of highly parallel applications. However, because of their diverging architectures programmers are facing diverging programming paradigms. Programmers also have to deal with low-level concepts of parallel programming that make it a cumbersome task. In order to assist programmers in developing parallel applications Algorithmic Skeletons have been proposed. They encapsulate well-defined, frequently recurring parallel programming patterns, thereby shielding programmers from low-level aspects of parallel programming. The main contribution of this paper is a comparison of two skeleton library implementations, one in C++ and one in Java, in terms of library design and programmability. Besides, on the basis of four benchmark applications we evaluate the performance of the presented implementations on two test systems, a GPU cluster and a Xeon Phi system. The two implementations achieve comparable performance with a slight advantage for the C++ implementation. Xeon Phi performance ranges between CPU and GPU performance.     

Secure coding in C and C++ of strings and integers

Although the flexibility and performance of C and C++ aren't in question, security has increasingly become an issue. The C and C++ communities have recognized this and have taken steps to improve security at all levels, including improved standards, compiler implementations, and static and runtime analysis tools.     

Online scheduling and placement of hardware tasks with multiple variants on dynamically reconfigurable field-programmable gate arrays

Hardware task scheduling and placement at runtime plays a crucial role in achieving better system performance by exploring dynamically reconfigurable Field-Programmable Gate Arrays (FPGAs). Although a number of online algorithms have been proposed in the literature, no strategy has been engaged in efficient usage of reconfigurable resources by orchestrating multiple hardware versions of tasks. By exploring this flexibility, on one hand, the algorithms can be potentially stronger in performance; however, on the other hand, they can suffer much more runtime overhead in selecting dynamically the best suitable variant on-the-fly based on its runtime conditions imposed by its runtime constraints. In this work, we propose a fast efficient online task scheduling and placement algorithm by incorporating multiple selectable hardware implementations for each hardware request; the selections reflect trade-offs between the required reconfigurable resources and the task runtime performance. Experimental studies conclusively reveal the superiority of the proposed algorithm in terms of not only scheduling and placement quality but also faster runtime decisions over rigid approaches.     

Synthesizing MPI Implementations from Functional Data-Parallel Programs

Distributed memory architectures such as Linux clusters have become increasingly common but remain difficult to program. We target this problem and present a novel technique to automatically generate data distribution plans, and subsequently MPI implementations in C++, from programs written in a functional core language. The main novelty of our approach is that we support distributed arrays, maps, and lists in the same framework, rather than just arrays. We formalize distributed data layouts as types, which are then used both to search (via type inference) for optimal data distribution plans and to generate the MPI implementations. We introduce the core language and explain our formalization of distributed data layouts. We describe how we search for data distribution plans using an adaptation of the Damas–Milner type inference algorithm, and how we generate MPI implementations in C++ from such plans.     

Extending STL with Efficient Data Structures

The Standard Template Library(STL)is a C library that provides a set of well structured generic C components that work together.Based on its well-structured design,STL can be extended by adding new generic algorithms or new generic containers.In this paper,the work on extending STY by adding several efficient container classes for threaded binary search trees is discussed.It is shown that the addition of threads significantly increases the efficiency of some important access operations on the binary tree containers.In general,significant gain in efficiency can be expected in situations where the data structures ar relatively stable,that is,the data structures are looked up often but modified little.