1 /* reducer.h -*- C++ -*-
3 * Copyright (C) 2009-2016, Intel Corporation
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
10 * * Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in
14 * the documentation and/or other materials provided with the
16 * * Neither the name of Intel Corporation nor the names of its
17 * contributors may be used to endorse or promote products derived
18 * from this software without specific prior written permission.
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
26 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
27 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
28 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
30 * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 * POSSIBILITY OF SUCH DAMAGE.
33 * *********************************************************************
35 * PLEASE NOTE: This file is a downstream copy of a file mainitained in
36 * a repository at cilkplus.org. Changes made to this file that are not
37 * submitted through the contribution process detailed at
38 * http://www.cilkplus.org/submit-cilk-contribution will be lost the next
39 * time that a new version is released. Changes only submitted to the
40 * GNU compiler collection or posted to the git repository at
41 * https://bitbucket.org/intelcilkruntime/intel-cilk-runtime.git are
44 * We welcome your contributions to this open source project. Thank you
45 * for your assistance in helping us improve Cilk Plus.
50 * @brief Defines foundation classes for creating Intel(R) Cilk(TM) Plus reducers.
54 * @see @ref pagereducers
56 * @defgroup Reducers Reducers
59 #ifndef REDUCER_H_INCLUDED
60 #define REDUCER_H_INCLUDED
62 #include "cilk/hyperobject_base.h"
63 #include "cilk/metaprogramming.h"
67 //===================== C++ interfaces ===================================
73 /** Class for provisionally constructed objects.
75 * The monoid_base<T,V>::construct() functions manually construct both a
76 * monoid and a view. If one of these is constructed successfully, and the
77 * construction of the other (or some other initialization) fails, then the
78 * first one must be destroyed to avoid a memory leak. Because the
79 * construction is explicit, the destruction must be explicit, too.
81 * A provisional_guard object wraps a pointer to a newly constructed
82 * object. A call to its confirm() function confirms that the object is
83 * really going to be used. If the guard is destroyed without being
84 * confirmed, then the pointed-to object is destroyed (but not
89 * provisional_guard<T1> x1_provisional( new (x1) T1 );
90 * … more initialization …
91 * x1_provisional.confirm();
95 * provisional_guard<T1> x1_provisional( new (x1) T1 );
96 * x1_provisional.confirm_if( new (x2) T2 );
98 * If an exception is thrown in the "more initialization" code in the
99 * first example, or in the `T2` constructor in the second example, then
100 * `x1_provisional` will not be confirmed, so when its destructor is
101 * called during exception unwinding, the `T1` object that was constructed
102 * in `x1` will be destroyed.
104 * **NOTE**: Do *not* be tempted to chain a `provisional_guard`
105 * constructor with `confirm_if` as in this example:
108 * provisional_guard<T1>( new (x1) T1 ).confirm_if( new (x2) T2 );
110 * The code above is problematic because the evaluation of the T2
111 * constructor is unsequenced with respect to the call to the
112 * `provisional_guard` constructor (and with respect the T1 constructor).
113 * Thus, the compiler may choose to evaluate `new (x2) T2` before
114 * constructing the guard and leak the T1 object if the `T2` constructor
117 * @tparam Type The type of the provisionally constructed object.
119 template <typename Type
>
120 class provisional_guard
{
125 /** Constructor. Creates a guard for a provisionally constructed object.
127 * @param ptr A pointer to the provisionally constructed object.
129 provisional_guard(Type
* ptr
) : m_ptr(ptr
) {}
131 /** Destructor. Destroy the object pointed to by the contained pointer
132 * if it has not been confirmed.
134 ~provisional_guard() { if (m_ptr
) m_ptr
->~Type(); }
136 /** Confirm the provisional construction. Do *not* delete the contained
137 * pointer when the guard is destroyed.
139 void confirm() { m_ptr
= 0; }
141 /** Confirm provisional construction if argument is non-null. Note that
142 * if an exception is thrown during evaluation of the argument
143 * expression, then this function will not be called, and the
144 * provisional object will not be confirmed. This allows the usage:
146 * x1_provisional.confirm_if( new (x2) T2() );
148 * @param cond An arbitrary pointer. The provisional object will be
149 * confirmed if @a cond is not null.
151 * @returns The value of the @a cond argument.
153 template <typename Cond
>
154 Cond
* confirm_if(Cond
* cond
) { if (cond
) m_ptr
= 0; return cond
; }
157 /** Base class for defining monoids.
159 * The monoid_base class template is useful for creating classes that model
160 * the monoid concept. It provides the core type and memory management
161 * functionality. A subclass of monoid_base need only declare and implement
162 * the `identity` and `reduce` functions.
164 * The monoid_base class also manages the integration between the monoid, the
165 * reducer class that is based on it, and an optional view class which wraps
166 * value objects and restricts access to their operations.
168 * @tparam Value The value type for the monoid.
169 * @tparam View An optional view class that serves as a proxy for the value
172 * @see monoid_with_view
174 template <typename Value
, typename View
= Value
>
180 /** Value type of the monoid.
182 typedef Value value_type
;
184 /** View type of the monoid. Defaults to be the same as the value type.
185 * @see monoid_with_view
187 typedef View view_type
;
190 /** Should reducers created with this monoid be aligned?
193 * "Aligned" means that the view is allocated at a cache-line aligned
194 * offset in the reducer, and the reducer must be cache-line aligned.
195 * "Unaligned" means that the reducer as a whole is just naturally
196 * aligned, but it contains a large enough block of uninitialized
197 * storage for a cache-line aligned view to be allocated in it at
198 * reducer construction time.
200 * Since the standard heap allocator (new reducer) does not allocate
201 * cache-line aligned storage, only unaligned reducers can be safely
202 * allocated on the heap.
204 * Default is false (unaligned) unless overridden in a subclass.
207 * (In Intel Cilk Plus library versions 1.0 and 1.01, the default was true.
208 * In Intel Cilk Plus library versions prior to 1.0, reducers were always
209 * aligned, and this data member did not exist.)
211 align_reducer
= false
214 /** Destroys a view. Destroys (without deallocating) the @a View object
215 * pointed to by @a p.
217 * @param p The address of the @a View object to be destroyed.
219 void destroy(view_type
* p
) const { p
->~view_type(); }
221 /** Allocates raw memory. Allocate @a s bytes of memory with no
224 * @param s The number of bytes of memory to allocate.
225 * @return An untyped pointer to the allocated memory.
227 void* allocate(size_t s
) const { return operator new(s
); }
229 /** Deallocates raw memory pointed to by @a p
230 * without doing any destruction.
232 * @param p Pointer to the memory to be deallocated.
234 * @pre @a p points to a block of memory that was allocated by a
235 * call to allocate().
237 void deallocate(void* p
) const { operator delete(p
); }
239 /** Creates the identity value. Constructs (without allocating) a @a View
240 * object representing the default value of the @a Value type.
242 * @param p A pointer to a block of raw memory large enough to hold a
245 * @post The memory pointed to by @a p contains a @a View object that
246 * represents the default value of the @a View type.
248 * @deprecated This function constructs the @a View object with its default
249 * constructor, which will often, but not always, yield the
250 * appropriate identity value. Monoid classes should declare
251 * their identity function explicitly, rather than relying on
252 * this default definition.
254 void identity(View
* p
) const { new ((void*) p
) View(); }
257 /** @name Constructs the monoid and the view with arbitrary arguments.
259 * A @ref reducer object contains monoid and view data members, which are
260 * declared as raw storage (byte arrays), so that they are not implicitly
261 * constructed when the reducer is constructed. Instead, a reducer
262 * constructor calls one of the monoid class's static construct()
263 * functions with the addresses of the monoid and the view, and the
264 * construct() function uses placement `new` to construct them.
265 * This allows the monoid to determine the order in which the monoid and
266 * view are constructed, and to make one of them dependent on the other.
268 * Any arguments to the reducer constructor are just passed on as
269 * additional arguments to the construct() function (after the monoid
270 * and view addresses are set).
272 * A monoid whose needs are satisfied by the suite of construct()
273 * functions below, such as @ref monoid_with_view, can just inherit them
274 * from monoid_base. Other monoids will need to provide their own versions
275 * to override the monoid_base functions.
279 /** Default-constructs the monoid, identity-constructs the view.
281 * @param monoid Address of uninitialized monoid object.
282 * @param view Address of uninitialized initial view object.
285 template <typename Monoid
>
286 static void construct(Monoid
* monoid
, View
* view
)
288 provisional_guard
<Monoid
> guard( new((void*) monoid
) Monoid() );
289 monoid
->identity(view
);
294 /** Default-constructs the monoid, and passes one to five const reference
295 * arguments to the view constructor.
299 template <typename Monoid
, typename T1
>
300 static void construct(Monoid
* monoid
, View
* view
, const T1
& x1
)
302 provisional_guard
<Monoid
> guard( new((void*) monoid
) Monoid() );
303 guard
.confirm_if( new((void*) view
) View(x1
) );
306 template <typename Monoid
, typename T1
, typename T2
>
307 static void construct(Monoid
* monoid
, View
* view
,
308 const T1
& x1
, const T2
& x2
)
310 provisional_guard
<Monoid
> guard( new((void*) monoid
) Monoid() );
311 guard
.confirm_if( new((void*) view
) View(x1
, x2
) );
314 template <typename Monoid
, typename T1
, typename T2
, typename T3
>
315 static void construct(Monoid
* monoid
, View
* view
,
316 const T1
& x1
, const T2
& x2
, const T3
& x3
)
318 provisional_guard
<Monoid
> guard( new((void*) monoid
) Monoid() );
319 guard
.confirm_if( new((void*) view
) View(x1
, x2
, x3
) );
322 template <typename Monoid
, typename T1
, typename T2
, typename T3
,
324 static void construct(Monoid
* monoid
, View
* view
,
325 const T1
& x1
, const T2
& x2
, const T3
& x3
,
328 provisional_guard
<Monoid
> guard( new((void*) monoid
) Monoid() );
329 guard
.confirm_if( new((void*) view
) View(x1
, x2
, x3
, x4
) );
332 template <typename Monoid
, typename T1
, typename T2
, typename T3
,
333 typename T4
, typename T5
>
334 static void construct(Monoid
* monoid
, View
* view
,
335 const T1
& x1
, const T2
& x2
, const T3
& x3
,
336 const T4
& x4
, const T5
& x5
)
338 provisional_guard
<Monoid
> guard( new((void*) monoid
) Monoid() );
339 guard
.confirm_if( new((void*) view
) View(x1
, x2
, x3
, x4
, x5
) );
344 /** Default-constructs the monoid, and passes one non-const reference
345 * argument to the view constructor.
348 template <typename Monoid
, typename T1
>
349 static void construct(Monoid
* monoid
, View
* view
, T1
& x1
)
351 provisional_guard
<Monoid
> guard( new((void*) monoid
) Monoid() );
352 guard
.confirm_if( new((void*) view
) View(x1
) );
356 /** Copy-constructs the monoid, and identity-constructs the view
359 * @param monoid Address of uninitialized monoid object.
360 * @param view Address of uninitialized initial view object.
361 * @param m Object to be copied into `*monoid`
364 template <typename Monoid
>
365 static void construct(Monoid
* monoid
, View
* view
, const Monoid
& m
)
367 provisional_guard
<Monoid
> guard( new((void*) monoid
) Monoid(m
) );
368 monoid
->identity(view
);
373 /** Copy-constructs the monoid, and passes one to four const reference
374 * arguments to the view constructor.
378 template <typename Monoid
, typename T1
>
379 static void construct(Monoid
* monoid
, View
* view
, const Monoid
& m
,
382 provisional_guard
<Monoid
> guard( new((void*) monoid
) Monoid(m
) );
383 guard
.confirm_if( new((void*) view
) View(x1
) );
386 template <typename Monoid
, typename T1
, typename T2
>
387 static void construct(Monoid
* monoid
, View
* view
, const Monoid
& m
,
388 const T1
& x1
, const T2
& x2
)
390 provisional_guard
<Monoid
> guard( new((void*) monoid
) Monoid(m
) );
391 guard
.confirm_if( new((void*) view
) View(x1
, x2
) );
394 template <typename Monoid
, typename T1
, typename T2
, typename T3
>
395 static void construct(Monoid
* monoid
, View
* view
, const Monoid
& m
,
396 const T1
& x1
, const T2
& x2
, const T3
& x3
)
398 provisional_guard
<Monoid
> guard( new((void*) monoid
) Monoid(m
) );
399 guard
.confirm_if( new((void*) view
) View(x1
, x2
, x3
) );
402 template <typename Monoid
, typename T1
, typename T2
, typename T3
,
404 static void construct(Monoid
* monoid
, View
* view
, const Monoid
& m
,
405 const T1
& x1
, const T2
& x2
, const T3
& x3
,
408 provisional_guard
<Monoid
> guard( new((void*) monoid
) Monoid(m
) );
409 guard
.confirm_if( new((void*) view
) View(x1
, x2
, x3
, x4
) );
418 /** Monoid class that gets its value type and identity and reduce operations
421 * A simple implementation of the monoid-view-reducer architecture would
422 * distribute knowledge about the type and operations for the reduction
423 * between the monoid and the view - the identity and reduction operations are
424 * specified in the monoid, the reduction operations are implemented in the
425 * view, and the value type is specified in both the monoid and the view.
428 * monoid_with_view is a subclass of @ref monoid_base that gets its value type
429 * and its identity and reduction operations from its view class. No
430 * customization of the monoid_with_view class itself is needed beyond
431 * instantiating it with an appropriate view class. (Customized subclasses of
432 * monoid_with_view may be needed for other reasons, such as to keep some
433 * state for the reducer.) All of the Intel Cilk Plus predefined reducers use
434 * monoid_with_view or one of its subclasses.
436 * The view class `View` of a monoid_with_view must provide the following
437 * public definitions:
439 * Definition | Meaning
440 * ---------------------------------|--------
441 * `value_type` | a typedef of the value type for the reduction
442 * `View()` | a default constructor which constructs the identity value for the reduction
443 * `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)
445 * @tparam View The view class for the monoid.
446 * @tparam Align If true, reducers instantiated on this monoid will be
447 * cache-aligned. By default, library reducers (unlike legacy
448 * library reducer _wrappers_) are aligned only as required by
451 template <class View
, bool Align
= false>
452 class monoid_with_view
: public monoid_base
<typename
View::value_type
, View
>
455 /** Should reducers created with this monoid be aligned?
457 enum { align_reducer
= Align
};
459 /** Create the identity value.
461 * Implements the monoid `identity` operation by using the @a View class's
462 * default constructor.
464 * @param p A pointer to a block of raw memory large enough to hold a
467 void identity(View
* p
) const { new((void*) p
) View(); }
469 /** Reduce the values of two views.
471 * Implements the monoid `reduce` operation by calling the left view's
472 * `%reduce()` function with the right view as an operand.
474 * @param left The left operand of the reduce operation.
475 * @param right The right operand of the reduce operation.
476 * @post The left view contains the result of the reduce
477 * operation, and the right view is undefined.
479 void reduce(View
* left
, View
* right
) const { left
->reduce(right
); }
483 /** Base class for simple views with (usually) scalar values.
485 * The scalar_view class is intended as a base class which provides about half
486 * of the required definitions for simple views. It defines the `value_type`
487 * required by a @ref monoid_with_view (but not the identity constructor and
488 * reduce operation, which are inherently specific to a particular kind of
489 * reduction). It also defines the value access functions which will be called
490 * by the corresponding @ref reducer functions. (It uses copy semantics for
491 * the view_move_in() and view_move_out() functions, which is appropriate
492 * for simple scalar types, but not necessarily for more complex types like
495 * @tparam Type The type of value wrapped by the view.
497 template <typename Type
>
501 Type m_value
; ///< The wrapped accumulator variable.
504 /** Value type definition required by @ref monoid_with_view.
506 typedef Type value_type
;
508 /** Default constructor.
510 scalar_view() : m_value() {}
512 /** Value constructor.
514 scalar_view(const Type
& v
) : m_value(v
) {}
516 /** @name Value functions required by the reducer class.
518 * Note that the move in/out functions use simple assignment semantics.
522 /** Set the value of the view.
524 void view_move_in(Type
& v
) { m_value
= v
; }
526 /** Get the value of the view.
528 void view_move_out(Type
& v
) { v
= m_value
; }
530 /** Set the value of the view.
532 void view_set_value(const Type
& v
) { m_value
= v
; }
534 /** Get the value of the view.
536 Type
const& view_get_value() const { return m_value
; }
538 /** Type returned by view_get_value.
540 typedef Type
const& return_type_for_get_value
;
542 /** Get a reference to the value contained in the view. For legacy
543 * reducer support only.
545 Type
& view_get_reference() { return m_value
; }
547 /** Get a reference to the value contained in the view. For legacy
548 * reducer support only.
550 Type
const& view_get_reference() const { return m_value
; }
555 /** Wrapper class for move-in construction.
557 * Some types allow their values to be _moved_ as an alternative to copying.
558 * Moving a value may be much faster than copying it, but may leave the value
559 * of the move's source undefined. Consider the `swap` operation provided by
560 * many STL container classes:
566 * The assignment _copies_ the value of `y` into `x` in time linear in the
567 * size of `y`, leaving `y` unchanged. The `swap` _moves_ the value of `y`
568 * into `x` in constant time, but it also moves the value of `x` into `y`,
569 * potentially leaving `y` undefined.
571 * A move_in_wrapper simply wraps a pointer to an object. It is created by a
572 * call to cilk::move_in(). Passing a move_in_wrapper to a view constructor
573 * (actually, passing it to a reducer constructor, which passes it to the
574 * monoid `construct()` function, which passes it to the view constructor)
575 * allows, but does not require, the value pointed to by the wrapper to be
576 * moved into the view instead of copied.
578 * A view class exercises this option by defining a _move-in constructor_,
579 * i.e., a constructor with a move_in_wrapper parameter. The constructor calls
580 * the wrapper's `value()` function to get a reference to its pointed-to
581 * value, and can then use that reference in a move operation.
583 * A move_in_wrapper also has an implicit conversion to its pointed-to value,
584 * so if a view class does not define a move-in constructor, its ordinary
585 * value constructor will be called with the wrapped value. For example, an
586 * @ref ReducersAdd "op_add" view does not have a move-in constructor, so
589 * reducer< op_add<int> > xr(move_in(x));
591 * will simply call the `op_add_view(const int &)` constructor. But an
592 * @ref ReducersList "op_list_append" view does have a move-in constructor,
596 * reducer< op_list_append<int> > xr(move_in(x));
598 * will call the `op_list_append_view(move_in_wrapper<int>)` constructor,
599 * which can `swap` the value of `x` into the view.
601 * @note Remember that passing the value of a variable to a reducer
602 * constructor using a move_in_wrapper leaves the variable undefined.
603 * You cannot assume that the constructor either will or will not copy
606 * @tparam Type The type of the wrapped value.
608 * @see cilk::move_in()
610 template <typename Type
>
611 class move_in_wrapper
616 /** Constructor that captures the address of its argument. This is almost
617 * always called from the @ref move_in function.
619 explicit move_in_wrapper(Type
& ref
) : m_pointer(&ref
) { }
621 /** Implicit conversion to the wrapped value. This allows a move_in_wrapper
622 * to be used where a value of the wrapped type is expected, in which case
623 * the wrapper is completely transparent.
625 operator Type
&() const { return *m_pointer
; }
627 /** Get a reference to the pointed-to value. This has the same effect as
628 * the implicit conversion, but makes the intent clearer in a move-in
631 Type
& value() const { return *m_pointer
; }
634 /** Function to create a move_in_wrapper for a value.
636 * @tparam Type The type of the argument, which will be the `type` of the
639 * @see move_in_wrapper
641 template <typename Type
>
643 move_in_wrapper
<Type
> move_in(Type
& ref
)
644 { return move_in_wrapper
<Type
>(ref
); }
647 /** @copydoc move_in(Type&)
649 * @note Applying a function that is explicitly specified as modifying its
650 * argument to a const argument is obviously an irrational thing to
651 * do. This move_in() variant is just provided to allow calling a
652 * move-in constructor with a function return value, which the
653 * language treats as a const. Using it for any other purpose will
654 * probably end in tears.
656 template <typename Type
>
658 move_in_wrapper
<Type
> move_in(const Type
& ref
)
659 { return move_in_wrapper
<Type
>(ref
); }
662 /** Wrapper class to allow implicit downcasts to reducer subclasses.
664 * The Intel Cilk Plus library contains a collection of reducer wrapper classes which
665 * were created before the `cilk::reducer<Monoid>` style was developed. For
666 * example, `cilk::reducer_opadd<Type>` provided essentially the same
667 * functionality that is now provided by
668 * `cilk::reducer< cilk::op_add<Type> >`. These legacy reducer classes are
669 * deprecated, but still supported, and they have been reimplemented as
670 * subclasses of the corresponding `cilk::reducer` classes. For example:
673 * reducer_opadd<T> : public reducer< op_add<T> > { ... };
675 * This reimplementation allows transparent conversion between legacy and
676 * new reducers. That is, a `reducer<op_add>*` or `reducer<op_add>&` can be
677 * used anywhere that a `reducer_opadd*` or `reducer_opadd&` is expected,
680 * The conversion from the legacy reducer to the new reducer is just an
681 * up-cast, which is provided for free by C++. The conversion from the new
682 * reducer to the legacy reducer is a down-cast, though, which requires an
683 * explicit conversion member function in the `reducer` class. The challenge
684 * is to define a function in the reducer template class which will convert
685 * each cilk::reducer specialization to the corresponding legacy reducer,
688 * The trick is in the legacy_reducer_downcast template class, which provides
689 * a mapping from `cilk::reducer` specializations to legacy reducer classes.
690 * `reducer<Monoid>` has a conversion function to convert itself to
691 * `legacy_reducer_downcast< reducer<Monoid> >::%type`. By default,
692 * `legacy_reducer_downcast<Reducer>::%type` is just a trivial subclass of
693 * `Reducer`, which is uninteresting, but a reducer with a legacy counterpart
694 * will have a specialization of `legacy_reducer_downcast` whose `type` is
695 * the corresponding legacy reducer. For example:
697 * template <typename Type>
698 * struct legacy_reducer_downcast< reducer< op_add<Type> > >
700 * typedef reducer_opadd<Type> type;
704 * @tparam Reducer The new-style reducer class whose corresponding legacy
705 * reducer class is `type`, if there is such a legacy reducer
708 template <typename Reducer
>
709 struct legacy_reducer_downcast
711 /** The related legacy reducer class.
713 * By default, this is just a trivial subclass of Reducer, but it can be
714 * overridden in the specialization of legacy_reducer_downcast for
715 * a reducer that has a corresponding legacy reducers.
717 struct type
: Reducer
{ };
724 template <typename Value
, typename View
>
725 struct reducer_set_get
727 // sizeof(notchar) != sizeof(char)
728 struct notchar
{ char x
[2]; };
730 // `does_view_define_return_type_for_get_value(View*)` returns `char` if
731 // `View` defines `return_type_for_get_value`, and `notchar` if it doesn't.
733 template <typename T
>
734 struct using_type
{};
736 template <typename T
>
737 static char does_view_define_return_type_for_get_value(
738 using_type
<typename
T::return_type_for_get_value
>*);
740 template <typename T
>
741 static notchar
does_view_define_return_type_for_get_value(...);
743 // `VIEW_DOES_DEFINE_RETURN_TYPE_FOR_GET_VALUE` is true if `View` defines
744 // `return_type_for_get_value`.
746 enum { VIEW_DOES_DEFINE_RETURN_TYPE_FOR_GET_VALUE
=
747 sizeof( does_view_define_return_type_for_get_value
<View
>(0) )
750 // `return_type_for_get_value` is `View::return_type_for_get_value`
751 // if it is defined, and just `Value` otherwise.
753 template <typename InnerView
, bool ViewDoesDefineReturnTypeForGetValue
>
754 struct return_type_for_view_get_value
{
758 template <typename InnerView
>
759 struct return_type_for_view_get_value
<InnerView
, true> {
760 typedef typename
InnerView::return_type_for_get_value type
;
767 return_type_for_view_get_value
<
769 VIEW_DOES_DEFINE_RETURN_TYPE_FOR_GET_VALUE
771 return_type_for_get_value
;
773 static void move_in(View
& view
, Value
& v
) { view
.view_move_in(v
); }
774 static void move_out(View
& view
, Value
& v
) { view
.view_move_out(v
); }
776 static void set_value(View
& view
, const Value
& v
)
777 { view
.view_set_value(v
); }
779 static return_type_for_get_value
get_value(const View
& view
)
780 { return view
.view_get_value(); }
783 template <typename Value
>
784 struct reducer_set_get
<Value
, Value
>
786 typedef const Value
& return_type_for_get_value
;
788 static void move_in(Value
& view
, Value
& v
) { view
= v
; }
789 static void move_out(Value
& view
, Value
& v
) { v
= view
; }
791 static void set_value(Value
& view
, const Value
& v
)
794 static return_type_for_get_value
get_value(const Value
& view
)
801 /** Base class defining the data layout that is common to all reducers.
803 template <typename Monoid
>
805 typedef typename
Monoid::view_type view_type
;
807 // This makes the reducer a hyper-object. (Partially initialized in
808 // the derived reducer_content class.)
810 __cilkrts_hyperobject_base m_base
;
812 // The monoid is allocated here as raw bytes, and is constructed explicitly
813 // by a call to the monoid_type::construct() function in the constructor of
814 // the `reducer` subclass.
816 storage_for_object
<Monoid
> m_monoid
;
818 // Used for sanity checking at destruction.
822 // The leftmost view comes next. It is defined in the derived
823 // reducer_content class.
825 /** @name C-callable wrappers for the C++-coded monoid dispatch functions.
829 static void reduce_wrapper(void* r
, void* lhs
, void* rhs
);
830 static void identity_wrapper(void* r
, void* view
);
831 static void destroy_wrapper(void* r
, void* view
);
832 static void* allocate_wrapper(void* r
, __STDNS
size_t bytes
);
833 static void deallocate_wrapper(void* r
, void* view
);
841 * @param leftmost The address of the leftmost view in the reducer.
843 reducer_base(char* leftmost
)
845 static const cilk_c_monoid c_monoid_initializer
= {
846 (cilk_c_reducer_reduce_fn_t
) &reduce_wrapper
,
847 (cilk_c_reducer_identity_fn_t
) &identity_wrapper
,
848 (cilk_c_reducer_destroy_fn_t
) &destroy_wrapper
,
849 (cilk_c_reducer_allocate_fn_t
) &allocate_wrapper
,
850 (cilk_c_reducer_deallocate_fn_t
) &deallocate_wrapper
853 m_base
.__c_monoid
= c_monoid_initializer
;
855 m_base
.__view_offset
= (char*)leftmost
- (char*)this;
856 m_base
.__view_size
= sizeof(view_type
);
857 m_initialThis
= this;
859 __cilkrts_hyper_create(&m_base
);
864 __CILKRTS_STRAND_STALE(~reducer_base())
866 // Make sure we haven't been memcopy'd or corrupted
868 this == m_initialThis
||
869 // Allow for a layout bug that may put the initialThis field one
870 // word later in 1.0 reducers than in 0.9 and 1.1 reducers.
871 this == *(&m_initialThis
+ 1)
873 __cilkrts_hyper_destroy(&m_base
);
876 /** Monoid data member.
878 * @return A pointer to the reducer's monoid data member.
880 Monoid
* monoid_ptr() { return &m_monoid
.object(); }
882 /** Leftmost view data member.
884 * @return A pointer to the reducer's leftmost view data member.
886 * @note This function returns the address of the *leftmost* view,
887 * which is unique for the lifetime of the reducer. It is
888 * intended to be used in constructors and destructors.
889 * Use the reducer::view() function to access the per-strand
892 view_type
* leftmost_ptr()
894 char* view_addr
= (char*)this + m_base
.__view_offset
;
895 return reinterpret_cast<view_type
*>(view_addr
);
900 /** @name Access the current view.
902 * These functions return a reference to the instance of the reducer's
903 * view that was created for the current strand of a parallel computation
904 * (and create it if it doesn't already exist). Note the difference from
905 * the (private) leftmost_ptr() function, which returns a pointer to the
906 * _leftmost_ view, which is the same in all strands.
910 /** Per-strand view instance.
912 * @return A reference to the per-strand view instance.
916 return *static_cast<view_type
*>(__cilkrts_hyper_lookup(&m_base
));
921 const view_type
& view() const
923 return const_cast<reducer_base
*>(this)->view();
928 /** Initial view pointer field.
932 * @return a reference to the m_initialThis field.
934 * @note This function is provided for "white-box" testing of the
935 * reducer layout code. There is never any reason for user code
938 const void* const & initial_this() const { return m_initialThis
; }
941 template <typename Monoid
>
942 void reducer_base
<Monoid
>::reduce_wrapper(void* r
, void* lhs
, void* rhs
)
944 Monoid
* monoid
= static_cast<reducer_base
*>(r
)->monoid_ptr();
945 monoid
->reduce(static_cast<view_type
*>(lhs
),
946 static_cast<view_type
*>(rhs
));
949 template <typename Monoid
>
950 void reducer_base
<Monoid
>::identity_wrapper(void* r
, void* view
)
952 Monoid
* monoid
= static_cast<reducer_base
*>(r
)->monoid_ptr();
953 monoid
->identity(static_cast<view_type
*>(view
));
956 template <typename Monoid
>
957 void reducer_base
<Monoid
>::destroy_wrapper(void* r
, void* view
)
959 Monoid
* monoid
= static_cast<reducer_base
*>(r
)->monoid_ptr();
960 monoid
->destroy(static_cast<view_type
*>(view
));
963 template <typename Monoid
>
964 void* reducer_base
<Monoid
>::allocate_wrapper(void* r
, __STDNS
size_t bytes
)
966 Monoid
* monoid
= static_cast<reducer_base
*>(r
)->monoid_ptr();
967 return monoid
->allocate(bytes
);
970 template <typename Monoid
>
971 void reducer_base
<Monoid
>::deallocate_wrapper(void* r
, void* view
)
973 Monoid
* monoid
= static_cast<reducer_base
*>(r
)->monoid_ptr();
974 monoid
->deallocate(static_cast<view_type
*>(view
));
978 /** Base class defining the data members of a reducer.
980 * @tparam Aligned The `m_view` data member, and therefore the entire
981 * structure, are cache-line aligned if this parameter
984 template <typename Monoid
, bool Aligned
= Monoid::align_reducer
>
985 class reducer_content
;
987 /** Base class defining the data members of an aligned reducer.
989 template <typename Monoid
>
990 class reducer_content
<Monoid
, true> : public reducer_base
<Monoid
>
992 typedef typename
Monoid::view_type view_type
;
994 // The leftmost view is defined as raw bytes. It will be constructed
995 // by the monoid `construct` function. It is cache-aligned, which
996 // will push it into a new cache line. Furthermore, its alignment causes
997 // the reducer as a whole to be cache-aligned, which makes the reducer
998 // size a multiple of a cache line. Since there is nothing in the reducer
999 // after the view, all this means that the leftmost view gets one or more
1000 // cache lines all to itself, which prevents false sharing.
1002 __CILKRTS_CACHE_ALIGN
1003 char m_leftmost
[sizeof(view_type
)];
1005 /** Test if the reducer is cache-line-aligned.
1007 * Used in assertions.
1009 bool reducer_is_cache_aligned() const
1010 { return 0 == ((std::size_t) this & (__CILKRTS_CACHE_LINE__
- 1)); }
1016 reducer_content() : reducer_base
<Monoid
>((char*)&m_leftmost
)
1018 #ifndef CILK_IGNORE_REDUCER_ALIGNMENT
1019 assert(reducer_is_cache_aligned() &&
1020 "Reducer should be cache aligned. Please see comments following "
1021 "this assertion for explanation and fixes.");
1023 /* "REDUCER SHOULD BE CACHE ALIGNED" ASSERTION.
1025 * This Reducer class instantiation specifies cache-line alignment of the
1026 * leftmost view field (and, implicitly, of the reducer itself). You got
1027 * this assertion because a reducer with this class was allocated at a
1028 * non-cache-aligned address, probably because it was allocated on the
1029 * heap with `new`. This can be a problem for two reasons:
1031 * 1. If the leftmost view is not on a cache line by itself, there might
1032 * be a slowdown resulting from accesses to the same cache line from
1033 * different threads.
1035 * 2. The compiler thinks that reducer is cache-line aligned, but it
1036 * really isn't. If the reducer is contained in a structure, then the
1037 * compiler will believe that the containing structure, and other
1038 * fields contained in it, are also more aligned than they really
1039 * are. In particular, if the structure contains a numeric array that
1040 * is used in a vectorizable loop, then the compiler might generate
1041 * invalid vector instructions, resulting in a runtime error.
1043 * The compiler will always allocate reducer variables, and structure
1044 * variables containing reducers, with their required alignment.
1045 * Reducers, and structures containing a reducer, which are allocated
1046 * on the heap with `new` will _not_ be properly aligned.
1048 * There are three ways that you can fix this assertion failure.
1050 * A. Rewrite your code to use the new-style `reducer< op_XXX<Type> >`
1051 * instead of the legacy `reducer_XXX<type>`. The new-style reducers
1052 * are not declared to be cache-aligned, and will work properly if
1053 * they are not cache-aligned.
1055 * B. If you must allocate an old-style reducer or a structure containing
1056 * a reducer on the heap, figure out how to align it correctly. The
1057 * suggested fix is to use `cilk::aligned_new()` and
1058 * `cilk::aligned_delete()` instead of `new` and `delete`, as follows:
1060 * Type* ptr = cilk::aligned_new<Type>(constructor-arguments);
1061 * cilk::aligned_delete(ptr);
1063 * C. Define the macro CILK_IGNORE_REDUCER_ALIGNMENT, which will suppress
1064 * the assertion check. Do this only if you are comfortable that
1065 * problem (2) above will not occur.
1070 /** Base class defining the data members of an unaligned reducer.
1072 template <typename Monoid
>
1073 class reducer_content
<Monoid
, false> : public reducer_base
<Monoid
>
1075 typedef typename
Monoid::view_type view_type
; ///< The view type.
1077 // Reserve space for the leftmost view. The view will be allocated at an
1078 // aligned offset in this space at runtime, to guarantee that the view
1079 // will get one or more cache lines all to itself, to prevent false
1082 // The number of bytes to reserve is determined as follows:
1083 // * Start with the view size.
1084 // * Round up to a multiple of the cache line size, to get the total size
1085 // of the cache lines that will be dedicated to the view.
1086 // * Add (cache line size - 1) filler bytes to guarantee that the reserved
1087 // area will contain a cache-aligned block of the required cache lines,
1088 // no matter where the reserved area starts.
1091 // View size rounded up to multiple cache lines
1092 ( (sizeof(view_type
) + __CILKRTS_CACHE_LINE__
- 1)
1093 & ~ (__CILKRTS_CACHE_LINE__
- 1)
1095 // plus filler to allow alignment.
1096 + __CILKRTS_CACHE_LINE__
- 1
1101 /** Constructor. Find the first cache-aligned position in the reserved
1102 * area, and pass it to the base constructor as the leftmost view
1106 reducer_base
<Monoid
>(
1107 (char*)( ((std::size_t)&m_leftmost
+ __CILKRTS_CACHE_LINE__
- 1)
1108 & ~ (__CILKRTS_CACHE_LINE__
- 1) ) )
1113 } // namespace internal
1116 // The __cilkrts_hyperobject_ functions are defined differently depending on
1117 // whether a file is compiled with or without the CILK_STUB option. Therefore,
1118 // reducers compiled in the two modes should be link-time incompatible, so that
1119 // object files compiled with stubbed reducers won't be linked into an
1120 // unstubbed program, or vice versa. We achieve this by putting the reducer
1121 // class definition into the cilk::stub namespace in a stubbed compilation.
1129 * A reducer is instantiated on a Monoid. The Monoid provides the value
1130 * type, associative reduce function, and identity for the reducer.
1132 * @tparam Monoid The monoid class that the reducer is instantiated on. It
1133 * must model the @ref reducers_monoid_concept "monoid
1136 * @see @ref pagereducers
1138 template <class Monoid
>
1139 class reducer
: public internal::reducer_content
<Monoid
>
1141 typedef internal::reducer_content
<Monoid
> base
;
1142 using base::monoid_ptr
;
1143 using base::leftmost_ptr
;
1145 typedef Monoid monoid_type
; ///< The monoid type.
1146 typedef typename
Monoid::value_type value_type
; ///< The value type.
1147 typedef typename
Monoid::view_type view_type
; ///< The view type.
1150 typedef internal::reducer_set_get
<value_type
, view_type
> set_get
;
1152 reducer(const reducer
&); ///< Disallow copying.
1153 reducer
& operator=(const reducer
&); ///< Disallow assignment.
1157 /** @name Constructors
1159 * All reducer constructors call the static `construct()` function of the
1160 * monoid class to construct the reducer's monoid and leftmost view.
1162 * The reducer constructor arguments are simply passed through to the
1163 * construct() function. Thus, the constructor parameters accepted by a
1164 * particular reducer class are determined by its monoid class.
1168 /** 0 – 6 const reference parameters.
1174 monoid_type::construct(monoid_ptr(), leftmost_ptr());
1177 template <typename T1
>
1178 reducer(const T1
& x1
)
1180 monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1
);
1183 template <typename T1
, typename T2
>
1184 reducer(const T1
& x1
, const T2
& x2
)
1186 monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1
, x2
);
1189 template <typename T1
, typename T2
, typename T3
>
1190 reducer(const T1
& x1
, const T2
& x2
, const T3
& x3
)
1192 monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1
, x2
, x3
);
1195 template <typename T1
, typename T2
, typename T3
, typename T4
>
1196 reducer(const T1
& x1
, const T2
& x2
, const T3
& x3
, const T4
& x4
)
1198 monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1
, x2
, x3
, x4
);
1201 template <typename T1
, typename T2
, typename T3
, typename T4
, typename T5
>
1202 reducer(const T1
& x1
, const T2
& x2
, const T3
& x3
, const T4
& x4
,
1205 monoid_type::construct(monoid_ptr(), leftmost_ptr(),
1206 x1
, x2
, x3
, x4
, x5
);
1209 template <typename T1
, typename T2
, typename T3
, typename T4
,
1210 typename T5
, typename T6
>
1211 reducer(const T1
& x1
, const T2
& x2
, const T3
& x3
, const T4
& x4
,
1212 const T5
& x5
, const T6
& x6
)
1214 monoid_type::construct(monoid_ptr(), leftmost_ptr(),
1215 x1
, x2
, x3
, x4
, x5
, x6
);
1220 /** 1 non-const reference parameter.
1224 template <typename T1
>
1227 monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1
);
1234 __CILKRTS_STRAND_STALE(~reducer())
1236 leftmost_ptr()->~view_type();
1237 monoid_ptr()->~monoid_type();
1243 * @return A reference to the monoid object belonging to this reducer.
1245 Monoid
& monoid() { return *monoid_ptr(); }
1247 const Monoid
& monoid() const
1248 { return const_cast<reducer
*>(this)->monoid(); }
1252 /** Access the current view.
1254 * Return a reference to the instance of the reducer's view that was
1255 * created for the current strand of a parallel computation (and create
1256 * it if it doesn't already exist).
1258 view_type
& view() { return base::view(); }
1259 const view_type
& view() const { return base::view(); }
1263 /** @name Dereference the reducer to get the view.
1265 * "Dereferencing" a reducer yields the view for the current strand. The
1266 * view, in turn, acts as a proxy for its contained value, exposing only
1267 * those operations which are consistent with the reducer's monoid. Thus,
1268 * all modifications of the reducer's accumulator variable are written as
1274 * reducer->func(...)
1276 * (The permitted operations on a reducer's accumulator are listed in the
1277 * documentation for that particular kind of reducer.)
1279 * @note `*r` is a synonym for `r.view()`. Recommended style is to use
1280 * `*r` (or `r->`) in the common case where code is simply
1281 * updating the accumulator variable wrapped in the view, and to
1282 * use `r.view()` in the unusual case where it is desirable to
1283 * call attention to the view itself.
1288 /** Dereference operator.
1290 * @return A reference to the per-strand view instance.
1292 view_type
& operator*() { return view(); }
1293 view_type
const& operator*() const { return view(); }
1297 /** Pointer operator.
1299 * @return A pointer to the per-strand view instance.
1301 view_type
* operator->() { return &view(); }
1302 view_type
const* operator->() const { return &view(); }
1306 /** Deprecated view access.
1308 * `r()` is a synonym for `*r` which was used with early versions of
1309 * Intel Cilk Plus reducers. `*r` is now the preferred usage.
1311 * @deprecated Use operator*() instead of operator()().
1313 * @return A reference to the per-strand view instance.
1315 view_type
& operator()() { return view(); }
1316 view_type
const& operator()() const { return view(); }
1321 /** @name Set and get the value.
1323 * These functions are used to set an initial value for the reducer before
1324 * starting the reduction, or to get the final value after the reduction
1327 * @note These functions are completely different from the view
1328 * operations that are made available via operator*() and
1329 * operator->(), which are used to _modify_ the reducer's value
1330 * _during_ the reduction.
1332 * @warning These functions _can_ be called at any time, and in
1333 * general, they will refer to the value contained in the view
1334 * for the current strand. However, using them other than to
1335 * set the reduction's initial value or get its final value
1336 * will almost always result in undefined behavior.
1340 /** Move a value into the reducer.
1342 * This function is used to set the initial value of the reducer's
1343 * accumulator variable by either copying or _moving_ the value of @a obj
1344 * into it. Moving a value can often be performed in constant time, even
1345 * for large container objects, but has the side effect of leaving the
1346 * value of @a obj undefined. (See the description of the
1347 * @ref move_in_wrapper class for a discussion of moving values.)
1350 * A move_in() call to initialize a reducer is often paired with a
1351 * move_out() call to get its final value:
1355 * … do the reduction …
1359 * - You cannot assume either that this will function will copy its
1360 * value or that it will move it.
1361 * - You must assume that the value of @a obj will be undefined
1362 * after the call to move_in().
1363 * - You can assume that move_in() will be at least as efficient as
1364 * set_value(), and you should therefore prefer move_in() unless
1365 * you need the value of @a obj to be unchanged after the call.
1366 * (But you should usually prefer the move-in constructor over a
1367 * move_in() call - see the note below.)
1369 * @note The behavior of a default constructor followed by move-in
1375 * @note is not necessarily the same as a move-in constructor:
1377 * reducer<Type> xr(move_in(x));
1379 * @note In particular, when @a Type is a container type with a
1380 * non-empty allocator, the move-in constructor will create the
1381 * accumulator variable with the same allocator as the input
1382 * argument @a x, while the default constructor will create the
1383 * accumulator variable with a default allocator. The mismatch of
1384 * allocators in the latter case means that the input argument
1385 * @a x may have to be copied in linear time instead of being
1386 * moved in constant time.
1388 * @note Best practice is to prefer the move-in constructor over the
1389 * move-in function unless the move-in function is required for
1390 * some specific reason.
1392 * @warning Calling this function other than to set the initial value
1393 * for a reduction will almost always result in undefined
1396 * @param obj The object containing the value that will be moved into the
1399 * @post The reducer contains the value that was initially in @a obj.
1400 * @post The value of @a obj is undefined.
1404 void move_in(value_type
& obj
) { set_get::move_in(view(), obj
);}
1406 /** Move the value out of the reducer.
1408 * This function is used to retrieve the final value of the reducer's
1409 * accumulator variable by either copying or _moving_ the value of @a obj
1410 * into it. Moving a value can often be performed in constant time, even
1411 * for large container objects, but has the side effect of leaving the
1412 * value of the reducer's accumulator variable undefined. (See the
1413 * description of the @ref move_in_wrapper class for a discussion of
1417 * A move_in() call to initialize a reducer is often paired with a
1418 * move_out() call to get its final value:
1422 * … do the reduction …
1426 * - You cannot assume either that this will function will copy its
1427 * value or that it will move it.
1428 * - You must assume that the value of the reducer's accumulator
1429 * variable will be undefined after the call to move_out().
1430 * - You can assume that move_out() will be at least as efficient as
1431 * get_value(), and you should therefore prefer move_out() unless
1432 * you need the accumulator variable to be preserved after the
1435 * @warning Calling this function other than to retrieve the final
1436 * value of a reduction will almost always result in undefined
1439 * @param obj The object that the value of the reducer will be moved into.
1441 * @post @a obj contains the value that was initially in the reducer.
1442 * @post The value of the reducer is undefined.
1446 void move_out(value_type
& obj
) { set_get::move_out(view(), obj
); }
1448 /** Set the value of the reducer.
1450 * This function sets the initial value of the reducer's accumulator
1451 * variable to the value of @a obj.
1453 * @note The behavior of a default constructor followed by
1459 * @note is not necessarily the same as a value constructor:
1461 * reducer<Type> xr(x);
1463 * @note In particular, when @a Type is a container type with a
1464 * non-empty allocator, the value constructor will create the
1465 * accumulator variable with the same allocator as the input
1466 * argument @a x, while the default constructor will create the
1467 * accumulator variable with a default allocator.
1469 * @warning Calling this function other than to set the initial value
1470 * for a reduction will almost always result in undefined
1473 * @param obj The object containing the value that will be copied into
1476 * @post The reducer contains a copy of the value in @a obj.
1480 void set_value(const value_type
& obj
) { set_get::set_value(view(), obj
); }
1482 /** Get the value of the reducer.
1484 * This function gets the final value of the reducer's accumulator
1487 * @warning Calling this function other than to retrieve the final
1488 * value of a reduction will almost always result in undefined
1491 * @return A reference to the value contained in the reducer.
1495 typename
set_get::return_type_for_get_value
get_value() const
1496 { return set_get::get_value(view()); }
1500 /** Implicit downcast to legacy reducer wrapper, if any.
1502 * @see legacy_reducer_downcast
1504 operator typename legacy_reducer_downcast
<reducer
>::type
& ()
1506 typedef typename legacy_reducer_downcast
<reducer
>::type downcast_type
;
1507 return *reinterpret_cast<downcast_type
*>(this);
1511 /** Implicit downcast to legacy reducer wrapper, if any.
1513 * @see legacy_reducer_downcast
1515 operator const typename legacy_reducer_downcast
<reducer
>::type
& () const
1517 typedef typename legacy_reducer_downcast
<reducer
>::type downcast_type
;
1518 return *reinterpret_cast<const downcast_type
*>(this);
1524 using stub::reducer
;
1527 } // end namespace cilk
1529 #endif /* __cplusplus */
1531 /** @page page_reducers_in_c Creating and Using Reducers in C
1535 * The Intel Cilk Plus runtime supports reducers written in C as well as in C++. The
1536 * basic logic is the same, but the implementation details are very
1537 * different. The C++ reducer implementation uses templates heavily to create
1538 * very generic components. The C reducer implementation uses macros, which
1539 * are a much blunter instrument. The most immediate consequence is that the
1540 * monoid/view/reducer architecture is mostly implicit rather than explicit
1543 * @section reducers_c_overview Overview of Using Reducers in C
1545 * The basic usage pattern for C reducers is:
1547 * 1. Create and initialize a reducer object.
1548 * 2. Tell the Intel Cilk Plus runtime about the reducer.
1549 * 3. Update the value contained in the reducer in a parallel computation.
1550 * 4. Tell the Intel Cilk Plus runtime that you are done with the reducer.
1551 * 5. Retrieve the value from the reducer.
1553 * @subsection reducers_c_creation Creating and Initializing a C Reducer
1555 * The basic pattern for creating and initializing a reducer object in C is
1557 * CILK_C_DECLARE_REDUCER(value-type) reducer-name =
1558 * CILK_C_INIT_REDUCER(value-type,
1560 * identity-function,
1564 * This is simply an initialized definition of a variable named
1565 * _reducer-name_. The @ref CILK_C_DECLARE_REDUCER macro expands to an
1566 * anonymous `struct` declaration for a reducer object containing a view of
1567 * type _value-type_, and the @ref CILK_C_INIT_REDUCER macro expands to a
1568 * struct initializer.
1570 * @subsection reducers_c_reduce_func Reduce Functions
1572 * The reduce function for a reducer is called when a parallel execution
1573 * strand terminates, to combine the values computed by the terminating
1574 * strand and the strand to its left. It takes three arguments:
1576 * - `void* reducer` - the address of the reducer.
1577 * - `void* left` - the address of the value for the left strand.
1578 * - `void* right` - the address of the value for the right (terminating)
1581 * It must apply the reducer's reduction operation to the `left` and `right`
1582 * values, leaving the result in the `left` value. The `right` value is
1583 * undefined after the reduce function call.
1585 * @subsection reducers_c_identity_func Identity Functions
1587 * The identity function for a reducer is called when a parallel execution
1588 * strand begins, to initialize its value to the reducer's identity value. It
1589 * takes two arguments:
1591 * - `void* reducer` - the address of the reducer.
1592 * - `void* v` - the address of a freshly allocated block of memory of size
1593 * `sizeof(value-type)`.
1595 * It must initialize the memory pointed to by `v` so that it contains the
1596 * reducer's identity value.
1598 * @subsection reducers_c_destroy_func Destroy Functions
1600 * The destroy function for a reducer is called when a parallel execution
1601 * strand terminates, to do any necessary cleanup before its value is
1602 * deallocated. It takes two arguments:
1604 * - `void* reducer` - the address of the reducer.
1605 * - `void* p` - the address of the value for the terminating strand.
1607 * It must release any resources belonging to the value pointed to by `p`, to
1608 * avoid a resource leak when the memory containing the value is deallocated.
1610 * The runtime function `__cilkrts_hyperobject_noop_destroy` can be used for
1611 * the destructor function if the reducer's values do not need any cleanup.
1613 * @subsection reducers_c_register Tell the Intel Cilk Plus Runtime About the
1616 * Call the @ref CILK_C_REGISTER_REDUCER macro to register the reducer with
1617 * the Intel Cilk Plus runtime:
1619 * CILK_C_REGISTER_REDUCER(reducer-name);
1621 * The runtime will manage reducer values for all registered reducers when
1622 * parallel execution strands begin and end.
1624 * @subsection reducers_c_update Update the Value Contained in the Reducer
1626 * The @ref REDUCER_VIEW macro returns a reference to the reducer's value for
1627 * the current parallel strand:
1629 * REDUCER_VIEW(reducer-name) = REDUCER_VIEW(reducer-name) OP x;
1631 * C++ reducer views restrict access to the wrapped value so that it can only
1632 * be modified in ways consistent with the reducer's operation. No such
1633 * protection is provided for C reducers. It is entirely the responsibility
1634 * of the user to avoid modifying the value in any inappropriate way.
1636 * @subsection c_reducers_unregister Tell the Intel Cilk Plus Runtime That You Are
1637 * Done with the Reducer
1639 * When the parallel computation is complete, call the @ref
1640 * CILK_C_UNREGISTER_REDUCER macro to unregister the reducer with the
1641 * Intel Cilk Plus runtime:
1643 * CILK_C_UNREGISTER_REDUCER(reducer-name);
1645 * The runtime will stop managing reducer values for the reducer.
1647 * @subsection c_reducers_retrieve Retrieve the Value from the Reducer
1649 * When the parallel computation is complete, use the @ref REDUCER_VIEW macro
1650 * to retrieve the final value computed by the reducer.
1652 * @subsection reducers_c_example_custom Example - Creating and Using a
1655 * The `IntList` type represents a simple list of integers.
1657 * struct _intListNode {
1659 * _intListNode* next;
1661 * typedef struct { IntListNode* head; IntListNode* tail; } IntList;
1663 * // Initialize a list to be empty
1664 * void IntList_init(IntList* list) { list->head = list->tail = 0; }
1666 * // Append an integer to the list
1667 * void IntList_append(IntList* list, int x)
1669 * IntListNode* node = (IntListNode*) malloc(sizeof(IntListNode));
1670 * if (list->tail) list->tail->next = node; else list->head = node;
1671 * list->tail = node;
1674 * // Append the right list to the left list, and leave the right list
1676 * void IntList_concat(IntList* left, IntList* right)
1679 * left->tail->next = right->head;
1680 * if (right->tail) left->tail = right->tail;
1685 * IntList_init(*right);
1688 * This code creates a reducer that supports creating an `IntList` by
1689 * appending values to it.
1691 * void identity_IntList(void* reducer, void* list)
1693 * IntList_init((IntList*)list);
1696 * void reduce_IntList(void* reducer, void* left, void* right)
1698 * IntList_concat((IntList*)left, (IntList*)right);
1701 * CILK_C_DECLARE_REDUCER(IntList) my_list_int_reducer =
1702 * CILK_C_INIT_REDUCER(IntList,
1704 * identity_int_list,
1705 * __cilkrts_hyperobject_noop_destroy);
1706 * // Initial value omitted //
1707 * ListInt_init(&REDUCER_VIEW(my_int_list_reducer));
1709 * CILK_C_REGISTER_REDUCER(my_int_list_reducer);
1710 * cilk_for (int i = 0; i != n; ++i) {
1711 * IntList_append(&REDUCER_VIEW(my_int_list_reducer), a[i]);
1713 * CILK_C_UNREGISTER_REDUCER(my_int_list_reducer);
1715 * IntList result = REDUCER_VIEW(my_int_list_reducer);
1717 * @section reducers_c_predefined Predefined C Reducers
1719 * Some of the predefined reducer classes in the Intel Cilk Plus library come with
1720 * a set of predefined macros to provide the same capabilities in C.
1721 * In general, two macros are provided for each predefined reducer family:
1723 * - `CILK_C_REDUCER_operation(reducer-name, type-name, initial-value)` -
1724 * Declares a reducer object named _reducer-name_ with initial value
1725 * _initial-value_ to perform a reduction using the _operation_ on values
1726 * of the type specified by _type-name_. This is the equivalent of the
1727 * general code described in @ref reducers_c_creation :
1729 * CILK_C_DECLARE_REDUCER(type) reducer-name =
1730 * CILK_C_INIT_REDUCER(type, ..., initial-value);
1732 * where _type_ is the C type corresponding to _type_name_. See @ref
1733 * reducers_c_type_names below for the _type-names_ that you can use.
1735 * - `CILK_C_REDUCER_operation_TYPE(type-name)` - Expands to the `typedef`
1736 * name for the type of the reducer object declared by
1737 * `CILK_C_REDUCER_operation(reducer-name, type-name, initial-value)`.
1739 * See @ref reducers_c_example_predefined.
1741 * The predefined C reducers are:
1743 * | Operation | Name | Documentation |
1744 * |-------------------|---------------|-------------------------------|
1745 * | addition | `OPADD` | @ref ReducersAdd |
1746 * | bitwise AND | `OPAND` | @ref ReducersAnd |
1747 * | bitwise OR | `OPOR` | @ref ReducersOr |
1748 * | bitwise XOR | `OPXOR` | @ref ReducersXor |
1749 * | multiplication | `OPMUL` | @ref ReducersMul |
1750 * | minimum | `MIN` | @ref ReducersMinMax |
1751 * | minimum & index | `MIN_INDEX` | @ref ReducersMinMax |
1752 * | maximum | `MAX` | @ref ReducersMinMax |
1753 * | maximum & index | `MAX_INDEX` | @ref ReducersMinMax |
1755 * @subsection reducers_c_type_names Numeric Type Names
1757 * The type and function names created by the C reducer definition macros
1758 * incorporate both the reducer kind (`opadd`, `opxor`, etc.) and the value
1759 * type of the reducer (`int`, `double`, etc.). The value type is represented
1760 * by a _numeric type name_ string. The types supported in C reducers, and
1761 * their corresponding numeric type names, are given in the following table:
1763 * | Type | Numeric Type Name |
1764 * |-----------------------|-------------------------------|
1765 * | `char` | `char` |
1766 * | `unsigned char` | `uchar` |
1767 * | `signed char` | `schar` |
1768 * | `wchar_t` | `wchar_t` |
1769 * | `short` | `short` |
1770 * | `unsigned short` | `ushort` |
1772 * | `unsigned int` | `uint` |
1773 * | `unsigned int` | `unsigned` (alternate name) |
1774 * | `long` | `long` |
1775 * | `unsigned long` | `ulong` |
1776 * | `long long` | `longlong` |
1777 * | `unsigned long long` | `ulonglong` |
1778 * | `float` | `float` |
1779 * | `double` | `double` |
1780 * | `long double` | `longdouble` |
1782 * @subsection reducers_c_example_predefined Example - Using a Predefined C
1785 * To compute the sum of all the values in an array of `unsigned int`:
1787 * CILK_C_REDUCER_OPADD(sum, uint, 0);
1788 * CILK_C_REGISTER_REDUCER(sum);
1789 * cilk_for(int i = 0; i != n; ++i) {
1790 * REDUCER_VIEW(sum) += a[i];
1792 * CILK_C_UNREGISTER_REDUCER(sum);
1793 * printf("The sum is %u\n", REDUCER_VIEW(sum));
1797 /** @name C language reducer macros
1799 * These macros are used to declare and work with reducers in C code.
1801 * @see @ref page_reducers_in_c
1807 /** @name Compound identifier macros.
1809 * These macros are used to construct an identifier by concatenating two or
1810 * three identifiers.
1814 /** Expand to an identifier formed by concatenating two identifiers.
1816 #define __CILKRTS_MKIDENT(a,b) __CILKRTS_MKIDENT_IMP(a,b,)
1818 /** Expand to an identifier formed by concatenating three identifiers.
1820 #define __CILKRTS_MKIDENT3(a,b,c) __CILKRTS_MKIDENT_IMP(a,b,c)
1822 /** Helper macro to do the concatenation.
1824 #define __CILKRTS_MKIDENT_IMP(a,b,c) a ## b ## c
1828 /** Compiler-specific keyword for the "type of" operator.
1830 #if defined(__GNUC__) && !defined(__INTEL_COMPILER)
1831 # define _Typeof __typeof__
1834 /** @name Predefined reducer function declaration macros.
1836 * These macros are used to create the function headers for the identity,
1837 * reduction, and destructor functions for a builtin reducer family. The
1838 * macro can be followed by a semicolon to create a declaration, or by a
1839 * brace-enclosed body to create a definition.
1843 /** Create an identity function header.
1845 * @note The name of the function's value pointer parameter will always be `v`.
1847 * @param name The reducer family name.
1848 * @param tn The type name.
1850 #define __CILKRTS_DECLARE_REDUCER_IDENTITY(name,tn) CILK_EXPORT \
1851 void __CILKRTS_MKIDENT3(name,_identity_,tn)(void* key, void* v)
1853 /** Create a reduction function header.
1855 * @param name The reducer family name.
1856 * @param tn The type name.
1857 * @param l The name to use for the function's left value pointer parameter.
1858 * @param r The name to use for the function's right value pointer
1861 #define __CILKRTS_DECLARE_REDUCER_REDUCE(name,tn,l,r) CILK_EXPORT \
1862 void __CILKRTS_MKIDENT3(name,_reduce_,tn)(void* key, void* l, void* r)
1864 /** Create a destructor function header.
1866 * @param name The reducer family name.
1867 * @param tn The type name.
1868 * @param p The name to use for the function's value pointer parameter.
1870 #define __CILKRTS_DECLARE_REDUCER_DESTROY(name,tn,p) CILK_EXPORT \
1871 void __CILKRTS_MKIDENT3(name,_destroy_,tn)(void* key, void* p)
1878 /***************************************************************************
1879 * Real implementation
1880 ***************************************************************************/
1882 /** Declaration of a C reducer structure type.
1884 * This macro expands into an anonymous structure declaration for a C reducer
1885 * structure which contains a @a Type value. For example:
1887 * CILK_C_DECLARE_REDUCER(int) my_add_int_reducer =
1888 * CILK_C_INIT_REDUCER(int, …);
1890 * @param Type The type of the value contained in the reducer object.
1892 * @see @ref reducers_c_creation
1894 #define CILK_C_DECLARE_REDUCER(Type) struct { \
1895 __cilkrts_hyperobject_base __cilkrts_hyperbase; \
1896 __CILKRTS_CACHE_ALIGN Type value; \
1899 /** Initializer for a C reducer structure.
1901 * This macro expands into a brace-enclosed structure initializer for a C
1902 * reducer structure that was declared with
1903 * `CILK_C_DECLARE_REDUCER(Type)`. For example:
1905 * CILK_C_DECLARE_REDUCER(int) my_add_int_reducer =
1906 * CILK_C_INIT_REDUCER(int,
1909 * __cilkrts_hyperobject_noop_destroy,
1912 * @param Type The type of the value contained in the reducer object. Must
1913 * be the same as the @a Type argument of the
1914 * CILK_C_DECLARE_REDUCER macro call that created the
1916 * @param Reduce The address of the @ref reducers_c_reduce_func
1917 * "reduce function" for the reducer.
1918 * @param Identity The address of the @ref reducers_c_identity_func
1919 * "identity function" for the reducer.
1920 * @param Destroy The address of the @ref reducers_c_destroy_func
1921 * "destroy function" for the reducer.
1922 * @param ... The initial value for the reducer. (A single expression if
1923 * @a Type is a scalar type; a list of values if @a Type is a
1924 * struct or array type.)
1926 * @see @ref reducers_c_creation
1929 #define CILK_C_INIT_REDUCER(Type, Reduce, Identity, Destroy, ...) \
1933 , __cilkrts_hyperobject_alloc \
1934 , __cilkrts_hyperobject_dealloc \
1937 , __CILKRTS_CACHE_LINE__ \
1943 /** Register a reducer with the Intel Cilk Plus runtime.
1945 * The runtime will manage reducer values for all registered reducers when
1946 * parallel execution strands begin and end. For example:
1948 * CILK_C_REGISTER_REDUCER(my_add_int_reducer);
1949 * cilk_for (int i = 0; i != n; ++i) {
1953 * @param Expr The reducer to be registered.
1955 * @see @ref page_reducers_in_c
1957 #define CILK_C_REGISTER_REDUCER(Expr) \
1958 __cilkrts_hyper_create(&(Expr).__cilkrts_hyperbase)
1960 /** Unregister a reducer with the Intel Cilk Plus runtime.
1962 * The runtime will stop managing reducer values for a reducer after it is
1963 * unregistered. For example:
1965 * cilk_for (int i = 0; i != n; ++i) {
1968 * CILK_C_UNREGISTER_REDUCER(my_add_int_reducer);
1970 * @param Expr The reducer to be unregistered.
1972 * @see @ref page_reducers_in_c
1974 #define CILK_C_UNREGISTER_REDUCER(Expr) \
1975 __cilkrts_hyper_destroy(&(Expr).__cilkrts_hyperbase)
1977 /** Get the current view for a reducer.
1979 * The `REDUCER_VIEW(reducer-name)` returns a reference to the reducer's
1980 * value for the current parallel strand. This can be used to initialize the
1981 * value of the reducer before it is used, to modify the value of the reducer
1982 * on the current parallel strand, or to retrieve the final value of the
1983 * reducer at the end of the parallel computation.
1985 * REDUCER_VIEW(my_add_int_reducer) = REDUCER_VIEW(my_add_int_reducer) + x;
1987 * @note C++ reducer views restrict access to the wrapped value so that it
1988 * can only be modified in ways consistent with the reducer's operation. No
1989 * such protection is provided for C reducers. It is entirely the
1990 * responsibility of the user to refrain from modifying the value in any
1991 * inappropriate way.
1993 * @param Expr The reducer whose value is to be returned.
1995 * @see @ref page_reducers_in_c
1997 #define REDUCER_VIEW(Expr) (*(_Typeof((Expr).value)*) \
1998 __cilkrts_hyper_lookup(&(Expr).__cilkrts_hyperbase))
2000 //@} C language reducer macros
2002 #endif // CILK_REDUCER_H_INCLUDED