HN Theater @HNTheaterMonth

This looks exciting, and I certainly plan to use it, but this style of parallelism isn't ideal due to the constant join()s which will really take its toll with Amdahl's law. This talk covers that and makes an argument for composing parallel code using futures instead: https://www.youtube.com/watch?v=4OCUEgSNIAY

⬐ CyberDildonics

You are talking about two very different things: parallelism and concurrency.

Also the joins don't sync data together, they wait for all threads to finish. That is not directly what Amdahl's law is about.

⬐ craftkiller

I disagree. Go to minute 45 in the talk for a visual of what I'm about to describe: Hypothetically an ideal multithreaded program would light up as much of the CPU as possible. If we viewed it as a timeline it would start at a single point, expand as a bubble to fill the available CPU resources, and then at the end contract back down.

Using this style of parallelism creates many bubbles that each condense down to a single point every time you call join(), similar to a beaded necklace. This means that the 'p' in Amdahl's law for the percentage of time spent in parallel tasks is already stunted from the blocks of sequential code (or necklace string) caused by the joins.

⬐ jerven

There is no need to call join more than once in a work stealing pipeline, join is the terminal operation. In other words it rather similar to future.get(), it is a synchronisation point; which yes is amdalhs law target.

Futures and workstealing parallel execution are two techniques that work hand in hand.

Practically it can't be compared with C++ annotated OpenMP for loops, which have an implicit join at the loop termination. In a parallel data flow system like Rayon there are no implicit joins, only explicit as required. join() in this system is more like return dataflow as show in the presentation you link too.

⬐ craftkiller

In a literal sense, yes. But, and perhaps I am understanding this wrong, the article in the join primitive section states: "Once they have both finished, it will return". If you ignore the cost of spinning up and tearing down the threads isn't this conceptually the same as the implicit join at the end of an OpenMP loop?

⬐ CyberDildonics

> In a literal sense, yes.

And that's why this isn't directly related to Amdalh's law, which is about data synchronization. If something is parallel yet not concurrent it doesn't need to be synchronized. So what you are describing is a pragmatic hangup.

⬐ jerven

In this specific case yes, but so is the await await as shown at https://youtu.be/4OCUEgSNIAY?t=3545 in your linked talk.

The nice thing is that join is recursive in the quicksort example and that means its equivalent to the await await syntax in practical terms. Which also means when both are finished it will return.

  let mid = partition(v);
      let (lo, hi) = v.split_at_mut(mid);
      Future:of(|| quick_sort::<J,T>(lo)).await(),
              Future:of(|| quick_sort::<J,T>(hi)).await());

Is exactly the same in parallelism as this

    let mid = partition(v);
    let (lo, hi) = v.split_at_mut(mid);
    J::join(|| quick_sort::<J,T>(lo),
            || quick_sort::<J,T>(hi));

Except that join gives better scheduling due to work stealing which will avoid unbalanced cpu usage.

My Rust is non existent but conceptually Rayon is similar to java9 parallel streams which I know well.

Kaiser also gave a pretty good keynote at Meeting C++, "Plain Threads are the GOTO of todays computing:" https://www.youtube.com/watch?v=4OCUEgSNIAY

Same talk maybe?

⬐ rubiquity

I like to think exceptions are also a slightly less egregious form of the GOTO.

⬐ Dylan16807

I don't really agree there. Exceptions can only break out. They're a moderately stronger form of return. You can't create spaghetti control flow with exceptions.

⬐ MetaCosm

Read this: http://www.lighterra.com/papers/exceptionsharmful/

There is a reason exceptions are often banned from environments and it isn't because they are awesome. They make code "exceptionally" (zing) hard to reason about.

⬐ Dylan16807

They can be bad without being goto-like/unstructured. You can make a lot of the same arguments about break statements when it comes to skipping code and reaching a statement without being sure what the previous statement was or screwing up your loop.

⬐ jeorgun

Many things are — http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-...

⬐ MetaCosm

I am a bit confused, what is the relevance of that paper to the comment? Unless I misunderstood, the comment appeared to be about flow control issues of exceptions(hidden control flow and corrupt state), and I don't see that addressed in that paper.

⬐ rubiquity

The paper is about subroutines (function calls) being a lot less complex because all a subroutine can do is finish and then go back to its caller. There are no semantics in subroutines for jumping around willy-nilly.

⬐ _yosefk

Actually, plain threads indeed are pretty much the goto's of parallel computing, one difference being that while various techniques analogous to "structured programming" - "structured threading", if you like - are available, they all work for some systems better than others, and often aren't very portable/ubiquitous yet. So right now they can't almost-kill raw threads the way ifs, fors and whiles almost killed goto's.

⬐ fmstephe

I think this is a really important observation.

There was a very interesting discussion between Cliff Click and Rich Hickey (linked at bottom). The highlight of it for me was Cliff Click suggesting that people often assume that because we use a range of great abstractions every day, garbage collection was his example of a very successful abstraction, there is tendency among programmers to assume that all abstractions are great. Cliff Click gives the example of a MPI as an abstraction which proved powerful in some domains but very fragile in general.

As far as I can tell we are still looking for a really good abstraction to replace threads.

http://www.azulsystems.com/blog/cliff/2008-05-27-clojure-stm...

⬐ jeffdavis

"garbage collection was his example of a very successful abstraction...we are still looking for a really good abstraction to replace threads"

Isolated preemptible processes are a more successful abstraction than GC or threads. Why are threads the comparison point for concurrent abstractions?

⬐ fmstephe

That is a very fair statement. It is certainly true that threads are a more successful abstraction than garbage collection.

Perhaps a better statement is to observe that garbage collection has improved continuously over time and expanded the range of applications where garbage collection is used (as an aside if we look at the GC systems developed by Azul we get a indication of where GC can take us in the future).

Meanwhile the abstractions we are using to replace threads tend to be restricted to certain domains. A recent example of this would be the really interesting discussion around the use of green threads in Rust.

https://mail.mozilla.org/pipermail/rust-dev/2013-November/00...

Rust started with a user-space light weight threads system built into the language and has since pushed that into library. The issue was that green threads are tricky abstraction in some domains.

Although my comment above was clumsy, I really just wanted to add the linked conversation between Rich Hickey and Cliff Click, because I felt it was a really good illustration of what josefk was saying, which I understood to be roughly that the comparison with GOTO isn't quite right, because we don't have a small neat set of constructs, like if, while and for etc, to replace it. Replacing threads looks like it will be much harder.

⬐ _yosefk

Personally I'd probably label MPI as "too low-level" an abstraction, not unlike threads; and I think there are many great high-level threading abstractions which I wouldn't call fragile, from Cilk/TBB and the like to transactional memory.

What I meant to say was, Cilk/similar can be very useful at times, transactional memory at other times, Erlang-style fully isolated lightweight processes at still other times, etc. - and none of these approaches comes with a universally available interface, also none is universally taught (while threads are.)

So my guess is that raw threads will be used increasingly less but (A) it will take time and (B) either we miss something right now or it will take more mechanisms and approaches to replace raw threads than it took to replace goto.

That said, anyone needing to do something with threads today at any sort of scale (even if it's one guy who writes something that needs to be maintained over a long span of time) should IMO hide the threads behind something. (My take on it is https://github.com/yosefk/checkedthreads)

⬐ fmstephe

I agree that it looks like we will end up with a much larger, and less universally applicable, toolbox of abstractions.

Feels like a fun time to be programming, while we search for the right set of abstractions. :)