Execution policies

Where loops run (decisions.md [execution-policies]). More...

Namespaces
namespace	Emrys::execution
	The library's execution policies: the constant execution::sequential and its type.

Concepts
concept	Emrys::ExecutionPolicy
	An execution policy: execution::sequential, a policy of the standard library such as std::execution::par, or a policy of the user's own with a const forEachIndex(count, f) (see Execution policies).

Classes
struct	Emrys::execution::Sequential
	The type of execution::sequential, the default execution policy: plain loops on the calling thread, in index order. More...

Variables
constexpr Sequential	Emrys::execution::sequential {}
	The default execution policy: plain loops on the calling thread, in index order (Sequential).

Detailed Description

Where loops run (decisions.md [execution-policies]).

An operation whose work grows with a run-time count of elements (a particle set's particles, a grid's cells, a mixture's components, a Monte Carlo estimate's draws) has an overload that takes an execution policy as its first argument, as the standard algorithms do, and the overload without one runs Sequential:

#include <execution>
filter.predict(std::execution::par, rng, dt);
filter.update(std::execution::par, fix);
upkeep(std::execution::par, filter.state(), rng);
auto const moments = filter.state().moments(std::execution::par);

• execution::sequential, the constant of type execution::Sequential, runs plain loops on the calling thread. It is what every operation did before it took a policy, bitwise, and it brings in nothing from <execution>.
• Any policy of the standard library, such as std::execution::par or std::execution::par_unseq, runs the loops through std::for_each with that policy. The caller includes <execution>; with GCC's library, a parallel run also links TBB, without which the standard library runs the loop on one thread.
• A policy of the user's own, such as a handle to an engine's thread pool where the standard library's parallel algorithms are absent or unwanted, is any type with a const forEachIndex(count, f) that calls f(i) exactly once for each i in [0, count), in any order and possibly at once, and returns when every call has. Every loop in the library is built on that one operation. It runs the same chunked loops as a standard policy, so the rest of this list holds for it as for par, except where the scratch comes from. A policy may also have a const get_allocator(), from which the library takes the scratch of its reductions, scans, and compactions, re-bound to each element type, instead of from the heap; it allocates on the calling thread, before or after a loop and never inside one, so that allocator need not be safe to call from several threads. The library calls nothing else on the policy:

  struct PoolPolicy
  {
      ThreadPool * pool;
      std::pmr::memory_resource * scratch;
   
      template <typename F>
      void
      forEachIndex(Eigen::Index count, F const & f) const
      {
          pool->parallelFor(0, count, f);  // returns when every f(i) has
      }
   
      [[nodiscard]] std::pmr::polymorphic_allocator<>
      get_allocator() const
      {
          return scratch;
      }
  };
   
  filter.predict(PoolPolicy{&pool, &arena}, rng, dt);

• A for-each, which writes one element per index, gives the same result under every policy. A reduction or a scan, such as a log-sum-exp, a weighted mean, or a cumulative sum, splits the elements into fixed chunks of internal::chunkSize, runs the chunks under the policy, and combines their results in order. Its result is the same at any thread count and from run to run, and differs from Sequential's only by rounding. Below a chunk it is Sequential's.
• The draws from a std::uniform_random_bit_generator stay sequential: they are drawn before a parallel loop, into scratch, so the loop body is a pure function of its index.
• What a parallel loop calls, such as a model's propagate(), a measurement model's function, or a ParticleSet::forEach() callback, runs concurrently for different elements, so it must not write shared state. Under par_unseq and unseq it must not allocate or synchronize either, which rules out a space of dynamic size.
• The standard library's parallel algorithms allocate, and so do the chunks' results, so a filter's steps allocate nothing (Allocation) only under Sequential. Under a standard policy that memory comes from the heap, not from the state's allocator, which the standard algorithms give no way to pass. Under a user's policy the library's scratch is the only memory a step asks for beyond Sequential's, so a policy with get_allocator() keeps a filter's steps off the heap.
• std::execution::seq is a standard policy like the others, not Sequential: it runs on the calling thread but takes the chunked path, so it gives the parallel policies' results bitwise, allocates as they do, and, as the standard says of sequenced_policy, calls the elements in no specified order. It reproduces a parallel run on one thread; Sequential is the plain loops.