P0019.bs

<pre class='metadata'>
Title:  Atomic Ref
Abstract: Extension to the atomic operations library to allow atomic operations to apply to non-atomic objects.
Editor: H. Carter Edwards, hedwards@nvidia.com
Editor: Hans Boehm, hboehm@google.com
Editor: Olivier Giroux, ogiroux@nvidia.com
Editor: Daniel Sunderland, dsunder@sandia.gov
Editor: Mark Hoemmen, mhoemme@sandia.gov
Editor: David Hollman, dshollm@sandia.gov
Editor: Bryce Adelstein Lelbach, blelbach@nvidia.com
Shortname: D0019
Revision: 7
Audience: LWG
Status: D
Group: WG21
Date: 2018-03-14
Repository: https://github.com/kokkos/ISO-CPP-Papers.git
URL: https://kokkos.github.io/ISO-CPP-Papers/P0019.html
Toggle Diffs: Yes
Warning: Custom
Custom Warning Title: Work in Progress
Custom Warning Text: This document is a work in progress that has not yet been
                     submitted to the committee for discussion in its current
                     form. 
Markup Shorthands: markdown yes
</pre>

Revision History
================

[[P0019r7]]

-   Update to reference resolution of padding bits from [[P0528r2]]

-   Add a note clarifying that `atomic_ref` may not be lock free 
    even if `atomic` is lock free

-   Convert to bikeshed

-   Improve wording

[[P0019r6]]

-   `2017-11-07 Albuquerque LEWG review
    <http://wiki.edg.com/bin/view/Wg21albuquerque/P0019>`
    
    -   Settle on name `atomic_ref`
    
    -   Split out atomic_ref<T[]> into a separate paper,
        apply editorial changes accordingly
	
    -   Restore copy constructor; not assignment operator
    
    -   add **Throws: Nothing** to constructor but do not add noexcept
    
    -   Remove *wrapping* terminology
    
    -   Address problem of CAS on `atomic_ref<T>` where `T` is
        a struct containing padding bits
	
    -   With these revisions move to LWG
    

[[P0019r5]]

-   2017-03-01 Kona LEWG review

    -   Merge in P0440 Floating Point Atomic View because LEWG
        consensus to move P0020 Floating Point Atomic to C++20 IS
	
    -   Rename from `atomic_view` and `atomic_array_view`;
        authors' selection `atomic_ref<T>` and `atomic_ref<T[]>`,
        other name suggested `atomic_wrapper`.
	
    -   Remove `constexpr` qualification from default constructor
        because this qualification constrains implementations and
        does not add apparent value.
	
-   Remove default constructor, copy constructor, and assignment operator
    for tighter alignment with `atomic<T>` and prevent empty references.
    
-   Revise syntax to align with [[P0558r1]], Resolving atomic<T>
    base class inconsistencies
    
-   Recommend feature next macro

[[P0019r4]]
  
-   wrapper constructor strengthen requires clause and omit throws clause

-   Note types must be trivially copyable, as required for all atomics

-   2016-11-09 Issaquah SG1 decision: move to LEWG targeting Concurrency TS V2

[[P0019r3]]
  
-   Align proposal with content of corresponding sections in N5131, 2016-07-15.

-   Remove the *one root wrapping constructor* requirement from `atomic_array_view`.

-   Other minor revisions responding to feedback from SG1 @ Oulu.


Overview
========

This paper proposes an extension to the atomic operations library [**atomics**]
to allow atomic operations to apply to non-atomic objects.
As required by [**atomics.types.generic**] the value type **T**
must be trivially copyable.

This paper includes *atomic floating point* capability defined in [[P0020r5]].


Motivation
==========

##  Atomic Operations on a Single Non-atomic Object

An *atomic reference* is used to perform
atomic operations on a referenced non-atomic object.
The intent is for *atomic reference* to provide the best-performing
implementation of atomic operations for the non-atomic object type.
All atomic operations performed through an *atomic reference*
on a referenced non-atomic object
are atomic with respect to any other *atomic reference* that references
the same object, as defined by equality of pointers to that object. 
The intent is for atomic operations
to directly update the referenced object.
An *atomic reference constructor* may acquire a resource,
such as a lock from a collection of address-sharded locks,
to perform atomic operations.
Such *atomic reference* objects are not lock free and not address free.
When such a resource is necessary, subsequent
copy and move constructors and assignment operators
may reduce overhead by copying or moving the previously
acquired resource as opposed to re-acquiring that resource.

Introducing concurrency within legacy codes may require
replacing operations on existing non-atomic objects with atomic operations
such that the non-atomic object cannot be replaced with an **atomic** object.

An object may be heavily used non-atomically in well-defined phases
of an application.  Forcing such objects to be exclusively **atomic**
would incur an unnecessary performance penalty.


##  Atomic Operations on Members of a Very Large Array

High-performance computing (HPC) applications use very large arrays.
Computations with these arrays typically have distinct phases that
allocate and initialize members of the array,
update members of the array,
and read members of the array.
Parallel algorithms for initialization (e.g., zero fill)
have non-conflicting access when assigning member values.
Parallel algorithms for updates have conflicting access
to members which must be guarded by atomic operations.
Parallel algorithms with read-only access require best-performing
streaming read access, random read access, vectorization,
or other guaranteed non-conflicting HPC pattern.

*Reference-ability* Constraints
===============================

An object referenced by an *atomic reference* must satisfy
possibly architecture-specific constraints.
For example, the object might need to be properly aligned in memory
or may not be allowed to reside in GPU register memory.
We do not enumerate all potential constraints or
specify behavior when these constraints are violated.
It is a quality-of-implementation issue to generate appropriate
information when constraints are violated.

Note: Whether an implementation of `atomic<T>` is lock free, 
does not necessarily constrain whether the corresponding 
implementation of `atomic_ref<T>` is lock free.


Concern with `atomic<T>` and padding bits in `T`
====================================================
A concern has been discussed for `atomic<T>` where `T` is a
class type that contains padding bits and how construction and
`compare_exchange` operations are effected by the value of
those padding bits.  We require that the resolution of padding
bits follow [[P0528r2]].


Proposal
========

The proposed changes are relative to the working draft of the standard
as of [[N4727]].

<blockquote>
Text in blockquotes is not proposed wording
</blockquote>

<blockquote>
The � character is used to denote a placeholder section number which
the editor shall determine.
</blockquote>

<blockquote>
Apply the following changes to 32.2.� [atomics.syn]:
</blockquote>
  
```c++
namespace std {
namespace experimental {
inline namespace concurrency_v2 {

template< class T > struct atomic_ref ;
template< class T > struct atomic_ref< T * >;

}}}
```

<blockquote>
Add a new section [atomics.ref.generic] after [atomics.types.generic]
</blockquote>

```c++
template< class T > struct atomic_ref {
private:
  T & ref_; // exposition only
public:
  using value_type = T;
  static constexpr bool is_always_lock_free = implementation-defined ;
  static constexpr size_t required_alignment = implementation-defined ;
  
  atomic_ref() = delete ;
  atomic_ref( const atomic_ref & );
  explicit atomic_ref( T & obj );

  atomic_ref & operator = ( const atomic_ref & ) = delete ;

  T operator=(T) const noexcept ;

  bool is_lock_free() const noexcept;
  void store( T , memory_order = memory_order_seq_cst ) const noexcept;
  T load( memory_order = memory_order_seq_cst ) const noexcept;
  operator T() const noexcept ;
  T exchange( T , memory_order = memory_order_seq_cst ) const noexcept;
  bool compare_exchange_weak( T& , T , memory_order , memory_order ) const noexcept;
  bool compare_exchange_strong( T& , T , memory_order , memory_order ) const noexcept;
  bool compare_exchange_weak( T& , T , memory_order = memory_order_seq_cst ) const noexcept;
  bool compare_exchange_strong( T&, T, memory_order = memory_order_seq_cst ) const noexcept;
};
```

<blockquote>
Add a new subsection [atomics.ref.operations] to [atomics.ref.generic]
</blockquote>

Except for the members defined below, for every operation in `atomic_ref<T>` 
that is in `atomic<T>` the operation
applies to the value referenced by `ref_` whenever it would apply to the value
stored in `atomic<T>`.

**static constexpr size_t required_alignment** ;

  The required alignment of an object to be referenced by an atomic reference,
  which is at least `alignof(T)`.

  [*Note:* An architecture may support lock-free atomic operations
  on objects of type `T` only if those objects meet a required
  alignment.  The intent is for `atomic_ref` to provide lock-free
  atomic operations whenever possible. 
  For example, an architecture may be able to support lock-free
  operations on `std::complex<double>` only if aligned to
  `2*alignof(double)` and not `alignof(double)` . - *end note*]

**atomic_ref( T & obj ) ;**

  *Requires:* The referenced non-atomic object shall be
  aligned to `required_alignment`.
  
  *Effects:* Construct an atomic reference that references the non-atomic object.
  
  *Throws:* Nothing.

  *Remarks:*  The lifetime (6.8) of `*this`
  shall not exceed the lifetime of the referenced non-atomic object.
  While any `atomic_ref` instance exists that references the object
  all accesses of that object shall exclusively occur through those
  `atomic_ref` instances.

  If the referenced *object* is of a class or aggregate type
  then members of that object shall not be concurrently
  referenced by an `atomic_ref` object.
  
  Atomic operations applied to object through a referencing
  atomic reference are atomic with respect to atomic operations
  applied through any other atomic reference that references that object.
  
  [*Note*: The constructor may acquire a shared resource,
  such as a lock associated with the referenced object,
  to enable atomic operations applied to the referenced
  non-atomic object. - *end note*]

  **atomic_ref( const atomic_ref & ) ;**

  *Effects:* Construct an atomic reference that references the non-atomic object
  referenced by the given `atomic_ref`.

Apply the following changes to 32.6.2.� [atomics.types.int]:

```c++
template<> struct atomic_ref< integral > {
  using value_type = integral ;
  using difference_type = value_type;
  static constexpr bool is_always_lock_free = implementation-defined ;
  static constexpr size_t required_alignment = implementation-defined ;

  atomic_ref() = delete ;
  atomic_ref( const atomic_ref & ) ;
  explicit atomic_ref(  integral  & obj );
  
  atomic_ref & operator = ( const atomic_ref & ) = delete ;

  integral operator=( integral ) const noexcept ;

  bool is_lock_free() const noexcept;
  void store( integral , memory_order = memory_order_seq_cst ) const noexcept;
  integral load( memory_order = memory_order_seq_cst ) const noexcept;
  operator integral () const noexcept ;
  integral exchange( integral , memory_order = memory_order_seq_cst ) const noexcept;
  bool compare_exchange_weak( integral & , integral , memory_order , memory_order ) const noexcept;
  bool compare_exchange_strong( integral & , integral  , memory_order , memory_order ) const noexcept;
  bool compare_exchange_weak( integral & , integral  , memory_order = memory_order_seq_cst ) const noexcept;
  bool compare_exchange_strong( integral &, integral , memory_order = memory_order_seq_cst ) const noexcept;
  
  integral fetch_add( integral , memory_order = memory_order_seq_cst) const noexcept;
  integral fetch_sub( integral , memory_order = memory_order_seq_cst) const noexcept;
  integral fetch_and( integral , memory_order = memory_order_seq_cst) const noexcept;
  integral fetch_or(  integral , memory_order = memory_order_seq_cst) const noexcept;
  integral fetch_xor( integral , memory_order = memory_order_seq_cst) const noexcept;
  
  integral operator++(int) const noexcept;
  integral operator--(int) const noexcept;
  integral operator++() const noexcept;
  integral operator--() const noexcept;
  integral operator+=( integral ) const noexcept;
  integral operator-=( integral ) const noexcept;
  integral operator&=( integral ) const noexcept;
  integral operator|=( integral ) const noexcept;
  integral operator^=( integral ) const noexcept;
};
```

Apply the following changes to 32.6.3.� [atomics.types.float]:

```c++

template<> struct atomic_ref< floating-point > {
  using value_type = floating-point ;
  using difference_type = value_type;
  static constexpr bool is_always_lock_free = *implementation-defined* ;
  static constexpr size_t required_alignment = *implementation-defined* ;

  atomic_ref() = delete ;
  atomic_ref( const atomic_ref & );
  explicit atomic_ref( floating-point & obj ) noexcept ;

  atomic_ref & operator = ( const atomic_ref & ) = delete ;

  floating-point operator=( floating-point ) noexcept ;

  bool is_lock_free() const noexcept;
  void store( floating-point , memory_order = memory_order_seq_cst ) const noexcept;
  floating-point load( memory_order = memory_order_seq_cst ) const noexcept;
  operator floating-point () const noexcept ;
  floating-point exchange( floating-point , memory_order = memory_order_seq_cst ) const noexcept;
  bool compare_exchange_weak( floating-point & , floating-point , memory_order , memory_order ) const noexcept;
  bool compare_exchange_strong( floating-point & , floating-point  , memory_order , memory_order ) const noexcept;
  bool compare_exchange_weak( floating-point & , floating-point  , memory_order = memory_order_seq_cst ) const noexcept;
  bool compare_exchange_strong( floating-point &, floating-point , memory_order = memory_order_seq_cst ) const noexcept;

  floating-point fetch_add( floating-point , memory_order = memory_order_seq_cst) const noexcept;
  floating-point fetch_sub( floating-point , memory_order = memory_order_seq_cst) const noexcept;

  floating-point operator+=( floating-point ) const noexcept ;
  floating-point operator-=( floating-point ) const noexcept ;
};
```

Apply the following changes to 32.6.4.� [atomics.types.pointer]:

```c++
template<class T> struct atomic_ref< T * > {
  using value_type = T * ;
  using difference_type = ptrdiff_t;
  static constexpr bool is_always_lock_free = *implementation-defined* ;
  static constexpr size_t required_alignment = *implementation-defined* ;
  
  atomic_ref() = delete ;
  atomic_ref( const atomic_ref & );
  explicit atomic_ref( T * & obj );

  atomic_ref & operator = ( const atomic_ref & ) = delete ;

  T * operator=( T * ) const noexcept ;

  bool is_lock_free() const noexcept;
  void store( T * , memory_order = memory_order_seq_cst ) const noexcept;
  T * load( memory_order = memory_order_seq_cst ) const noexcept;
  operator T * () const noexcept ;
  T * exchange( T * , memory_order = memory_order_seq_cst ) const noexcept;
  bool compare_exchange_weak( T * & , T * , memory_order , memory_order ) const noexcept;
  bool compare_exchange_strong( T * & , T *  , memory_order , memory_order ) const noexcept;
  bool compare_exchange_weak( T * & , T *  , memory_order = memory_order_seq_cst ) const noexcept;
  bool compare_exchange_strong( T * &, T * , memory_order = memory_order_seq_cst ) const noexcept;

  T * fetch_add( difference_type , memory_order = memory_order_seq_cst) const noexcept;
  T * fetch_sub( difference_type , memory_order = memory_order_seq_cst) const noexcept;

  T * operator++(int) const noexcept;
  T * operator--(int) const noexcept;
  T * operator++() const noexcept;
  T * operator--() const noexcept;
  T * operator+=( difference_type ) const noexcept;
  T * operator-=( difference_type ) const noexcept;
};
```

Feature Testing {#test}
===============

The `__cpp_lib_atomic_ref` feature test macro should be added.