4 ms·

> Why can't the runtime automatically leverage multiple cores and speed up the process? Do any runtimes actually do this? (Honest question)

thanatropism 9y ago
Matlab.
jackhack 9y ago
Erlang/elixir's runtime, OTP (open telecom platform) will do this. It can scale to multiple cores, or across multiple machines in a network, almost effortlessly. https://en.wikipedia.org/wiki/Erlang_(programming_language) https://en.wikipedia.org/wiki/Erlang_(programming_language)
- klibertp 9y ago
  It doesn't happen automatically on BEAM - you still need to explicitly spawn your processes.
cormacrelf 9y ago
Edit: Apache Spark. See below. Some do. But more importantly, if your runtime doesn't, then it's still more obvious how to add parallelism, and more self-contained when you do. Let's say you were using asynchronous IO in a functional style; not even full-on monads, just async/await like in C#. Since you have explicit data dependencies, you can easily see where the `await` is unnecessary, or coalesce multiple calls into await Task.WhenAll(...). var slow = await conn.Query(@"slow query"); var fast = await conn.Query(@"select top 1 * from some_table"); var emailresult = await SendEmail(fast); return (slow, emailresult); Instead of awaiting `slow` before continuing with `fast`, it's fairly obvious that you could start the task and not await it until the others have already kicked off: var slowTask = conn.Query(@"slow query"); var fast = await conn.Query(@"select top 1 * from some_table"); var emailresult = await SendEmail(fast); return (await slowTask, emailresult); That way, your email sends almost immediately, since line 1 never relinquishes control flow and just continues straight on. Then your `await slowTask` only blocks the return, instead of the entire function. This is pretty big if you're lining up a hundred slow IO tasks. Note: while async IO gives you the actual parallelism, it's only because of the explicit dependencies that we are able to see which parts can be done simultaneously. I've been coding like this for so long I can barely imagine how to do it imperatively, but if you exposed an interface like `async Task GetSlowQueryResults()` and `async Task SendEmail()` using internal fields for intermediate results, it's utterly opaque and you can't tell which has to complete first. Edit to respond better to your actual question: There's a kinda big problem with auto-parallelizing, which is that in FP, outside of IO, everything is parallelizable. Spinning up threads or even shuffling data within a thread pool is pretty costly, so most attempts at micro-parallelizing everything haven't gone anywhere. You can annotate things in Haskell to run in parallel, or simply choose a parallel map or parallel reduce instead of a sequential one. On the other hand, when spinning up threads/processes/jobs is relatively inexpensive compared with the cost of actually computing things, the idea is very successful. Take Apache Spark. You write a program in functional Scala or Python, and the scheduler will automatically distribute work over your cluster if it's big enough to warrant it. The scheduler also makes note of where intermediate results are, and will happily cache, reuse, shuffle or partition them around to continue on with the work. The engine essentially evaluates a DAG, with some optimizations for transport/persistence costs.
iainmerrick 9y ago
AFAIK this is still an active area of research. In principle pure functional programs can be freely parallelized, but in practice it's hard to do it completely automatically without losing more in overheads than you gain through parallelism. In Haskell I think the standard approach is still to annotate your code, indicating which parts should be evaluated in parallel. See https://wiki.haskell.org/Parallelism https://wiki.haskell.org/Parallelism
- jandrese 9y ago
  Even if all of your functions are pure they can still have data dependence with one another. So you obviously can't parallelize foo(bar()) automatically. There are other things that can make a real mess of paraellizability too, like error checking. Say you have some code like: comprehend all item in list, verify(item) or errorout("failed at ", stringify(name(item))) The compiler can't auto parallelize it because the exit condition is unknowable, at least if you want there to only be a single exit from the function. You can get around this with even more strict requirements, but after enough of these restrictions even simple tasks start to get hard.
imtringued 9y ago
No. The reason? In the nano second to 1 microsecond range your CPU already automatically parallelises your code by using out of order execution. Unless you're wastefully busy waiting, the latency of issuing a new job to a second thread is in the 10s of microseconds. You can't just issue new job without first knowing how much time the job is going to take and whether it's even worth it to parallelise it. Profiling every line of code at runtime will introduce even more overhead. It's far simpler to just let the developer annotate the parts of the codebase that should run in parallel. Example: r=a/b + c*d can in theory be parallelised but you'd have to pay 10 microseconds in overhead which is likely more than 5000 times slower than just running it on a single core. TL;DR automatically parallelising a program is trivial, making a parallelised program run faster than a non parallelised program is not

thanatropism 9y ago

Matlab.

jackhack 9y ago

Erlang/elixir's runtime, OTP (open telecom platform) will do this. It can scale to multiple cores, or across multiple machines in a network, almost effortlessly. https://en.wikipedia.org/wiki/Erlang_(programming_language) https://en.wikipedia.org/wiki/Erlang_(programming_language)

klibertp 9y ago
It doesn't happen automatically on BEAM - you still need to explicitly spawn your processes.

cormacrelf 9y ago

Edit: Apache Spark. See below. Some do. But more importantly, if your runtime doesn't, then it's still more obvious how to add parallelism, and more self-contained when you do. Let's say you were using asynchronous IO in a functional style; not even full-on monads, just async/await like in C#. Since you have explicit data dependencies, you can easily see where the `await` is unnecessary, or coalesce multiple calls into await Task.WhenAll(...). var slow = await conn.Query(@"slow query"); var fast = await conn.Query(@"select top 1 * from some_table"); var emailresult = await SendEmail(fast); return (slow, emailresult); Instead of awaiting `slow` before continuing with `fast`, it's fairly obvious that you could start the task and not await it until the others have already kicked off: var slowTask = conn.Query(@"slow query"); var fast = await conn.Query(@"select top 1 * from some_table"); var emailresult = await SendEmail(fast); return (await slowTask, emailresult); That way, your email sends almost immediately, since line 1 never relinquishes control flow and just continues straight on. Then your `await slowTask` only blocks the return, instead of the entire function. This is pretty big if you're lining up a hundred slow IO tasks. Note: while async IO gives you the actual parallelism, it's only because of the explicit dependencies that we are able to see which parts can be done simultaneously. I've been coding like this for so long I can barely imagine how to do it imperatively, but if you exposed an interface like `async Task GetSlowQueryResults()` and `async Task SendEmail()` using internal fields for intermediate results, it's utterly opaque and you can't tell which has to complete first. Edit to respond better to your actual question: There's a kinda big problem with auto-parallelizing, which is that in FP, outside of IO, everything is parallelizable. Spinning up threads or even shuffling data within a thread pool is pretty costly, so most attempts at micro-parallelizing everything haven't gone anywhere. You can annotate things in Haskell to run in parallel, or simply choose a parallel map or parallel reduce instead of a sequential one. On the other hand, when spinning up threads/processes/jobs is relatively inexpensive compared with the cost of actually computing things, the idea is very successful. Take Apache Spark. You write a program in functional Scala or Python, and the scheduler will automatically distribute work over your cluster if it's big enough to warrant it. The scheduler also makes note of where intermediate results are, and will happily cache, reuse, shuffle or partition them around to continue on with the work. The engine essentially evaluates a DAG, with some optimizations for transport/persistence costs.

iainmerrick 9y ago

AFAIK this is still an active area of research. In principle pure functional programs can be freely parallelized, but in practice it's hard to do it completely automatically without losing more in overheads than you gain through parallelism. In Haskell I think the standard approach is still to annotate your code, indicating which parts should be evaluated in parallel. See https://wiki.haskell.org/Parallelism https://wiki.haskell.org/Parallelism

jandrese 9y ago
Even if all of your functions are pure they can still have data dependence with one another. So you obviously can't parallelize foo(bar()) automatically. There are other things that can make a real mess of paraellizability too, like error checking. Say you have some code like: comprehend all item in list, verify(item) or errorout("failed at ", stringify(name(item))) The compiler can't auto parallelize it because the exit condition is unknowable, at least if you want there to only be a single exit from the function. You can get around this with even more strict requirements, but after enough of these restrictions even simple tasks start to get hard.

imtringued 9y ago

No. The reason? In the nano second to 1 microsecond range your CPU already automatically parallelises your code by using out of order execution. Unless you're wastefully busy waiting, the latency of issuing a new job to a second thread is in the 10s of microseconds. You can't just issue new job without first knowing how much time the job is going to take and whether it's even worth it to parallelise it. Profiling every line of code at runtime will introduce even more overhead. It's far simpler to just let the developer annotate the parts of the codebase that should run in parallel. Example: r=a/b + c*d can in theory be parallelised but you'd have to pay 10 microseconds in overhead which is likely more than 5000 times slower than just running it on a single core. TL;DR automatically parallelising a program is trivial, making a parallelised program run faster than a non parallelised program is not