| /* reducer.h -*- C++ -*- |
| * |
| * @copyright |
| * Copyright (C) 2009-2013, Intel Corporation |
| * All rights reserved. |
| * |
| * @copyright |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * |
| * * Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * * Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in |
| * the documentation and/or other materials provided with the |
| * distribution. |
| * * Neither the name of Intel Corporation nor the names of its |
| * contributors may be used to endorse or promote products derived |
| * from this software without specific prior written permission. |
| * |
| * @copyright |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, |
| * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, |
| * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS |
| * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED |
| * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
| * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY |
| * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
| * POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| /** @file reducer.h |
| * |
| * @brief Defines foundation classes for creating Cilk reducers. |
| * |
| * @ingroup Reducers |
| * |
| * @see @ref pagereducers |
| * |
| * @defgroup Reducers Reducers |
| */ |
| |
| #ifndef REDUCER_H_INCLUDED |
| #define REDUCER_H_INCLUDED |
| |
| #include "cilk/hyperobject_base.h" |
| #include "cilk/metaprogramming.h" |
| |
| #ifdef __cplusplus |
| |
| //===================== C++ interfaces =================================== |
| |
| #include <new> |
| |
| namespace cilk { |
| |
| /** Base class for defining monoids. |
| * |
| * The monoid_base class template is useful for creating classes that model |
| * the monoid concept. It provides the core type and memory management |
| * functionality. A subclass of monoid_base need only declare and implement |
| * the `identity` and `reduce` functions. |
| * |
| * The monoid_base class also manages the integration between the monoid, the |
| * reducer class that is based on it, and an optional view class which wraps |
| * value objects and restricts access to their operations. |
| * |
| * @tparam Value The value type for the monoid. |
| * @tparam View An optional view class that serves as a proxy for the value |
| * type. |
| * |
| * @see monoid_with_view |
| */ |
| template <typename Value, typename View = Value> |
| class monoid_base |
| { |
| protected: |
| |
| /** Class for provisionally constructed objects. |
| * |
| * The monoid_base::construct() functions manually construct both a monoid |
| * and a view. If one of these is constructed successfully, and the |
| * construction of the other (or some other initialization) fails, then |
| * the first one must be destroyed to avoid a memory leak. Because the |
| * construction is explicit, the destruction must be explicit, too. |
| * |
| * A provisional_guard object wraps a pointer to a newly constructed |
| * object. A call to its confirm() function confirms that the object is |
| * really going to be used. If the guard is destroyed without being |
| * confirmed, then the pointed-to object is destroyed (but not |
| * deallocated). |
| * |
| * Expected usage: |
| * |
| * provisional_guard<T1> x1_provisional( new (x1) T1() ); |
| * … more initialization … |
| * x1_provisional.confirm(); |
| * |
| * or |
| * |
| * provisional_guard<T1> x1_provisional( new (x1) T1() ); |
| * x1_provisional.confirm_if( new (x2) T2() ); |
| * |
| * If an exception is thrown in the “more initialization” code in the |
| * first example, or in the `T2` constructor in the second example, then |
| * `x1_provisional` will not be confirmed, so when its destructor is |
| * called during exception unwinding, the `T1` object that was constructed |
| * in `x1` will be destroyed. |
| * |
| * @see provisional() |
| * |
| * @tparam Type The type of the provisionally constructed object. |
| */ |
| template <typename Type> |
| class provisional_guard { |
| Type* m_ptr; |
| |
| public: |
| |
| /** Constructor. Creates a guard for a provisionally constructed object. |
| * |
| * @param ptr A pointer to the provisionally constructed object. |
| */ |
| provisional_guard(Type* ptr) : m_ptr(ptr) {} |
| |
| /** Destructor. Destroy the object pointed to by the contained pointer |
| * if it has not been confirmed. |
| */ |
| ~provisional_guard() { if (m_ptr) m_ptr->~Type(); } |
| |
| /** Confirm the provisional construction. Do *not* delete the contained |
| * pointer when the guard is destroyed. |
| */ |
| void confirm() { m_ptr = 0; } |
| |
| /** Confirm provisional construction if argument is non-null. Note that |
| * if an exception is thrown during evaluation of the argument |
| * expression, then this function will not be called, and the |
| * provisional object will not be confirmed. This allows the usage: |
| * |
| * x1_provisional.confirm_if( new (x2) T2() ); |
| * |
| * @param cond An arbitrary pointer. The provisional object will be |
| * confirmed if @a cond is not null. |
| * |
| * @returns The value of the @a cond argument. |
| */ |
| template <typename Cond> |
| Cond* confirm_if(Cond* cond) { if (cond) m_ptr = 0; return cond; } |
| }; |
| |
| |
| /** Create a provisional_guard object. This function allows simpler code |
| * when the only use of a provisional_guard is in a |
| * provisional_guard::confirm_if() call immediately following its |
| * creation. Instead of |
| * |
| * provisional_guard<T>guard( new (ptr_to_T) T() ); |
| * guard.confirm_if( new (ptr_to_U) U() ); |
| * |
| * you can just write |
| * |
| * provisional( new (ptr_to_T) T() ).confirm_if( new (ptr_to_U) U() ); |
| * |
| * @tparam Type The type of the provisionally constructed object. |
| * |
| * @param ptr A pointer to a provisionally constructed object. |
| * |
| * @returns A @ref provisional_guard object that guards the |
| * provisionally constructed object pointed to by @a ptr. |
| */ |
| template <typename Type> |
| static provisional_guard<Type> provisional(Type* ptr) |
| { return provisional_guard<Type>(ptr); } |
| |
| public: |
| |
| /** Value type of the monoid. |
| */ |
| typedef Value value_type; |
| |
| /** View type of the monoid. Defaults to be the same as the value type. |
| * @see monoid_with_view |
| */ |
| typedef View view_type; |
| |
| enum { |
| /** Should reducers created with this monoid be aligned? |
| * |
| * @details |
| * “Aligned” means that the view is allocated at a cache-line aligned |
| * offset in the reducer, and the reducer must be cache-line aligned. |
| * “Unaligned” means that the reducer as a whole is just naturally |
| * aligned, but it contains a large enough block of uninitialized |
| * storage for a cache-line aligned view to be allocated in it at |
| * reducer construction time. |
| * |
| * Since the standard heap allocator (new reducer) does not allocate |
| * cache-line aligned storage, only unaligned reducers can be safely |
| * allocated on the heap. |
| * |
| * Default is false (unaligned) unless overridden in a subclass. |
| * |
| * @since 1.02 |
| * (In Cilk library versions 1.0 and 1.01, the default was true. |
| * In Cilk library versions prior to 1.0, reducers were always aligned, |
| * and this data member did not exist.) |
| */ |
| align_reducer = false |
| }; |
| |
| /** Destroy a view. Destroys (without deallocating) the @a View object |
| * pointed to by @a p. |
| * |
| * @param p The address of the @a View object to be destroyed. |
| */ |
| void destroy(view_type* p) const { p->~view_type(); } |
| |
| /** Allocate raw memory. Allocate @a s bytes of memory with no |
| * initialization. |
| * |
| * @param s The number of bytes of memory to allocate. |
| * @return An untyped pointer to the allocated memory. |
| */ |
| void* allocate(size_t s) const { return operator new(s); } |
| |
| /** Deallocate raw memory. Deallocates the memory pointed to by @a p |
| * without doing any destruction. |
| * |
| * @param p Pointer to the memory to be deallocated. |
| * |
| * @pre @a p points to a block of memory that was allocated by a |
| * call to allocate(). |
| */ |
| void deallocate(void* p) const { operator delete(p); } |
| |
| /** Create the identity value. Constructs (without allocating) a @a View |
| * object representing the default value of the @a Value type. |
| * |
| * @param p A pointer to a block of raw memory large enough to hold a |
| * @a View object. |
| * |
| * @post The memory pointed to by @a p contains a @a View object that |
| * represents the default value of the @a View type. |
| * |
| * @deprecated This function constructs the @a View object with its default |
| * constructor, which will often, but not always, yield the |
| * appropriate identity value. Monoid classes should declare |
| * their identity function explicitly, rather than relying on |
| * this default definition. |
| */ |
| void identity(View* p) const { new ((void*) p) View(); } |
| |
| |
| /** @name Construct the monoid and the view with arbitrary arguments. |
| * |
| * A @ref reducer object contains monoid and view data members, which are |
| * declared as raw storage (byte arrays), so that they are not implicitly |
| * constructed when the reducer is constructed. Instead, a reducer |
| * constructor calls one of the monoid class’s static construct() |
| * functions with the addresses of the monoid and the view, and the |
| * construct() function uses placement `new` to construct them. |
| * |
| * This allows the monoid to determine the order in which the monoid and |
| * view are constructed, and to make one of them dependent on the other. |
| * |
| * Any arguments to the reducer constructor are just passed on as |
| * additional arguments to the construct() function (after the monoid |
| * and view addresses). |
| * |
| * Any monoid whose needs are satisfied by the suite of construct() |
| * functions below, such as @ref monoid_with_view, can just inherit them |
| * from monoid_base. Other monoids will need to provide their own versions |
| * to override the monoid_base functions. |
| */ |
| //@{ |
| |
| /** Default-construct the monoid, and pass zero to five const reference |
| * arguments to the view constructor. |
| */ |
| //@{ |
| |
| template <typename Monoid> |
| static void construct(Monoid* monoid, View* view) |
| { provisional( new ((void*)monoid) Monoid() ).confirm_if( |
| (monoid->identity(view), view) ); } |
| |
| template <typename Monoid, typename T1> |
| static void construct(Monoid* monoid, View* view, const T1& x1) |
| { provisional( new ((void*)monoid) Monoid() ).confirm_if( |
| new ((void*)view) View(x1) ); } |
| |
| template <typename Monoid, typename T1, typename T2> |
| static void construct(Monoid* monoid, View* view, |
| const T1& x1, const T2& x2) |
| { provisional( new ((void*)monoid) Monoid() ).confirm_if( |
| new ((void*)view) View(x1, x2) ); } |
| |
| template <typename Monoid, typename T1, typename T2, typename T3> |
| static void construct(Monoid* monoid, View* view, |
| const T1& x1, const T2& x2, const T3& x3) |
| { provisional( new ((void*)monoid) Monoid() ).confirm_if( |
| new ((void*)view) View(x1, x2, x3) ); } |
| |
| template <typename Monoid, typename T1, typename T2, typename T3, |
| typename T4> |
| static void construct(Monoid* monoid, View* view, |
| const T1& x1, const T2& x2, const T3& x3, |
| const T4& x4) |
| { provisional( new ((void*)monoid) Monoid() ).confirm_if( |
| new ((void*)view) View(x1, x2, x3, x4) ); } |
| |
| template <typename Monoid, typename T1, typename T2, typename T3, |
| typename T4, typename T5> |
| static void construct(Monoid* monoid, View* view, |
| const T1& x1, const T2& x2, const T3& x3, |
| const T4& x4, const T5& x5) |
| { provisional( new ((void*)monoid) Monoid() ).confirm_if( |
| new ((void*)view) View(x1, x2, x3, x4, x5) ); } |
| |
| //@} |
| |
| /** Default-construct the monoid, and pass one non-const reference argument |
| * to the view constructor. |
| */ |
| //@{ |
| template <typename Monoid, typename T1> |
| static void construct(Monoid* monoid, View* view, T1& x1) |
| { provisional( new ((void*)monoid) Monoid() ).confirm_if( |
| new ((void*)view) View(x1) ); } |
| //@} |
| |
| /** Copy-construct the monoid, and pass zero to four const reference |
| * arguments to the view constructor. |
| */ |
| //@{ |
| |
| template <typename Monoid> |
| static void construct(Monoid* monoid, View* view, const Monoid& m) |
| { provisional( new ((void*)monoid) Monoid(m) ).confirm_if( |
| new ((void*)view) View() ); } |
| |
| template <typename Monoid, typename T1> |
| static void construct(Monoid* monoid, View* view, const Monoid& m, |
| const T1& x1) |
| { provisional( new ((void*)monoid) Monoid(m) ).confirm_if( |
| new ((void*)view) View(x1) ); } |
| |
| template <typename Monoid, typename T1, typename T2> |
| static void construct(Monoid* monoid, View* view, const Monoid& m, |
| const T1& x1, const T2& x2) |
| { provisional( new ((void*)monoid) Monoid(m) ).confirm_if( |
| new ((void*)view) View(x1, x2) ); } |
| |
| template <typename Monoid, typename T1, typename T2, typename T3> |
| static void construct(Monoid* monoid, View* view, const Monoid& m, |
| const T1& x1, const T2& x2, const T3& x3) |
| { |
| provisional( new ((void*)monoid) Monoid(m) ).confirm_if( |
| new ((void*)view) View(x1, x2, x3) ); |
| } |
| |
| template <typename Monoid, typename T1, typename T2, typename T3, |
| typename T4> |
| static void construct(Monoid* monoid, View* view, const Monoid& m, |
| const T1& x1, const T2& x2, const T3& x3, |
| const T4& x4) |
| { |
| provisional( new ((void*)monoid) Monoid(m) ).confirm_if( |
| new ((void*)view) View(x1, x2, x3, x4) ); |
| } |
| |
| //@} |
| |
| //@} |
| }; |
| |
| |
| /** Monoid class that gets its value type and identity and reduce operations |
| * from its view. |
| * |
| * A simple implementation of the monoid-view-reducer architecture would |
| * distribute knowledge about the type and operations for the reduction |
| * between the monoid and the view — the identity and reduction operations are |
| * specified in the monoid, the reduction operations are implemented in the |
| * view, and the value type is specified in both the monoid and the view. |
| * This is inelegant. |
| * |
| * monoid_with_view is a subclass of @ref monoid_base that gets its value type |
| * and its identity and reduction operations from its view class. No |
| * customization of the monoid_with_view class itself is needed beyond |
| * instantiating it with an appropriate view class. (Customized subclasses of |
| * monoid_with_view may be needed for other reasons, such as to keep some |
| * state for the reducer.) All of the Cilk predefined reducers use |
| * monoid_with_view or one of its subclasses. |
| * |
| * The view class `View` of a monoid_with_view must provide the following public definitions: |
| * |
| * Definition | Meaning |
| * ---------------------------------|-------- |
| * `value_type` | a typedef of the value type for the reduction |
| * `View()` | a default constructor which constructs the identity value for the reduction |
| * `void reduce(const View* other)` | a member function which applies the reduction operation to the values of `this` view and the `other` view, leaving the result as the value of `this` view, and leaving the value of the `other` view undefined (but valid) |
| * |
| * @tparam View The view class for the monoid. |
| * @tparam Align If true, reducers instantiated on this monoid will be |
| * cache-aligned. By default, library reducers (unlike legacy |
| * library reducer _wrappers_) are aligned only as required by |
| * contents. |
| */ |
| template <class View, bool Align = false> |
| class monoid_with_view : public monoid_base<typename View::value_type, View> |
| { |
| public: |
| /** Should reducers created with this monoid be aligned? |
| */ |
| enum { align_reducer = Align }; |
| |
| /** Create the identity value. |
| * |
| * Implements the monoid `identity` operation by using the @a View class’s |
| * default constructor. |
| * |
| * @param p A pointer to a block of raw memory large enough to hold a |
| * @p View object. |
| */ |
| void identity(View* p) const { new ((void*)p) View(); } |
| |
| /** Reduce the values of two views. |
| * |
| * Implements the monoid `reduce` operation by calling the left view’s |
| * `%reduce()` function with the right view as an operand. |
| * |
| * @param left The left operand of the reduce operation. |
| * @param right The right operand of the reduce operation. |
| * @post The left view contains the result of the reduce |
| * operation, and the right view is undefined. |
| */ |
| void reduce(View* left, View* right) const { left->reduce(right); } |
| }; |
| |
| |
| /** Base class for simple views with (usually) scalar values. |
| * |
| * The scalar_view class is intended as a base class which provides about half |
| * of the required definitions for simple views. It defines the `value_type` |
| * required by a @ref monoid_with_view (but not the identity constructor and |
| * reduce operation, which are inherently specific to a particular kind of |
| * reduction). It also defines the value access functions which will be called |
| * by the corresponding @ref reducer functions. (It uses copy semantics for |
| * the view_move_in() and view_move_out() functions, which is appropriate |
| * for simple scalar types, but not necessarily for more complex types like |
| * STL containers. |
| * |
| * @tparam Type The type of value wrapped by the view. |
| */ |
| template <typename Type> |
| class scalar_view |
| { |
| protected: |
| Type m_value; ///< The wrapped accumulator variable. |
| |
| public: |
| /** Value type definition required by @ref monoid_with_view. |
| */ |
| typedef Type value_type; |
| |
| /** Default constructor. |
| */ |
| scalar_view() : m_value() {} |
| |
| /** Value constructor. |
| */ |
| scalar_view(const Type& v) : m_value(v) {} |
| |
| /** @name Value functions required by the reducer class. |
| * |
| * Note that the move in/out functions use simple assignment semantics. |
| */ |
| //@{ |
| |
| /** Set the value of the view. |
| */ |
| void view_move_in(Type& v) { m_value = v; } |
| |
| /** Get the value of the view. |
| */ |
| void view_move_out(Type& v) { v = m_value; } |
| |
| /** Set the value of the view. |
| */ |
| void view_set_value(const Type& v) { m_value = v; } |
| |
| /** Get the value of the view. |
| */ |
| Type const& view_get_value() const { return m_value; } |
| |
| /** Get a reference to the value contained in the view. For legacy |
| * reducer support only. |
| */ |
| Type & view_get_reference() { return m_value; } |
| |
| /** Get a reference to the value contained in the view. For legacy |
| * reducer support only. |
| */ |
| Type const& view_get_reference() const { return m_value; } |
| //@} |
| }; |
| |
| |
| /** Wrapper class for move-in construction. |
| * |
| * Some types allow their values to be _moved_ as an alternative to copying. |
| * Moving a value may be much faster than copying it, but may leave the value |
| * of the move’s source undefined. Consider the `swap` operation provided by |
| * many STL container classes: |
| * |
| * list<T> x, y; |
| * x = y; // Copy |
| * x.swap(y); // Move |
| * |
| * The assignment _copies_ the value of `y` into `x` in time linear in the |
| * size of `y`, leaving `y` unchanged. The `swap` _moves_ the value of `y` |
| * into `x` in constant time, but it also moves the value of `x` into `y`, |
| * potentially leaving `y` undefined. |
| * |
| * A move_in_wrapper simply wraps a pointer to an object. It is created by a |
| * call to cilk::move_in(). Passing a move_in_wrapper to a view constructor |
| * (actually, passing it to a reducer constructor, which passes it to the |
| * monoid `construct()` function, which passes it to the view constructor) |
| * allows, but does not require, the value pointed to by the wrapper to be |
| * moved into the view instead of copied. |
| * |
| * A view class exercises this option by defining a _move-in constructor_, |
| * i.e., a constructor with a move_in_wrapper parameter. The constructor calls |
| * the wrapper’s `value()` function to get a reference to its pointed-to |
| * value, and can then use that reference in a move operation. |
| * |
| * A move_in_wrapper also has an implicit conversion to its pointed-to value, |
| * so if a view class does not define a move-in constructor, its ordinary |
| * value constructor will be called with the wrapped value. For example, an |
| * @ref ReducersAdd "op_add" view does not have a move-in constructor, so |
| * |
| * int x; |
| * reducer< op_add<int> > xr(move_in(x)); |
| * |
| * will simply call the `op_add_view(const int &)` constructor. But an |
| * @ref ReducersList "op_list_append" view does have a move-in constructor, |
| * so |
| * |
| * list<int> x; |
| * reducer< op_list_append<int> > xr(move_in(x)); |
| * |
| * will call the `op_list_append_view(move_in_wrapper<int>)` constructor, |
| * which can `swap` the value of `x` into the view. |
| * |
| * @note Remember that passing the value of a variable to a reducer |
| * constructor using a move_in_wrapper leaves the variable undefined. |
| * You cannot assume that the constructor either will or will not copy |
| * or move the value. |
| * |
| * @tparam Type The type of the wrapped value. |
| * |
| * @see cilk::move_in() |
| */ |
| template <typename Type> |
| class move_in_wrapper |
| { |
| Type *m_pointer; |
| public: |
| |
| /** Constructor that captures the address of its argument. This is almost |
| * always called from the @ref move_in function. |
| */ |
| explicit move_in_wrapper(Type& ref) : m_pointer(&ref) { } |
| |
| /** Implicit conversion to the wrapped value. This allows a move_in_wrapper |
| * to be used where a value of the wrapped type is expected, in which case |
| * the wrapper is completely transparent. |
| */ |
| operator Type&() const { return *m_pointer; } |
| |
| /** Get a reference to the pointed-to value. This has the same effect as |
| * the implicit conversion, but makes the intent clearer in a move-in |
| * constructor. |
| */ |
| Type& value() const { return *m_pointer; } |
| }; |
| |
| /** Function to create a move_in_wrapper for a value. |
| * |
| * @tparam Type The type of the argument, which will be the `type` of the |
| * created wrapper. |
| * |
| * @see move_in_wrapper |
| */ |
| template <typename Type> |
| inline |
| move_in_wrapper<Type> move_in(Type& ref) |
| { return move_in_wrapper<Type>(ref); } |
| |
| |
| /** @copydoc move_in(Type&) |
| * |
| * @note Applying a function that is explicitly specified as modifying its |
| * argument to a const argument is obviously an irrational thing to |
| * do. This move_in() variant is just provided to allow calling a |
| * move-in constructor with a function return value, which the |
| * language treats as a const. Using it for any other purpose will |
| * probably end in tears. |
| */ |
| template <typename Type> |
| inline |
| move_in_wrapper<Type> move_in(const Type& ref) |
| { return move_in_wrapper<Type>(ref); } |
| |
| |
| /** Wrapper class to allow implicit downcasts to reducer subclasses. |
| * |
| * The Cilk library contains a collection of reducer wrapper classes which |
| * were created before the `cilk::reducer<Monoid>` style was developed. For |
| * example, `cilk::reducer_opadd<Type>` provided essentially the same |
| * functionality that is now provided by |
| * `cilk::reducer< cilk::op_add<Type> >`. These legacy reducer classes are |
| * deprecated, but still supported, and they have been reimplemented as |
| * subclasses of the corresponding `cilk::reducer` classes. For example: |
| * |
| * template <class T> |
| * reducer_opadd<T> : public reducer< op_add<T> > { ... }; |
| * |
| * This reimplementation allows transparent conversion between legacy and |
| * new reducers. That is, a `reducer<op_add>*` or `reducer<op_add>&` can be |
| * used anywhere that a `reducer_opadd*` or `reducer_opadd&` is expected, |
| * and vice versa. |
| * |
| * The conversion from the legacy reducer to the new reducer is just an |
| * up-cast, which is provided for free by C++. The conversion from the new |
| * reducer to the legacy reducer is a down-cast, though, which requires an |
| * explicit conversion member function in the `reducer` class. The challenge |
| * is to define a function in the reducer template class which will convert |
| * each cilk::reducer specialization to the corresponding legacy reducer, |
| * if there is one. |
| * |
| * The trick is in the legacy_reducer_downcast template class, which provides |
| * a mapping from `cilk::reducer` specializations to legacy reducer classes. |
| * `reducer<Monoid>` has a conversion function to convert itself to |
| * `legacy_reducer_downcast< reducer<Monoid> >::%type`. By default, |
| * `legacy_reducer_downcast<Reducer>::%type` is just a trivial subclass of |
| * `Reducer`, which is uninteresting, but a reducer with a legacy counterpart |
| * will have a specialization of `legacy_reducer_downcast` whose `type` is |
| * the corresponding legacy reducer. For example: |
| * |
| * template <typename Type> |
| * struct legacy_reducer_downcast< reducer< op_add<Type> > > |
| * { |
| * typedef reducer_opadd<Type> type; |
| * }; |
| * |
| * |
| * @tparam Reducer The new-style reducer class whose corresponding legacy reducer class |
| * is `type`, if there is such a legacy reducer class. |
| */ |
| template <typename Reducer> |
| struct legacy_reducer_downcast |
| { |
| /** The related legacy reducer class. |
| * |
| * By default, this is just a trivial subclass of Reducer, but it can be |
| * overridden in the specialization of legacy_reducer_downcast for |
| * a reducer that has a corresponding legacy reducers. |
| */ |
| struct type : Reducer { }; |
| }; |
| |
| |
| namespace internal { |
| /// @cond internal |
| |
| template <typename Value, typename View> |
| struct reducer_set_get |
| { |
| static View theView; // Declared but not defined |
| |
| // sizeof(notchar) is guaranteed larger than 1 |
| struct notchar { char x[2]; }; |
| |
| // check_for_ref returns char if 'get_value' returns by value and notchar |
| // if 'get_value' returns by reference. |
| static char check_for_ref(Value, ...); |
| static notchar check_for_ref(Value&, int); |
| |
| enum { GET_VALUE_BY_VALUE = |
| (1 == sizeof(check_for_ref(theView.view_get_value(), 0))) } ; |
| |
| typedef typename condition<GET_VALUE_BY_VALUE, |
| Value, const Value&>::type get_value_type; |
| |
| static void move_in(View& view, Value& v) { view.view_move_in(v); } |
| static void move_out(View& view, Value& v) { view.view_move_out(v); } |
| |
| static void set_value(View& view, const Value& v) |
| { view.view_set_value(v); } |
| |
| static get_value_type get_value(const View& view) |
| { return view.view_get_value(); } |
| }; |
| |
| template <typename Value> |
| struct reducer_set_get<Value, Value> |
| { |
| typedef const Value& get_value_type; |
| |
| static void move_in(Value& view, Value& v) { view = v; } |
| static void move_out(Value& view, Value& v) { v = view; } |
| |
| static void set_value(Value& view, const Value& v) { view = v; } |
| |
| static get_value_type get_value(const Value& view) { return view; } |
| }; |
| |
| /// @endcond |
| |
| |
| /** Base class defining the data layout that is common to all reducers. |
| */ |
| template <typename Monoid> |
| class reducer_base { |
| typedef typename Monoid::view_type view_type; |
| |
| // This makes the reducer a hyper-object. (Partially initialized in |
| // the derived reducer_content class.) |
| // |
| __cilkrts_hyperobject_base m_base; |
| |
| // The monoid is allocated here as raw bytes, and is constructed explicitly |
| // by a call to the monoid_type::construct() function in the constructor of |
| // the `reducer` subclass. |
| // |
| storage_for_object<Monoid> m_monoid; |
| |
| // Used for sanity checking at destruction. |
| // |
| void* m_initialThis; |
| |
| // The leftmost view comes next. It is defined in the derived |
| // reducer_content class. |
| |
| /** @name C-callable wrappers for the C++-coded monoid dispatch functions. |
| */ |
| //@{ |
| |
| static void reduce_wrapper(void* r, void* lhs, void* rhs); |
| static void identity_wrapper(void* r, void* view); |
| static void destroy_wrapper(void* r, void* view); |
| static void* allocate_wrapper(void* r, __STDNS size_t bytes); |
| static void deallocate_wrapper(void* r, void* view); |
| |
| //@} |
| |
| protected: |
| |
| /** Constructor. |
| * |
| * @param leftmost The address of the leftmost view in the reducer. |
| */ |
| reducer_base(char* leftmost) |
| { |
| static const cilk_c_monoid c_monoid_initializer = { |
| (cilk_c_reducer_reduce_fn_t) &reduce_wrapper, |
| (cilk_c_reducer_identity_fn_t) &identity_wrapper, |
| (cilk_c_reducer_destroy_fn_t) &destroy_wrapper, |
| (cilk_c_reducer_allocate_fn_t) &allocate_wrapper, |
| (cilk_c_reducer_deallocate_fn_t) &deallocate_wrapper |
| }; |
| |
| m_base.__c_monoid = c_monoid_initializer; |
| m_base.__flags = 0; |
| m_base.__view_offset = (char*)leftmost - (char*)this; |
| m_base.__view_size = sizeof(view_type); |
| m_initialThis = this; |
| |
| __cilkrts_hyper_create(&m_base); |
| } |
| |
| /** Destructor. |
| */ |
| __CILKRTS_STRAND_STALE(~reducer_base()) |
| { |
| // Make sure we haven't been memcopy'd or corrupted |
| __CILKRTS_ASSERT( |
| this == m_initialThis || |
| // Allow for a layout bug that may put the initialThis field one |
| // word later in 1.0 reducers than in 0.9 and 1.1 reducers. |
| this == *(&m_initialThis + 1) |
| ); |
| __cilkrts_hyper_destroy(&m_base); |
| } |
| |
| /** Monoid data member. |
| * |
| * @return A pointer to the reducer’s monoid data member. |
| */ |
| Monoid* monoid_ptr() { return &m_monoid.object(); } |
| |
| /** Leftmost view data member. |
| * |
| * @return A pointer to the reducer’s leftmost view data member. |
| * |
| * @note This function returns the address of the *leftmost* view, |
| * which is unique for the lifetime of the reducer. It is |
| * intended to be used in constructors and destructors. |
| * Use the reducer::view() function to access the per-strand |
| * view instance. |
| */ |
| view_type* leftmost_ptr() |
| { |
| char* view_addr = (char*)this + m_base.__view_offset; |
| return reinterpret_cast<view_type*>(view_addr); |
| } |
| |
| public: |
| |
| /** @name Access the current view. |
| * |
| * These functions return a reference to the instance of the reducer’s |
| * view that was created for the current strand of a parallel computation |
| * (and create it if it doesn’t already exist). Note the difference from |
| * the (private) leftmost_ptr() function, which returns a pointer to the |
| * _leftmost_ view, which is the same in all strands. |
| */ |
| //@{ |
| |
| /** Per-strand view instance. |
| * |
| * @return A reference to the per-strand view instance. |
| */ |
| view_type& view() |
| { |
| return *static_cast<view_type *>(__cilkrts_hyper_lookup(&m_base)); |
| } |
| |
| /** @copydoc view() |
| */ |
| const view_type& view() const |
| { |
| return const_cast<reducer_base*>(this)->view(); |
| } |
| |
| //@} |
| |
| /** Initial view pointer field. |
| * |
| * @internal |
| * |
| * @return a reference to the m_initialThis field. |
| * |
| * @note This function is provided for “white-box” testing of the |
| * reducer layout code. There is never any reason for user code |
| * to call it. |
| */ |
| const void* const & initial_this() const { return m_initialThis; } |
| }; |
| |
| template <typename Monoid> |
| void reducer_base<Monoid>::reduce_wrapper(void* r, void* lhs, void* rhs) |
| { |
| Monoid* monoid = static_cast<reducer_base*>(r)->monoid_ptr(); |
| monoid->reduce(static_cast<view_type*>(lhs), |
| static_cast<view_type*>(rhs)); |
| } |
| |
| template <typename Monoid> |
| void reducer_base<Monoid>::identity_wrapper(void* r, void* view) |
| { |
| Monoid* monoid = static_cast<reducer_base*>(r)->monoid_ptr(); |
| monoid->identity(static_cast<view_type*>(view)); |
| } |
| |
| template <typename Monoid> |
| void reducer_base<Monoid>::destroy_wrapper(void* r, void* view) |
| { |
| Monoid* monoid = static_cast<reducer_base*>(r)->monoid_ptr(); |
| monoid->destroy(static_cast<view_type*>(view)); |
| } |
| |
| template <typename Monoid> |
| void* reducer_base<Monoid>::allocate_wrapper(void* r, __STDNS size_t bytes) |
| { |
| Monoid* monoid = static_cast<reducer_base*>(r)->monoid_ptr(); |
| return monoid->allocate(bytes); |
| } |
| |
| template <typename Monoid> |
| void reducer_base<Monoid>::deallocate_wrapper(void* r, void* view) |
| { |
| Monoid* monoid = static_cast<reducer_base*>(r)->monoid_ptr(); |
| monoid->deallocate(static_cast<view_type*>(view)); |
| } |
| |
| |
| /** Base class defining the data members of a reducer. |
| * |
| * @tparam Aligned The `m_view` data member, and therefore the entire |
| * structure, are cache-line aligned if this parameter |
| * is `true'. |
| */ |
| template <typename Monoid, bool Aligned = Monoid::align_reducer> |
| class reducer_content; |
| |
| /** Base class defining the data members of an aligned reducer. |
| */ |
| template <typename Monoid> |
| class reducer_content<Monoid, true> : public reducer_base<Monoid> |
| { |
| typedef typename Monoid::view_type view_type; |
| |
| // The leftmost view is defined as raw bytes. It will be constructed |
| // by the monoid `construct` function. It is cache-aligned, which |
| // will push it into a new cache line. Furthermore, its alignment causes |
| // the reducer as a whole to be cache-aligned, which makes the reducer |
| // size a multiple of a cache line. Since there is nothing in the reducer |
| // after the view, all this means that the leftmost view gets one or more |
| // cache lines all to itself, which prevents false sharing. |
| // |
| __CILKRTS_CACHE_ALIGN |
| char m_leftmost[sizeof(view_type)]; |
| |
| /** Test if the reducer is cache-line-aligned. |
| * |
| * Used in assertions. |
| */ |
| bool reducer_is_cache_aligned() const |
| { return 0 == ((std::size_t) this & (__CILKRTS_CACHE_LINE__ - 1)); } |
| |
| protected: |
| |
| /** Constructor. |
| */ |
| reducer_content() : reducer_base<Monoid>((char*)&m_leftmost) |
| { |
| #ifndef CILK_IGNORE_REDUCER_ALIGNMENT |
| assert(reducer_is_cache_aligned() && |
| "Reducer should be cache aligned. Please see comments following this assertion for explanation and fixes."); |
| #endif |
| /* "REDUCER SHOULD BE CACHE ALIGNED" ASSERTION. |
| * |
| * This Reducer class instantiation specifies cache-line alignment of the |
| * leftmost view field (and, implicitly, of the reducer itself). You got |
| * this assertion because a reducer with this class was allocated at a |
| * non-cache-aligned address, probably because it was allocated on the |
| * heap with `new`. This can be a problem for two reasons: |
| * |
| * 1. If the leftmost view is not on a cache line by itself, there might |
| * be a slowdown resulting from accesses to the same cache line from |
| * different threads. |
| * |
| * 2. The compiler thinks that reducer is cache-line aligned, but it |
| * really isn't. If the reducer is contained in a structure, then the |
| * compiler will believe that the containing structure, and other |
| * fields contained in it, are also more aligned than they really |
| * are. In particular, if the structure contains a numeric array that |
| * is used in a vectorizable loop, then the compiler might generate |
| * invalid vector instructions, resulting in a runtime error. |
| * |
| * The compiler will always allocate reducer variables, and structure |
| * variables containing reducers, with their required alignment. |
| * Reducers, and structures containing a reducer, which are allocated |
| * on the heap with `new` will _not_ be properly aligned. |
| * |
| * There are three ways that you can fix this assertion failure. |
| * |
| * A. Rewrite your code to use the new-style `reducer< op_XXX<Type> >` |
| * instead of the legacy `reducer_XXX<type>`. The new-style reducers |
| * are not declared to be cache-aligned, and will work properly if |
| * they are not cache-aligned. |
| * |
| * B. If you must allocate an old-style reducer or a structure containing |
| * a reducer on the heap, figure out how to align it correctly. The |
| * suggested fix is to use `cilk::aligned_new()` and |
| * `cilk::aligned_delete()` instead of `new` and `delete`, as follows: |
| * |
| * Type* ptr = cilk::aligned_new<Type>(constructor-arguments); |
| * cilk::aligned_delete(ptr); |
| * |
| * C. Define the macro CILK_IGNORE_REDUCER_ALIGNMENT, which will suppress |
| * the assertion check. Do this only if you are comfortable that |
| * problem (2) above will not occur. |
| */ |
| } |
| }; |
| |
| /** Base class defining the data members of an unaligned reducer. |
| */ |
| template <typename Monoid> |
| class reducer_content<Monoid, false> : public reducer_base<Monoid> |
| { |
| typedef typename Monoid::view_type view_type; ///< The view type. |
| |
| // Reserve space for the leftmost view. The view will be allocated at an |
| // aligned offset in this space at runtime, to guarantee that the view |
| // will get one or more cache lines all to itself, to prevent false |
| // sharing. |
| // |
| // The number of bytes to reserve is determined as follows: |
| // * Start with the view size. |
| // * Round up to a multiple of the cache line size, to get the total size |
| // of the cache lines that will be dedicated to the view. |
| // * Add (cache line size - 1) filler bytes to guarantee that the reserved |
| // area will contain a cache-aligned block of the required cache lines, |
| // no matter where the reserved area starts. |
| // |
| char m_leftmost[ |
| // View size rounded up to multiple cache lines |
| ( (sizeof(view_type) + __CILKRTS_CACHE_LINE__ - 1) |
| & ~ (__CILKRTS_CACHE_LINE__ - 1) |
| ) |
| // plus filler to allow alignment. |
| + __CILKRTS_CACHE_LINE__ - 1 |
| ]; |
| |
| protected: |
| |
| /** Constructor. Find the first cache-aligned position in the reserved |
| * area, and pass it to the base constructor as the leftmost view |
| * address. |
| */ |
| reducer_content() : |
| reducer_base<Monoid>( |
| (char*)( ((std::size_t)&m_leftmost + __CILKRTS_CACHE_LINE__ - 1) |
| & ~ (__CILKRTS_CACHE_LINE__ - 1) ) ) |
| {} |
| }; |
| |
| |
| } // namespace internal |
| |
| |
| // The __cilkrts_hyperobject_ functions are defined differently depending on |
| // whether a file is compiled with or without the CILK_STUB option. Therefore, |
| // reducers compiled in the two modes should be link-time incompatible, so that |
| // object files compiled with stubbed reducers won't be linked into an |
| // unstubbed program, or vice versa. We achieve this by putting the reducer |
| // class definition into the cilk::stub namespace in a stubbed compilation. |
| |
| #ifdef CILK_STUB |
| namespace stub { |
| #endif |
| |
| /** Reducer class. |
| * |
| * A reducer is instantiated on a Monoid. The Monoid provides the value |
| * type, associative reduce function, and identity for the reducer. |
| * |
| * @tparam Monoid The monoid class that the reducer is instantiated on. It must model |
| * the @ref reducers_monoid_concept "monoid concept". |
| * |
| * @see @ref pagereducers |
| */ |
| template <class Monoid> |
| class reducer : public internal::reducer_content<Monoid> |
| { |
| typedef internal::reducer_content<Monoid> base; |
| using base::monoid_ptr; |
| using base::leftmost_ptr; |
| public: |
| typedef Monoid monoid_type; ///< The monoid type. |
| typedef typename Monoid::value_type value_type; ///< The value type. |
| typedef typename Monoid::view_type view_type; ///< The view type. |
| |
| private: |
| typedef internal::reducer_set_get<value_type, view_type> set_get; |
| |
| reducer(const reducer&); ///< Disallow copying. |
| reducer& operator=(const reducer&); ///< Disallow assignment. |
| |
| public: |
| |
| /** @name Constructors |
| * |
| * All reducer constructors call the static `construct()` function of the monoid class to |
| * construct the reducer's monoid and leftmost view. |
| * |
| * The reducer constructor arguments are simply passed through to the construct() function. |
| * Thus, the constructor parameters accepted by a particular reducer class are determined |
| * by its monoid class. |
| */ |
| //@{ |
| |
| /** 0 – 6 const reference parameters. |
| */ |
| //@{ |
| |
| reducer() |
| { |
| monoid_type::construct(monoid_ptr(), leftmost_ptr()); |
| } |
| |
| template <typename T1> |
| reducer(const T1& x1) |
| { |
| monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1); |
| } |
| |
| template <typename T1, typename T2> |
| reducer(const T1& x1, const T2& x2) |
| { |
| monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1, x2); |
| } |
| |
| template <typename T1, typename T2, typename T3> |
| reducer(const T1& x1, const T2& x2, const T3& x3) |
| { |
| monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1, x2, x3); |
| } |
| |
| template <typename T1, typename T2, typename T3, typename T4> |
| reducer(const T1& x1, const T2& x2, const T3& x3, const T4& x4) |
| { |
| monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1, x2, x3, x4); |
| } |
| |
| template <typename T1, typename T2, typename T3, typename T4, typename T5> |
| reducer(const T1& x1, const T2& x2, const T3& x3, const T4& x4, const T5& x5) |
| { |
| monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1, x2, x3, x4, x5); |
| } |
| |
| template <typename T1, typename T2, typename T3, typename T4, typename T5, typename T6> |
| reducer(const T1& x1, const T2& x2, const T3& x3, const T4& x4, const T5& x5, const T6& x6) |
| { |
| monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1, x2, x3, x4, x5, x6); |
| } |
| |
| //@} |
| |
| /** 1 non-const reference parameter. |
| */ |
| //@{ |
| |
| template <typename T1> |
| reducer(T1& x1) |
| { |
| monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1); |
| } |
| |
| //@} |
| |
| /** Destructor. |
| */ |
| __CILKRTS_STRAND_STALE(~reducer()) |
| { |
| leftmost_ptr()->~view_type(); |
| monoid_ptr()->~monoid_type(); |
| } |
| |
| //@{ |
| /** Get the monoid. |
| * |
| * @return A reference to the monoid object belonging to this reducer. |
| */ |
| Monoid& monoid() { return *monoid_ptr(); } |
| |
| const Monoid& monoid() const |
| { return const_cast<reducer*>(this)->monoid(); } |
| //@} |
| |
| //@{ |
| /** Access the current view. |
| * |
| * Return a reference to the instance of the reducer’s view that was |
| * created for the current strand of a parallel computation (and create |
| * it if it doesn’t already exist). |
| */ |
| view_type& view() { return base::view(); } |
| const view_type& view() const { return base::view(); } |
| //@} |
| |
| |
| /** @name Dereference the reducer to get the view. |
| * |
| * “Dereferencing” a reducer yields the view for the current strand. The |
| * view, in turn, acts as a proxy for its contained value, exposing only |
| * those operations which are consistent with the reducer’s monoid. Thus, |
| * all modifications of the reducer’s accumulator variable are written as |
| * |
| * *reducer OP ... |
| * |
| * or |
| * |
| * reducer->func(...) |
| * |
| * (The permitted operations on a reducer’s accumulator are listed in the |
| * documentation for that particular kind of reducer.) |
| * |
| * @note `*r` is a synonym for `r.view()`. Recommended style is to use |
| * `*r` (or `r->`) in the common case where code is simply |
| * updating the accumulator variable wrapped in the view, and to |
| * use `r.view()` in the unusual case where it is desirable to |
| * call attention to the view itself. |
| */ |
| //@{ |
| |
| //@{ |
| /** Dereference operator. |
| * |
| * @return A reference to the per-strand view instance. |
| */ |
| view_type& operator*() { return view(); } |
| view_type const& operator*() const { return view(); } |
| //@} |
| |
| //@{ |
| /** Pointer operator. |
| * |
| * @return A pointer to the per-strand view instance. |
| */ |
| view_type* operator->() { return &view(); } |
| view_type const* operator->() const { return &view(); } |
| //@} |
| |
| //@{ |
| /** Deprecated view access. |
| * |
| * `r()` is a synonym for `*r` which was used with early versions of Cilk |
| * reducers. `*r` is now the preferred usage. |
| * |
| * @deprecated Use operator*() instead of operator()(). |
| * |
| * @return A reference to the per-strand view instance. |
| */ |
| view_type& operator()() { return view(); } |
| view_type const& operator()() const { return view(); } |
| //@} |
| |
| //@} |
| |
| /** @name Set and get the value. |
| * |
| * These functions are used to set an initial value for the reducer before |
| * starting the reduction, or to get the final value after the reduction |
| * is complete. |
| * |
| * @note These functions are completely different from the view |
| * operations that are made available via operator*() and |
| * operator->(), which are used to _modify_ the reducer’s value |
| * _during_ the reduction. |
| * |
| * @warning These functions _can_ be called at any time, and in |
| * general, they will refer to the value contained in the view |
| * for the current strand. However, using them other than to |
| * set the reduction’s initial value or get its final value |
| * will almost always result in undefined behavior. |
| */ |
| //@{ |
| |
| /** Move a value into the reducer. |
| * |
| * This function is used to set the initial value of the reducer’s |
| * accumulator variable by either copying or _moving_ the value of @a obj |
| * into it. Moving a value can often be performed in constant time, even |
| * for large container objects, but has the side effect of leaving the |
| * value of @a obj undefined. (See the description of the |
| * @ref move_in_wrapper class for a discussion of moving values.) |
| * |
| * @par Usage |
| * A move_in() call to initialize a reducer is often paired with a |
| * move_out() call to get its final value: |
| * |
| * reducer<Type> xr; |
| * xr.move_in(x); |
| * … do the reduction … |
| * xr.move_out(x); |
| * |
| * @par Assumptions |
| * - You cannot assume either that this will function will copy its |
| * value or that it will move it. |
| * - You must assume that the value of @a obj will be undefined |
| * after the call to move_in(). |
| * - You can assume that move_in() will be at least as efficient as |
| * set_value(), and you should therefore prefer move_in() unless |
| * you need the value of @a obj to be unchanged after the call. |
| * (But you should usually prefer the move-in constructor over a |
| * move_in() call — see the note below.) |
| * |
| * @note The behavior of a default constructor followed by move-in |
| * initialization: |
| * |
| * reducer<Type> xr; |
| * xr.move_in(x); |
| * |
| * @note is not necessarily the same as a move-in constructor: |
| * |
| * reducer<Type> xr(move_in(x)); |
| * |
| * @note In particular, when @a Type is a container type with a |
| * non-empty allocator, the move-in constructor will create the |
| * accumulator variable with the same allocator as the input |
| * argument @a x, while the default constructor will create the |
| * accumulator variable with a default allocator. The mismatch of |
| * allocators in the latter case means that the input argument |
| * @a x may have to be copied in linear time instead of being |
| * moved in constant time. |
| * |
| * @note Best practice is to prefer the move-in constructor over the |
| * move-in function unless the move-in function is required for |
| * some specific reason. |
| * |
| * @warning Calling this function other than to set the initial value |
| * for a reduction will almost always result in undefined |
| * behavior. |
| * |
| * @param obj The object containing the value that will be moved into the |
| * reducer. |
| * |
| * @post The reducer contains the value that was initially in @a obj. |
| * @post The value of @a obj is undefined. |
| * |
| * @see set_value() |
| */ |
| void move_in(value_type& obj) { set_get::move_in(view(), obj);} |
| |
| /** Move the value out of the reducer. |
| * |
| * This function is used to retrieve the final value of the reducer’s |
| * accumulator variable by either copying or _moving_ the value of @a obj |
| * into it. Moving a value can often be performed in constant time, even |
| * for large container objects, but has the side effect of leaving the |
| * value of the reducer’s accumulator variable undefined. (See the |
| * description of the @ref move_in_wrapper class for a discussion of |
| * moving values.) |
| * |
| * @par Usage |
| * A move_in() call to initialize a reducer is often paired with a |
| * move_out() call to get its final value: |
| * |
| * reducer<Type> xr; |
| * xr.move_in(x); |
| * … do the reduction … |
| * xr.move_out(x); |
| * |
| * @par Assumptions |
| * - You cannot assume either that this will function will copy its |
| * value or that it will move it. |
| * - You must assume that the value of the reducer’s accumulator |
| * variable will be undefined after the call to move_out(). |
| * - You can assume that move_out() will be at least as efficient as |
| * get_value(), and you should therefore prefer move_out() unless |
| * you need the accumulator variable to be preserved after the |
| * call. |
| * |
| * @warning Calling this function other than to retrieve the final |
| * value of a reduction will almost always result in undefined |
| * behavior. |
| * |
| * @param obj The object that the value of the reducer will be moved into. |
| * |
| * @post @a obj contains the value that was initially in the reducer. |
| * @post The value of the reducer is undefined. |
| * |
| * @see get_value() |
| */ |
| void move_out(value_type& obj) { set_get::move_out(view(), obj); } |
| |
| /** Set the value of the reducer. |
| * |
| * This function sets the initial value of the reducer’s accumulator |
| * variable to the value of @a obj. |
| * |
| * @note The behavior of a default constructor followed by |
| * initialization: |
| * |
| * reducer<Type> xr; |
| * xr.set_value(x); |
| * |
| * @note is not necessarily the same as a value constructor: |
| * |
| * reducer<Type> xr(x); |
| * |
| * @note In particular, when @a Type is a container type with a |
| * non-empty allocator, the value constructor will create the |
| * accumulator variable with the same allocator as the input |
| * argument @a x, while the default constructor will create the |
| * accumulator variable with a default allocator. |
| * |
| * @warning Calling this function other than to set the initial value |
| * for a reduction will almost always result in undefined |
| * behavior. |
| * |
| * @param obj The object containing the value that will be copied into |
| * the reducer. |
| * |
| * @post The reducer contains a copy of the value in @a obj. |
| * |
| * @see move_in() |
| */ |
| void set_value(const value_type& obj) { set_get::set_value(view(), obj); } |
| |
| /** Get the value of the reducer. |
| * |
| * This function gets the final value of the reducer’s accumulator |
| * variable. |
| * |
| * @warning Calling this function other than to retrieve the final |
| * value of a reduction will almost always result in undefined |
| * behavior. |
| * |
| * @return A reference to the value contained in the reducer. |
| * |
| * @see move_out() |
| */ |
| typename set_get::get_value_type get_value() const |
| { return set_get::get_value(view()); } |
| |
| //@} |
| |
| /** Implicit downcast to legacy reducer wrapper, if any. |
| * |
| * @see legacy_reducer_downcast |
| */ |
| operator typename legacy_reducer_downcast<reducer>::type& () |
| { |
| typedef typename legacy_reducer_downcast<reducer>::type downcast_type; |
| return *reinterpret_cast<downcast_type*>(this); |
| } |
| |
| |
| /** Implicit downcast to legacy reducer wrapper, if any. |
| * |
| * @see legacy_reducer_downcast |
| */ |
| operator const typename legacy_reducer_downcast<reducer>::type& () const |
| { |
| typedef typename legacy_reducer_downcast<reducer>::type downcast_type; |
| return *reinterpret_cast<const downcast_type*>(this); |
| } |
| }; |
| |
| #ifdef CILK_STUB |
| } // namespace stub |
| using stub::reducer; |
| #endif |
| |
| } // end namespace cilk |
| |
| #endif /* __cplusplus */ |
| |
| /** @page page_reducers_in_c Creating and Using Reducers in C |
| * |
| * @tableofcontents |
| * |
| * The Cilk runtime supports reducers written in C as well as in C++. The basic logic is the |
| * same, but the implementation details are very different. The C++ reducer implementation uses |
| * templates heavily to create very generic components. The C reducer implementation uses |
| * macros, which are a much blunter instrument. The most immediate consequence is that the |
| * monoid/view/reducer architecture is mostly implicit rather than explicit in C reducers. |
| * |
| * @section reducers_c_overview Overview of Using Reducers in C |
| * |
| * The basic usage pattern for C reducers is: |
| * |
| * 1. Create and initialize a reducer object. |
| * 2. Tell the Cilk runtime about the reducer. |
| * 3. Update the value contained in the reducer in a parallel computation. |
| * 4. Tell the Cilk runtime that you are done with the reducer. |
| * 5. Retrieve the value from the reducer. |
| * |
| * @subsection reducers_c_creation Creating and Initializing a C Reducer |
| * |
| * The basic pattern for creating and initializing a reducer object in C is |
| * |
| * CILK_C_DECLARE_REDUCER(value-type) reducer-name = |
| * CILK_C_INIT_REDUCER(value-type, |
| * reduce-function, |
| * identity-function, |
| * destroy-function, |
| * initial-value); |
| * |
| * This is simply an initialized definition of a variable named _reducer-name_. The |
| * @ref CILK_C_DECLARE_REDUCER macro expands to an anonymous `struct` declaration for a reducer |
| * object containing a view of type _value-type_, and the @ref CILK_C_INIT_REDUCER macro |
| * expands to a struct initializer. |
| * |
| * @subsection reducers_c_reduce_func Reduce Functions |
| * |
| * The reduce function for a reducer is called when a parallel execution strand terminates, to |
| * combine the values computed by the terminating strand and the strand to its left. It takes |
| * three arguments: |
| * |
| * - `void* reducer` — the address of the reducer. |
| * - `void* left` — the address of the value for the left strand. |
| * - `void* right` — the address of the value for the right (terminating) strand. |
| * |
| * It must apply the reducer’s reduction operation to the `left` and `right` values, leaving |
| * the result in the `left` value. The `right` value is undefined after the reduce function |
| * call. |
| * |
| * @subsection reducers_c_identity_func Identity Functions |
| * |
| * The identity function for a reducer is called when a parallel execution strand begins, to |
| * initialize its value to the reducer’s identity value. It takes two arguments: |
| * |
| * - `void* reducer` — the address of the reducer. |
| * - `void* v` — the address of a freshly allocated block of memory of size |
| * `sizeof(value-type)`. |
| * |
| * It must initialize the memory pointed to by `v` so that it contains the reducer’s identity |
| * value. |
| * |
| * @subsection reducers_c_destroy_func Destroy Functions |
| * |
| * The destroy function for a reducer is called when a parallel execution strand terminates, to |
| * do any necessary cleanup before its value is deallocated. It takes two arguments: |
| * |
| * - `void* reducer` — the address of the reducer. |
| * - `void* p` — the address of the value for the terminating strand. |
| * |
| * It must release any resources belonging to the value pointed to by `p`, to avoid a resource |
| * leak when the memory containing the value is deallocated. |
| * |
| * The runtime function `__cilkrts_hyperobject_noop_destroy` can be used for the destructor |
| * function if the reducer’s values do not need any cleanup. |
| * |
| * @subsection reducers_c_register Tell the Cilk Runtime About the Reducer |
| * |
| * Call the @ref CILK_C_REGISTER_REDUCER macro to register the reducer with the Cilk runtime: |
| * |
| * CILK_C_REGISTER_REDUCER(reducer-name); |
| * |
| * The runtime will manage reducer values for all registered reducers when parallel execution |
| * strands begin and end. |
| * |
| * @subsection reducers_c_update Update the Value Contained in the Reducer |
| * |
| * The @ref REDUCER_VIEW macro returns a reference to the reducer’s value for the current |
| * parallel strand: |
| * |
| * REDUCER_VIEW(reducer-name) = REDUCER_VIEW(reducer-name) OP x; |
| * |
| * C++ reducer views restrict access to the wrapped value so that it can only be modified in |
| * ways consistent with the reducer’s operation. No such protection is provided for C reducers. |
| * It is |
| * entirely the responsibility of the user to avoid modifying the value in any |
| * inappropriate way. |
| * |
| * @subsection c_reducers_unregister Tell the Cilk Runtime That You Are Done with the Reducer |
| * |
| * When the parallel computation is complete, call the @ref CILK_C_UNREGISTER_REDUCER macro to |
| * unregister the reducer with the Cilk runtime: |
| * |
| * CILK_C_UNREGISTER_REDUCER(reducer-name); |
| * |
| * The runtime will stop managing reducer values for the reducer. |
| * |
| * @subsection c_reducers_retrieve Retrieve the Value from the Reducer |
| * |
| * When the parallel computation is complete, use the @ref REDUCER_VIEW macro to retrieve the |
| * final value computed by the reducer. |
| * |
| * @subsection reducers_c_example_custom Example — Creating and Using a Custom C Reducer |
| * |
| * The `IntList` type represents a simple list of integers. |
| * |
| * struct _intListNode { |
| * int value; |
| * _intListNode* next; |
| * } IntListNode; |
| * typedef struct { IntListNode* head; IntListNode* tail; } IntList; |
| * |
| * // Initialize a list to be empty |
| * void IntList_init(IntList* list) { list->head = list->tail = 0; } |
| * |
| * // Append an integer to the list |
| * void IntList_append(IntList* list, int x) |
| * { |
| * IntListNode* node = (IntListNode*) malloc(sizeof(IntListNode)); |
| * if (list->tail) list->tail->next = node; else list->head = node; |
| * list->tail = node; |
| * } |
| * |
| * // Append the right list to the left list, and leave the right list empty |
| * void IntList_concat(IntList* left, IntList* right) |
| * { |
| * if (left->head) { |
| * left->tail->next = right->head; |
| * if (right->tail) left->tail = right->tail; |
| * } |
| * else { |
| * *left = *right; |
| * } |
| * IntList_init(*right); |
| * } |
| * |
| * This code creates a reducer that supports creating an `IntList` by appending values to it. |
| * |
| * void identity_IntList(void* reducer, void* list) |
| * { |
| * IntList_init((IntList*)list); |
| * } |
| * |
| * void reduce_IntList(void* reducer, void* left, void* right) |
| * { |
| * IntList_concat((IntList*)left, (IntList*)right); |
| * } |
| * |
| * CILK_C_DECLARE_REDUCER(IntList) my_list_int_reducer = |
| * CILK_C_INIT_REDUCER(IntList, |
| * reduce_int_list, |
| * identity_int_list, |
| * __cilkrts_hyperobject_noop_destroy); |
| * // Initial value omitted // |
| * ListInt_init(&REDUCER_VIEW(my_int_list_reducer)); |
| * |
| * CILK_C_REGISTER_REDUCER(my_int_list_reducer); |
| * cilk_for (int i = 0; i != n; ++i) { |
| * IntList_append(&REDUCER_VIEW(my_int_list_reducer), a[i]); |
| * } |
| * CILK_C_UNREGISTER_REDUCER(my_int_list_reducer); |
| * |
| * IntList result = REDUCER_VIEW(my_int_list_reducer); |
| * |
| * @section reducers_c_predefined Predefined C Reducers |
| * |
| * Some of the predefined reducer classes in the Cilk library come with a set of predefined |
| * macros to provide the same capabilities in C. In general, two macros are provided for each |
| * predefined reducer family: |
| * |
| * - `CILK_C_REDUCER_operation(reducer-name, type-name, initial-value)` — Declares a |
| * reducer object named _reducer-name_ with initial value _initial-value_ to perform |
| * a reduction using the _operation_ on values of the type specified by _type-name_. |
| * This is the equivalent of the general code described in @ref reducers_c_creation : |
| * |
| * CILK_C_DECLARE_REDUCER(type) reducer-name = |
| * CILK_C_INIT_REDUCER(type, ..., initial-value); |
| * |
| * where _type_ is the C type corresponding to _type_name_. See @ref reducers_c_type_names |
| * below for the _type-names_ that you can use. |
| * |
| * - `CILK_C_REDUCER_operation_TYPE(type-name)` — Expands to the `typedef` name for the type |
| * of the reducer object declared by |
| * `CILK_C_REDUCER_operation(reducer-name, type-name, initial-value)`. |
| * |
| * See @ref reducers_c_example_predefined. |
| * |
| * The predefined C reducers are: |
| * |
| * | Operation | Name | Documentation | |
| * |-------------------|---------------|-------------------------------| |
| * | addition | `OPADD` | @ref ReducersAdd | |
| * | bitwise and | `OPAND` | @ref ReducersAnd | |
| * | bitwise or | `OPOR` | @ref ReducersOr | |
| * | bitwise xor | `OPXOR` | @ref ReducersXor | |
| * | multiplication | `OPMUL` | @ref ReducersMul | |
| * | minimum | `MIN` | @ref ReducersMinMax | |
| * | minimum & index | `MIN_INDEX` | @ref ReducersMinMax | |
| * | maximum | `MIN` | @ref ReducersMinMax | |
| * | maximum & index | `MIN_INDEX` | @ref ReducersMinMax | |
| * |
| * @subsection reducers_c_type_names Numeric Type Names |
| * |
| * The type and function names created by the C reducer definition macros incorporate both the |
| * reducer kind (`opadd`, `opxor`, etc.) and the value type of the reducer (`int`, `double`, |
| * etc.). The value type is represented by a _numeric type name_ string. The types supported |
| * in C reducers, and their corresponding numeric type names, are given in the following table: |
| * |
| * | Type | Numeric Type Name | |
| * |-----------------------|-------------------------------| |
| * | `char` | `char` | |
| * | `unsigned char` | `uchar` | |
| * | `signed char` | `schar` | |
| * | `wchar_t` | `wchar_t` | |
| * | `short` | `short` | |
| * | `unsigned short` | `ushort` | |
| * | `int` | `int` | |
| * | `unsigned int` | `uint` | |
| * | `unsigned int` | `unsigned` (alternate name) | |
| * | `long` | `long` | |
| * | `unsigned long` | `ulong` | |
| * | `long long` | `longlong` | |
| * | `unsigned long long` | `ulonglong` | |
| * | `float` | `float` | |
| * | `double` | `double` | |
| * | `long double` | `longdouble` | |
| * |
| * @subsection reducers_c_example_predefined Example — Using a Predefined C Reducer |
| * |
| * To compute the sum of all the values in an array of `unsigned int`: |
| * |
| * CILK_C_REDUCER_OPADD(sum, uint, 0); |
| * CILK_C_REGISTER_REDUCER(sum); |
| * cilk_for(int i = 0; i != n; ++i) { |
| * REDUCER_VIEW(sum) += a[i]; |
| * } |
| * CILK_C_UNREGISTER_REDUCER(sum); |
| * printf("The sum is %u\n", REDUCER_VIEW(sum)); |
| */ |
| |
| |
| /** @name C language reducer macros |
| * |
| * These macros are used to declare and work with reducers in C code. |
| * |
| * @see @ref page_reducers_in_c |
| */ |
| //@{ |
| |
| /// @cond internal |
| |
| /** @name Compound identifier macros. |
| * |
| * These macros are used to construct an identifier by concatenating two or three identifiers. |
| */ |
| //@{ |
| |
| /** Expand to an identifier formed by concatenating two identifiers. |
| */ |
| #define __CILKRTS_MKIDENT(a,b) __CILKRTS_MKIDENT_IMP(a,b,) |
| |
| /** Expand to an identifier formed by concatenating three identifiers. |
| */ |
| #define __CILKRTS_MKIDENT3(a,b,c) __CILKRTS_MKIDENT_IMP(a,b,c) |
| |
| /** Helper macro to do the concatenation. |
| */ |
| #define __CILKRTS_MKIDENT_IMP(a,b,c) a ## b ## c |
| |
| //@} |
| |
| /** Compiler-specific keyword for the “type of” operator. |
| */ |
| #if defined(__GNUC__) && !defined(__INTEL_COMPILER) |
| # define _Typeof __typeof__ |
| #endif |
| |
| /** @name Predefined reducer function declaration macros. |
| * |
| * These macros are used to create the function headers for the identity, reduction, |
| * and destructor functions for a builtin reducer family. The macro can be followed by |
| * a semicolon to create a declaration, or by a brace-enclosed body to create a definition. |
| */ |
| //@{ |
| |
| /** Create an identity function header. |
| * |
| * @note The name of the function’s value pointer parameter will always be `v`. |
| * |
| * @param name The reducer family name. |
| * @param tn The type name. |
| */ |
| #define __CILKRTS_DECLARE_REDUCER_IDENTITY(name,tn) CILK_EXPORT \ |
| void __CILKRTS_MKIDENT3(name,_identity_,tn)(void* key, void* v) |
| |
| /** Create a reduction function header. |
| * |
| * @param name The reducer family name. |
| * @param tn The type name. |
| * @param l The name to use for the function’s left value pointer parameter. |
| * @param r The name to use for the function’s right value pointer parameter. |
| */ |
| #define __CILKRTS_DECLARE_REDUCER_REDUCE(name,tn,l,r) CILK_EXPORT \ |
| void __CILKRTS_MKIDENT3(name,_reduce_,tn)(void* key, void* l, void* r) |
| |
| /** Create a destructor function header. |
| * |
| * @param name The reducer family name. |
| * @param tn The type name. |
| * @param p The name to use for the function’s value pointer parameter. |
| */ |
| #define __CILKRTS_DECLARE_REDUCER_DESTROY(name,tn,p) CILK_EXPORT \ |
| void __CILKRTS_MKIDENT3(name,_destroy_,tn)(void* key, void* p) |
| |
| //@} |
| |
| /// @endcond |
| |
| |
| /*************************************************************************** |
| * Real implementation |
| ***************************************************************************/ |
| |
| /** Declaration of a C reducer structure type. |
| * |
| * This macro expands into an anonymous structure declaration for a C reducer structure |
| * which contains a @a Type value. For example: |
| * |
| * CILK_C_DECLARE_REDUCER(int) my_add_int_reducer = |
| * CILK_C_INIT_REDUCER(int, …); |
| * |
| * @param Type The type of the value contained in the reducer object. |
| * |
| * @see @ref reducers_c_creation |
| */ |
| #define CILK_C_DECLARE_REDUCER(Type) struct { \ |
| __cilkrts_hyperobject_base __cilkrts_hyperbase; \ |
| __CILKRTS_CACHE_ALIGN Type value; \ |
| } |
| |
| /** Initializer for a C reducer structure. |
| * |
| * This macro expands into a brace-enclosed structure initializer for a C reducer structure |
| * that was declared with `CILK_C_DECLARE_REDUCER(Type)`. For example: |
| * |
| * CILK_C_DECLARE_REDUCER(int) my_add_int_reducer = |
| * CILK_C_INIT_REDUCER(int, |
| * add_int_reduce, |
| * add_int_identity, |
| * __cilkrts_hyperobject_noop_destroy, |
| * 0); |
| * |
| * @param Type The type of the value contained in the reducer object. Must be the same as |
| * the @a Type argument of the CILK_C_DECLARE_REDUCER macro call that created |
| * the reducer. |
| * @param Reduce The address of the @ref reducers_c_reduce_func "reduce function" for the |
| * reducer. |
| * @param Identity The address of the @ref reducers_c_identity_func "identity function" for |
| * the reducer. |
| * @param Destroy The address of the @ref reducers_c_destroy_func "destroy function" for the |
| * reducer. |
| * @param ... The initial value for the reducer. (A single expression if @a Type is a |
| * scalar type; a list of values if @a Type is a struct or array type.) |
| * |
| * @see @ref reducers_c_creation |
| */ |
| |
| #define CILK_C_INIT_REDUCER(Type, Reduce, Identity, Destroy, ...) \ |
| { { { Reduce \ |
| , Identity \ |
| , Destroy \ |
| , __cilkrts_hyperobject_alloc \ |
| , __cilkrts_hyperobject_dealloc \ |
| } \ |
| , 0 \ |
| , __CILKRTS_CACHE_LINE__ \ |
| , sizeof(Type) \ |
| } \ |
| , __VA_ARGS__ \ |
| } |
| |
| /** Register a reducer with the Cilk runtime. |
| * |
| * The runtime will manage reducer values for all registered reducers when parallel execution |
| * strands begin and end. For example: |
| * |
| * CILK_C_REGISTER_REDUCER(my_add_int_reducer); |
| * cilk_for (int i = 0; i != n; ++i) { |
| * … |
| * } |
| * |
| * @param Expr The reducer to be registered. |
| * |
| * @see @ref page_reducers_in_c |
| */ |
| #define CILK_C_REGISTER_REDUCER(Expr) \ |
| __cilkrts_hyper_create(&(Expr).__cilkrts_hyperbase) |
| |
| /** Unregister a reducer with the Cilk runtime. |
| * |
| * The runtime will stop managing reducer values for a reducer after it is unregistered. For |
| * example: |
| * |
| * cilk_for (int i = 0; i != n; ++i) { |
| * … |
| * } |
| * CILK_C_UNREGISTER_REDUCER(my_add_int_reducer); |
| * |
| * @param Expr The reducer to be unregistered. |
| * |
| * @see @ref page_reducers_in_c |
| */ |
| #define CILK_C_UNREGISTER_REDUCER(Expr) \ |
| __cilkrts_hyper_destroy(&(Expr).__cilkrts_hyperbase) |
| |
| /** Get the current view for a reducer. |
| * |
| * The `REDUCER_VIEW(reducer-name)` returns a reference to the reducer’s value for the |
| * current parallel strand. This can be used to initialize thevalue of the reducer before it |
| * is used, to modify the value of the reducer on the current parallel strand, or to retrieve |
| * the final value of the reducer at the end of the parallel computation. |
| * |
| * REDUCER_VIEW(my_add_int_reducer) = REDUCER_VIEW(my_add_int_reducer) + x; |
| * |
| * @note C++ reducer views restrict access to the wrapped value so that it can only be |
| * modified in ways consistent with the reducer’s operation. No such protection is provided |
| * for C reducers. It is entirely the responsibility of the user to refrain from modifying the |
| * value in any inappropriate way. |
| * |
| * @param Expr The reducer whose value is to be returned. |
| * |
| * @see @ref page_reducers_in_c |
| */ |
| #define REDUCER_VIEW(Expr) (*(_Typeof((Expr).value)*) \ |
| __cilkrts_hyper_lookup(&(Expr).__cilkrts_hyperbase)) |
| |
| //@} C language reducer macros |
| |
| #endif // CILK_REDUCER_H_INCLUDED |
