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

41–50 of 56 posts

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

#41

Post by jgtrosh »

amelius wrote: post #36
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.

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

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.

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

#42

Post by chrisseaton »

zzzcpan wrote: post #40
chrisseaton wrote: post #38

Earlier quoted context omitted.

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.

This is a real error I've seen someone make using Erlang in making a parallel sort when teaching parallel programming to masters students.

    actor A {
      receive half an array
      sort it
      send it to C
    }

    actor B {
      receive half an array
      sort it
      send it to C
    }

    actor C {
      (a, b) = divide input array into halves
      send a to A
      send b to B
      receive a'
      receive b'
      merge a', b'
    }
They send to A, send to B, and then think they're going to receive from A first, because they sent first, but B could finish first instead. Sometimes their program works, sometimes it doesn't.

Yeah it's their fault, but the model hasn't helped them not make the bug and worse they may never see the bug until they deploy into production.

If we used a fork-join model, they could not have made this mistake, and even if they did make some kind of mistake, at least they'd see it every time they ran their program.

    (a, b) = divide input array into halves
    fork {
      sort a
    }
    b' = sort b
    a' = join
    return a' + b'

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

#43

Post by toast0 »

chrisseaton wrote: post #27
toast0 wrote: post #20

Earlier quoted context omitted.

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

The actor model is very vulnerable to race conditions - that’s a big downside to it.

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.

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

#44

Post by zzzcpan »

chrisseaton wrote: post #42
zzzcpan wrote: post #40

Earlier quoted context omitted.

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.

This is a real error I've seen someone make using Erlang in making a parallel sort when teaching parallel programming to masters students. actor A { receive half an array sort it send it to C } actor B { receive half an array sort it send it to C } actor C { (a, b) = divide input array into halves send a to A send b to B receive a' receive b' merge a', b' } They send to A, send to B, and then think they're going to r…

Erlang lets you receive first message first even if it arrives last, you just have to specify which message, exactly as in your example. But order doesn't actually matter for sorting, you cannot possible make a mistake wrt to ordering here.

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

#45

Post by amelius »

jgtrosh wrote: post #41
amelius wrote: post #36

Earlier quoted context omitted.

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

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.

Wait a second, are we both talking about Delaunay triangulation?

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

#46

Post by kapv89 »

zbentley wrote: post #10
zzzcpan wrote: post #9

Earlier quoted context omitted.

What do you mean by "the concurrency problem"?

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.

Node.js is pretty good in this sense. Except for the very hard parts, because of node's async nature, you can introduce good amount of concurrency in your code by default, resulting in a decent amount of IO being concurrent. You have to get used to a fully-async programming model though.

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

#47

Post by toast0 »

chrisseaton wrote: post #42
zzzcpan wrote: post #40

Earlier quoted context omitted.

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.

This is a real error I've seen someone make using Erlang in making a parallel sort when teaching parallel programming to masters students. actor A { receive half an array sort it send it to C } actor B { receive half an array sort it send it to C } actor C { (a, b) = divide input array into halves send a to A send b to B receive a' receive b' merge a', b' } They send to A, send to B, and then think they're going to r…

As with most things in Erlang; if it's important, you must make it explicit. Implicit ordering works in your fork-join example with only a single fork, but if you require an ordering, you must be explicit about passing information through to enforce the ordering you need.

If you instead did

    fork {
      sort a
    }
    fork {
      sort b
    }
    a' = join
    b' = join
you would have the same problem as in Erlang. or you could have actor C sort B inside the actor between send a to A and receive a' and you would also have an implicit ordering.

In this case, merge sort could work with either order if a stable sort isn't required, or if the sort key is the whole element.

If it matters, this is easy to defend against, you just send a tag (a ref in Erlang would be perfect for this case, if the merge happened in a fourth actor, a numeric indication of ordering would be more useful) in the message to actors A and B, and use that to enforce an ordering when receiving the replies.

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

#48

Post by jgtrosh »

amelius wrote: post #45
jgtrosh wrote: post #41

Earlier quoted context omitted.

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.

Wait a second, are we both talking about Delaunay triangulation?

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?

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

#49

Post by amelius »

jgtrosh wrote: post #48
amelius wrote: post #45

Earlier quoted context omitted.

Wait a second, are we both talking about Delaunay triangulation?

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?

Yes, that's what I was thinking about.

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

#50

Post by chrisseaton »

toast0 wrote: post #47
chrisseaton wrote: post #42

Earlier quoted context omitted.

This is a real error I've seen someone make using Erlang in making a parallel sort when teaching parallel programming to masters students. actor A { receive half an array sort it send it to C } actor B { receive half an array sort it send it to C } actor C { (a, b) = divide input array into halves send a to A send b to B receive a' receive b' merge a', b' } They send to A, send to B, and then think they're going to r…

As with most things in Erlang; if it's important, you must make it explicit. Implicit ordering works in your fork-join example with only a single fork, but if you require an ordering, you must be explicit about passing information through to enforce the ordering you need. If you instead did fork { sort a } fork { sort b } a' = join b' = join you would have the same problem as in Erlang. or you could have actor C sort…

> you would have the same problem as in Erlang

Ah but that's not how fork-join works - you fork multiple jobs, and then you must join them all at the same time - you can't join just one.

You have to do something like

    (a, b) = join
Post reply on HN