5 ms·

You're missing C#/.NET which has had async/parallel programming constructs for a long time, and served as the model for await/async copied by many other languag

You're missing C#/.NET which has had async/parallel programming constructs for a long time, and served as the model for await/async copied by many other languages. It's gone through several design patterns from the original APM (async programming model) to EAP (event based pattern) to TPL (task parallel library) to the all purpose Task/ValueTask embedded into the language. It's very fast and efficient, and you can build your own scheduler too. Combined with hardware intrinsics in the latest .NET Core, it's very good for computational and server work. I'm surprised Julia considers this such a big update but it does seem to be an overstatement to say this changes technical computing.

opportune 7y ago
I really dislike using Tasks over threads due to the reusability issues. Specifically that Tasks are not reusable and threads are. It makes parallel computational work a headache, because you need to implement the reusability in a higher scope than tasks, then make an effort to prevent race-conditions, double checkouts, etc. Tasks are really meant for responsive computing, not proactive computing (yes, even TPL and Dataflow), and thus I don't think they are well suited to parallelized computation in areas like e.g. simulation.
- manigandham 7y ago
  What do you mean by reusable exactly? And how does proactive computing differ? Do you have an example you can share?
  - opportune 7y ago
    Reusable as in, I can create a datastructure in a thread, do some computation, yield control from the thread (wait for something else to tell it to go again), then come back to the thread with the same datastructure and keep going. With Tasks, you are supposed to let tasks complete rather than let them pause/sync so anything you declare locally is lost when you want to restart it. The workaround is to declare things in a higher scope and pass them into tasks as they are reran - this makes tasks not suited to things where you want to persist data, since tasks are opinionated in that they are only meant to contain logic, not state, so you have to add your own external logic to manage the allocation of state to the tasks that you keep recreating This trait of tasks makes sense when writing things like web servers because it prevents developers from shooting themselves in the foot by writing something that isn't stateless. By proactive computing, I mean some program that always has control of the entire execution graph. For example, a simulation may initialize a bunch of datastructures, separate some of them into threads, run the threads, wait for all of them to complete x ticks, do some synchronization or measurement of the total system, then continue y times, and exit.
    - DNF2 7y ago
      What would be the purpose of yielding control from the thread and tell it to wait, rather than just let it run to completion?
      - ska 7y ago
        Sometimes you don't know where you want to spend your CPU budget until you have more information.
        DNF2 7y ago
        Maybe I misunderstand you, but telling the thread to halt is surely a waste of those resources?
      - opportune 7y ago
        Because sometimes you need to sync the entire program state, or some subset of the state, to make measurements or to let disparate parts of the system interact
- minxomat 7y ago
  When a program is composed as a Dataflow pipeline, you don't handle tasks at all (unless you want to). I'm not sure what reusability issues you're referring to. Dataflow is very applicable to high CPU-throughput (i.e. efficient) pipelines. Concurrent by default, parallel on-demand. In practice, any I/O in my pipelines takes place in singleton consumers at the end of complex, highly-parallel, CPU-intensive code. C# code that uses Tasks and C# programs built on Dataflow are very different. The latter benefits you most when you commit entirely to that paradigm. If you want to get more low-level, low-overhead (for i.e. simulations), the same thing applies to things like Threading Building Blocks[1] in C++. I'd even argue that TBB is one of the best applications of this theory, going so far as to ship with dedicated tooling for the whole lifecycle of designing to implementing to profiling task- and graph-parallel programs [2]. Furthermore, it works well with other HPC libraries. Here [3] is an example of mixing it with OpenMP. In summary, both Dataflow and TBB (et al) can readily be used to create CPU-intensive, proactive computing pipelines today. Even though they're "just" fancy Task schedulers, which are in turn "just" fancy thread multiplexers. [1] - https://www.threadingbuildingblocks.org/tutorial-intel-tbb-flow-graph https://www.threadingbuildingblocks.org/tutorial-intel-tbb-f... [2] - https://www.youtube.com/watch?v=9bBqFW5hnVM https://www.youtube.com/watch?v=9bBqFW5hnVM [3] - https://software.intel.com/en-us/node/506128 https://software.intel.com/en-us/node/506128
ska 7y ago
I’m not certain an overstatement. I’m not convinced either. As you note these ideas are old (they mostly predate C# and .NET by decades). On the other hand, to a first order approximation, C# has made zero impact in this area. There are a bunch of reasons, but that’s the way it is. Fair or not, Julia does seem to have the potential to be the first really interesting shift in this area in ages. Doesn’t mean it will get there, but there is interest.
- manigandham 7y ago
  I was pointing out another very mainstream language (even more than Go and far more than Erlang) that has the same abilities. What do you mean by impact/shift exactly? I guess I'm not understanding what's suddenly going to change now since, as you say, these ideas are old and implemented several times before.
  - ska 7y ago
    What I mean is that C# has not been taken up for heavy numeric work in a significant way. Julia, for good or ill, seems to have some potential to be.
    - seanmcdirmid 7y ago
      Task concurrency is probably not a great idea for heavy numeric work anyways, right? I’m scratching my head a bit about what the use case for this is in Julia given that there are much better ways of doing parallelism already.
      - DNF2 7y ago
        Which ways are those?
        seanmcdirmid 7y ago
        Data parallelism mostly.
StefanKarpinski 7y ago
Julia has has the equivalent of async/await forever, except without needing to annotate anything with keywords—that’s just how I/O works. If you call a blocking function, it yields back into the scheduler. In Julia (as of 1.3), tasks are mapped onto multiple threads which run at the same time (in parallel) and threads that are idle can steal work efficiently. This is similar (as was said) to Cilk, TBB and Go. It is not the same as async/await in C#, which is concurrent but not parallel. What is 100% new and does not exist in any other system is that the task scheduling is depth first (rather than breadth first), which is a much better order for doing compute-heavy workloads. This ability is new and was the culmination of an Intel research project, applied to Julia.
- dwohnitmok 7y ago
  What do you mean by depth first vs breadth first? Naively I would assume task scheduling necessarily to be depth first in some sense because you have to evaluate your tasks' dependencies first.
  - StefanKarpinski 7y ago
    Consider a machine with N cores running a program which spawns N parallel tasks, each of which in turn spawns N parallel tasks. Which subtasks do the cores work on initially? If it's the first subtask of each top-level task, that's breadth-first scheduling. If it's all N subtasks of the first top-level task, that's depth-first scheduling. The latter is better for high-performance computing because it tends to be the lower level libraries that are really carefully tuned to make optimal use of the machine (think BLAS/FTT/parallel sum/prefix sum). Previously it was unknown how to implement this kind of scheduling efficiently. See this talk by Kiran Pamnany for more details: https://www.youtube.com/watch?v=YdiZa0Y3F3c https://www.youtube.com/watch?v=YdiZa0Y3F3c
    - dwohnitmok 7y ago
      Ah I see what you mean! I really hate to pile on with the Haskell observation but the 1995 paper by Blelloch that is mentioned in that talk is exactly the heart of GHC's data parallelism as well (under the name nested data parallelism). See slide 8 here: https://www.microsoft.com/en-us/research/wp-content/uploads/2007/01/NdpSlides.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... Later versions of Blelloch's language are referred to in other parallel Haskell papers. FWIW I think this is nonetheless fantastic news for Julia! It's certainly poised to do great work in areas that I doubt will get any Haskell traction anytime soon (if ever) for good reasons. EDIT: Interesting, I think Julia is taking a coarser grained approach here that breaks down a bit for irregularly balanced execution trees, but relies less on fusion (i.e. doesn't use fusion at all) which is nice. I'm curious to see how this particular implementation of the "depth first" idea goes! EDIT EDIT: Actually I'm not sure how much fusion is necessary for GHC's approach... Time to investigate more closely. Also call out to anyone more familiar with Data Parallel Haskell to chime in. I'm getting out of my depth.

opportune 7y ago

I really dislike using Tasks over threads due to the reusability issues. Specifically that Tasks are not reusable and threads are. It makes parallel computational work a headache, because you need to implement the reusability in a higher scope than tasks, then make an effort to prevent race-conditions, double checkouts, etc. Tasks are really meant for responsive computing, not proactive computing (yes, even TPL and Dataflow), and thus I don't think they are well suited to parallelized computation in areas like e.g. simulation.

manigandham 7y ago
What do you mean by reusable exactly? And how does proactive computing differ? Do you have an example you can share?
- opportune 7y ago
  Reusable as in, I can create a datastructure in a thread, do some computation, yield control from the thread (wait for something else to tell it to go again), then come back to the thread with the same datastructure and keep going. With Tasks, you are supposed to let tasks complete rather than let them pause/sync so anything you declare locally is lost when you want to restart it. The workaround is to declare things in a higher scope and pass them into tasks as they are reran - this makes tasks not suited to things where you want to persist data, since tasks are opinionated in that they are only meant to contain logic, not state, so you have to add your own external logic to manage the allocation of state to the tasks that you keep recreating This trait of tasks makes sense when writing things like web servers because it prevents developers from shooting themselves in the foot by writing something that isn't stateless. By proactive computing, I mean some program that always has control of the entire execution graph. For example, a simulation may initialize a bunch of datastructures, separate some of them into threads, run the threads, wait for all of them to complete x ticks, do some synchronization or measurement of the total system, then continue y times, and exit.
  - DNF2 7y ago
    What would be the purpose of yielding control from the thread and tell it to wait, rather than just let it run to completion?
    - ska 7y ago
      Sometimes you don't know where you want to spend your CPU budget until you have more information.
      - DNF2 7y ago
        Maybe I misunderstand you, but telling the thread to halt is surely a waste of those resources?
    - opportune 7y ago
      Because sometimes you need to sync the entire program state, or some subset of the state, to make measurements or to let disparate parts of the system interact
minxomat 7y ago
When a program is composed as a Dataflow pipeline, you don't handle tasks at all (unless you want to). I'm not sure what reusability issues you're referring to. Dataflow is very applicable to high CPU-throughput (i.e. efficient) pipelines. Concurrent by default, parallel on-demand. In practice, any I/O in my pipelines takes place in singleton consumers at the end of complex, highly-parallel, CPU-intensive code. C# code that uses Tasks and C# programs built on Dataflow are very different. The latter benefits you most when you commit entirely to that paradigm. If you want to get more low-level, low-overhead (for i.e. simulations), the same thing applies to things like Threading Building Blocks[1] in C++. I'd even argue that TBB is one of the best applications of this theory, going so far as to ship with dedicated tooling for the whole lifecycle of designing to implementing to profiling task- and graph-parallel programs [2]. Furthermore, it works well with other HPC libraries. Here [3] is an example of mixing it with OpenMP. In summary, both Dataflow and TBB (et al) can readily be used to create CPU-intensive, proactive computing pipelines today. Even though they're "just" fancy Task schedulers, which are in turn "just" fancy thread multiplexers. [1] - https://www.threadingbuildingblocks.org/tutorial-intel-tbb-flow-graph https://www.threadingbuildingblocks.org/tutorial-intel-tbb-f... [2] - https://www.youtube.com/watch?v=9bBqFW5hnVM https://www.youtube.com/watch?v=9bBqFW5hnVM [3] - https://software.intel.com/en-us/node/506128 https://software.intel.com/en-us/node/506128

ska 7y ago

I’m not certain an overstatement. I’m not convinced either. As you note these ideas are old (they mostly predate C# and .NET by decades). On the other hand, to a first order approximation, C# has made zero impact in this area. There are a bunch of reasons, but that’s the way it is. Fair or not, Julia does seem to have the potential to be the first really interesting shift in this area in ages. Doesn’t mean it will get there, but there is interest.

manigandham 7y ago
I was pointing out another very mainstream language (even more than Go and far more than Erlang) that has the same abilities. What do you mean by impact/shift exactly? I guess I'm not understanding what's suddenly going to change now since, as you say, these ideas are old and implemented several times before.
- ska 7y ago
  What I mean is that C# has not been taken up for heavy numeric work in a significant way. Julia, for good or ill, seems to have some potential to be.
  - seanmcdirmid 7y ago
    Task concurrency is probably not a great idea for heavy numeric work anyways, right? I’m scratching my head a bit about what the use case for this is in Julia given that there are much better ways of doing parallelism already.
    - DNF2 7y ago
      Which ways are those?
      - seanmcdirmid 7y ago
        Data parallelism mostly.

StefanKarpinski 7y ago

Julia has has the equivalent of async/await forever, except without needing to annotate anything with keywords—that’s just how I/O works. If you call a blocking function, it yields back into the scheduler. In Julia (as of 1.3), tasks are mapped onto multiple threads which run at the same time (in parallel) and threads that are idle can steal work efficiently. This is similar (as was said) to Cilk, TBB and Go. It is not the same as async/await in C#, which is concurrent but not parallel. What is 100% new and does not exist in any other system is that the task scheduling is depth first (rather than breadth first), which is a much better order for doing compute-heavy workloads. This ability is new and was the culmination of an Intel research project, applied to Julia.

dwohnitmok 7y ago
What do you mean by depth first vs breadth first? Naively I would assume task scheduling necessarily to be depth first in some sense because you have to evaluate your tasks' dependencies first.
- StefanKarpinski 7y ago
  Consider a machine with N cores running a program which spawns N parallel tasks, each of which in turn spawns N parallel tasks. Which subtasks do the cores work on initially? If it's the first subtask of each top-level task, that's breadth-first scheduling. If it's all N subtasks of the first top-level task, that's depth-first scheduling. The latter is better for high-performance computing because it tends to be the lower level libraries that are really carefully tuned to make optimal use of the machine (think BLAS/FTT/parallel sum/prefix sum). Previously it was unknown how to implement this kind of scheduling efficiently. See this talk by Kiran Pamnany for more details: https://www.youtube.com/watch?v=YdiZa0Y3F3c https://www.youtube.com/watch?v=YdiZa0Y3F3c
  - dwohnitmok 7y ago
    Ah I see what you mean! I really hate to pile on with the Haskell observation but the 1995 paper by Blelloch that is mentioned in that talk is exactly the heart of GHC's data parallelism as well (under the name nested data parallelism). See slide 8 here: https://www.microsoft.com/en-us/research/wp-content/uploads/2007/01/NdpSlides.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... Later versions of Blelloch's language are referred to in other parallel Haskell papers. FWIW I think this is nonetheless fantastic news for Julia! It's certainly poised to do great work in areas that I doubt will get any Haskell traction anytime soon (if ever) for good reasons. EDIT: Interesting, I think Julia is taking a coarser grained approach here that breaks down a bit for irregularly balanced execution trees, but relies less on fusion (i.e. doesn't use fusion at all) which is nice. I'm curious to see how this particular implementation of the "depth first" idea goes! EDIT EDIT: Actually I'm not sure how much fusion is necessary for GHC's approach... Time to investigate more closely. Also call out to anyone more familiar with Data Parallel Haskell to chime in. I'm getting out of my depth.