1   Introduction

This paper proposes an extension to the atomic operations library [atomics] for atomic operations applied to non-atomic objects. The proposal is in five parts: (1) the concept of an atomic view, (2) application of this concept applied to single objects, (3) application of this concept applied to members of a very large array, (4) application of this concept applied to an object in a large legacy code which cannot replace that object with a corresponding atomic<T> object, and (5) motivating use cases and illustrative examples.

namespace std {

namespace experimental {

template< class T > atomic_view ;

template< class T > atomic_array_view ;

template< class T > atomic_global_view ;

}}

2   Atomic View Concept

A class conforming to the atomic view concept provides atomic operations for the viewed non-atomic object. These operations replicate the operations on std::atomic<T> [29.5, Atomic types]; however, operations are const with respect to the atomic view object in contrast to the non-const and volatile operations of a std::atomic<T> object. An atomic view does not own (neither exclusively nor shared) the viewed non-atomic object.

The following atomic-view-concept specification is included to define requirements for classes conforming to the atomic-view-concept and does not imply the existiance of a template class of this name.

template< class T >

struct atomic-view-concept {

// Functionality matches corresponding member of atomic<T>

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 operator=(T) const noexcept ;

// Functionality that may exist and deviate from corresponding member of atomic<T>, if any.

atomic-view-concept ();

atomic-view-concept ( const atomic-view-concept & );

atomic-view-concept ( atomic-view-concept && );

atomic-view-concept & operator = ( const atomic-view-concept & );

atomic-view-concept & operator = ( atomic-view-concept && );

constexpr explicit bool operator() const noexcept;

};

Constructors and assignment operators of an atomic-view-concept may acquire resources such as concurrent locks to support atomic operations on the non-atomic object, and may track membership in a set of transitive copies for the purpose of sharing those resources.

constexpr explict bool operator() const noexept ;

Returns if the atomic-view-concept object views an object. A default constructed atomic-view-concept object returns false.

A class conforming to the atomic view concept shall provide the following operations when T is an integral type. These operations replicate the operations on std::atomic<integral> [29.5, Atomic types]; however, operations are const with respect to the atomic view object in contrast to the non-const and volatile operations of a std::atomic<integral> object.

template<> struct atomic-view-concept < integral > {

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;

};

Note that for consistency the atomic-view-concept<integral> mathematical operator overloads retain the same mathematical inconsistency with respect to the mathematical operators for the integral type, as illustrated below.

int i(0)
++( ++i );        // ++i returns an lvalue
( i += 1 ) += 2 ; // i+= returns an lvalue

std::atomic<int> ai(0);
++( ++( ai ) );    // error: ++ai returns an rvalue
( ai += 1 ) += 2 ; // error: ai+= returns an rvalue

3   Atomic View for a Single Object

An atomic_view<T> object is used to perform atomic operations on the viewed non-atomic object. The intent is for atomic_view<T> to provide the best-performing implementation of atomic-view-concept operations for the type T.

template< class T > struct atomic_view { // conforms to atomic view concept

explicit atomic_view( T & ); // Originating Constructor is NOT noexcept

atomic_view();

atomic_view( atomic_view && ) noexcept ;

atomic_view( const atomic_view & ) noexcept ;

atomic_view & operator = ( const atomic_view & ) noexcept ;

~atomic_view() noexcept ;

};

[Note: The intent is for atomic operations of atomic_view<T> to directly update the referenced object. The set of transitive copies of atomic_view<T> may require a resource, such as a locking mechanism, to perform atomic operations. The intent is to enable amortization of the time and space overhead of obtaining and releasing such a resource. – end note]

atomic_view<T>::atomic_view( T & obj );

Requires: The referenced obj must be properly aligned for its type T, otherwise behavior is undefined.

Effects: This originating constructor wraps the referenced object. The constructed instance is the originating member of a set of transitive copies of atomic_view<T>. [Note: This constructor may obtain a resource as necessary to support atomic operations. The originating constructor is allowed to throw an exception if such a resource could not be obtained. – end note]

atomic_view<T>::atomic_view( const atomic_view & rhs ) noexcept ;

Effects: If rhs is a member of a set of transitive copies of atomic_view<T> the copy constructed instance is a member of that set.

atomic_view<T>::~atomic_view() noexcept ;

Effects: If this instance is a member of a set of transitive copies then this instance is removed from the set. [Note: If the set will become empty then a resource shared by that set should be released. – end note]

atomic_view<T> & atomic_view<T>::operator = ( const atomic_view & rhs ) noexcept ;

Effects: If this instance is a member of a set of transitive copies then that instance is removed from the set. [Note: If the set will become empty then a resource shared by that set should be released. – end note] If rhs is a member of a set of transitive copies of atomic_view<T> the copy constructed instance is a member of that set.

4   Atomic View for 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.

An atomic_array_view<T> object is used to perform atomic operations on the viewed non-atomic members of the array. The intent is for atomic_array_view<T> to provide the best-performing implementation of atomic-view-concept operations for the members of the array.

template< class T > struct atomic_array_view {

bool is_lock_free() const noexcept ;

// Returns true if the view wraps an array and member access is valid.

explicit bool operator() const noexcept ;

atomic_array_view( T * , size_t ); // Originating Constructor is NOT noexcept

atomic_array_view() noexcept ;

atomic_array_view( atomic_array_view && ) noexcept ;

atomic_array_view( const atomic_array_view & ) noexcept ;

atomic_array_view & operator = ( const atomic_array_view & ) noexcept ;

~atomic_array_view() noexcept ;

size_t size() const noexcept ;

typedef implementation-defined-atomic-view-concept-type reference ;

reference operator[]( size_t ) const noexcept ;

};

[Note: The intent is for atomic operations on members of atomic_array_view<T> to directly update the referenced member. The set of transitive copies of atomic_array_view<T> may require resources, such as locking mechanisms, to perform atomic operations. The intent is to enable amortization of the time and space overhead of obtaining and releasing such resources. – end note]

typedef implementation-defined-atomic-view-concept-type reference;

The reference type conforms to atomic-view-concept for type T.

bool atomic_array_view<T>::is_lock_free() const noexcept ;

Effects: Returns whether atomic operations on members are lock free.

atomic_array_view<T>::atomic_array_view( T * ptr , size_t N );

Requires: The array referenced by [ptr .. ptr+N-1] must be properly aligned for its type T, otherwise behavior is undefined.

Effects: This originating constructor wraps the referenced array [ptr .. ptr+N-1]. The constructed instance is the originating member of a set of transitive copies of atomic_array_view<T>. [Note: This constructor may obtain resources as necessary to support atomic operations. The originating constructor is allowed to throw an exception if such resources could not be obtained. – end note]

atomic_array_view<T>::atomic_array_view( const atomic_array_view & rhs ) noexcept ;

Effects: If rhs is a member of a set of transitive copies of atomic_array_view<T> the copy constructed instance is a member of that set.

atomic_array_view<T>::~atomic_array_view() noexcept ;

Effects: If this instance is a member of a set of transitive copies this instance is removed from the set. [Note: If the set will become empty then resources shared by that set should be released. – end note]

atomic_array_view<T> & atomic_array_view<T>::operator = ( const atomic_array_view & rhs ) noexcept ;

Effects: If this instance is a member of a set of transitive copies that instance is removed from the set. [Note: If the set will become empty then resources shared by that set should be released. – end note] If rhs is a member of a set of transitive copies of atomic_array_view<T> the copy constructed instance is a member of that set.

atomic_array_view<T>::reference atomic_array_view<T>::operator[]( size_t i ) const noexcept ;

Requires: The index i must be in the range [0 .. N-1], otherwise behavior is undefined.

Effects: Return an instance of reference type for the member object referenced by the input index i. [Note: The intent is for efficient generation of the returned instance with respect to obtaining a resource, such as a shared locking mechanism, that may be required to support atomic operations on the referenced member. – end note]

5   Atomic Global Views for a Single Non-atomic Object

An atomic_global_view<T> object is used to perform atomic operations on the globally accessible viewed non-atomic object. The intent is for atomic_global_view<T> to provide the best-performing implementation of atomic-view-concept operations for the type T. All atomic operations on an instance of atomic_global_view<T> are atomic with respect to any other instance that views the same globally accessible object, as defined by equality of pointers to that object.

[Note: Introducing concurrency within legacy codes may require replacing operations on existing non-atomic objects with atomic operations. Such replacement may not be able to introduce a set of transitive copies of atomic_view<T>. – end note]

template< class T > struct atomic_global_view { // conforms to atomic view concept

atomic_global_view( T & ); // Wrapping constructor is NOT noexcept

atomic_global_view( const atomic_global_view & ) noexcept ;

atomic_global_view( atomic_global_view && ) noexcept ;

~atomic_global_view() noexcept ;

atomic_global_view() = delete ;

atomic_global_view & operator = ( const atomic_concurrent__view & ) = delete ;

};

[Note: The intent is for atomic operations of atomic_global_view<T> to directly update the referenced object. – end note]

atomic_global_view<T>::atomic_global_view( T & obj );

Requires: The referenced obj must be properly aligned for its type T, otherwise behavior is undefined.

Effects: This wrapping constructor wraps the globally accessible referenced object. Atomic operations on this instance are atomic with respect to atomic operations on any atomic_global_view<T> instance that reference the same globally accessible object. [Note: This constructor may obtain a resource as necessary to support atomic operations. This constructor is allowed to throw an exception if such a resource could not be obtained. – end note]

Effects: If rhs references a globally accessible object then this instance references the same object otherwise this instance does not reference a globally accessible object.

atomic_global_view<T>::~atomic_global_view() noexcept ;

Effects: This instance does not reference a globally accessible object.

6   Notes and Examples

void foo( int & i ) {
  i = 42 ;
  atomic_view<int> ai(i);
  // Operations on ‘i’ must happen before operations on ‘ai’
  foreach( parallel_policy, 0, N, [=](){ ++ai ; } );
}

// atomic array view wrapper constructor:
atomic_array_view<T> array( ptr , N );

// atomic operation on a member:
array[i].atomic-operation(...);

// atomic operations through a temporary value
// within a concurrent function:
atomic_array_view<T>::reference x = array[i];
x.atomic-operation-a(...);
x.atomic-operation-b(...);

struct implementation-defined-proxy-type {   // conforms to atomic view concept

  // Construction limited to move
  implementation-defined-proxy-type(implementation-defined-proxy-type && ) = noexcept ;
  ~implementation-defined-proxy-type();

  implementation-defined-proxy-type() = delete ;
  implementation-defined-proxy-type( const implementation-defined-proxy-type & ) = delete ;
  implementation-defined-proxy-type &
    operator = ( const implementation-defined-proxy-type & ) = delete ;
};

void foo( int * i , size_t N ) {
  i[0] = 42 ;
  i[N-1] = 42 ;
  atomic_array_view<int> ai(i,N);
  // Operations on ‘i’ must happen before operations on ‘ai’
  foreach( parallel_policy, 0, M, [=]( int j ){ ++ai[j%N] ; } );
}

void foo( int & i ) {
  i = 42 ;
  // Operations on ‘i’ must happen before operations on ‘ai’
  foreach( parallel_policy, 0, N, [=](){ ++atomic_global_view<ai>(i) ; } );
}

// atomic operation on an object:
atomic_global_view<T>(x).atomic-operation(...);

// When multiple atomic operations are performed the cost of
// constructing and destructing the atomic view can be amortized
// through a temporary atomic view object.
{
  atomic_global_view ax(x);
  ax.atomic-operation-a(...);
  ax.atomic-operation-b(...);
}