vtkSMPTools.h

Go to the documentation of this file.

// SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
// SPDX-License-Identifier: BSD-3-Clause
#ifndef vtkSMPTools_h
#define vtkSMPTools_h

#include "vtkCommonCoreModule.h" // For export macro
#include "vtkObject.h"

#include "SMP/Common/vtkSMPToolsAPI.h"
#include "vtkSMPThreadLocal.h" // For Initialized

#include <cmath>       // For std::ceil
#include <functional>  // For std::function
#include <type_traits> // For std:::enable_if

#ifndef DOXYGEN_SHOULD_SKIP_THIS
namespace vtk
{
namespace detail
{
namespace smp
{
VTK_ABI_NAMESPACE_BEGIN
template <typename T>
class vtkSMPTools_Has_Initialize
{
  typedef char (&no_type)[1];
  typedef char (&yes_type)[2];
  template <typename U, void (U::*)()>
  struct V
  {
  };
  template <typename U>
  static yes_type check(V<U, &U::Initialize>*);
  template <typename U>
  static no_type check(...);

public:
  static bool const value = sizeof(check<T>(nullptr)) == sizeof(yes_type);
};

template <typename T>
class vtkSMPTools_Has_Initialize_const
{
  typedef char (&no_type)[1];
  typedef char (&yes_type)[2];
  template <typename U, void (U::*)() const>
  struct V
  {
  };
  template <typename U>
  static yes_type check(V<U, &U::Initialize>*);
  template <typename U>
  static no_type check(...);

public:
  static bool const value = sizeof(check<T>(0)) == sizeof(yes_type);
};

template <typename Functor, bool Init>
struct vtkSMPTools_FunctorInternal;

template <typename Functor>
struct vtkSMPTools_FunctorInternal<Functor, false>
{
  Functor& F;
  vtkSMPTools_FunctorInternal(Functor& f)
    : F(f)
  {
  }
  void Execute(vtkIdType first, vtkIdType last) { this->F(first, last); }
  void For(vtkIdType first, vtkIdType last, vtkIdType grain)
  {
    auto& SMPToolsAPI = vtkSMPToolsAPI::GetInstance();
    SMPToolsAPI.For(first, last, grain, *this);
  }
  vtkSMPTools_FunctorInternal<Functor, false>& operator=(
    const vtkSMPTools_FunctorInternal<Functor, false>&);
  vtkSMPTools_FunctorInternal(const vtkSMPTools_FunctorInternal<Functor, false>&);
};

template <typename Functor>
struct vtkSMPTools_FunctorInternal<Functor, true>
{
  Functor& F;
  vtkSMPThreadLocal<unsigned char> Initialized;
  vtkSMPTools_FunctorInternal(Functor& f)
    : F(f)
    , Initialized(0)
  {
  }
  void Execute(vtkIdType first, vtkIdType last)
  {
    unsigned char& inited = this->Initialized.Local();
    if (!inited)
    {
      this->F.Initialize();
      inited = 1;
    }
    this->F(first, last);
  }
  void For(vtkIdType first, vtkIdType last, vtkIdType grain)
  {
    auto& SMPToolsAPI = vtkSMPToolsAPI::GetInstance();
    SMPToolsAPI.For(first, last, grain, *this);
    this->F.Reduce();
  }
  vtkSMPTools_FunctorInternal<Functor, true>& operator=(
    const vtkSMPTools_FunctorInternal<Functor, true>&);
  vtkSMPTools_FunctorInternal(const vtkSMPTools_FunctorInternal<Functor, true>&);
};

template <typename Functor>
class vtkSMPTools_Lookup_For
{
  static bool const init = vtkSMPTools_Has_Initialize<Functor>::value;

public:
  typedef vtkSMPTools_FunctorInternal<Functor, init> type;
};

template <typename Functor>
class vtkSMPTools_Lookup_For<Functor const>
{
  static bool const init = vtkSMPTools_Has_Initialize_const<Functor>::value;

public:
  typedef vtkSMPTools_FunctorInternal<Functor const, init> type;
};

template <typename Iterator, typename Functor, bool Init>
struct vtkSMPTools_RangeFunctor;

template <typename Iterator, typename Functor>
struct vtkSMPTools_RangeFunctor<Iterator, Functor, false>
{
  Functor& F;
  Iterator& Begin;
  vtkSMPTools_RangeFunctor(Iterator& begin, Functor& f)
    : F(f)
    , Begin(begin)
  {
  }
  void operator()(vtkIdType first, vtkIdType last)
  {
    Iterator itFirst(Begin);
    std::advance(itFirst, first);
    Iterator itLast(itFirst);
    std::advance(itLast, last - first);
    this->F(itFirst, itLast);
  }
};

template <typename Iterator, typename Functor>
struct vtkSMPTools_RangeFunctor<Iterator, Functor, true>
{
  Functor& F;
  Iterator& Begin;
  vtkSMPTools_RangeFunctor(Iterator& begin, Functor& f)
    : F(f)
    , Begin(begin)
  {
  }
  void Initialize() { this->F.Initialize(); }
  void operator()(vtkIdType first, vtkIdType last)
  {
    Iterator itFirst(Begin);
    std::advance(itFirst, first);
    Iterator itLast(itFirst);
    std::advance(itLast, last - first);
    this->F(itFirst, itLast);
  }
  void Reduce() { this->F.Reduce(); }
};

template <typename Iterator, typename Functor>
class vtkSMPTools_Lookup_RangeFor
{
  static bool const init = vtkSMPTools_Has_Initialize<Functor>::value;

public:
  typedef vtkSMPTools_RangeFunctor<Iterator, Functor, init> type;
};

template <typename Iterator, typename Functor>
class vtkSMPTools_Lookup_RangeFor<Iterator, Functor const>
{
  static bool const init = vtkSMPTools_Has_Initialize_const<Functor>::value;

public:
  typedef vtkSMPTools_RangeFunctor<Iterator, Functor const, init> type;
};

template <typename T>
using resolvedNotInt = typename std::enable_if<!std::is_integral<T>::value, void>::type;
VTK_ABI_NAMESPACE_END
} // namespace smp
} // namespace detail
} // namespace vtk
#endif // DOXYGEN_SHOULD_SKIP_THIS

VTK_ABI_NAMESPACE_BEGIN
class VTKCOMMONCORE_EXPORT vtkSMPTools
{
public:

  template <typename Functor>
  static void For(vtkIdType first, vtkIdType last, vtkIdType grain, Functor& f)
  {
    typename vtk::detail::smp::vtkSMPTools_Lookup_For<Functor>::type fi(f);
    fi.For(first, last, grain);
  }

  template <typename Functor>
  static void For(vtkIdType first, vtkIdType last, vtkIdType grain, Functor const& f)
  {
    typename vtk::detail::smp::vtkSMPTools_Lookup_For<Functor const>::type fi(f);
    fi.For(first, last, grain);
  }


  template <typename Functor>
  static void For(vtkIdType first, vtkIdType last, Functor& f)
  {
    vtkSMPTools::For(first, last, 0, f);
  }

  template <typename Functor>
  static void For(vtkIdType first, vtkIdType last, Functor const& f)
  {
    vtkSMPTools::For(first, last, 0, f);
  }


  template <typename Iter, typename Functor>
  static vtk::detail::smp::resolvedNotInt<Iter> For(
    Iter begin, Iter end, vtkIdType grain, Functor& f)
  {
    vtkIdType size = std::distance(begin, end);
    typename vtk::detail::smp::vtkSMPTools_Lookup_RangeFor<Iter, Functor>::type fi(begin, f);
    vtkSMPTools::For(0, size, grain, fi);
  }

  template <typename Iter, typename Functor>
  static vtk::detail::smp::resolvedNotInt<Iter> For(
    Iter begin, Iter end, vtkIdType grain, Functor const& f)
  {
    vtkIdType size = std::distance(begin, end);
    typename vtk::detail::smp::vtkSMPTools_Lookup_RangeFor<Iter, Functor const>::type fi(begin, f);
    vtkSMPTools::For(0, size, grain, fi);
  }


  template <typename Iter, typename Functor>
  static vtk::detail::smp::resolvedNotInt<Iter> For(Iter begin, Iter end, Functor& f)
  {
    vtkSMPTools::For(begin, end, 0, f);
  }

  template <typename Iter, typename Functor>
  static vtk::detail::smp::resolvedNotInt<Iter> For(Iter begin, Iter end, Functor const& f)
  {
    vtkSMPTools::For(begin, end, 0, f);
  }

  static const char* GetBackend();

  static bool SetBackend(const char* backend);

  static void Initialize(int numThreads = 0);

  static int GetEstimatedNumberOfThreads();

  static int GetEstimatedDefaultNumberOfThreads();

  static void SetNestedParallelism(bool isNested);

  static bool GetNestedParallelism();

  static bool IsParallelScope();

  static bool GetSingleThread();

  struct Config
  {
    int MaxNumberOfThreads = 0;
    std::string Backend = vtk::detail::smp::vtkSMPToolsAPI::GetInstance().GetBackend();
    bool NestedParallelism = false;

    Config() = default;
    Config(int maxNumberOfThreads)
      : MaxNumberOfThreads(maxNumberOfThreads)
    {
    }
    Config(std::string backend)
      : Backend(backend)
    {
    }
    Config(bool nestedParallelism)
      : NestedParallelism(nestedParallelism)
    {
    }
    Config(int maxNumberOfThreads, std::string backend, bool nestedParallelism)
      : MaxNumberOfThreads(maxNumberOfThreads)
      , Backend(backend)
      , NestedParallelism(nestedParallelism)
    {
    }
#ifndef DOXYGEN_SHOULD_SKIP_THIS
    Config(vtk::detail::smp::vtkSMPToolsAPI& API)
      : MaxNumberOfThreads(API.GetInternalDesiredNumberOfThread())
      , Backend(API.GetBackend())
      , NestedParallelism(API.GetNestedParallelism())
    {
    }
#endif // DOXYGEN_SHOULD_SKIP_THIS
  };
  static constexpr vtkIdType THRESHOLD = 100000;

  template <typename T>
  static void LocalScope(Config const& config, T&& lambda)
  {
    auto& SMPToolsAPI = vtk::detail::smp::vtkSMPToolsAPI::GetInstance();
    SMPToolsAPI.LocalScope<vtkSMPTools::Config>(config, lambda);
  }

  template <typename InputIt, typename OutputIt, typename Functor>
  static void Transform(InputIt inBegin, InputIt inEnd, OutputIt outBegin, Functor transform)
  {
    auto& SMPToolsAPI = vtk::detail::smp::vtkSMPToolsAPI::GetInstance();
    SMPToolsAPI.Transform(inBegin, inEnd, outBegin, transform);
  }

  template <typename InputIt1, typename InputIt2, typename OutputIt, typename Functor>
  static void Transform(
    InputIt1 inBegin1, InputIt1 inEnd, InputIt2 inBegin2, OutputIt outBegin, Functor transform)
  {
    auto& SMPToolsAPI = vtk::detail::smp::vtkSMPToolsAPI::GetInstance();
    SMPToolsAPI.Transform(inBegin1, inEnd, inBegin2, outBegin, transform);
  }

  template <typename Iterator, typename T>
  static void Fill(Iterator begin, Iterator end, const T& value)
  {
    auto& SMPToolsAPI = vtk::detail::smp::vtkSMPToolsAPI::GetInstance();
    SMPToolsAPI.Fill(begin, end, value);
  }

  template <typename RandomAccessIterator>
  static void Sort(RandomAccessIterator begin, RandomAccessIterator end)
  {
    auto& SMPToolsAPI = vtk::detail::smp::vtkSMPToolsAPI::GetInstance();
    SMPToolsAPI.Sort(begin, end);
  }

  template <typename RandomAccessIterator, typename Compare>
  static void Sort(RandomAccessIterator begin, RandomAccessIterator end, Compare comp)
  {
    auto& SMPToolsAPI = vtk::detail::smp::vtkSMPToolsAPI::GetInstance();
    SMPToolsAPI.Sort(begin, end, comp);
  }

  template <typename RandomAccessIterator, typename ValueType>
  static ValueType ExclusiveScan(
    RandomAccessIterator begin, RandomAccessIterator end, ValueType init);
}; // vtkSMPTools

//------------------------------------------------------------------------------
// This templated method is defined here in vtkSMPTools.h, rather than in the
// backend implementation classes, because it leverages high-level
// vtkSMPTools methods (e.g., vtkSMPTools::For()) -- i.e., scan is not yet
// implemented in the backend classes. This may change as methods such as
// std::exclusive_scan become stable, and universally support parallel
// implementations. Further, this implementation has the benefit that it
// performs the scan operation in-place, not all backends (at this time)
// efficiently support in-place scans. (TODO: currently GCC does not perform
// in-place scan correctly [this is a known bug, fixed in GCC versions 14.3
// and 13.4 see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108236].
// Eventually, the sequential loops that follow below should be replaced with
// std::exclusive_scan().)
template <typename RandomAccessIterator, typename ValueType>
ValueType vtkSMPTools::ExclusiveScan(
  RandomAccessIterator begin, RandomAccessIterator end, ValueType init)
{
  // Compute the number of elements in the container.
  typename std::iterator_traits<RandomAccessIterator>::difference_type num =
    std::distance(begin, end);

  // Capture the last value before it is overwritten. It will be used to compute
  // the return value.
  ValueType retVal = *(end - 1);

  // It's best to perform a sequential scan for "smallish" data.
  if (vtkSMPTools::THRESHOLD > num)
  {
    ValueType val, sum = init;
    for (auto iter = begin; iter != end; ++iter)
    {
      val = *iter;
      *iter = sum;
      sum += val;
    }
  }

  // Otherwise, threaded computation
  else
  {
    // Perform the parallel scan using two vtkSMPTools::For() passes. The
    // first for loop sums values across batches of elements. Then a
    // subsequent sequential summation across the resulting batches
    // determines the initial, offset sum for each batch. Finally the second
    // vtkSMPTools::For loop updates the sums across all batches. These
    // operations are performed in-place. The number of batches is set to
    // a small multiple of the number of threads. Empirically, a multiple
    // of 2-4 times the number of threads works well.
    int numBatches = 4 * vtkSMPTools::GetEstimatedNumberOfThreads();
    std::vector<ValueType> batchOffsets(numBatches);
    int batchSize = static_cast<int>(std::ceil(static_cast<double>(num) / numBatches));

    // First pass: sum across batches.
    vtkSMPTools::For(0, numBatches,
      [&](int batchId, vtkIdType endBatchId)
      {
        auto beginBatch = begin + (batchId * batchSize);
        auto endBatch = begin + (endBatchId * batchSize);
        endBatch = (endBatch > end ? end : endBatch);

        ValueType val, sum{}; // sum initialized to 0 (built-in type); or default constructed
        for (auto iter = beginBatch; iter < endBatch; ++iter)
        {
          val = *iter;
          *iter = sum;
          sum += val;
        }
        batchOffsets[batchId] = sum;
      }); // end lambda

    // Perform a sequential, in-place prefix sum across each batch to create
    // the batch offsets. The initial value of the scan, init, is added in
    // here.
    ValueType val, count = init;
    for (int batchNum = 0; batchNum < numBatches; ++batchNum)
    {
      val = batchOffsets[batchNum];
      batchOffsets[batchNum] = count;
      count += val;
    }

    // Now add batch offsets to all entries to produce the prefix sum.
    vtkSMPTools::For(0, numBatches,
      [&](int batchId, vtkIdType endBatchId)
      {
        auto beginBatch = begin + (batchId * batchSize);
        auto endBatch = begin + (endBatchId * batchSize);
        endBatch = (endBatch > end ? end : endBatch);

        ValueType offset = batchOffsets[batchId];
        for (auto iter = beginBatch; iter < endBatch; ++iter)
        {
          *iter += offset;
        }
      }); // end lambda
  } // threaded scan

  return (retVal += *(end - 1));
} // ExclusiveScan()

VTK_ABI_NAMESPACE_END
#endif
// VTK-HeaderTest-Exclude: vtkSMPTools.h