For completeness' sake, Haskell has had this for over a decade :) A SO thread that gives a nice overview [0], the paper [1], the library [2]. Here's how a parallel fib looks like:

  fib :: Int -> Int
  fib n
    | n <= 1    = 1
    | otherwise = x ‘par‘ (y ‘pseq‘ x + y + 1)
    where
      x = fib (n-1)
      y = fib (n-2)

[0] https://stackoverflow.com/questions/958449/what-is-a-spark-i...

[1] http://simonmar.github.io/bib/papers/strategies.pdf

[2] http://hackage.haskell.org/package/parallel-3.2.2.0/docs/Con...

Perl6 also has been able to do this for a couple of years:

    sub fib(Int $n) {
        return $n if $n < 2;
        my $t = start { fib($n - 2) }
        fib($n - 1) + await($t);
    }

For complete completenes sake, Haskell has existed for almost three decades :)

While the earliest versions of Haskell date back that far, those combinators only came out in 2007 (IIRC).

Those functions weren’t part of Haskell back then.

What do you mean? That's my point exactly. While Haskell has that now, they didn't always have it.

If a programming language is created in 2019 they can certainly instantly incorporate insights from existing technology in their design an plans. However, that doesn't mean that any programming language/compiler project started today will instantly have all of those features. Things take time in each new framework.

I don't know what your point is, then.

Haskell didn’t have it originally. Ok. But what do you think that says about whether it’s a new idea or not? What’s the connection? Why mention it in this thread about whether it's a new idea or not?

At what point did anyone claim it was a new idea? The blog post cites prior art in the very first paragraph. Not in a footnote—in the main text. The top post here cites several other languages with a similar model. This entire thread reads like a bunch of dudes who are really dying to "well, actually" someone.

I think people were responding to

> The only systems which have supported compute-oriented composable parallelism like this are Cilk and TBB

Because it isn’t true. Haskell is an example of why it isn’t true.

It's extremely debatable that Haskell is compute-oriented. I know that Haskell people like to talk about doing numerical computing in Haskell, but in reality it does not seem to be a thing. No one has ever used Haskell to implement large scale scientific computations on supercomputers, for example.

No one? Ever? https://onlinelibrary.wiley.com/doi/full/10.1002/cpe.3746

This particular example appears to be an implementation of a 'Computer algebra system', which seems to be a type of symbolic computing rather than numerical computing.

You're really asking for a Dan Luu sequel here.

> this kind of composable parallelism are Go and Erlang, ... which therefore optimize for I/O throughput rather than CPU throughput

Parallelism is always for CPU throughput, precisely why you don't run any more OS threads than the number of cores.

Concurrency primitives (whether in Go, Erlang or any other programming language) are meant for I/O-bound tasks. Let's not conflate concurrency primitives enabling I/O-bound tasks and parallelism primitives enabling CPU-bound tasks.

> precisely why you don't run any more OS threads than the number of cores

It’s often worth running more than your number of cores, in order to keep execution units busy during memory fetches for example, or integer units busy while float units are a bottleneck otherwise. (Did a PhD partially on this kind of thing.)

That's what hyperthreading is for, which implies having the same number of threads as logical cores.

Hyperthreading and out of order execution are meant to accomplish keeping the execution units busy.

No it implies having the same number of OS threads as hardware threads, which is more than the number of hardware cores.

That's what logical cores means. Hardware threads / hyper threads are also called logical cores by the bios and OS.

You are obviously correct and I'm not sure why you are being downvoted.

You can still use Erlang style concurrency (or Go style as well) to truly parallelize CPU bound tasks. It’s a bit less efficient due to Erlangs design where you can’t readily share mutable data between processes but will still enable true parallel calculations on all cores. By default BEAM runs one execution thread per core. For example, it’d be trivial to write a true parallel merge sort in Erlang/Elixir.

Now NodeJS or Python Asio style concurrency _are_ truly limited by their VMs and can’t do native parallel computations in a single process.

(Since this is basically now a comment where everyone "me too"s in a reply...)

F# also has facilities for this, depending on what you're after. The _MailboxProcessor_ type, though not as "for real" as the green threading in Go, allows for some pretty high throughput with a relatively sane message-passing abstraction.

And .NET itself offers many means to do parallel programming (which can get quite optimized), of which F# has some nice abstractions for.

So I don't think it's quite fair to say that only Go and Erlang have good support for parallelism. I also don't think they use their abstractions typically for parallelism (but I good be wrong).

> (Since this is basically now a comment where everyone "me too"s in a reply...)

Related work in Common Lisp:

https://github.com/pcostanza/claws/

https://european-lisp-symposium.org/static/2014/costanza.pdf

He didn't really say that, though, rather that just Go and Erlang has a similar kind of _composable_ parallelism. (Don't know about Haskell.)

That name though, couldn't it just be Agent?

As a physicist, it's been really cool seeing the awareness of Julia in the community gradually increase.

Large swathes of the physics community have been migrating their code to Python over the past few years but it really seems now that Julia is getting so many amazing features and packages that it can't be ignored.

Same here, I worked in a computational biophysics department with lots of python/bash/R and I was the only one who wrote lots of high-performance code in Julia. People were curious about the language but it was still very much unknown. Hope we will see a broader adoption of Julia in the future - it's just that much better for the stuff we do on a daily basis.

Great to see this finally land - thanks for all the team's work. Looking forward to giving it a whirl.

Threading is something of a prerequisite for acceptance as a serious language among many folks. So great to not just check that box, but to stick the pen right through it.

The devil is always in the details, but from the doc the interface looks pretty nice (given threaded code generally looks like it was written by Cthulhu).

> given threaded code generally looks like it was written by Cthulhu

Whereas in Julia, we use Cthulhu to read code ;) - https://github.com/JuliaDebug/Cthulhu.jl.

This is a bit over the top isn’t it? It’s just task parallelism. It’s exactly what for example Haskell has been doing for decades isn’t it? It’s even the same demo and interface!

My understanding is that it's not just about the parallelism, but about the type of threading model that is used, which makes it extremely composable.

It's literally just futures. (Still very hard to implement, of course, and in particular IMO this kind of implementation (M-to-N threading) is much better than the async/await implementations) but CS is pretty settled on futures being the "best" model, even C++ has them!)

My understanding was that the depth-first scheduling was basically 'new'.

In my experience most work-stealing schedulers for task parallelism like this are going to be depth-first. I’ve written several myself. Primarily for temporal locality - if you just created a task it’ll be resident in cache.

I'm still trying to access the relevant papers, but from bits of discussions here it seems to me that the difference between the Julia scheduler and cilk is that the former will try to distribute sibling leaf tasks among executors enforcing as close as a global depth first view as possible, while cilk does depth first on each executor but different executors will be exploring distinct the problem space branching off as close to the root as possible (due to the steal the oldest ancestor behaviour). It is a compromise between better cross executor cache locality and increased contention I guess.

Futures in c++ are really meant for concurrency especially for IO. They currently are way too heavy weight for fine grained parallelism (although there is work ongoing on that). Also futures are about packaging tasks, all the stuff being discussed here is about optimal scheduling which is completely orthogonal.

Do people use Cilk heavily in the high-performance computing world? They did not when I was part of it. I think OpenMP (https://www.openmp.org/) is what more people would reach for. It started as a way to parallelize loops, but has had a task framework for a long time which I believe also allows composeable parallelism.

OpenMP, however, depends on not just compiler extensions, but pragmas, so it tends to not find traction outside of the HPC world.

While extremely elegant and minimalistic, I do not think cilk ever gained much traction. GCC has deprecated it and is removing it. I think that OpenMP was too entrenched in the language extension space (and has since grown at least the potential of cilk like functionality), while more portable libraries (TBB for example) covered everything else.

I think it has been highly influential though.

Yes, Cilk has been enormously influential. I have personally cited it many times. But I always had the impression it was a little too early for its time, and was never picked up by the HPC community, hence my question.

Cilk maybe not, but TBB is just a library (or more accurately a toolbox of primitives), which integrates nicely with OpenMP: https://software.intel.com/en-us/node/506128

The real gain is with MPI, anyway... shared memory is a trap. All the projects I've worked on have exploited parallelism through message passing, or a battle tested multithreaded linear algebra library.

There are many techniques and calling any of them the one solution and all others a trap is extremely myopic. Shared memory is extremely useful for IPC and fork join parallelism.

My understanding is that, at least in c/Fortran/c++ land common practice is openmp within a machine and MPI across machines. I've done some work of the sort but I'm far from an expert though.

You are correct.

> All the projects I've worked on have exploited parallelism through message passing

What? Lots of parallelism doesn't use message passing!

GPU is the way to go these days to get most parallelism, and it is definitely the shared memory variety. Message passing is the go to when parallelism needs to cross machine boundaries.

GPU parallelism is highly specialized and requires very specific workloads (e.g., many linear algebra workloads). GPUs are a bad choice for general parallelized tasks.

Yes, but for heavy numeric problems, GPUs are your best bet if you can make them work. The question is what is Julia being used for, I guess.

A quibble: it's not necessarily "heavy numeric" problems, but problems where the calculations involve extensive data-reuse. (Of which matrix operations are the most obvious.) The GPU is massively parallel, but the up-front cost of transferring data to the GPU is quite high.

Hence, in order for that up-front cost to be worth it, the algorithms run on the GPU need to re-use that data many times. If the algorithms running on the GPU don't make extensive reuse of the data sent to it, it would be faster to just do the calculation on the host CPU.

MPI is the HPC horizontal scaling strategy, for when you need to go from 1 core to 500k.

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.

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.

Hum, isn't cilk-like work stealing depth first? Idle executors steal oldest ancestor and busy executors eagerly execute recursive calls while pushing parent in the local job stack?

Proof of optimality was in the early cilk papers in the '90s.

I'm sure the same algorithms made into Julia via Intel (which bought cilk in the early '00), but it is hardly new except in the 'everything old is new again'.

Also IIRC OpenMP supports (or at least allows) work stealing although at least GCC does not implement it yet.

It's all about better L3 utilization. Cilk is good for using L1 and L2, i.e. caches that are core-local, and suboptimal for using L3, i.e. caches that are shared between cores.

Can you expand on this or point me to a paper discussing this?

In the presentation posted here there was a paper citation that compared in terms of cache the model used (parallel depth first scheduling) over work stealing, but I didn't have time to read it yet.

https://www.cs.cmu.edu/%7Echensm/papers/ConstructiveCacheSha...

Can't manage to download the file though my flimsy mobile connection, but I'm starting to understand the difference.

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.

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

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

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.

I'm not surprised that Haskell supports this kind of parallelism, although I wasn't aware of it previously. After all, if you're going to the trouble of being that pure, why not be parallel?

Isn't a blocking function, by definition, something that blocks and doesn't yield? How could the language know to automatically yield on something without annotations?

> "async/await in C#, which is concurrent but not parallel"

C# is multithreaded. Things can only be parallel if you have 2 separate paths of execution that don't depend on each other or any serial order, but you can also kick off millions of individual tasks in a single function and await them all too. These tasks are all scheduled onto threads in a managed threadpool that also share work and run at the same time. I fail to see how this is any different or less capable than the others you mentioned.

C# has threads but async/await does not use them. If you think that `async` in C# does the same thing as `@spawn` in Julia and `go` in Go, you are mistaken. It does not. There is also an `@async` macro in Julia that does what the `async` keyword in C# does (which, again, does not involve threads).

https://stackoverflow.com/questions/37419572/if-async-await-...

https://blog.stephencleary.com/2013/11/there-is-no-thread.ht...

https://blogs.msdn.microsoft.com/benwilli/2015/09/10/tasks-a...

I'm very familiar with C# and I'm not talking about threads, only that multi-threading is a basic requirement and C# has a threadpool running threads in parallel.

I said that C# also uses Tasks which are scheduled onto these threads, which is what you said Julia does, so it's the same. C# can also start new threads just as easily, or use channels like Go with the TPL/Dataflow, System.Threading.Channels, actor frameworks, Reactive Extensions, or just chaining tasks together. Other than the depth-first algorithm, it seems like C# has the same capabilities as Julia and the others, if not more, and is much more "mainstream".

Can you explain how blocking functions are automatically yielded without keywords though? I cant find any documentation on this that doesnt mention the @async macro.

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.

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

[2] - https://www.youtube.com/watch?v=9bBqFW5hnVM

[3] - https://software.intel.com/en-us/node/506128

What do you mean by reusable exactly? And how does proactive computing differ? Do you have an example you can share?

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.

What would be the purpose of yielding control from the thread and tell it to wait, rather than just let it run to completion?

Sometimes you don't know where you want to spend your CPU budget until you have more information.

Maybe I misunderstand you, but telling the thread to halt is surely a waste of those resources?

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

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.

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.

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.

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.

Which ways are those?

Data parallelism mostly.

We're not talking about concurrency, but actual parallelism.

Anyway, if by data parallelism you mean simd, then that is already available and widely used in Julia. Multithreading comes on top of that.

The interface does look a lot like Cilk, which is a definite plus as that is an absolute pleasure to use.

This however offers a lot more configurability than Cilk (or at least more accessible configuration). Whether that’s a curse or blessing... I guess we’ll find out! :)

Also, have you looked into implementing Cilk-style reducers at all? [0]

[0]: https://www.cilkplus.org/docs/doxygen/include-dir/group___re...

Big difference is that Cilk appears to typically synchronize on function return, while julia needs an explicit wait/fetch (there is also a @sync macro). That is, spawn/wait can be matched from the AST in cilk, while julia demands that the user communicates and stores a reference to the started task for later waiting.

It is easy to forget to wait on a task, or even lose reference to it. The current scheduler will typically execute this task quickly, even if nobody ever waits on it; until load changes and you have races everywhere. There are currently no warnings comparable to Python's "RuntimeWarning: coroutine foo was never awaited".

Cilk does indeed sync on function return. You can also manually call 'cilk_sync'. I do think that Cilk’s approach is better (more in line with “make error states unrepresentable”, which I’m a big fan of), but Julia’s approach seems to be more in line with their overall goal of giving the programmer as much control as possible. Not sure if that’s a good thing or not, but as said above... we’ll find out soon!

Affine types to represent futures would help here.

>The only mainstream languages with this kind of composable parallelism are Go and Erlang, both of which target writing servers, rather than high-performance computing, and which therefore optimize for I/O throughput rather than CPU throughput.

Rust, while perhaps not as mainstream and not necessarily targeting scientific computing users, has data-bound parallelization like this via the rayon library.

Which indeed was named after Cilk.

> The only mainstream languages with this kind of composable parallelism are Go and Erlang

I think there are a few more of those languages. AFAIK Clojure and Rust should be added to the list.

> The only mainstream languages with this kind of composable parallelism are Go and Erlang

Concurrency? Go is not good at parallelism, compared to, say, Haskell.

What's wrong with parallelism in Go?

I have something in the works which is very similar - but is language agnostic. Pro: no need to switch to another language; Con: not high performance.

We are using this in production for now over 1 year, and it helps tremendously. We are currently only supporting a ruby client, but other languages should be more or less easy to bring into the mix. A wider release is planned for later this year - feel free to ask me anything via email!

Will this be worked to scale to multiple machines?

Julia has supported distributed compute forever. Just give it a machine file and you have an instant fully connected cluster.

MATLAB has had this for years. But it costs $1,000 on top of the existing license cost. And it's lumped together with their GPGPU/cluster tools.

If you're talking about the Parallel Computing Toolbox (PCT), then, no, you do not get access to multithreading through that, only multiprocessing and GPU processing. I recently considered buying the PCT, and this is one of the main reasons I probably won't.

The only type of multithreading in Matlab is the type that is built into the core language, and you don't get any control over that.

Finally, the claim to originality here isn't just the introduction of multithreading (which isn't even new in Julia!), but the particular threading model and scheduler, which lends itself particularly well to composable multithreading.

Scala futures seem to offer all of this functionality as well, no? And you can do all the regular monad stuff on them as well, which is super nice.