Document number: N4037

Date: 2014-02-14

Non-Transactional Implementation of Atomic Tree Move

by Paul E. McKenney

1 Introduction

Concurrent search trees are well understood [9, 2], as are concurrent search trees that use lightweight read-side synchronizations mechanisms [10, 11, 17, 16, 7, 1, 8] such as read-copy update (RCU) [14, 12].

However, non-transactional-memory-based algorithms that atomically move an element from one search tree to another, while avoiding delaying lockless readers, are lacking. Such algorithms are known for hash tables [18, 19]. A challenge to find such an algorithm for trees was put forward at the 2014 C++ Standards Committee meeting at Issaquah, WA USA, and this document describes one solution. As such, it is a work in progress: Future work will implement multiple solutions and compare their performance and scalability. ...

6 Summary

This paper has demonstrated a prototype solution to the Issaquah challenge of atomically moving data between two search trees without unnecessary contention.

Future work includes efficiently balancing the trees, evaluating other non-TM implementations, and comparing against TM implementations.

Document number: N4021

Date: 2014-05-21

A Proposal to Add 2D Graphics Rendering and Display to C++, Revision 1

by Michael B. McLaughlin, Herb Sutter and Jason Zink

The goal of this proposal is to define a 2D drawing API for the C++ programming language. This proposal is a revision of N3888, which was presented at the meeting of SG13 at the Issaquah meeting in February 2014. This proposal aims to provide a clean, modern C++ API that builds on the N3888 API and incorporates the feedback on it. [Note: The N3888 API was a mechanical transformation of the cairo graphics library. Cairo is a comprehensive, cross-platform, widely-used, mature 2D graphics library written in C with an object-oriented style. -- end note]

Document number: N4013

Date: 2014-05-26

Atomic operations on non-atomic data

by Hans-J. Boehm

Here we address the question of whether there should be some mechanism for applying atomic operations to non-atomic data. As pointed out in the next section, we address a somewhat different set of problems from prior discussion of non-atomic operations on atomic data (c.f. the last part of  N3710 or the Issaquah discussion.

Document number: N3993

Date: 2014-05-23

On Parallel Invocations of Functions in Parallelism TS

by Artur Laksberg

Abstract

This document proposes a change to N3989 (Technical Specification for C++ Extensions for Parallelism).

Introduction

At the Issaquah meeting in February 2014, Hans Boehm raised the following issue regarding N3850 (Working Draft, Technical Specification for C++ Extensions for Parallelism):

It seems to me that the execution policies need to be a bit more precise about which calls to parameter functions they can make. Something needs to specify that sort may make parallel invocations to swap, but only if the arguments for concurrent calls don’t overlap. I didn’t quickly find such text. In general, “non-racing” calls can be made concurrently, but “racing” ones cannot.

Upon further discussion, it was decided that the resolution of this issue warrants a separate paper that can be presented for discussion in SG1 during the Rapperswil meeting.

Proposed Resolution

First, we introduce changes to 17.6.5.9 [res.on.data.races]/8 that state that an implementation cannot introduce a data race on objects accessed during the execution of the algorithms.

Additionally, instead of talking about “applying user-defined function objects”, we define an umbrella term “element access functions”, which includes the functions required by the specification, as well as the user-provided function objects. We then define the behavior in terms of “invoking the element access functions”.

Document number: N4028

Date: 2014-05-23

Defining a Portable C++ ABI

by Herb Sutter

Goals, Non-Goals and Constraints

The primary goal is to:

• Enable writing portable C++ code that will be compiled to an object file that can successfully:
  
  link with object files created by other conforming C++ compilers, or different versions of the same compiler, on the same platform; and 
  
  be called using FFIs from other language compilers/runtimes on the same platform, such as Java JNI and .NET PInvoke, if those FFI implementations support the (single) C++ ABI for that platform.

Here a target platform has the same meaning as de facto in C, namely the combination of:

• Operating system: Such as Windows, OS X, Android, iOS, etc. The OS determines things like the binary format (such as PE, COFF, and ELF), the meaning of pointers (such as the legality of stealing low bits and the rules for high bits above bit 48), and more.
• Processor family: Such as x86 or ARM. This affects the instruction set targeted by code generation, alignment, endian-ness, and more.
• Bitness: Such as 32-bit or 64-bit. This affects the size and interpretation of pointers and references, size_t, and ptrdiff_t, and more.

This largely maps to “object files that could reasonably be expected to be part of a single executing program,” since a given single running program will be running on a given OS and processor at a time.

Examples and corollaries:

• It should be possible to ship a single (not “fat”) compiled binary library for Windows x86 32-bit whose interface uses C++ features such as classes, virtual functions, and overloading, and have that be usable with code compiled by other compilers for Windows x86 32-bit.
• It should be possible for an operating system API to expose a well abstracted modern C++ API that uses features like classes, virtual functions, and overloading, and also meets normal OS API requirements for ABI stability.

Notable non-goals and constraints:

• We need not, and should not, try to guarantee some “universal C++ ABI” whereby a single ob-ject file could link with other object files on different platforms, such as 32-bit ARM Linux and 64-bit x86 Windows. That would defeat the original purpose of C and C++ to be a portable lan-guage that can generate executable code that is competitive with handcrafted platform-specific code on a given platform.
• We must not change or restrict anything that is expressible today in platform-specific ways. Any new capabilities must be purely additive. All of the various incompatible compiler option flavors and standard library implementation flavors that are allowed today must still be preserved, both for compatibility and because most of them exist for good reasons (sometimes you do want packing, sometimes you do want a non-default calling convention, etc.).
• We should accommodate that some vendors, such as Microsoft, feel they must be able to break the standard library ABI on every major release (see next section).
• We should accommodate that some vendors, such as GCC, feel they must not break the standard library ABI (see next section).

Document number: N4048

Date: 2014-05-26

More Improvements to std::future -- Revision 1

by Vicente J. Botet Escribá

This paper complements "N3784 Improvements to std::future<T> and Related APIs" [4] with more future observers and factories. It is a revision of N3865 [3] making coherent the expected proposal [6] and this one.

Document number: N3974

Date: 2014-05-28

Polymorphic Deleter for Unique Pointers

by Marco Arena, Davide di Gennaro and Peter Sommerlad

... However, with heap-allocated polymorphic types in C++11 code this means one needs to use shared_ptr<Base> and make_shared<Derived> to avoid the need to define a virtual destructor for Base. There is no standard deleter for unique_ptr that will allow to safely use unique_ptr<Base> if Base doesn't define a virtual destructor. Such a misuse is not even detectable easily. However, always using shared_ptr to get its desired deleter magic would also incur the overhead of the atomic reference counter and the overhead of full type erasure.

This proposal tries to ease the burden for programmers of heap allocated polymorphic classes and gives them the option to use unique_ptr with a standard provided deleter classes that either check correct provisioning of a virtual destructor in the base class or provide a slight overhead infrastructure for safe deletes through base type pointers, even if the base class doesn't define a virtual destructor.

Document number: N4029

Date: 2014-05-23

Let return Be Direct and explicit

by Herb Sutter

This paper proposes also permitting explicit conversions from the return's expression to the return type, and generally viewing return-by-value as direct initialization of the returned value.

Document number: N3991

Date: 2014-05-23

Task Region r2

by Pablo Halpern, Arch Robison, Hong Hong, Artur Laksberg, Gor Nishanov, Herb Sutter

1 Abstract

This paper introduces C++ a library function template task_region and a library class task_region_handle with member functions run and wait that together enable developers to write expressive and portable fork-join
parallel code.

This proposal is a revision of N3832.

2 Changes from N3832

The main change from the previous revision of this paper is the addition of the task_region_handle class as an explicit means of communicating from a task_region to the spawn point of a child task. A change in this vein was requested at the February 2014 Issaquah meeting as a way to avoid “magic” or “out-of-band communication.” It was also suggested that requiring an explicit handshake between these parts of a task region would make it easier for compilers and linkers to avoid combining disparate implementations of the library proposed herein.

An additional change is that the type of parallelism described in N3832 was “terminally strict” whereas the type of parallelism described in this paper is “fully strict” (see Strict Fork-join Parallelism, below). The change was made because terminal strictness was deemed to present implementation difficulties for little gain in expressiveness.

These changes created an issue not present in the original paper: potential violations of fully-strict fork-join parallelism. A few sentences in the formal wording and a new issue in the issues section was added to the
paper in response.

Finally, task_cancelled_exception was renamed to task_canceled_exception (one el instead of two).

Document number: N4031

Date: 2014-05-22

make_array, revision 1

by Zhihao Yuan

Changes since N3824

• Editorial wording updates.
• Comments updates.