diff options
Diffstat (limited to 'libcilkrts/include/cilk/reducer_ostream.h')
| -rw-r--r-- | libcilkrts/include/cilk/reducer_ostream.h | 293 |
1 files changed, 293 insertions, 0 deletions
diff --git a/libcilkrts/include/cilk/reducer_ostream.h b/libcilkrts/include/cilk/reducer_ostream.h new file mode 100644 index 00000000000..d9addeee89f --- /dev/null +++ b/libcilkrts/include/cilk/reducer_ostream.h @@ -0,0 +1,293 @@ +/* + * @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 + |