On Oct 7, 2011, at 12:38 PM, Jim Peters wrote: > Brian Anderson wrote: >> All task stuff is in the library now, partly because it allows more >> freedom to experiment. It does take away the compiler's ability to >> do any special optimizations with tasks. >> >> There's definitely a lot of opportunity to improve and influence the >> design of the task system still. > > It would be good if the option was left open to bring it back into the > compiler some day, so that later on more optimisation could be done if > someone felt that that would be useful.
I've been doing some background thinking on what a good data parallel story for Rust could be. Most data parallel languages so far fall into the camp of requiring a lot of compiler heroics to make them work well. Once we get to this point in Rust, it'll probably be a good time to think about this some more. I like keeping the core language as simple as possible, but maybe we can do more aggressive things with syntax extensions. > Eric Holk wrote: > For example in my 100,000 task example, if the spawning task yielded > directly to the spawned task, and the spawned task ran to completion > before yielding, then there would be no explosion of tasks. However > then there would also be no parallelism (unless the spawning task was > rescheduled onto another core). So that is a pretty powerful choice > the runtime is making. As it currently stands, the scheduler is free to run tasks on whatever core it wants, although last I checked it doesn't actually move tasks except when they are first created. Spawning tasks still creates parallelism. The case where the "yield to receiver" pattern would work well, I think, is in a program like MapReduce, where a bunch of tasks are doing independent work and sending intermediate results to a single accumulator task. One way to think of it is that rather than everyone sending their results to the receiver, the receiver would travel around gathering results from the sender. >> Other languages have lighter task-like things that >> could be used for things like iterators, but they tend to require >> extensive code transformations to implement efficiently. > > You're talking about emulating coroutines with a transformation into > normal called code? (I forget the name of the transformation.) If > you have a cheap coroutine switch operation that shouldn't be > necessary. I think I need to study Rust's implementation more. > Reading about LLVM's lack of support for coroutine switches was > disappointing -- although maybe that has improved. Two examples I was thinking of are stream processing languages like StreamIt, and task parallel languages like Cilk. In Cilk, spawn is basically a function call, but it marks the stack with a stealable continuation. Some other thread can then steal the continuation and pick up executing after the spawn statement. This works well because Cilk doesn't allow tasks to outlive the function they were spawned in, and continuation stealing allows large chunks of work to be stolen early on. Languages like StreamIt, on the other hand, define programs in terms of streams of data and filters on the data. The filters are typically small, so the compiler will try to take several adjacent filters and combine them into a bigger filter to reduce scheduling overhead. Data parallel languages such as Copperhead do similar things. -Eric _______________________________________________ Rust-dev mailing list [email protected] https://mail.mozilla.org/listinfo/rust-dev
