Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Problem with Threads (2006) [pdf]

www2.eecs.berkeley.edu

Post reply on HN
Print view View original

31–40 of 56 posts

Re: The Problem with Threads (2006) [pdf]

#31

Post by amelius »

chrisseaton wrote: post #6
jgtrosh wrote: post #4

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 w…

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 threa…

Triangulation and mesh refinement seem suitable for divide and conquer, except perhaps in pathological cases.

Re: The Problem with Threads (2006) [pdf]

#32

Post by chrisseaton »

amelius wrote: post #31
chrisseaton wrote: post #6

Earlier quoted context omitted.

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 threa…

Triangulation and mesh refinement seem suitable for divide and conquer, except perhaps in pathological cases.

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.

Re: The Problem with Threads (2006) [pdf]

#33

Post by jgtrosh »

chrisseaton wrote: post #32
amelius wrote: post #31

Earlier quoted context omitted.

Triangulation and mesh refinement seem suitable for divide and conquer, except perhaps in pathological cases.

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.

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?

Re: The Problem with Threads (2006) [pdf]

#34

Post by zzzcpan »

chrisseaton wrote: post #30
zzzcpan wrote: post #29

Earlier quoted context omitted.

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.

How co you argue it’s deterministic? If one actor asks two other actors to do a job and send the result back, those results come in a nondeterimistic order. That’s a race condition. It’s easy to write programs with bugs in them because of this. Something like fork-join is deterministic because results come in a fixed order. And for generating SIMD from actors? Or handling irregularity efficiently? I feel like you’re…

Non-deterministic order is not a race condition. You also need some sort of shared resource and being unaware of said non-deterministic order of incoming messages. With actor model you can't have shared resources and can't be unaware that messages come in no specific order.

And I'm not arguing for a sufficiently clever compiler, just that you can express any concurrency with actors. You can definitely create a convention backed by actors that compiles into SIMD if you need it.

Re: The Problem with Threads (2006) [pdf]

#35

Post by chrisseaton »

zzzcpan wrote: post #34
chrisseaton wrote: post #30

Earlier quoted context omitted.

How co you argue it’s deterministic? If one actor asks two other actors to do a job and send the result back, those results come in a nondeterimistic order. That’s a race condition. It’s easy to write programs with bugs in them because of this. Something like fork-join is deterministic because results come in a fixed order. And for generating SIMD from actors? Or handling irregularity efficiently? I feel like you’re…

Non-deterministic order is not a race condition. You also need some sort of shared resource and being unaware of said non-deterministic order of incoming messages. With actor model you can't have shared resources and can't be unaware that messages come in no specific order. And I'm not arguing for a sufficiently clever compiler, just that you can express any concurrency with actors. You can definitely create a conven…

> [it is a general race condition if] there is some order among events a and b but the order is not predetermined by the program

(Christoph von Praun)

If two actors do some work concurrently and when finished send a message to another actor, the order those messages arrive at the other actor, event a and event b, is not predetermined by the program. So it's a race condition.

    actor a {
      do some work;
      send 'a' to x;
    }

    actor b {
      do some work;
      send 'b' to x;
    }

    actor x {
      receive;
You can express any concurrency with actors, but we do not know how to do so as efficiently as with other concurrency models for parallelism. Someone might be able to implement it efficiently, but nobody has managed it yet, so we're still reliant on shared memory and other approaches concurrency.

Re: The Problem with Threads (2006) [pdf]

#36

Post by amelius »

chrisseaton wrote: post #32
amelius wrote: post #31

Earlier quoted context omitted.

Triangulation and mesh refinement seem suitable for divide and conquer, except perhaps in pathological cases.

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.

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).

Re: The Problem with Threads (2006) [pdf]

#37

Post by zzzcpan »

chrisseaton wrote: post #35
zzzcpan wrote: post #34

Earlier quoted context omitted.

Non-deterministic order is not a race condition. You also need some sort of shared resource and being unaware of said non-deterministic order of incoming messages. With actor model you can't have shared resources and can't be unaware that messages come in no specific order. And I'm not arguing for a sufficiently clever compiler, just that you can express any concurrency with actors. You can definitely create a conven…

> [it is a general race condition if] there is some order among events a and b but the order is not predetermined by the program (Christoph von Praun) If two actors do some work concurrently and when finished send a message to another actor, the order those messages arrive at the other actor, event a and event b, is not predetermined by the program. So it's a race condition. actor a { do some work; send 'a' to x; } a…

Common, you are literally trying to describe message passing as race conditions.

Re: The Problem with Threads (2006) [pdf]

#38

Post by chrisseaton »

zzzcpan wrote: post #37
chrisseaton wrote: post #35

Earlier quoted context omitted.

> [it is a general race condition if] there is some order among events a and b but the order is not predetermined by the program (Christoph von Praun) If two actors do some work concurrently and when finished send a message to another actor, the order those messages arrive at the other actor, event a and event b, is not predetermined by the program. So it's a race condition. actor a { do some work; send 'a' to x; } a…

Common, you are literally trying to describe message passing as race conditions.

It's not my definition! And you're right, normal message passing does leave you vulnerable to race conditions and your program can run a different way each time you run it! That's a major problem with it.

That's why I think other models of concurrency, such as the fork-join model, where the equivalent of 'messages' have to arrive in a deterministic order and so there are no race conditions, are safer.

Re: The Problem with Threads (2006) [pdf]

#39

Post by chrisseaton »

jgtrosh wrote: post #33
chrisseaton wrote: post #32

Earlier quoted context omitted.

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.

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?

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.

Re: The Problem with Threads (2006) [pdf]

#40

Post by zzzcpan »

chrisseaton wrote: post #38
zzzcpan wrote: post #37

Earlier quoted context omitted.

Common, you are literally trying to describe message passing as race conditions.

It's not my definition! And you're right, normal message passing does leave you vulnerable to race conditions and your program can run a different way each time you run it! That's a major problem with it. That's why I think other models of concurrency, such as the fork-join model, where the equivalent of 'messages' have to arrive in a deterministic order and so there are no race conditions, are safer.

Message passing forces you to explicitly handle non-deterministic order, how can it leave you vulnerable to race conditions? If you need to receive a specific message first, you wait for that specific message, that's it. Simple and deterministic.
Post reply on HN