src/test/bench/task-perf-word-count.rs

   1 /**
   2    A parallel word-frequency counting program.
   3
   4    This is meant primarily to demonstrate Rust's MapReduce framework.
   5
   6    It takes a list of files on the command line and outputs a list of
   7    words along with how many times each word is used.
   8
   9 */
  10
  11 use std;
  12
  13 import option = option::t;
  14 import option::some;
  15 import option::none;
  16 import str;
  17 import std::map;
  18 import vec;
  19 import std::io;
  20
  21 import std::time;
  22 import u64;
  23 import result;
  24
  25 import task;
  26 import task::joinable_task;
  27 import comm;
  28 import comm::chan;
  29 import comm::port;
  30 import comm::recv;
  31 import comm::send;
  32
  33 fn map(input: str, emit: map_reduce::putter) {
  34     let f = io::string_reader(input);
  35
  36
  37     while true {
  38         alt read_word(f) { some(w) { emit(w, 1); } none. { break; } }
  39     }
  40 }
  41
  42 fn reduce(_word: str, get: map_reduce::getter) {
  43     let count = 0;
  44
  45     while true { alt get() { some(_) { count += 1; } none. { break; } } }
  46 }
  47
  48 mod map_reduce {
  49     export putter;
  50     export getter;
  51     export mapper;
  52     export reducer;
  53     export map_reduce;
  54
  55     type putter = fn@(str, int);
  56
  57     type mapper = fn(str, putter);
  58
  59     type getter = fn@() -> option<int>;
  60
  61     type reducer = fn(str, getter);
  62
  63     tag ctrl_proto {
  64         find_reducer(str, chan<chan<reduce_proto>>);
  65         mapper_done;
  66     }
  67
  68     tag reduce_proto { emit_val(int); done; ref; release; }
  69
  70     fn start_mappers(ctrl: chan<ctrl_proto>, -inputs: [str]) ->
  71        [joinable_task] {
  72         let tasks = [];
  73         for i: str in inputs {
  74             tasks += [task::spawn_joinable {|| map_task(ctrl, i)}];
  75         }
  76         ret tasks;
  77     }
  78
  79     fn map_task(ctrl: chan<ctrl_proto>, input: str) {
  80         // log(error, "map_task " + input);
  81         let intermediates = map::new_str_hash();
  82
  83         fn emit(im: map::hashmap<str, chan<reduce_proto>>,
  84                 ctrl: chan<ctrl_proto>, key: str, val: int) {
  85             let c;
  86             alt im.find(key) {
  87               some(_c) {
  88                 c = _c;
  89               }
  90               none. {
  91                 let p = port();
  92                 send(ctrl, find_reducer(key, chan(p)));
  93                 c = recv(p);
  94                 im.insert(key, c);
  95                 send(c, ref);
  96               }
  97             }
  98             send(c, emit_val(val));
  99         }
 100
 101         map(input, bind emit(intermediates, ctrl, _, _));
 102
 103         intermediates.values {|v| send(v, release); }
 104
 105         send(ctrl, mapper_done);
 106     }
 107
 108     fn reduce_task(key: str, out: chan<chan<reduce_proto>>) {
 109         let p = port();
 110
 111         send(out, chan(p));
 112
 113         let state = @{mutable ref_count: 0, mutable is_done: false};
 114
 115         fn get(p: port<reduce_proto>, state: @{mutable ref_count: int,
 116                                                mutable is_done: bool})
 117             -> option<int> {
 118             while !state.is_done || state.ref_count > 0 {
 119                 alt recv(p) {
 120                   emit_val(v) {
 121                     // #error("received %d", v);
 122                     ret some(v);
 123                   }
 124                   done. {
 125                     // #error("all done");
 126                     state.is_done = true;
 127                   }
 128                   ref. { state.ref_count += 1; }
 129                   release. { state.ref_count -= 1; }
 130                 }
 131             }
 132             ret none;
 133         }
 134
 135         reduce(key, bind get(p, state));
 136     }
 137
 138     fn map_reduce(-inputs: [str]) {
 139         let ctrl = port::<ctrl_proto>();
 140
 141         // This task becomes the master control task. It task::_spawns
 142         // to do the rest.
 143
 144         let reducers: map::hashmap<str, chan<reduce_proto>>;
 145
 146         reducers = map::new_str_hash();
 147
 148         let num_mappers = vec::len(inputs) as int;
 149         let tasks = start_mappers(chan(ctrl), inputs);
 150
 151         while num_mappers > 0 {
 152             alt recv(ctrl) {
 153               mapper_done. {
 154                 // #error("received mapper terminated.");
 155                 num_mappers -= 1;
 156               }
 157               find_reducer(k, cc) {
 158                 let c;
 159                 // log(error, "finding reducer for " + k);
 160                 alt reducers.find(k) {
 161                   some(_c) {
 162                     // log(error,
 163                     // "reusing existing reducer for " + k);
 164                     c = _c;
 165                   }
 166                   none. {
 167                     // log(error, "creating new reducer for " + k);
 168                     let p = port();
 169                     let ch = chan(p);
 170                     tasks +=
 171                         [task::spawn_joinable{||reduce_task(k, ch)}];
 172                     c = recv(p);
 173                     reducers.insert(k, c);
 174                   }
 175                 }
 176                 send(cc, c);
 177               }
 178             }
 179         }
 180
 181         reducers.values {|v| send(v, done); }
 182
 183         for t in tasks { task::join(t); }
 184     }
 185 }
 186
 187 fn main(argv: [str]) {
 188     let inputs = if vec::len(argv) < 2u {
 189         [input1(), input2(), input3()]
 190     } else {
 191         vec::map(vec::slice(argv, 1u, vec::len(argv)),
 192                  {|f| result::get(io::read_whole_file_str(f)) })
 193     };
 194
 195     let start = time::precise_time_ns();
 196
 197     map_reduce::map_reduce(inputs);
 198     let stop = time::precise_time_ns();
 199
 200     let elapsed = stop - start;
 201     elapsed /= 1000000u64;
 202
 203     log(error, "MapReduce completed in "
 204              + u64::str(elapsed) + "ms");
 205 }
 206
 207 fn read_word(r: io::reader) -> option<str> {
 208     let w = "";
 209
 210     while !r.eof() {
 211         let c = r.read_char();
 212
 213
 214         if is_word_char(c) {
 215             w += str::from_char(c);
 216         } else { if w != "" { ret some(w); } }
 217     }
 218     ret none;
 219 }
 220
 221 fn is_digit(c: char) -> bool {
 222     alt c {
 223       '0' { true }
 224       '1' { true }
 225       '2' { true }
 226       '3' { true }
 227       '4' { true }
 228       '5' { true }
 229       '6' { true }
 230       '7' { true }
 231       '8' { true }
 232       '9' { true }
 233       _ { false }
 234     }
 235 }
 236
 237 fn is_alpha_lower(c: char) -> bool {
 238     alt c {
 239       'a' { true }
 240       'b' { true }
 241       'c' { true }
 242       'd' { true }
 243       'e' { true }
 244       'f' { true }
 245       'g' { true }
 246       'h' { true }
 247       'i' { true }
 248       'j' { true }
 249       'k' { true }
 250       'l' { true }
 251       'm' { true }
 252       'n' { true }
 253       'o' { true }
 254       'p' { true }
 255       'q' { true }
 256       'r' { true }
 257       's' { true }
 258       't' { true }
 259       'u' { true }
 260       'v' { true }
 261       'w' { true }
 262       'x' { true }
 263       'y' { true }
 264       'z' { true }
 265       _ { false }
 266     }
 267 }
 268
 269 fn is_alpha_upper(c: char) -> bool {
 270     alt c {
 271       'A' { true }
 272       'B' { true }
 273       'C' { true }
 274       'D' { true }
 275       'E' { true }
 276       'F' { true }
 277       'G' { true }
 278       'H' { true }
 279       'I' { true }
 280       'J' { true }
 281       'K' { true }
 282       'L' { true }
 283       'M' { true }
 284       'N' { true }
 285       'O' { true }
 286       'P' { true }
 287       'Q' { true }
 288       'R' { true }
 289       'S' { true }
 290       'T' { true }
 291       'U' { true }
 292       'V' { true }
 293       'W' { true }
 294       'X' { true }
 295       'Y' { true }
 296       'Z' { true }
 297       _ { false }
 298     }
 299 }
 300
 301 fn is_alpha(c: char) -> bool { is_alpha_upper(c) || is_alpha_lower(c) }
 302
 303 fn is_word_char(c: char) -> bool { is_alpha(c) || is_digit(c) || c == '_' }
 304
 305
 306
 307 fn input1() -> str { " Lorem ipsum dolor sit amet, consectetur
 308 adipiscing elit. Vestibulum tempor erat a dui commodo congue. Proin ac
 309 imperdiet est. Nunc volutpat placerat justo, ac euismod nisl elementum
 310 et. Nam a eros eleifend dolor porttitor auctor a a felis. Maecenas dui
 311 odio, malesuada eget bibendum at, ultrices suscipit enim. Sed libero
 312 dolor, sagittis eget mattis quis, imperdiet quis diam. Praesent eu
 313 tristique nunc. Integer blandit commodo elementum. In eros lacus,
 314 pretium vel fermentum vitae, euismod ut nulla.
 315
 316 Cras eget magna tempor mauris gravida laoreet. Suspendisse venenatis
 317 volutpat molestie. Pellentesque suscipit nisl feugiat sem blandit
 318 venenatis. Mauris id odio nec est elementum congue sed id
 319 diam. Maecenas viverra, mi id aliquam commodo, ipsum dolor iaculis
 320 odio, sed fringilla neque ipsum quis orci. Pellentesque dui dolor,
 321 faucibus a rutrum sed, faucibus a mi. In eget sodales
 322 ipsum. Pellentesque sollicitudin dapibus diam, ac interdum tellus
 323 porta ac.
 324
 325 Donec ligula mi, sodales vel cursus a, dapibus ut sapien. In convallis
 326 tempor libero, id dapibus mi sodales quis. Suspendisse
 327 potenti. Vestibulum feugiat bibendum bibendum. Maecenas metus magna,
 328 consequat in mollis at, malesuada id sem. Donec interdum viverra enim
 329 nec ornare. Donec pellentesque neque magna.
 330
 331 Donec euismod, ante quis tempor pretium, leo lectus ornare arcu, sed
 332 porttitor nisl ipsum elementum lectus. Nam rhoncus dictum sapien sed
 333 tincidunt. Integer sit amet dui orci. Quisque lectus elit, dignissim
 334 eget mattis nec, cursus nec erat. Fusce vitae metus nulla, et mattis
 335 quam. Nullam sit amet diam augue. Nunc non ante eu enim lacinia
 336 condimentum ac eget lectus.
 337
 338 Aliquam ut pulvinar tellus. Vestibulum ante ipsum primis in faucibus
 339 orci luctus et ultrices posuere cubilia Curae; Pellentesque non urna
 340 urna. Nulla facilisi. Aenean in felis quis massa aliquam eleifend non
 341 sed libero. Proin sit amet iaculis urna. In hac habitasse platea
 342 dictumst. Aenean scelerisque aliquet dolor, sit amet viverra est
 343 laoreet nec. Curabitur non urna a augue rhoncus pulvinar. Integer
 344 placerat vehicula nisl sed egestas. Morbi iaculis diam at erat
 345 sollicitudin nec interdum libero tristique.  " }
 346
 347 fn input2() -> str { " Lorem ipsum dolor sit amet, consectetur
 348 adipiscing elit. Proin enim nibh, scelerisque faucibus accumsan id,
 349 feugiat id ipsum. In luctus mauris a massa consequat dignissim. Donec
 350 sit amet sem urna. Nullam pellentesque accumsan mi, at convallis arcu
 351 pharetra in. Quisque euismod gravida nibh in rutrum. Phasellus laoreet
 352 elit porta augue molestie nec imperdiet quam venenatis. Maecenas et
 353 egestas arcu. Donec vulputate mauris enim. Aenean malesuada urna sed
 354 dui eleifend quis posuere massa malesuada. Proin varius fringilla
 355 feugiat. Donec mollis lorem sit amet ligula blandit quis fermentum dui
 356 eleifend. Fusce molestie sodales magna in mattis. Aenean imperdiet,
 357 elit sit amet accumsan vehicula, velit massa semper nibh, et varius
 358 justo sem ut orci. Sed et magna lectus. Vestibulum vehicula, tellus
 359 non dapibus mattis, libero ligula ullamcorper odio, in interdum odio
 360 sem at mi.
 361
 362 Donec ut rhoncus mi. Donec ullamcorper, sem nec laoreet ullamcorper,
 363 metus metus accumsan orci, ac luctus est velit a dolor. Donec eros
 364 lectus, facilisis ut volutpat sit amet, pellentesque eu
 365 velit. Praesent eget nibh et arcu vestibulum consequat. Pellentesque
 366 habitant morbi tristique senectus et netus et malesuada fames ac
 367 turpis egestas. Pellentesque lectus est, rhoncus ut cursus sit amet,
 368 hendrerit quis dui. Maecenas vel purus in tellus luctus semper vel non
 369 orci. Proin viverra, erat eget pretium ultrices, quam quam vulputate
 370 tortor, eu dapibus risus nunc ac ipsum. Vestibulum ante ipsum primis
 371 in faucibus orci luctus et ultrices posuere cubilia Curae; Ut aliquet
 372 augue volutpat arcu mattis ullamcorper. Quisque vulputate consectetur
 373 massa, quis cursus mauris lacinia vitae. Morbi id mi eu leo accumsan
 374 aliquet ac et arcu. Quisque risus nisi, rhoncus vulputate egestas sed,
 375 rhoncus quis risus. Sed semper odio sed nulla accumsan vitae auctor
 376 tortor mattis.
 377
 378 Vivamus vitae mauris turpis. Praesent consectetur mi non sem lacinia a
 379 cursus sapien gravida. Aenean viverra turpis sit amet ligula
 380 vestibulum a ornare nunc feugiat. Mauris et risus arcu. Cras dictum
 381 porta cursus. Donec tempus laoreet eros. Nam nec turpis non dui
 382 hendrerit laoreet eu ut ipsum. Nam in sem eget turpis lacinia euismod
 383 eu eget nulla.
 384
 385 Suspendisse at varius elit. Donec consectetur pharetra massa nec
 386 viverra. Cras vehicula lorem id sapien hendrerit tristique. Mauris
 387 vitae mi ipsum. Suspendisse feugiat commodo iaculis. Maecenas vitae
 388 dignissim nunc. Sed hendrerit, arcu et aliquet suscipit, urna quam
 389 fermentum eros, vel accumsan metus quam quis risus. Praesent id eros
 390 pulvinar tellus fringilla cursus. Sed nec vulputate ipsum. Suspendisse
 391 sagittis, magna vitae faucibus semper, nibh felis vehicula tortor, et
 392 molestie velit lorem ac massa.
 393
 394 Duis aliquam accumsan lobortis. Morbi interdum cursus risus, vel
 395 dapibus nisl fermentum sit amet. Etiam in mauris at lectus lacinia
 396 mollis. Proin pretium sem nibh, id scelerisque arcu. Mauris pretium
 397 adipiscing metus. Suspendisse quis convallis augue. Aliquam sed dui
 398 augue, vel tempor ligula. Suspendisse luctus velit quis urna suscipit
 399 sit amet ullamcorper nunc mollis. Praesent vitae velit justo. Donec
 400 quis risus felis. Nullam rutrum, odio non varius ornare, tortor odio
 401 posuere felis, eget accumsan sem sapien et nunc. Fusce mi neque,
 402 elementum non convallis eu, hendrerit id arcu. Morbi tempus tincidunt
 403 ullamcorper. Nullam blandit, diam quis sollicitudin tincidunt, elit
 404 justo varius lacus, aliquet luctus neque nibh quis turpis. Etiam massa
 405 sapien, tristique ut consectetur eu, elementum vel orci.  " }
 406
 407 fn input3() -> str { " Lorem ipsum dolor sit amet, consectetur
 408 adipiscing elit. Pellentesque bibendum sapien ut magna fringilla
 409 mollis. Vivamus in neque non metus faucibus accumsan eu pretium
 410 nunc. Ut erat augue, pulvinar eget blandit nec, cursus quis
 411 ipsum. Aliquam eu ornare risus. Mauris ipsum tortor, posuere vel
 412 gravida ut, tincidunt eu nunc. Aenean pellentesque, justo eu aliquam
 413 condimentum, neque eros feugiat nibh, in dictum nisi augue euismod
 414 lectus. Nam fringilla placerat metus aliquam rutrum. Nullam dapibus
 415 vehicula ligula ut tempor. Aliquam vehicula, diam vitae fermentum
 416 aliquam, justo augue venenatis enim, porta euismod dolor libero in
 417 arcu. Sed sollicitudin dictum eros non ornare. Donec nec purus
 418 orci. Mauris euismod fringilla consequat. Praesent non erat quis risus
 419 dapibus semper ac adipiscing lorem. Aliquam pulvinar dapibus
 420 mollis. Donec fermentum sollicitudin metus, sit amet condimentum leo
 421 adipiscing a.
 422
 423 Vestibulum mi felis, commodo placerat rhoncus sed, feugiat tincidunt
 424 orci. Integer faucibus ornare placerat. Nam et odio massa. Suspendisse
 425 porttitor nunc quis mi mollis imperdiet. Ut ut neque ipsum, sit amet
 426 facilisis erat. Nam ac lacinia turpis. Vivamus ullamcorper iaculis
 427 odio, et euismod sem imperdiet non. Duis porta felis sit amet nunc
 428 venenatis eu vestibulum nisi scelerisque. Nullam luctus mollis nunc
 429 vel pulvinar. Nam lorem tellus, imperdiet sed sodales eu, auctor ut
 430 nunc.
 431
 432 Nulla at mauris at leo sagittis varius eu a elit. Etiam consequat,
 433 tellus ut sagittis porttitor, est justo convallis eros, quis suscipit
 434 justo tortor vitae sem. In in odio augue. Pellentesque habitant morbi
 435 tristique senectus et netus et malesuada fames ac turpis
 436 egestas. Nulla varius ornare ligula quis euismod. Maecenas lobortis
 437 sodales sapien a mattis. Nulla blandit lobortis lacus, ut lobortis
 438 neque dictum ut. Praesent semper laoreet nisl. Etiam arcu eros,
 439 pretium eget eleifend eu, condimentum quis leo. Donec imperdiet porta
 440 erat. Aenean tempor sapien ut arcu porta mollis. Duis ultrices commodo
 441 quam venenatis commodo.
 442
 443 Aliquam odio tellus, tincidunt nec condimentum pellentesque, semper
 444 eget magna. Nam et lacus urna. Pellentesque urna nisi, pharetra vitae
 445 dignissim non, scelerisque eu massa. Sed sapien neque, cursus a
 446 malesuada ut, porta et quam. Donec odio sapien, blandit non aliquam
 447 vel, lobortis quis ligula. Nullam fermentum velit nec quam ultrices et
 448 venenatis sapien congue. Pellentesque vitae nunc arcu. Nullam eget
 449 laoreet nulla. Curabitur dignissim convallis nunc sed blandit. Sed ac
 450 ipsum mi. Ut euismod tellus hendrerit arcu egestas sollicitudin. Nam
 451 eget laoreet ipsum. Morbi sed nulla odio, at volutpat ante. Vivamus
 452 elementum dictum gravida.
 453
 454 Phasellus diam nisi, ullamcorper et placerat non, ultrices ut
 455 lectus. Etiam tincidunt scelerisque imperdiet. Quisque pretium pretium
 456 urna quis cursus. Sed sit amet velit sem. Maecenas eu orci et leo
 457 ultricies dictum. Mauris pellentesque ante a purus gravida
 458 convallis. Integer non tellus ante. Nulla hendrerit lobortis augue sit
 459 amet vulputate. Donec cursus hendrerit diam convallis
 460 luctus. Curabitur ipsum mauris, fermentum quis tincidunt ac, laoreet
 461 sollicitudin sapien. Fusce velit urna, gravida non pulvinar eu, tempor
 462 id nunc.  " }