libcilkrts/include/cilk/reducer_ostream.h

/*
 *  @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.
 *
 */

/*
 * reducer_ostream.h
 *
 * Purpose: Hyper-object to write to 'std::ostream's
 *
 * Classes: reducer_ostream
 *
 * Description:
 * ============
 * Output streams ('std::ostream's) are a convenient means of writing text to
 * files, the user console, or sockets.  In a serial program, text is written
 * to an ostream in a specific, logical order.  For example, computing while
 * traversing a data structure and printing them to an 'ostream' will result
 * in the values being printed in the order of traversal.  In a parallel
 * version of the same program, however, different parts of the data structure
 * may be traversed in a different order, resulting in a non-deterministic
 * ordering of the stream.  Worse, multiple strands may write to the same
 * stream simultaneously, resulting in a data race.  Replacing the
 * 'std::ostream' with a 'cilk::reducer_ostream' will solve both problems: Data
 * will appeaer in the stream in the same order as it would for the serial
 * program, and there will be no races (no locks) on the common stream.
 *
 * Usage Example:
 * ==============
 * Assume we wish to traverse an array of objects, performing an operation on
 * each object and writing the result to a file.  Without a reducer_ostream,
 * we have a race on the 'output' file stream:
 *..
 *  void compute(std::ostream& os, double x)
 *  {
 *      // Perform some significant computation and print the result:
 *      os << std::asin(x);
 *  }
 *
 *  int test()
 *  {
 *      const std::size_t ARRAY_SIZE = 1000000;
 *      extern double myArray[ARRAY_SIZE];
 *
 *      std::ofstream output("output.txt");
 *      cilk_for (std::size_t i = 0; i < ARRAY_SIZE; ++i)
 *      {
 *          compute(output, myArray[i]);
 *      }
 *
 *      return 0;
 *  }
 *..
 * The race is solved by using a reducer_ostream to proxy the 'output' file:
 *..
 *  void compute(cilk::reducer_ostream& os, double x)
 *  {
 *      // Perform some significant computation and print the result:
 *      *os << std::asin(x);
 *  }
 *
 *  int test()
 *  {
 *      const std::size_t ARRAY_SIZE = 1000000;
 *      extern double myArray[ARRAY_SIZE];
 *
 *      std::ofstream output("output.txt");
 *      cilk::reducer_ostream hyper_output(output);
 *      cilk_for (std::size_t i = 0; i < ARRAY_SIZE; ++i)
 *      {
 *          compute(hyper_output, myArray[i]);
 *      }
 *
 *      return 0;
 *  }
 *..
 *
 * Limitations:
 * ============
 * There are two possible values for the formatting flags immediately after a
 * 'cilk_spawn' statement: they may either have the value that was set by the
 * spawn function, or they may have default values.  Because of
 * non-determinism in the processor scheduling, there is no way to determine
 * which it will be.  Similarly, the formatting flags after a 'cilk_sync' may
 * or may not have the same value as before the sync.  Therefore, one must use
 * a disciplined coding style to avoid formatting errors.  There are two
 * approaches to mitigating the problem: The first is to eliminate the
 * difference between the two possible outcomes by ensuring that the spawned
 * function always returns the flags to their initial state:
 *..
 *  void compute(cilk::reducer_ostream& os, double x)
 *  {
 *      // Perform some significant computation and print the result:
 *      int saveprec = os.precision(5);
 *      os << std::asin(x);
 *      os.precision(saveprec);
 *  }
 *..
 * The second approach is to write your streaming operations such that they
 * don't depend on the previous state of the formatting flags by setting any
 * important flags before every block of output:
 *..
 *      cilk_spawn compute(hyper_output, value);
 *
 *      hyper_output->precision(2);  // Don't depend on previous precision
 *      *hyper_output << f();
 *      *hyper_output << g();
 *..
 * Another concern is memory usage.  A reducer_ostream will buffer as much text
 * as necessary to ensure that the order of output matches that of the serial
 * version of the program.  If all spawn branches perform an equal amount of
 * output, then one can expect that half of the output before a sync will be
 * buffered in memory.  This hyperobject is therefore not well suited for
 * serializing very large quantities of text output.
 */

#ifndef REDUCER_OSTREAM_H_INCLUDED
#define REDUCER_OSTREAM_H_INCLUDED

#include <cilk/reducer.h>
#include <iostream>
#include <sstream>

namespace cilk {

/**
 * @brief Class 'reducer_ostream' is the representation of a hyperobject for
 * output text streaming.
 */
class reducer_ostream
{
public:
    /// Internal representation of the per-strand view of the data for reducer_ostream
    class View: public std::ostream
    {
    public:
        /// Type of the std::stream reducer_ostream is based on
        typedef std::ostream Base;

        friend class reducer_ostream;

        View():
            std::ostream(0)
        {
            Base::rdbuf(&strbuf_);
        };

    private:
        void use_ostream (const std::ostream &os)
        {
            Base::rdbuf(os.rdbuf());
            Base::flags(os.flags());       // Copy formatting flags
            Base::setstate(os.rdstate());  // Copy error state
        }

    private:
        std::stringbuf  strbuf_;
    };

public:
    /// Definition of data view, operation, and identity for reducer_ostream
    struct Monoid: monoid_base< View >
    {
        static void reduce (View *left, View *right);
    };

private:
    // Hyperobject to serve up views
    reducer<Monoid> imp_;

    // Methods that provide the API for the reducer
public:

    // Construct an initial 'reducer_ostream' from an 'std::ostream'.  The
    // specified 'os' stream is used as the eventual destination for all
    // text streamed to this hyperobject.
    explicit reducer_ostream(const std::ostream &os);

    // Return a modifiable reference to the underlying 'ostream' object.
    std::ostream& get_reference();

    /**
     * Append data from some type to the reducer_ostream
     *
     * @param v Value to be appended to the reducer_ostream
     */
    template<typename T>
    std::ostream &
    operator<< (const T &v)
    {
        return imp_.view() << v;
    }

    /**
     * Append data from a std::ostream to the reducer_ostream
     *
     * @param _Pfn std::ostream to copy from
     */
    std::ostream &
    operator<< (std::ostream &(*_Pfn)(std::ostream &))
    {
        View &v = imp_.view();

        return ((*_Pfn)(v));
    }

    reducer_ostream&       operator*()       { return *this; }
    reducer_ostream const& operator*() const { return *this; }

    reducer_ostream*       operator->()       { return this; }
    reducer_ostream const* operator->() const { return this; }
};


// -------------------------------------------
// class reducer_ostream::Monoid
// -------------------------------------------

/**
 * Appends string from "right" reducer_basic_string onto the end of
 * the "left". When done, the "right" reducer_basic_string is empty.
 */
void
reducer_ostream::Monoid::reduce(View *left, View *right)
{
    left->operator<< (&right->strbuf_);
}

// --------------------------
// class reducer_ostream
// --------------------------

/**
 * Construct a reducer_ostream which will write to the specified std::ostream
 *
 * @param os std::ostream to write to
 */
inline
reducer_ostream::reducer_ostream(const std::ostream &os) :
    imp_()
{
    View &v = imp_.view();

    v.use_ostream(os);
}

/**
 * Get a reference to the std::ostream
 */
inline
std::ostream &
reducer_ostream::get_reference()
{
    View &v = imp_.view();

    return v;
}

} // namespace cilk

#endif //  REDUCER_OSTREAM_H_INCLUDED