/* reducer_ostream.h -*- C++ -*-
|
*
|
* Copyright (C) 2009-2016, Intel Corporation
|
* All rights reserved.
|
*
|
* 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.
|
*
|
* 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.
|
*
|
* *********************************************************************
|
*
|
* PLEASE NOTE: This file is a downstream copy of a file mainitained in
|
* a repository at cilkplus.org. Changes made to this file that are not
|
* submitted through the contribution process detailed at
|
* http://www.cilkplus.org/submit-cilk-contribution will be lost the next
|
* time that a new version is released. Changes only submitted to the
|
* GNU compiler collection or posted to the git repository at
|
* https://bitbucket.org/intelcilkruntime/intel-cilk-runtime.git are
|
* not tracked.
|
*
|
* We welcome your contributions to this open source project. Thank you
|
* for your assistance in helping us improve Cilk Plus.
|
*/
|
|
/** @file reducer_ostream.h
|
*
|
* @brief Defines a class for writing to an ostream in parallel.
|
*
|
* @ingroup ReducersOstream
|
*
|
* @see @ref ReducersOstream
|
*/
|
|
#ifndef REDUCER_OSTREAM_H_INCLUDED
|
#define REDUCER_OSTREAM_H_INCLUDED
|
|
#include <cilk/reducer.h>
|
#include <ostream>
|
#include <sstream>
|
|
/** @defgroup ReducersOstream Ostream Reducers
|
*
|
* Ostream reducers allow multiple strands to write to an ostream in parallel.
|
*
|
* @ingroup Reducers
|
*
|
* You should be familiar with @ref pagereducers "Intel(R) Cilk(TM) Plus reducers",
|
* described in file reducers.md, and particularly with @ref reducers_using,
|
* before trying to use the information in this file.
|
*
|
* @section redostream_usage Usage Example
|
*
|
* One of the most common debugging techniques is adding `print` statements
|
* to the code being debugged. When the code is parallelized, the results can
|
* be less than satisfactory, as output from multiple strands is mingled in an
|
* unpredictable way. Like other reducers, an ostream reducer requires minimal
|
* recoding to guarantee that the output from parallelized computation will be
|
* ordered the same as though the computation were executed serially.
|
*
|
* cilk::reducer<cilk::op_ostream> r(std::cerr);
|
* cilk_for (int i = 0; i != data.size(); ++i) {
|
* *r << "Iteration " << i << ":\n";
|
* ... some computation ...
|
* *r << " Step 1:" << some information;
|
* ... some more computation ...
|
* *r << " Step 2:" << some more information;
|
* ... still more computation ...
|
* *r << " Step 3:" << still more information;
|
* }
|
*
|
* Output on standard error:
|
*
|
* Iteration 1:
|
* Step 1: ...
|
* Step 2: ...
|
* Step 3: ...
|
* Iteration 2:
|
* Step 1: ...
|
* Step 2: ...
|
* Step 3: ...
|
* Iteration 3:
|
* Step 1: ...
|
* Step 2: ...
|
* Step 3: ...
|
* ...
|
*
|
* @section redostream_overview Overview
|
*
|
* An "ostream reducer" is not really a reducer. It uses the reducer
|
* technology to coordinate operations on parallel strands to achieve
|
* the same behavior in a parallel computation that would be seen in a
|
* serial computation, but it does not have a monoid. It has a "monoid
|
* class," because that is part of the implementation framework, but it
|
* does not represent a mathematical monoid: there is no value type, no
|
* associative operation, and no identity value. The reducer is used for
|
* its side effect rather than to construct a value.
|
*
|
* You might think of an ostream reducer as a relative of a
|
* @ref ReducersString "string reducer" which uses stream output
|
* syntax (`stream << value`) instead of string append syntax
|
* (`string += value`), and which writes its result string to an
|
* ostream instead of making it available as the reducer value.
|
*
|
* Another difference is that "real" reducers protect their contained
|
* value quite strongly from improper access by the user. Ostream reducers,
|
* on the other hand, pretty much have to expose the ostream, since normal
|
* use of an ostream involves accessing its internal state. Furthermore,
|
* the ostream reducer just coordinates output to an existing ostream -
|
* there is nothing to keep the user from writing directly to the attached
|
* stream, with unpredictable results.
|
*
|
* @section redostream_operations Operations
|
*
|
* In the operation descriptions below, the type name `Ostream` refers to the
|
* reducer's ostream type, `std::basic_ostream<Char, Traits>`.
|
*
|
* @subsection redostream_constructors Constructors
|
*
|
* The only constructor is
|
*
|
* reducer(const Ostream& os)
|
*
|
* This creates a reducer that is associated with the existing ostream `os`.
|
* Anything "written to" the reducer will (eventually) be written to `os`.
|
*
|
* @subsection redostream_get_set Set and Get
|
*
|
* Just as a stream does not have a "value," neither does an ostream
|
* reducer. Therefore, none of the usual `set_value`, `get_value`,
|
* `move_in`, or `move_out` functions are available for ostream reducers.
|
*
|
* @subsection redostream_initial Initial Values
|
*
|
* Ostream reducers do not have default constructors.
|
*
|
* @subsection redostream_view_ops View Operations
|
*
|
* An ostream reducer view is actually a kind of `std::ostream`. Therefore,
|
* any operation that can be used on an ostream can be used on an ostream
|
* reducer view. For example:
|
*
|
* reducer<op_ostream> r(cout);
|
* *r << setw(5) << (x=1) << endl;
|
*
|
*
|
* @section redostream_performance Performance Considerations
|
*
|
* Ostream reducers work by creating a string stream for each non-leftmost
|
* view. When two strands are merged, the contents of the string buffer of the
|
* right view are written to the left view. Since all non-leftmost strands are
|
* eventually merged, all output is eventually written to the associated
|
* ostream.
|
*
|
* This implementation has two consequences.
|
*
|
* First, all output written to an ostream reducer on a stolen strand is kept
|
* in memory (in a string buffer) until the strand is merged with the leftmost
|
* strand. This means that some portion of the output written to an ostream
|
* reducer during a parallel computation - half of the total output, on
|
* average - will temporarily be held in memory during the computation.
|
* Obviously, ostream reducers will work better for small and moderate amounts
|
* of output.
|
*
|
* Second, buffered ostream reducer content must be copied at every merge.
|
* The total amount of copying is potentially proportional to the total amount
|
* of output multiplied by the number of strands stolen during the computation.
|
*
|
* In short, writing to an ostream in a parallel computation with an ostream
|
* reducer will always be less efficient than writing the same output directly
|
* to the ostream in a serial computation. The value of the ostream
|
* reducer is not in the writing of the ostream itself, but in removing the
|
* race and serialization obstacles that the ostream output would cause in an
|
* otherwise parallelizable computation.
|
*
|
*
|
* @section redostream_state Stream State
|
*
|
* The reducer implementation can correctly order the output that is written
|
* to an ostream. However, an ostream has additional state that controls its
|
* behavior, such as its formatting attributes, error state, extensible arrays, * and registered callbacks. If these are modified during the computation, the * reducer implementation cannot guarantee that they will be the same in a
|
* parallel computation as in a serial computation. In particular:
|
*
|
* - In the serial execution, the ostream state in the continuation of a
|
* spawn will be the same as the state at the end of the spawned function.
|
* In the parallel execution, if the continuation is stolen, its view will
|
* contain a newly created ostream with the default initial state.
|
* - In the serial execution, the ostream state following a sync is the same
|
* as the state before the sync. In the parallel execution, if the
|
* continuation is stolen, then the state following the sync will be the
|
* same as the state at the end of some spawned function.
|
*
|
* In short, you must not make any assumptions about the stream state of an
|
* ostream reducer:
|
*
|
* - Following a `cilk_spawn`.
|
* - Following a `cilk_sync`.
|
* - At the start of an iteration of a `cilk_for` loop.
|
* - Following the completion of a `cilk_for` loop.
|
*
|
* @section redostream_types Type and Operator Requirements
|
*
|
* `std::basic_ostream<Char, Traits>` must be a valid type.
|
*/
|
|
namespace cilk {
|
|
/** @ingroup ReducersOstream */
|
//@{
|
|
/** The ostream reducer view class.
|
*
|
* This is the view class for reducers created with
|
* `cilk::reducer< cilk::op_basic_ostream<Char, Traits> >`. It holds the
|
* actual ostream for a parallel strand, and allows only stream output
|
* operations to be performed on it.
|
*
|
* @note The reducer "dereference" operation (`reducer::operator *()`)
|
* yields a reference to the view. Thus, for example, the view
|
* class's `<<` operation would be used in an expression like
|
* `*r << "x = " << x`, where `r` is an ostream reducer.
|
*
|
* @tparam Char The ostream element type (not the ostream type).
|
* @tparam Traits The character traits type.
|
*
|
* @see ReducersOstream
|
* @see op_basic_ostream
|
*/
|
template<typename Char, typename Traits>
|
class op_basic_ostream_view : public std::basic_ostream<Char, Traits>
|
{
|
typedef std::basic_ostream<Char, Traits> base;
|
typedef std::basic_ostream<Char, Traits> ostream_type;
|
|
// A non-leftmost view is associated with a private string buffer. (The
|
// leftmost view is associated with the buffer of the reducer's associated
|
// ostream, so its private buffer is unused.)
|
//
|
std::basic_stringbuf<Char, Traits> m_buffer;
|
|
public:
|
|
/** Value type. Required by @ref monoid_with_view.
|
*/
|
typedef ostream_type value_type;
|
|
/** Reduce operation. Required by @ref monoid_with_view.
|
*/
|
void reduce(op_basic_ostream_view* other)
|
{
|
// Writing an empty buffer results in failure. Testing `sgetc()` is the
|
// easiest way of checking for an empty buffer.
|
if (other->m_buffer.sgetc() != Traits::eof()) {
|
*this << (&other->m_buffer);
|
}
|
}
|
|
/** Non-leftmost (identity) view constructor. The view is associated with
|
* its internal buffer. Required by @ref monoid_base.
|
*/
|
op_basic_ostream_view() : base(&m_buffer) {}
|
|
/** Leftmost view constructor. The view is associated with an existing
|
* ostream.
|
*/
|
op_basic_ostream_view(const ostream_type& os) : base(0)
|
{
|
base::rdbuf(os.rdbuf()); // Copy stream buffer
|
base::flags(os.flags()); // Copy formatting flags
|
base::setstate(os.rdstate()); // Copy error state
|
}
|
|
/** Sets/gets.
|
*
|
* These are all no-ops.
|
*/
|
//@{
|
|
void view_set_value(const value_type&)
|
{ assert("set_value() is not allowed on ostream reducers" && 0); }
|
const value_type& view_get_value() const
|
{ assert("get_value() is not allowed on ostream reducers" && 0);
|
return *this; }
|
typedef value_type const& return_type_for_get_value;
|
void view_move_in(const value_type&)
|
{ assert("move_in() is not allowed on ostream reducers" && 0); }
|
void view_move_out(const value_type&)
|
{ assert("move_out() is not allowed on ostream reducers" && 0); }
|
|
//@}
|
};
|
|
/** Ostream monoid class. Instantiate the cilk::reducer template class with an
|
* op_basic_ostream monoid to create an ostream reducer class:
|
*
|
* cilk::reducer< cilk::op_basic_string<char> > r;
|
*
|
* @tparam Char The stream element type (not the stream type).
|
* @tparam Traits The character traits type.
|
*
|
* @see ReducersOstream
|
* @see op_basic_ostream_view
|
* @see reducer_ostream
|
* @see op_ostream
|
* @see op_wostream
|
*/
|
template<typename Char,
|
typename Traits = std::char_traits<Char>,
|
bool Align = false>
|
class op_basic_ostream :
|
public monoid_with_view< op_basic_ostream_view<Char, Traits>, Align >
|
{
|
typedef monoid_with_view< op_basic_ostream_view<Char, Traits>, Align >
|
base;
|
typedef std::basic_ostream<Char, Traits> ostream_type;
|
typedef provisional_guard<typename base::view_type> view_guard;
|
|
public:
|
|
/** View type of the monoid.
|
*/
|
typedef typename base::view_type view_type;
|
|
/** @name Construct function.
|
*
|
* The only supported ostream reducer constructor takes a reference to
|
* an existing ostream.
|
*
|
* @param os The ostream destination for receive all data written to the
|
* reducer.
|
*/
|
static void construct(
|
op_basic_ostream* monoid,
|
view_type* view,
|
const ostream_type& os)
|
{
|
view_guard vg( new((void*) view) view_type(os) );
|
vg.confirm_if( new((void*) monoid) op_basic_ostream );
|
}
|
};
|
|
|
/**
|
* Convenience typedef for narrow ostreams.
|
*/
|
typedef op_basic_ostream<char> op_ostream;
|
|
/**
|
* Convenience typedef for wide ostreams.
|
*/
|
typedef op_basic_ostream<wchar_t> op_wostream;
|
|
/// @cond internal
|
|
class reducer_ostream;
|
|
/** Metafunction specialization for reducer conversion.
|
*
|
* This specialization of the @ref legacy_reducer_downcast template class
|
* defined in reducer.h causes the `reducer<op_basic_ostream<char> >` class
|
* to have an `operator reducer_ostream& ()` conversion operator that
|
* statically downcasts the `reducer<op_basic_ostream<char> >` to
|
* `reducer_ostream`. (The reverse conversion, from `reducer_ostream` to
|
* `reducer<op_basic_ostream<char> >`, is just an upcast, which is provided
|
* for free by the language.)
|
*/
|
template<bool Align>
|
struct legacy_reducer_downcast<
|
reducer<op_basic_ostream<char, std::char_traits<char>, Align> > >
|
{
|
typedef reducer_ostream type;
|
};
|
|
/// @endcond
|
|
/** Deprecated ostream reducer class.
|
*
|
* reducer_ostream is the same as @ref cilk::reducer<@ref op_ostream>, except
|
* that reducer_ostream is a proxy for the contained view, so that ostream
|
* operations can be applied directly to the reducer. For example, a number is
|
* written to a `reducer<op_ostream>` with `*r << x`, but a number can be
|
* written to a `reducer_ostream` with `r << x`.
|
*
|
* @deprecated Users are strongly encouraged to use `reducer<monoid>`
|
* reducers rather than the old wrappers like reducer_ostream. The
|
* `reducer<monoid>` reducers show the reducer/monoid/view
|
* architecture more clearly, are more consistent in their
|
* implementation, and present a simpler model for new
|
* user-implemented reducers.
|
*
|
* @note Implicit conversions are provided between `%reducer_ostream`
|
* and `reducer<%op_ostream>`. This allows incremental code
|
* conversion: old code that used `%reducer_ostream` can pass a
|
* `%reducer_ostream` to a converted function that now expects a
|
* pointer or reference to a `reducer<%op_ostream>`, and vice versa.
|
*
|
* @tparam Char The stream element type (not the stream type).
|
* @tparam Traits The character traits type.
|
*
|
* @see op_ostream
|
* @see reducer
|
* @see ReducersOstream
|
*/
|
class reducer_ostream :
|
public reducer<op_basic_ostream<char, std::char_traits<char>, true> >
|
{
|
typedef reducer<op_basic_ostream<char, std::char_traits<char>, true> > base;
|
using base::view;
|
public:
|
|
/// The view type for the reducer.
|
typedef base::view_type View;
|
|
/// The monoid type for the reducer.
|
typedef base::monoid_type Monoid;
|
|
/** Constructs an initial `reducer_ostream` from a `std::ostream`. The
|
* specified stream is used as the eventual destination for all text
|
* streamed to this hyperobject.
|
*/
|
explicit reducer_ostream(const std::ostream &os) : base(os) {}
|
|
/** Returns a modifiable reference to the underlying 'ostream' object.
|
*/
|
std::ostream& get_reference() { return view(); }
|
|
/** Writes to the ostream.
|
*/
|
template<typename T>
|
std::ostream& operator<< (const T &v)
|
{
|
return view() << v;
|
}
|
|
/**
|
* Calls a manipulator.
|
*
|
* @param _Pfn Pointer to the manipulator function.
|
*/
|
reducer_ostream& operator<< (std::ostream &(*_Pfn)(std::ostream &))
|
{
|
(*_Pfn)(view());
|
return *this;
|
}
|
|
/** @name Dereference
|
* @details Dereferencing a wrapper is a no-op. It simply returns the
|
* wrapper. Combined with the rule that the wrapper forwards view
|
* operations to its contained view, this means that view operations can
|
* be written the same way on reducers and wrappers, which is convenient
|
* for incrementally converting old code using wrappers to use reducers
|
* instead. That is:
|
*
|
* reducer<op_ostream> r;
|
* *r << "a"; // *r returns the view
|
* // operator<<() is a view member function
|
*
|
* reducer_ostream w;
|
* *w << "a"; // *w returns the wrapper
|
* // operator<<() is a wrapper member function
|
* // that calls the corresponding view function
|
*/
|
//@{
|
reducer_ostream& operator*() { return *this; }
|
reducer_ostream const& operator*() const { return *this; }
|
|
reducer_ostream* operator->() { return this; }
|
reducer_ostream const* operator->() const { return this; }
|
//@}
|
|
/** @name Upcast
|
* @details In Intel Cilk Plus library 0.9, reducers were always cache-aligned.
|
* In library 1.0, reducer cache alignment is optional. By default,
|
* reducers are unaligned (i.e., just naturally aligned), but legacy
|
* wrappers inherit from cache-aligned reducers for binary compatibility.
|
*
|
* This means that a wrapper will automatically be upcast to its aligned
|
* reducer base class. The following conversion operators provide
|
* pseudo-upcasts to the corresponding unaligned reducer class.
|
*/
|
//@{
|
operator reducer<op_ostream>& ()
|
{
|
return *reinterpret_cast< reducer<op_ostream>* >(this);
|
}
|
operator const reducer<op_ostream>& () const
|
{
|
return *reinterpret_cast< const reducer<op_ostream>* >(this);
|
}
|
//@}
|
};
|
|
} // namespace cilk
|
|
#endif // REDUCER_OSTREAM_H_INCLUDED
|
