8 ms·

This piece seems to have predicted a very active field in everyday software development since then. What are the alternative paradigms that have actually becom

This piece seems to have predicted a very active field in everyday software development since then. What are the alternative paradigms that have actually become common use? Coroutines, async/await, that's what I hear about online but what are others? I've seen people who touted zmq-communicating-processes with standard patterns as the solution to all problems, and I'm happy not to have to maintain the results. Have we effectively “solved” the concurrency problem, and if so what's left as an exercise for the future?

chrisseaton 8y ago
Although this paper talks initially about concurrency, you can see that really he's talking about concurrency specifically for the purpose of parallelism. Coroutines don't solve the parallelism part, because they're concurrent but exclusive. Async/await as implemented in JavaScript doesn't solve the parallelism part either for the same reason, and async/await as implemented in C# has exactly the same problem as threads. There are many ideas for how to solve the problem - but I think anyone who is honest will tell you none are a perfect solution to all situations where you want parallelism or concurrency. For example to use zmq-communicating-processes effectively you need a problem where you can divide the data or tasks cleanly a-priori. We simply don't have the mathematical understanding of how to do that to some important algorithms that people really need to run in parallel today, such as triangulation or mesh refinement. We probably need some radical new idea, or maybe it's looking increasingly like only a mix of ideas will work.
- amelius 8y ago
  Triangulation and mesh refinement seem suitable for divide and conquer, except perhaps in pathological cases.
  - chrisseaton 8y ago
    They’re the canonical example everyone uses of where it doesn’t work well! In both of them there is tons of parallelism but you can’t work out what work is separate (divide it) until you have started the work.
    - jgtrosh 8y ago
      Isn't that something you could approach with work-stealing techniques? You'd need to build the work pile as you go but that seems appropriate. Maybe I'm missing something?
      - chrisseaton 8y ago
        The problem is: given a list of tasks that you want to solve in parallel, you cannot know ahead of time which jobs use the same data. You have to start solving them to figure that out. The problem isn't distributing the work, it's knowing when it's safe to do two things in parallel.
    - amelius 8y ago
      Let's say you have a domain X that you need to triangulate. You break it along a plane, into two domains A and B, about equally large. Imagine that you have a magical black box system that can triangulate A and B. Would this not help you to triangulate X? I can hardly believe it wouldn't. (Again, perhaps in pathological cases yes, or if a near-optimal solution is not good enough).
      - jgtrosh 8y ago
        Iirc, triangulation iterations can replace previous cuts. So A and B might not have any meaning in the next iteration if you triangulate properly. That's why it's okay to cut at random, because it only affects outcome indirectly.
        amelius 8y ago
        Wait a second, are we both talking about Delaunay triangulation?
        jgtrosh 8y ago
        Yes. After checking Wikipedia I was referring to the edge flipping operation which is described in the “flip algorithms” section. So there's also a divide and conquer algorithm in the article, but it needs extra steps to fix the divide edge. Was that what you were talking about?
barbegal 8y ago
Promises in javascript have become quite popular. Unfortunately, they're not understood very well so they aren't being used much in areas where they can improve the performance of javascript applications and instead are being used to reduce nested callbacks.
- klodolph 8y ago
  There's nothing wrong with using promises to reduce nested callbacks.
- acjohnson55 8y ago
  Really? At my company, promises have long since won the day. Now I'm trying to get people on async/await, which gets you like 90% of the way to the simplicity of synchronous code.
zzzcpan 8y ago
What do you mean by "the concurrency problem"?
- zbentley 8y ago
  My hunch: that modern programming often requires concurrent execution of software, but that most ways in which we have to model concurrency in code are at best hard to learn, and are frequently orders of magnitude harder to learn and use.
  - zzzcpan 8y ago
    It would be the mainstream languages problem then or something. Concurrency with actor model is easier to learn and use than OOP, which many people seem to be able to use.
    - gumby 8y ago
      I find a lot (most?) OOP code I read is either spaghetti (with weird object interdependencies), diffuse (waay to many classes and subclasses so following the flow of computation becomes difficult) or both. It's a great tool, but perhaps harder than widely realized. And concurrency is even harder, especially with the ever-popular "tweak until it parses/compiles, then ship" approach, or when many people are working on the same section of code. The Hewitt Actor approach reduces independencies dramatically, at some cost for certain algorithms, and with added clarity for many others. And it scales somewhat automatically beyond one machine which is a big win these days. My $0.02.
    - chrisseaton 8y ago
      The actor model is non-deterministic and doesn't solve all concurrency problems, such as creating fine-grained or irregular data parallelism. There isn't (and it may not be possible to have) one single solution to 'the concurrency problem'.
      - zzzcpan 8y ago
        Actor model is very deterministic, but it can model unbounded non-determinism, i.e. any concurrency problem. Including fine-grained and irregular data parallelism. It's up to the compiler to generate SIMD instructions out of it, if that's what you mean.
nickpsecurity 8y ago
On the parallelism side, it might bring ideas to look at languages attempting it so far. IBM's X10, Cray's Chapel, and Taft's ParaSail come to mind.
- pcwalton 8y ago
  You don't even need to get that exotic. OpenGL shaders, for instance, offer a simple, safe data parallelism model.
  - nickpsecurity 8y ago
    I don't know much about those. Thanks for the tip!
pcwalton 8y ago
Data parallelism in CUDA, OpenGL, and other GPU APIs is doing fantastically and has for decades. (If writes are allowed, these APIs technically have the same problems as threads, but in practice they're easier to deal with since traditional mutex locks and condition variables are mostly unavailable in that environment, and the APIs force you to carefully declare the sharing semantics of your data buffers.) Most parallel (not concurrent) problems map well to the data parallel model. Even Make is basically a data parallel API with read-only constant data, just with a more complex dependency graph.
toast0 8y ago
At risk of being that guy, the actor model (ala Erlang) is pretty good at concurrency. If you're unfamiliar, it's basically no shared state, and communication with other actors (Erlang processes) by sending asynchronous messages to the other actor's message queue. The code for each actor is usually pretty small and easy to reason about. However, emergent behavior of the system, and ordering between messages from multiple actors can become tricky. Also, exposure to this idea long term will warp your mind :)
- dnautics 8y ago
  It's also relatively easy to implement async/await using actor primitives.
- acjohnson55 8y ago
  The actor model is a great tool, but I think it's best looked at as a low level concurrency primitive. Most of the time, folks should be working with higher level constructs in conceptually simpler control flow paradigms like call-and-return (async/await) or streams.
  - true_religion 8y ago
    In Erlang, all those control flow paradigms exist in library form. You are right about the actor model being a low-level choice, but its a choice that has to be made since the whole system revolves around allowing/disallowing shared state.
- chrisseaton 8y ago
  The actor model is very vulnerable to race conditions - that’s a big downside to it.
  - toast0 8y ago
    It depends on what is racing. If you have the same/dependent information in two (or more actors), you're going to have a coordination challenge. So try not to do that. On the other hand, everything that happens with state within an actor is inherently non-racy, because an actor is sequential code and no other actor can mess with its state.

chrisseaton 8y ago

Although this paper talks initially about concurrency, you can see that really he's talking about concurrency specifically for the purpose of parallelism. Coroutines don't solve the parallelism part, because they're concurrent but exclusive. Async/await as implemented in JavaScript doesn't solve the parallelism part either for the same reason, and async/await as implemented in C# has exactly the same problem as threads. There are many ideas for how to solve the problem - but I think anyone who is honest will tell you none are a perfect solution to all situations where you want parallelism or concurrency. For example to use zmq-communicating-processes effectively you need a problem where you can divide the data or tasks cleanly a-priori. We simply don't have the mathematical understanding of how to do that to some important algorithms that people really need to run in parallel today, such as triangulation or mesh refinement. We probably need some radical new idea, or maybe it's looking increasingly like only a mix of ideas will work.

amelius 8y ago
Triangulation and mesh refinement seem suitable for divide and conquer, except perhaps in pathological cases.
- chrisseaton 8y ago
  They’re the canonical example everyone uses of where it doesn’t work well! In both of them there is tons of parallelism but you can’t work out what work is separate (divide it) until you have started the work.
  - jgtrosh 8y ago
    Isn't that something you could approach with work-stealing techniques? You'd need to build the work pile as you go but that seems appropriate. Maybe I'm missing something?
    - chrisseaton 8y ago
      The problem is: given a list of tasks that you want to solve in parallel, you cannot know ahead of time which jobs use the same data. You have to start solving them to figure that out. The problem isn't distributing the work, it's knowing when it's safe to do two things in parallel.
  - amelius 8y ago
    Let's say you have a domain X that you need to triangulate. You break it along a plane, into two domains A and B, about equally large. Imagine that you have a magical black box system that can triangulate A and B. Would this not help you to triangulate X? I can hardly believe it wouldn't. (Again, perhaps in pathological cases yes, or if a near-optimal solution is not good enough).
    - jgtrosh 8y ago
      Iirc, triangulation iterations can replace previous cuts. So A and B might not have any meaning in the next iteration if you triangulate properly. That's why it's okay to cut at random, because it only affects outcome indirectly.
      - amelius 8y ago
        Wait a second, are we both talking about Delaunay triangulation?
        jgtrosh 8y ago
        Yes. After checking Wikipedia I was referring to the edge flipping operation which is described in the “flip algorithms” section. So there's also a divide and conquer algorithm in the article, but it needs extra steps to fix the divide edge. Was that what you were talking about?

barbegal 8y ago

Promises in javascript have become quite popular. Unfortunately, they're not understood very well so they aren't being used much in areas where they can improve the performance of javascript applications and instead are being used to reduce nested callbacks.

klodolph 8y ago
There's nothing wrong with using promises to reduce nested callbacks.
acjohnson55 8y ago
Really? At my company, promises have long since won the day. Now I'm trying to get people on async/await, which gets you like 90% of the way to the simplicity of synchronous code.

zzzcpan 8y ago

What do you mean by "the concurrency problem"?

zbentley 8y ago
My hunch: that modern programming often requires concurrent execution of software, but that most ways in which we have to model concurrency in code are at best hard to learn, and are frequently orders of magnitude harder to learn and use.
- zzzcpan 8y ago
  It would be the mainstream languages problem then or something. Concurrency with actor model is easier to learn and use than OOP, which many people seem to be able to use.
  - gumby 8y ago
    I find a lot (most?) OOP code I read is either spaghetti (with weird object interdependencies), diffuse (waay to many classes and subclasses so following the flow of computation becomes difficult) or both. It's a great tool, but perhaps harder than widely realized. And concurrency is even harder, especially with the ever-popular "tweak until it parses/compiles, then ship" approach, or when many people are working on the same section of code. The Hewitt Actor approach reduces independencies dramatically, at some cost for certain algorithms, and with added clarity for many others. And it scales somewhat automatically beyond one machine which is a big win these days. My $0.02.
  - chrisseaton 8y ago
    The actor model is non-deterministic and doesn't solve all concurrency problems, such as creating fine-grained or irregular data parallelism. There isn't (and it may not be possible to have) one single solution to 'the concurrency problem'.
    - zzzcpan 8y ago
      Actor model is very deterministic, but it can model unbounded non-determinism, i.e. any concurrency problem. Including fine-grained and irregular data parallelism. It's up to the compiler to generate SIMD instructions out of it, if that's what you mean.

nickpsecurity 8y ago

On the parallelism side, it might bring ideas to look at languages attempting it so far. IBM's X10, Cray's Chapel, and Taft's ParaSail come to mind.

pcwalton 8y ago
You don't even need to get that exotic. OpenGL shaders, for instance, offer a simple, safe data parallelism model.
- nickpsecurity 8y ago
  I don't know much about those. Thanks for the tip!

pcwalton 8y ago

Data parallelism in CUDA, OpenGL, and other GPU APIs is doing fantastically and has for decades. (If writes are allowed, these APIs technically have the same problems as threads, but in practice they're easier to deal with since traditional mutex locks and condition variables are mostly unavailable in that environment, and the APIs force you to carefully declare the sharing semantics of your data buffers.) Most parallel (not concurrent) problems map well to the data parallel model. Even Make is basically a data parallel API with read-only constant data, just with a more complex dependency graph.

toast0 8y ago

At risk of being that guy, the actor model (ala Erlang) is pretty good at concurrency. If you're unfamiliar, it's basically no shared state, and communication with other actors (Erlang processes) by sending asynchronous messages to the other actor's message queue. The code for each actor is usually pretty small and easy to reason about. However, emergent behavior of the system, and ordering between messages from multiple actors can become tricky. Also, exposure to this idea long term will warp your mind :)

dnautics 8y ago
It's also relatively easy to implement async/await using actor primitives.
acjohnson55 8y ago
The actor model is a great tool, but I think it's best looked at as a low level concurrency primitive. Most of the time, folks should be working with higher level constructs in conceptually simpler control flow paradigms like call-and-return (async/await) or streams.
- true_religion 8y ago
  In Erlang, all those control flow paradigms exist in library form. You are right about the actor model being a low-level choice, but its a choice that has to be made since the whole system revolves around allowing/disallowing shared state.
chrisseaton 8y ago
The actor model is very vulnerable to race conditions - that’s a big downside to it.
- toast0 8y ago
  It depends on what is racing. If you have the same/dependent information in two (or more actors), you're going to have a coordination challenge. So try not to do that. On the other hand, everything that happens with state within an actor is inherently non-racy, because an actor is sequential code and no other actor can mess with its state.