Document number: N3571

Date: 2013-03-15

A Proposal To Add Single Instruction Multiple Data Computation to the Standard Library

by Pierre Esterie, Mathias Gaunard, Joel Falcou

For maximum accessibility, programmers should be able to vectorize their code without needing a high level of expertise for every single SIMD extension. This proposal introduces a high-level abstraction to the user that gives access to SIMD computation in an instinctive way. It comes as a C++ template library, headers only that relies on a possibly full library implementation. With a high level template type for abstracting a SIMD register, the user can easily introduce SIMD in his application by instantiating this type and applying high level functions on it.

Document number: N3570

Date: 2013-03-14

Quoted Strings Library Proposal (Revision 1)

by Beman Dawes

Character strings enclosed in quotation marks are an element of numerous common data formats (e.g. XML, CSV), yet C++ standard library stream I/O offers no direct support. Furthermore, standard library stream I/O has a problem with embedded spaces in strings that can trip the unwary. The proposed solution provides direct support for quoted strings, avoids embedded spaces problems and is more efficient than likely user provided solutions.

The proposal is suitable for either C++1y or a standard library Technical Specification (TS). It is a pure addition that will break no existing standard-conforming user code. It is based on a Boost component that has been shipping for several years. The declarations for the proposed functions can go in a new header or an existing header.

Document number: N3565

Date: 2013-03-15

IP Address Design Constraints

by Aleksandar Fabijanic

This is a summary of IP address class design constraints that surfaced during Portland SG4 meeting [PORTLD] and subsequent [CPPSTDN] discussions. Goal is to determine a direction for the standard C++ IP address class proposal. This document does not aim to be a final verdict on what the design of standard IP address classes should look like; rather, it summarizes the concerns raised in discussions so far, weighing pros and cons of each proposed design. It is meant to serve as a reference for SG4 IP address discussion during Bristol meeting in April 2013.

Document number: N3563

Date: 2013-03-15

C++ Mapreduce

by Chris Mysen, Lawrence Crowl, Adam Berkan

For large scale distributed problems, the map-reduce framework has proven to be a highly effective way at creating highly parallel workflows working over distributed filesystems on petabyte scale operations and has been used for analysis, machine learning, and implementation of many distributed computation problems at Google.

This proposal outlines the details of a version of mapreduce which is logically simple but very extensible, based heavily off of both distributed and threaded versions of mapreduce, allowing for implementations which work as distributed, threaded, or both. There are some simplifications in this implementation which are detailed later, but much of the flexibility of many of the implemented map-reduces is retained.

Document number: N3562

Date: 2013-03-15

Executors and schedulers, revision 1

by Matt Austern, Lawrence Crowl, Chandler Carruth, Niklas Gustafsson, Chris Mysen, Jeffrey Yasskin

This paper is a proposal for executors, objects that can execute units of work packaged as function objects, in the form of an abstract base class and several concrete classes that inherit from it. It is based on components that are heavily used in internal Google and Microsoft code, with changes to better match the style of the C++ standard.

This proposal discusses the design decisions behind the API and also includes a first draft of formal wording for the working paper.

Document number: N3561

Date: 2013-03-15

Semantics of Vector Loops

by Robert Geva, Clark Nelson

In the SG1 conference call on Feb 5 2013, I presented the topic of a critical section in a vector loop. The discussion on the narrow topic itself resulted in the consensus that a critical section in a vector loops is undefined behavior. However, the discussion also led to broader interest in the semantics of a vector loop, which I was asked to present. This paper describes the semantics we propose. Note that this paper is meant as a continuation of earlier papers on vector loops, and is probably not self-contained. It does not repeat the syntax and language rules portions of the proposal.

As was stated in earlier meetings, this proposal is an attempt to codify existing practice in vector programming. While in a narrow sense, there are no existing practices of vector programming within standard C++, vector programming is broadly used in ad hoc ways. The expectations of programmers are well understood. The proposal here is not to invent new programming models. Instead, it is an attempt to codify the existing expectations of existing practitioners using C++ methodology.

Document number: N3557

Date: 2013-03-18

Considering a Fork-Join Parallelism Library

by Pablo Halpern

There is general consensus in the Concurrency and Parallelism study group (SG1) that strict fork-join parallelism would be a desirable feature to add to C++. They asked me to research whether it is possible to create a pure library interface for strict fork-join parallelism that achieves the same benefits as the well-established keyword-based language interface pioneered by the Cilk project and proposed for standardization in N3409. The technical and aesthetic advantages offered by the language approach include simple syntax, appropriate lifetimes for arguments in asynchronous function calls, correct overload resolution for asynchronous function calls, clear and enforceable strictness, and correct exception handling. This paper describes the challenges of creating a comparable library interface and explores the possibility of making small, general-purpose, language changes to enable a library solution to overcome those challenges. Ultimately, however, the library interface shows significant weaknesses when integrating with core features such as object lifetimes and exception scope. The library interface in particular is susceptible to misuses which may introduce subtle problems into programs that would be hard for many programmers to diagnose. Since our goal is making parallel programming accessible to the widest possible range of programmers I question whether a library approach could ever achieve this goal.

Document number: N3556

Date: 2013-03-18

Thread-Local Storage in X-Parallel Computations

by Pablo Halpern, Charles E. Leiserson

... [W]e designate the model under discussion as being an X-parallel model, where X might represent a variety of individual parallelization technologies, including vector units, GPU’s, task-based multithreading, attached processing, and the like. ...

The purpose of this paper is to develop terminology so that the impact of any X-parallel model on TLS can be described clearly and evaluated effectively. We compare the semantics of accessing a TLS variable within an X-parallel region to the semantics of accessing the same variable in serial execution. We propose a 5-level hierarchical taxonomy of TLS concordance, where each level in the hierarchy is more faithful to the way the existing threading model treats TLS than the level below. Placing an X-parallel model lower within the taxonomy does not necessarily mean that it is a bad model, but lower in the hierarchy does mean that an X-parallel model is a less faithful extension to the existing standard than a higher-level model, at least as far as its adherence to legacy TLS behavior is concerned.

We conclude with a brief discussion in which we advocate that any X-parallel model should provide Level-5 (full) concordance — the highest level — unless there is a compelling reason to the contrary.

Document number: N3543

Date: 2013-03-15

Priority Queue, Queue and Stack: Changes and Additions

by Gary Powell, Tim Blechmann

Priority Queues, Stacks and heaps are extremely useful data structures suitable for solving many common ordering problems. C++ 2011 provides only a couple of template adaptor classes; priority_queue, stack and queue, which provide limited functionality. To overcome the current limitations, this paper proposes that new containers be added to the standard library to replace the current adaptors which would then be depreciated. Additionally there are several alternative implementations of heaps having different performance characteristics which should be added to the standard library. Especially, the suggested options for these heaps deal with these additional aspects:

• Iterators: Heaps provide iterators to iterate all elements.
• Mutability: The priority of heap elements can be modified.
• Mergeable: While all heaps can be merged, some can be merged efficiently.
• Stability: Heaps can be configured to be stable sorted.
• Comparison: Heaps can be compared for equivalence.

Document number: N3542

Date: 2013-03-18

Proposal for Unbounded-Precision Integer Types

by Pete Becker

This paper proposes two unbounded-precision integer types. The type integer represents signed integer values. The type bits represents an unbounded set of bit values.

To support interoperability, objects of either type can be constructed from values of any of the standard integer types. So code like this just works:

    integer i = 30000;
    integer j = 1000 * i;

    bits b = 0xFF;
    bits c = b & 0xAA;

Converting a negative number to an object of type bits sets the number to the complement of this initializer, so this code just works:

    bits b = -3; // sets b to ...11111100