lazy.h

Go to the documentation of this file.

// ------------------------------------------------------------------------
//
// SPDX-License-Identifier: LGPL-2.1-or-later
// Copyright (C) 2023 - 2024 by the deal.II authors
//
// This file is part of the deal.II library.
//
// Part of the source code is dual licensed under Apache-2.0 WITH
// LLVM-exception OR LGPL-2.1-or-later. Detailed license information
// governing the source code and code contributions can be found in
// LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
//
// ------------------------------------------------------------------------
 
#ifndef dealii_lazy_h
#define dealii_lazy_h
 
 
#include <deal.II/base/config.h>
 
#include <deal.II/base/exceptions.h>
#include <deal.II/base/memory_consumption.h>
#include <deal.II/base/mutex.h>
#include <deal.II/base/task_result.h>
 
#include <atomic>
#include <mutex>
#include <optional>
#include <type_traits>
 
 
DEAL_II_NAMESPACE_OPEN
 
template <typename T>
DEAL_II_CXX20_REQUIRES((std::is_move_constructible_v<T> &&
                        std::is_move_assignable_v<T>))
class Lazy
{
public:
  Lazy();
 
 
  Lazy(const Lazy &other);
 
 
  Lazy(Lazy &&other) noexcept;
 
 
  Lazy &
  operator=(const Lazy &other);
 
 
  Lazy &
  operator=(Lazy &&other) noexcept;
 
 
  void
  reset() noexcept;
 
 
  template <typename Callable>
  void
  ensure_initialized(const Callable &creator) const
    DEAL_II_CXX20_REQUIRES((std::is_invocable_r_v<T, Callable>));
 
 
  bool
  has_value() const;
 
 
  const T &
  value() const;
 
 
  template <typename Callable>
  const T &
  value_or_initialize(const Callable &creator) const
    DEAL_II_CXX20_REQUIRES((std::is_invocable_r_v<T, Callable>));
 
  std::size_t
  memory_consumption() const;
 
private:
  mutable Threads::TaskResult<T> task_result;
 
 
  mutable std::atomic<bool> object_is_initialized;
};
 
// ------------------------------- inline functions --------------------------
 
#ifndef DOXYGEN
 
template <typename T>
DEAL_II_CXX20_REQUIRES((std::is_move_constructible_v<T> &&
                        std::is_move_assignable_v<T>))
inline Lazy<T>::Lazy()
  : object_is_initialized(false)
{}
 
 
 
template <typename T>
DEAL_II_CXX20_REQUIRES((std::is_move_constructible_v<T> &&
                        std::is_move_assignable_v<T>))
inline Lazy<T>::Lazy(const Lazy &other)
{
  // If the other object has a value stored, then get it and set our
  // own object to a copy of it:
  if (other.has_value())
    {
      object_is_initialized.store(true);
      task_result.emplace_object(other.value());
    }
  else
    object_is_initialized.store(false);
}
 
 
 
template <typename T>
DEAL_II_CXX20_REQUIRES((std::is_move_constructible_v<T> &&
                        std::is_move_assignable_v<T>))
inline Lazy<T>::Lazy(Lazy &&other) noexcept
  : task_result(std::move(other.task_result))
{
  object_is_initialized.store(other.object_is_initialized.load());
 
  // Mark the other object as uninitialized.
  other.object_is_initialized.store(false);
}
 
 
 
template <typename T>
DEAL_II_CXX20_REQUIRES((std::is_move_constructible_v<T> &&
                        std::is_move_assignable_v<T>))
inline Lazy<T> &Lazy<T>::operator=(const Lazy &other)
{
  // If the other object has a value stored, then get it and set our
  // own object to a copy of it:
  if (other.has_value())
    {
      object_is_initialized.store(true);
      task_result.emplace_object(other.value());
    }
  else
    {
      object_is_initialized.store(false);
      task_result.clear();
    }
 
  return *this;
}
 
 
 
template <typename T>
DEAL_II_CXX20_REQUIRES((std::is_move_constructible_v<T> &&
                        std::is_move_assignable_v<T>))
inline Lazy<T> &Lazy<T>::operator=(Lazy &&other) noexcept
{
  task_result = std::move(other.task_result);
  object_is_initialized.store(other.object_is_initialized.load());
 
  // Mark the other object as uninitialized.
  other.object_is_initialized.store(false);
 
  return *this;
}
 
 
 
template <typename T>
DEAL_II_CXX20_REQUIRES((std::is_move_constructible_v<T> &&
                        std::is_move_assignable_v<T>))
inline void Lazy<T>::reset() noexcept
{
  object_is_initialized.store(false);
  task_result.clear();
}
 
 
template <typename T>
DEAL_II_CXX20_REQUIRES((std::is_move_constructible_v<T> &&
                        std::is_move_assignable_v<T>))
template <typename Callable>
inline DEAL_II_ALWAYS_INLINE
  void Lazy<T>::ensure_initialized(const Callable &creator) const
  DEAL_II_CXX20_REQUIRES((std::is_invocable_r_v<T, Callable>))
{
  //
  // Use Schmidt's double checking [1] for checking and initializing the
  // object.
  //
  // [1] https://en.wikipedia.org/wiki/Double-checked_locking
  //
 
  //
  // Check the object_is_initialized atomic with "acquire" semantics [1].
  //
  // This ensures that (a) all subsequent reads (of the object) are
  // ordered after this check, and that (b) all writes to the object
  // before the atomic bool was set to true with "release" semantics are
  // visible on this thread.
  //
  // [1]
  // https://en.cppreference.com/w/cpp/atomic/memory_order#Release-Acquire_ordering
  //
  if (!object_is_initialized.load(std::memory_order_acquire))
#  ifdef DEAL_II_HAVE_CXX20
    [[unlikely]]
#  endif
    {
      // Check again. If this thread won the race to the lock then we
      // would like to initialize the object. Otherwise another thread has
      // already initialized the object and flipped the object_is_initialized
      // bit. (Here, the initialization_mutex ensures consistent ordering
      // with a memory fence, so we will observe the updated bool without
      // acquire semantics.)
      //
      // Naively, we should think that we can check again for
      // object_is_initialized to be true, and if it is false just execute
      // the 'creator' function object. The problem with this approach is that
      // if we have N worker threads and spawn N+1 tasks that all want to
      // end querying the Lazy object, then N will be run right away of which
      // N-1 will block. The one remaining task will have gotten into the
      // locked section and run the 'creator' object. But if the 'creator'
      // itself spawns tasks, the scheduler may decide to first execute
      // the (N+1)st task from above which will then promptly get stuck
      // here as well -- and we're in a deadlock situation.
      //
      // The solution to the problem is to use a scheme whereby the
      // work we do in setting up 'creator' cannot block, and where we block
      // below is in a context where it's the *scheduler* that blocks to ensure
      // that it can continue to schedule tasks.
      //
      // This is what TaskResult::try_emplace_task() does:
      if (!object_is_initialized.load(std::memory_order_relaxed))
        task_result.try_emplace_task(creator);
 
      // At this point, either this or another thread have emplaced a
      // task and we wait for it to complete. If we do need to wait, then
      // the waiting happens in the task scheduler, which can run other
      // tasks in the meantime, ensuring progress:
      task_result.join();
 
      // At this point, we know that the task has completed (whether set by
      // this or another thread), and we can flip the object_is_initialized
      // boolean with "release" semantics [1].
      //
      // This ensures that the above move is visible on all threads
      // before checking the atomic bool with acquire semantics.
      // If another thread that had also been waiting in the join() call
      // above has gotten here first and set the flag to 'true', that
      // ok.
      object_is_initialized.store(true, std::memory_order_release);
    }
 
  Assert(has_value(),
         ExcMessage("The current object does not contain a valid object "
                    "even though we have just initialized it."));
}
 
 
template <typename T>
DEAL_II_CXX20_REQUIRES((std::is_move_constructible_v<T> &&
                        std::is_move_assignable_v<T>))
inline DEAL_II_ALWAYS_INLINE bool Lazy<T>::has_value() const
{
  //
  // In principle it would be sufficient to solely check the atomic<bool>
  // object_is_initialized because the load() is performed with "acquire"
  // semantics. But just in case let's check the object.has_value() boolean
  // as well:
  //
  return (object_is_initialized && (task_result.empty() == false));
}
 
 
template <typename T>
DEAL_II_CXX20_REQUIRES((std::is_move_constructible_v<T> &&
                        std::is_move_assignable_v<T>))
inline DEAL_II_ALWAYS_INLINE const T &Lazy<T>::value() const
{
  Assert(
    has_value(),
    ExcMessage(
      "value() has been called but the contained object has not been "
      "initialized. Did you forget to call 'ensure_initialized()' first?"));
 
  return task_result.value();
}
 
 
template <typename T>
DEAL_II_CXX20_REQUIRES((std::is_move_constructible_v<T> &&
                        std::is_move_assignable_v<T>))
template <typename Callable>
inline DEAL_II_ALWAYS_INLINE const T &Lazy<T>::value_or_initialize(
  const Callable &creator) const
  DEAL_II_CXX20_REQUIRES((std::is_invocable_r_v<T, Callable>))
{
  ensure_initialized(creator);
  return task_result.value();
}
 
 
template <typename T>
DEAL_II_CXX20_REQUIRES((std::is_move_constructible_v<T> &&
                        std::is_move_assignable_v<T>))
std::size_t Lazy<T>::memory_consumption() const
{
  return MemoryConsumption::memory_consumption(task_result) + //
         sizeof(*this) - sizeof(task_result);
}
 
#endif
 
DEAL_II_NAMESPACE_CLOSE
#endif