1/* 2 * @copyright 3 * Copyright (C) 2009-2013, Intel Corporation 4 * All rights reserved. 5 * 6 * @copyright 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 11 * * Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * * Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * * Neither the name of Intel Corporation nor the names of its 18 * contributors may be used to endorse or promote products derived 19 * from this software without specific prior written permission. 20 * 21 * @copyright 22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 23 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 24 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 25 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 26 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 27 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 28 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS 29 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 30 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY 32 * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 33 * POSSIBILITY OF SUCH DAMAGE. 34 * 35 */ 36 37/* 38 * reducer_ostream.h 39 * 40 * Purpose: Hyper-object to write to 'std::ostream's 41 * 42 * Classes: reducer_ostream 43 * 44 * Description: 45 * ============ 46 * Output streams ('std::ostream's) are a convenient means of writing text to 47 * files, the user console, or sockets. In a serial program, text is written 48 * to an ostream in a specific, logical order. For example, computing while 49 * traversing a data structure and printing them to an 'ostream' will result 50 * in the values being printed in the order of traversal. In a parallel 51 * version of the same program, however, different parts of the data structure 52 * may be traversed in a different order, resulting in a non-deterministic 53 * ordering of the stream. Worse, multiple strands may write to the same 54 * stream simultaneously, resulting in a data race. Replacing the 55 * 'std::ostream' with a 'cilk::reducer_ostream' will solve both problems: Data 56 * will appeaer in the stream in the same order as it would for the serial 57 * program, and there will be no races (no locks) on the common stream. 58 * 59 * Usage Example: 60 * ============== 61 * Assume we wish to traverse an array of objects, performing an operation on 62 * each object and writing the result to a file. Without a reducer_ostream, 63 * we have a race on the 'output' file stream: 64 *.. 65 * void compute(std::ostream& os, double x) 66 * { 67 * // Perform some significant computation and print the result: 68 * os << std::asin(x); 69 * } 70 * 71 * int test() 72 * { 73 * const std::size_t ARRAY_SIZE = 1000000; 74 * extern double myArray[ARRAY_SIZE]; 75 * 76 * std::ofstream output("output.txt"); 77 * cilk_for (std::size_t i = 0; i < ARRAY_SIZE; ++i) 78 * { 79 * compute(output, myArray[i]); 80 * } 81 * 82 * return 0; 83 * } 84 *.. 85 * The race is solved by using a reducer_ostream to proxy the 'output' file: 86 *.. 87 * void compute(cilk::reducer_ostream& os, double x) 88 * { 89 * // Perform some significant computation and print the result: 90 * *os << std::asin(x); 91 * } 92 * 93 * int test() 94 * { 95 * const std::size_t ARRAY_SIZE = 1000000; 96 * extern double myArray[ARRAY_SIZE]; 97 * 98 * std::ofstream output("output.txt"); 99 * cilk::reducer_ostream hyper_output(output); 100 * cilk_for (std::size_t i = 0; i < ARRAY_SIZE; ++i) 101 * { 102 * compute(hyper_output, myArray[i]); 103 * } 104 * 105 * return 0; 106 * } 107 *.. 108 * 109 * Limitations: 110 * ============ 111 * There are two possible values for the formatting flags immediately after a 112 * 'cilk_spawn' statement: they may either have the value that was set by the 113 * spawn function, or they may have default values. Because of 114 * non-determinism in the processor scheduling, there is no way to determine 115 * which it will be. Similarly, the formatting flags after a 'cilk_sync' may 116 * or may not have the same value as before the sync. Therefore, one must use 117 * a disciplined coding style to avoid formatting errors. There are two 118 * approaches to mitigating the problem: The first is to eliminate the 119 * difference between the two possible outcomes by ensuring that the spawned 120 * function always returns the flags to their initial state: 121 *.. 122 * void compute(cilk::reducer_ostream& os, double x) 123 * { 124 * // Perform some significant computation and print the result: 125 * int saveprec = os.precision(5); 126 * os << std::asin(x); 127 * os.precision(saveprec); 128 * } 129 *.. 130 * The second approach is to write your streaming operations such that they 131 * don't depend on the previous state of the formatting flags by setting any 132 * important flags before every block of output: 133 *.. 134 * cilk_spawn compute(hyper_output, value); 135 * 136 * hyper_output->precision(2); // Don't depend on previous precision 137 * *hyper_output << f(); 138 * *hyper_output << g(); 139 *.. 140 * Another concern is memory usage. A reducer_ostream will buffer as much text 141 * as necessary to ensure that the order of output matches that of the serial 142 * version of the program. If all spawn branches perform an equal amount of 143 * output, then one can expect that half of the output before a sync will be 144 * buffered in memory. This hyperobject is therefore not well suited for 145 * serializing very large quantities of text output. 146 */ 147 148#ifndef REDUCER_OSTREAM_H_INCLUDED 149#define REDUCER_OSTREAM_H_INCLUDED 150 151#include <cilk/reducer.h> 152#include <iostream> 153#include <sstream> 154 155namespace cilk { 156 157/** 158 * @brief Class 'reducer_ostream' is the representation of a hyperobject for 159 * output text streaming. 160 */ 161class reducer_ostream 162{ 163public: 164 /// Internal representation of the per-strand view of the data for reducer_ostream 165 class View: public std::ostream 166 { 167 public: 168 /// Type of the std::stream reducer_ostream is based on 169 typedef std::ostream Base; 170 171 friend class reducer_ostream; 172 173 View(): 174 std::ostream(0) 175 { 176 Base::rdbuf(&strbuf_); 177 }; 178 179 private: 180 void use_ostream (const std::ostream &os) 181 { 182 Base::rdbuf(os.rdbuf()); 183 Base::flags(os.flags()); // Copy formatting flags 184 Base::setstate(os.rdstate()); // Copy error state 185 } 186 187 private: 188 std::stringbuf strbuf_; 189 }; 190 191public: 192 /// Definition of data view, operation, and identity for reducer_ostream 193 struct Monoid: monoid_base< View > 194 { 195 static void reduce (View *left, View *right); 196 }; 197 198private: 199 // Hyperobject to serve up views 200 reducer<Monoid> imp_; 201 202 // Methods that provide the API for the reducer 203public: 204 205 // Construct an initial 'reducer_ostream' from an 'std::ostream'. The 206 // specified 'os' stream is used as the eventual destination for all 207 // text streamed to this hyperobject. 208 explicit reducer_ostream(const std::ostream &os); 209 210 // Return a modifiable reference to the underlying 'ostream' object. 211 std::ostream& get_reference(); 212 213 /** 214 * Append data from some type to the reducer_ostream 215 * 216 * @param v Value to be appended to the reducer_ostream 217 */ 218 template<typename T> 219 std::ostream & 220 operator<< (const T &v) 221 { 222 return imp_.view() << v; 223 } 224 225 /** 226 * Append data from a std::ostream to the reducer_ostream 227 * 228 * @param _Pfn std::ostream to copy from 229 */ 230 std::ostream & 231 operator<< (std::ostream &(*_Pfn)(std::ostream &)) 232 { 233 View &v = imp_.view(); 234 235 return ((*_Pfn)(v)); 236 } 237 238 reducer_ostream& operator*() { return *this; } 239 reducer_ostream const& operator*() const { return *this; } 240 241 reducer_ostream* operator->() { return this; } 242 reducer_ostream const* operator->() const { return this; } 243}; 244 245 246// ------------------------------------------- 247// class reducer_ostream::Monoid 248// ------------------------------------------- 249 250/** 251 * Appends string from "right" reducer_basic_string onto the end of 252 * the "left". When done, the "right" reducer_basic_string is empty. 253 */ 254void 255reducer_ostream::Monoid::reduce(View *left, View *right) 256{ 257 left->operator<< (&right->strbuf_); 258} 259 260// -------------------------- 261// class reducer_ostream 262// -------------------------- 263 264/** 265 * Construct a reducer_ostream which will write to the specified std::ostream 266 * 267 * @param os std::ostream to write to 268 */ 269inline 270reducer_ostream::reducer_ostream(const std::ostream &os) : 271 imp_() 272{ 273 View &v = imp_.view(); 274 275 v.use_ostream(os); 276} 277 278/** 279 * Get a reference to the std::ostream 280 */ 281inline 282std::ostream & 283reducer_ostream::get_reference() 284{ 285 View &v = imp_.view(); 286 287 return v; 288} 289 290} // namespace cilk 291 292#endif // REDUCER_OSTREAM_H_INCLUDED 293 294