depspawn.h

/*
 DepSpawn: Data Dependent Spawn library
 Copyright (C) 2012-2023 Carlos H. Gonzalez, Basilio B. Fraguela. Universidade da Coruna
 
 Distributed under the MIT License. (See accompanying file LICENSE)
*/
 
 
#ifndef __DEPSPAWN_H
#define __DEPSPAWN_H
 
#include <functional>
#include <type_traits>
#include <utility>
#include <boost/function_types/function_arity.hpp>
#include <boost/function_types/parameter_types.hpp>
#include <boost/function.hpp>
#include <boost/mpl/begin.hpp>
#include <boost/mpl/next.hpp>
#include <boost/mpl/deref.hpp>
#include <atomic>
#include "depspawn/fixed_defines.h"
 
#ifdef BZ_ARRAY_H
#ifndef DEPSPAWN_BLITZ
#error Only the Blitz++ version released with DepSpawn can be used with DepSpawn
#endif
#endif
 
#ifdef DEPSPAWN_USE_TBB
#include <tbb/task.h>
#endif
 
// Also included when DEPSPAWN_USE_TBB for the sake of get_task_pool() and TaskPool::Task::run
#include "depspawn/TaskPool.h"
 
 
#ifndef DEPSPAWN_SCALABLE_POOL
#define DEPSPAWN_SCALABLE_POOL false
#endif
 
#ifdef WIN32
#include <windows.h>
#else
#include <unistd.h>
#endif
 
#ifdef DEPSPAWN_DUMMY_POOL
#include "depspawn/DummyLinkedListPool.h"
#else
#include "depspawn/LinkedListPool.h"
#endif
 
namespace depspawn {
  
  
  
  template<typename T>
  class Ignore {
  
    T t_;
  
  public:
    
    Ignore(T& t) :
    t_(t)
    {}
    
    Ignore<T> operator= (const T& other) {
      t_ = other;
      return *this;
    }
    
    operator T&() {
      return t_;
    }
    
    /* Formerly used in ref<Ignore<T>&&>::make(Ignore<T>& t)
       Now replaced by the conversion operator
    T& operator*() {
      return t_;
    }
    
    const T& operator*() const {
      return t_;
    }
    */
    
    void *addr() const { return (void *)&t_; }
  };
  
  template<typename T>
  inline Ignore<T> ignore(T&& t) {
    return Ignore<T>(std::forward<T>(t));
  }
  
 
  namespace internal {
    
#ifdef DEPSPAWN_DUMMY_POOL
    template<typename T, bool SCALABLE>
    using Pool_t = DummyLinkedListPool<T, SCALABLE>;
#else
    template<typename T, bool SCALABLE>
    using Pool_t = LinkedListPool<T, true, SCALABLE>;
#endif
    
    
    template<typename MembFuncPtr>
    struct memb_func_traits
    {};
    
    template< typename ClassT, typename R, typename... Arg>
    struct memb_func_traits<R ClassT::* (Arg...)>
    {
      typedef ClassT class_type;
      typedef R signature (Arg...);
    };
    
    template< typename ClassT, typename R, typename... Arg>
    struct memb_func_traits<R (ClassT::*) (Arg...) const>
    {
      typedef ClassT class_type;
      typedef R signature (Arg...);
    };
    
    template<typename F>
    struct function_type {
      typedef typename memb_func_traits<decltype(&F::operator())>::signature signature;
      typedef std::function<signature> type;
    };
    
    /* For pointer to member function spawn in Apple clang. 
       We choose ClassT& for the std::function 1st arg */
    template<typename ClassT, typename R, typename... Arg>
    struct function_type<R (ClassT::*) (Arg...)> {
      typedef R signature (ClassT&, Arg...);
      typedef std::function<signature> type;
    };
 
    /* For pointer to member function spawn in Apple clang.
       We choose ClassT& for the std::function 1st arg */
    template<typename ClassT, typename R, typename... Arg>
    struct function_type<R (ClassT::*) (Arg...) const> {
      typedef R signature (const ClassT&, Arg...);
      typedef std::function<signature> type;
    };
    
    template<typename F>
    typename function_type<F>::type make_function(F && f)
    {
      typedef typename function_type<F>::type result_type;
      return result_type(std::forward<F>(f));
    }
    
 
    template<typename T>
    struct is_function_object :public std::false_type {};
    
    template<typename T>
    struct is_function_object<std::function<T>> : public std::true_type {};
    
    template<typename T>
    struct is_function_object<boost::function<T>> : public std::true_type {};
 
    
    
    
    template <typename T>
    struct ParameterTypes {
      using intl_type = typename function_type<T>::signature;
      using type = typename ParameterTypes<intl_type>::type;
    };
    
    template <typename T>
    struct ParameterTypes<T&> {
      using type = typename ParameterTypes<T>::type;
    };
    
    template<typename R, typename... Types>
    struct ParameterTypes<R(Types...)> {
      using type = boost::function_types::parameter_types<R(Types...)>;
    };
    
    template<typename Function>
    struct ParameterTypes<std::function<Function>> {
      using type = boost::function_types::parameter_types<Function>;
    };
    
    template<typename Function>
    struct ParameterTypes<boost::function<Function>> {
      using type = boost::function_types::parameter_types<Function>;
    };
    
    template<typename R, typename... Types>
    struct ParameterTypes<R (&) (Types...)> {
      using type = boost::function_types::parameter_types<R(Types...)>;
    };
    
    template <typename R, typename C, typename... Types>
    struct ParameterTypes<R (C::*)(Types...)> {
      using type = boost::function_types::parameter_types<R(C&, Types...)>;
    };
    
    template <typename R, typename C, typename... Types>
    struct ParameterTypes<R (C::*)(Types...) const> {
      using type = boost::function_types::parameter_types<R(C&, Types...)>;
    };
    
 
    typedef size_t value_t;
    
    typedef std::pair<int, int> array_range_t;
    
    template<typename T>
    struct is_blitz_array : public std::false_type {};
    
    struct arg_info {
      value_t addr;                
      size_t size;                 
      array_range_t* array_range;  
      arg_info* next;              
      bool wr;                     
      char rank;                   
 
      void insert_in_arglist(arg_info*& args);
      
      void solve_overlap(arg_info *other);
      
      bool overlap_array(const arg_info *other) const;
      
      bool is_contained_array(const arg_info *other) const;
 
      bool is_array() const { return rank != 0; }
 
#ifdef DEPSPAWN_BLITZ
      template<typename T>
      inline typename std::enable_if< is_blitz_array<T>::value >::type fill_in_array(const T& a) {
        addr = (value_t)a.block();
        const auto& storage = a.storage();
        rank = storage.originalDims();
        array_range = new array_range_t[rank];
        const blitz::TinyVector<int, 2> * const extent = storage.extent();
        for(int i = 0; i < rank; i++) {
          array_range[i] = std::make_pair(extent[i][0], extent[i][1]);
        }
      }
#endif
 
      template<typename T>
      inline typename std::enable_if< ! is_blitz_array<T>::value >::type fill_in_array(const T& a) {
        addr        = (value_t)&a;
        rank        = 0;
        array_range = nullptr;
      }
 
      static Pool_t<arg_info, DEPSPAWN_SCALABLE_POOL> Pool;
 
    };
    
    
    template<typename T>
    struct ref {
      static inline auto make(T& t) -> decltype(std::ref(t)) {
    return std::ref(t);
      }
    };
    
    template<typename T>
    struct ref<T&&> {
      static inline T& make(T& t) {
    return t;
      }
    };
    
    template<typename T>
    struct ref<Ignore<T>&&> {
      static inline auto make(Ignore<T>& t) -> decltype(std::ref((T&)t)) {
    return std::ref((T&)t);
      }
    };
 
#ifdef DEPSPAWN_BLITZ
    template<typename type, int dim>
    struct ref<blitz::Array<type, dim>&&> {
      static inline blitz::Array<type, dim> make(blitz::Array<type, dim>& __t) {
    return __t;
      }
    };
    
    template<typename type, int dim>
    struct ref<blitz::Array<type, dim>&> {
      static inline blitz::Array<type, dim> make(blitz::Array<type, dim>& __t) {
    return __t;
      }
    };
    
    template<typename type, int dim>
    struct ref<const blitz::Array<type, dim>&> {
      static inline const blitz::Array<type, dim> make(const blitz::Array<type, dim>& __t) {
    return __t;
      }
    };
    
    template<typename type, int dim>
    struct ref<const blitz::Array<type, dim>> {
      static inline const blitz::Array<type, dim> make(const blitz::Array<type, dim>& __t) {
    return __t;
      }
    };
#endif // DEPSPAWN_BLITZ
    
    
    
    template<typename T>
    struct is_ignored {
      static const bool value = false;
    };
    
    template<typename T>
    struct is_ignored<Ignore<T>&&> {
      static const bool value = true;
    };
    
 
#ifdef DEPSPAWN_USE_TBB
    extern tbb::task* volatile master_task;
 
    struct AbstractBoxedFunction;
    struct AbstractRunner;
#else
    extern TaskPool * volatile TP;
    using AbstractRunner = TaskPool::Task;
#endif
 
    extern bool EnqueueTasks;
 
  } //namespace  internal
 
} //namespace depspawn
 
 
#include "depspawn/workitem.h"
 
namespace depspawn {
  
  namespace internal {
  
    extern thread_local Workitem * enum_thr_spec_father;
 
    extern void start_master();
    
    extern void common_wait_for(arg_info *pargs, int nargs);
 
#ifdef DEPSPAWN_USE_TBB
 
    struct AbstractBoxedFunction {
      
      Workitem* ctx_; 
      
      AbstractBoxedFunction(Workitem* ctx)
      : ctx_(ctx)
      {}
      
      void run_in_env(bool from_wait);
  
      virtual ~AbstractBoxedFunction() {}
      
    protected:
      
      virtual void run() = 0;
    };
    
    template<typename Function>
    struct BoxedFunction : public AbstractBoxedFunction {
      
      Function f_; 
      
      BoxedFunction(Workitem* ctx, Function&& f)
      : AbstractBoxedFunction(ctx), f_(std::move(f))
      {}
    
      virtual ~BoxedFunction() {}
      
    protected:
      
      void run() final {
        f_();
      }
    
    };
    
    struct AbstractRunner : public tbb::task {
 
      std::atomic<Workitem *> ctx_; 
      
      AbstractRunner(Workitem * ctx)
      : ctx_(ctx)
      { }
 
      virtual AbstractBoxedFunction * steal(Workitem *ctx) = 0;
      
      virtual ~AbstractRunner() {}
    };
 
    template<typename Function>
    struct runner : public AbstractRunner {
 
      Function f_; 
      
      template<typename InputFunction, typename... Args>
      runner(Workitem* ctx, const InputFunction& f, Args&&... args)
      : AbstractRunner(ctx), f_(std::bind(f, internal::ref<Args&&>::make(args)...))
      { }
      
      AbstractBoxedFunction * steal(Workitem *ctx) final {
        //Danger: ctx_ could have been already nullified by execute()
        //so the stealer sends it just in case
        return new BoxedFunction<Function>(ctx, std::move(f_));
      }
  
      tbb::task* execute() 
      {
        Workitem * const ctx_copy = ctx_.exchange(nullptr);
        
        if (ctx_copy != nullptr) {
          
          if (!ctx_copy->guard_.fetch_add(1)) {
            
            ctx_copy->status = Workitem::Status_t::Running;
            
            Workitem *& ref_father_lcl = enum_thr_spec_father;
            ref_father_lcl = ctx_copy;
            
            f_();
            
            //BBF: in case father thread runs a task.
            //Should be farther checked
            ref_father_lcl = nullptr;
            
            ctx_copy->finish_execution();
            
          } else {
            while (ctx_copy->guard_ < 3) { } //Wait for new BoxedFunction to be built
            ctx_copy->guard_ = 4; // Notify we are leaving
          }
          
        }
 
        //set_ref_count(1);
    
        return nullptr;
      }
  
      virtual ~runner() {}
  
    };
#endif
 
    template<typename T_it>
    int fill_args(arg_info*&) { return 0; }
 
    template<typename T_it, typename Head, typename... Tail>
    int fill_args(arg_info*& args, Head&& h, Tail&&... t) {
      typedef typename boost::mpl::deref<T_it>::type curr_t;    //Formal parameter type
      constexpr bool is_reference = std::is_reference<curr_t>::value;
      typedef typename std::remove_reference<curr_t>::type deref_t;
      constexpr bool is_const = std::is_const<deref_t>::value;
      constexpr bool is_writable = is_reference && !is_const;
      constexpr bool is_barray = is_blitz_array<typename std::remove_const<typename std::remove_reference<Head>::type>::type>::value;
      constexpr int process_argument =
      !is_ignored<curr_t&&>::value &&
      !is_ignored<Head&&>::value &&
      !(std::is_rvalue_reference<Head&&>::value && !is_barray);
      
      if(process_argument) {
    
        arg_info* n = arg_info::Pool.malloc();
    n->size = sizeof(Head);
    n->wr = is_writable;
    n->next = nullptr;
    n->fill_in_array(h);
    
    // Insert new_arg (n) in order
    n->insert_in_arglist(args);
      }
      
      return process_argument + fill_args<typename boost::mpl::next<T_it>::type>(args, std::forward<Tail>(t)...);
    }
 
typedef void spawn_ret_t;
 
  } //namespace internal
 
extern void set_task_queue_limit(int limit) noexcept;
 
extern int get_task_queue_limit() noexcept;
 
extern void set_threads(int nthreads = -1);
 
extern int get_num_threads() noexcept;
 
extern internal::TaskPool& get_task_pool();
 
#ifdef SEQUENTIAL_DEPSPAWN
 
#define spawn(f, ...) f(__VA_ARGS__)
 
#else
 
  template<typename Function, typename... Args>
  inline internal::spawn_ret_t spawn(const Function& f, Args&&... args) {
    using parameter_types = typename internal::ParameterTypes<Function>::type;
 
    internal::arg_info *pargs = nullptr;
    const int nargs = internal::fill_args<typename boost::mpl::begin<parameter_types>::type>(pargs, std::forward<Args>(args)...);
 
#ifdef DEPSPAWN_USE_TBB
    if(!internal::master_task)
      internal::start_master();
    
    internal::Workitem* w = internal::Workitem::Pool.malloc(pargs, nargs);
    w->insert_in_worklist(new (tbb::task::allocate_additional_child_of(*internal::master_task)) internal::runner<decltype(std::bind(f, internal::ref<Args&&>::make(args)...))>(w, f, std::forward<Args>(args)...));
#else
    if(!internal::TP || !internal::TP->is_running())
      internal::start_master();
    
    internal::Workitem* w = internal::Workitem::Pool.malloc(pargs, nargs);
    w->insert_in_worklist(internal::TP->build_task(w, f, internal::ref<Args&&>::make(args)...));
#endif
  }
  
  template<typename T, typename... Args>
  typename std::enable_if< std::is_reference<T>::value &&
                         ! std::is_member_function_pointer<typename std::remove_reference<T>::type>::value &&
                         ! std::is_function<typename std::remove_reference<T>::type>::value &&
                         ! internal::is_function_object<typename std::remove_reference<T>::type>::value,
                           internal::spawn_ret_t >::type
  spawn(T&& functor, Args&&... args) {
    using base_type = typename std::remove_reference<T>::type;
    return spawn(& base_type::operator(), std::forward<T>(functor), std::forward<Args>(args)...);
  }
 
  
#endif // SEQUENTIAL_DEPSPAWN
 
  void wait_for_all();
 
  void wait_for_subtasks(bool priority = true);
 
  template<typename... Args>
  void wait_for(const Args&... args) {
 
#ifdef DEPSPAWN_USE_TBB
    if(!internal::master_task) //There should be nothing to wait for
#else
    if(!internal::TP || !internal::TP->is_running()) //There should be nothing to wait for
#endif
      return;
    
    typedef void Function(const Args&... args);
    //std::function<Function> f = [](const Args&... args) { std::cout << "EXEC!\n"; };
    typedef boost::function_types::parameter_types<Function> parameter_types;
    internal::arg_info *pargs = nullptr;
    const int nargs = internal::fill_args<typename boost::mpl::begin<parameter_types>::type>(pargs, args...);
 
    internal::common_wait_for(pargs, nargs);
  }
 
  class Observer {
    
    internal::Workitem * const limit_;
    
    internal::Workitem * const cur_father_;
    
    const bool priority_;
    
    Observer(bool priority, internal::Workitem *w);
    
    friend void wait_for_subtasks(bool priority);
    
  public:
    
    Observer(bool priority = true);
    
    ~Observer();
    
  };
 
/* This helps expand __LINE__ so that each Observer has a different variable name,
   although this does not happen if we put two depspawn_sync in the same line.
   But this does not matter because they would be necessaritly nested, so actuallly
   all the depspawn_sync could have exactly the same name. This looks just nicer. */
#define depspawnBottomTOKENPASTE(x, y) x ## y
#define depspawnTOKENPASTE(x, y) depspawnBottomTOKENPASTE(x, y)
 
#define depspawn_sync(...) { depspawn::Observer depspawnTOKENPASTE(__depspawn_temporary, __LINE__);\
                             {__VA_ARGS__;} }
 
#ifdef DEPSPAWN_BLITZ
 
  template<typename F>
  void for_range(const blitz::Range& r, const F& f, int bs = -1) {
    const int num_threads = get_num_threads();
    
    if(bs == -1) bs = (r.length() + num_threads - 1) / (num_threads);
    int lbs;
    int i;
    for(i = r.first(); i < r.last(); i+=bs) {
      lbs = r.last() -i +1 <= bs ? r.last() -i +1 : bs;
      f(blitz::Range(i, i+lbs-1));
    }
  }
  
  template<typename F>
  void for_range(const blitz::Range& r1, const blitz::Range& r2, const F& f, int bs1 = -1, int bs2 = -1) {
    const int num_threads = get_num_threads();
 
    if(bs1 == -1) {
      bs1 = (r1.length()  + num_threads - 1) / (num_threads);
    }
    if(bs2 == -1) {
      bs2 = (r2.length() + num_threads - 1) / (num_threads);
    }
    int lbs1, lbs2;
    int i, j;
    for(i = r1.first(); i < r1.last(); i+=bs1) {
      lbs1 = r1.last() -i +1 <= bs1 ? r1.last() -i +1 : bs1;
      for(j = r2.first(); j < r2.last(); j+=bs2) {
    lbs2 = r2.last() -j +1 <= bs2 ? r2.last() -j +1 : bs2;
    f(blitz::Range(i, i+lbs1-1), blitz::Range(j, j+lbs2-1));
      }
    }
  }
 
#endif // DEPSPAWN_BLITZ
 
} //namespace depspawn
 
 
#ifdef DEPSPAWN_BLITZ
 
#define DEFINE_NEW_ARRAY_TYPE(type, dim) \
namespace depspawn { \
  namespace internal { \
    template<> \
    struct is_blitz_array<blitz::Array<type, dim>> : public std::true_type {}; \
  }; \
};
 
DEFINE_NEW_ARRAY_TYPE(int, 1);
DEFINE_NEW_ARRAY_TYPE(int, 2);
DEFINE_NEW_ARRAY_TYPE(int, 3);
DEFINE_NEW_ARRAY_TYPE(int, 4);
DEFINE_NEW_ARRAY_TYPE(unsigned int, 1);
DEFINE_NEW_ARRAY_TYPE(unsigned int, 2);
DEFINE_NEW_ARRAY_TYPE(unsigned int, 3);
DEFINE_NEW_ARRAY_TYPE(unsigned int, 4);
DEFINE_NEW_ARRAY_TYPE(unsigned long long, 1);
DEFINE_NEW_ARRAY_TYPE(unsigned long long, 2);
DEFINE_NEW_ARRAY_TYPE(unsigned long long, 3);
DEFINE_NEW_ARRAY_TYPE(unsigned long long, 4);
DEFINE_NEW_ARRAY_TYPE(long long, 1);
DEFINE_NEW_ARRAY_TYPE(long long, 2);
DEFINE_NEW_ARRAY_TYPE(long long, 3);
DEFINE_NEW_ARRAY_TYPE(long long, 4);
DEFINE_NEW_ARRAY_TYPE(float, 1);
DEFINE_NEW_ARRAY_TYPE(float, 2);
DEFINE_NEW_ARRAY_TYPE(float, 3);
DEFINE_NEW_ARRAY_TYPE(float, 4);
DEFINE_NEW_ARRAY_TYPE(double, 1);
DEFINE_NEW_ARRAY_TYPE(double, 2);
DEFINE_NEW_ARRAY_TYPE(double, 3);
DEFINE_NEW_ARRAY_TYPE(double, 4);
DEFINE_NEW_ARRAY_TYPE(long double, 1);
DEFINE_NEW_ARRAY_TYPE(long double, 2);
DEFINE_NEW_ARRAY_TYPE(long double, 3);
DEFINE_NEW_ARRAY_TYPE(long double, 4);
#endif // DEPSPAWN_BLITZ
 
 
#endif // __DEPSPAWN_H