C++17 in details: Parallel Algorithms | Bartłomiej Filipek

Bartłomiej Filipek <noreply@blogger.com>; C++17 in details: Parallel Algorithms; In His Blog; 2017-08-17.

Contents

Mentioned

  • C++11
  • C++14
  • C++17
  • “map reduce” is “transform reduce” in C++17.
  • execution policy.

Scheme

std::algorithm_name(policy, arguments...);

Components

#include <execution>
namespace std::execution
std::execution::ExecutionPolicy

Configuration
Sequential
The algorithm may not be parallelized.

  • (type) std::execution::sequenced_policy
  • (constant) std::execution::seq
Parallel
The algorithm may be parallelized; each individual ith can be scheduled concurrently, but within a stripe, serialization occurs.

  • (type) std::execution::parallel_policy
  • (constant) std::execution::par
Unsequenced (Vectorizable)
The algorithm can be vectorized; the workload as a whole is to be considered.

  • (type) std::execution::parallel_unsequenced_policy
  • (constant) std::execution::par_unseq

Catalog

Via Experimental Parallel Algorithms, at cppreference.com.

Generally…

  • adjacent difference
  • adjacent find.
  • all_of
  • any_of
  • none_of
  • copy
  • count
  • equal
  • fill
  • find
  • generate
  • includes
  • inner product
  • in place merge
  • merge
  • is heap
  • is partitioned
  • is sorted
  • lexicographical_compare
  • min element
  • minmax element
  • mismatch
  • move
  • n-th element
  • partial sort
  • sort copy
  • partition
  • remove & variations
  • replace & variations
  • reverse
  • rotate
  • search
  • set difference
  • intersection
  • union
  • symmetric difference
  • sort
  • stable partition
  • swap ranges
  • transform
  • unique
More New…
  • for_each
  • for_each_n
  • reduce
  • exclusive_scan
  • inclusive_scan
  • std::partial_sum
The Map/Reduce Idom
  • transform_reduce – applies a functor, then reduces out of order
  • transform_exclusive_scan – applies a functor, then calculates exclusive scan
  • transform_inclusive_scan – applies a functor, then calculates inclusive scan

Filler

  • GPU
  • Vectorization (SIMD)
  • Packages
    • CUDA
    • OpenCL
    • OpenGL
    • SYCL
    • Intel TBB
    • “other” vectorized libraries
  • Amdahl’s law; In Jimi Wales’ Wiki

Referenced

There are many resources referenced

Papers

isocpp.org
  • N4659Draft, Standard for Programming Language C++, 2017-03-21.
  • P0024R2Parallelism
    a.k.a. “the original paper for the spec”
  • P0636r0Changes between C++14 and C++17 DIS
  • N3554PDF: A Parallel Algorithms Library, 2013.
    a.k.a. “the initial Parallelism TS”

Popularization

In Modern C++ (Magazine)‖

Books

  • Jacek Galowicz; C++17 STL Cookbook; amzn.to
  • Marius Bancila; Modern C++ Programming Cookbook; amzn.to

YouTube

  • Bryce Adelstein; A Talk; On YouTube; WHEN?
    tl;dr → something about the distinction between std::execution::par, and std::execution::par_unseq.
  • Bryce Lelbach: C++Now 2017: C++17 Features; On YouTube; 2017.
  • Sean Parent; A Talk; At code::dive (Conference), hosted on YouTube; 2016; same material(?) was the subject of a keynote address at CppNow 2012 <rly?>
  • Jason Turner: C++ Weekly channel; On YouTube.
    tl;dr → covers C++17 features in a linear read-the-news-at-you-over-visual-media type format.

Implementations

Previously

In His Blog

Series

  1. Fixes and deprecation
  2. Language clarification
  3. Templates
  4. Attributes
  5. Simplification
  6. Library changes – Filesystem
  7. Library changes – Parallel STL
  8. Library changes – Utils
  9. Wrap up, Bonus

Previously filled.

Effective Modern C++ | Scott Meyers

Scott Meyers; Effective Modern C++: 42 Specific Ways to Improve Your Use of C++11 and C++14; O’Reilly Media; 1st edition; 2014-12-04; 320 pages; kindle: no, paper: $41.


Related

Scott Meyers; Effective Modern C++; At NDC on Vimeo; 2014; 1:00:??.

Mentions

  • Prefer auto, for a variety of reasons
  • Whereas
    • int (int unsigned) is 32 bits
    • std::size_t is always 64 bits
  • Closures might or might not use heap storage depending upon how many objects are captured.  The auto variant will be inlined & on the stack.

    • std::function<int (int)> = fla = [=](int x) { ... }
    • auto = fla = [=](int x) { ... }
  • A braced initializer does not have a t ype, but deduces to std::initializer_list<TYPE> mostly.
  • Proxy types, hidden proxy types (so you want to use auto)
    • ! std::is_same<std::vector<bool>::reference *, type *>::value
  • Uniform Initialization (mostly) can be done with brace initialization
    • disallows narrowing conversions
    • different rules for constructor overloading matches in the presence of std::initializer_list<TYPE>.
  • Atomic Data versus Transactions (mutexes)
    • bitwise const or internal synchronization
    • standard discipline for multithreaded design applies

Actualities

ol>

N3580: Concepts Lite | Sutton, Stoustrup, Dos Reis

Concepts Lite

Via: backfill

C++0x, C++11, C++14

Overview

C++11

Boost

  • boost::shared_mutex
    RAII

    • shared_lock takes a shared read lock
    • lock_guard
      • std::lock_guard<std::mutex>
    • unique_lock take an exclusive lock
  • boost::unique_future
  • boost::thread
    • Has cancellation, called interruption (rly?)
    • Uses boost::bind, which requires copyable arguments
  • boost::bind
  • boost::format
    • is like printf, but (um) better
  • Boost.Exception
  • Beyond C++11
    • join with timeout
    • thread interruption
    • thread groups
    • extra lock types

Future

  • Concepts
    • N3701 Concepts Lite; 2013-06-28
    • N3351 Concept Design for the STL; 2012-01-13.
    • N2081 Concepts (Revision 1); 2006-09-10.
    • Concept Maps (maybe, maybe not)
    • Concept GCC; In Jimi Wales’ Wiki.
  • Modules

Historical

  • #include <pthread.h>
  • pthread_create(pthread_t *, pthread_attr_t const *, void *(*routine)(void *), void *routine_arg)

Standards Working Documents

  • N2179 Language Support for Transporting Exceptions between Threads; 2007-03-03.
  • N2184 Thread Launching for C++; 2007-03-09
  • N2320 Multi-threading Library for Standard C++; 2007-06-24.
  • N2431 A name for the null pointer: nullptr; 2007-10-02.
  • N2880 C++ object lifetime interactions with the threads API; 2009-05-01.
  • N3070 Handling Detached Threads and thread_local Variables; 2010-03-11.
  • N3242 Working Draft, Standard for Programming Language C++; 2011-02-28.

Referenced

General

Detailed, Dated