Clio: A functional, distributed programming language that compiles to JavaScript
github.com
github.com
I saw the await key word for parallel fib but would like a bit more information about what's actually happening to be parallel.
It's not a very high quality benchmark, but the overhead doesn't seem bad on tiny examples.
Is it the use of web workers that makes that twice as fast?
Not sure if you're joking or not? Fib is the classic first parallel benchmark, especially for functional languages. The two tasks in each step are embarrassingly parallel.
> I have trouble believing that any compiler could generate them
Hah! I'd say I'd have a hard time believing compilers can automatically parallelise anything else... because fib is usually the only thing they're shown being able to do!
That baffles me. I think I've hardly read a paper on parallel functional programming that doesn't start with fib.
Here's example that agrees that it's the hello-world of parallelisation.
https://wiki.haskell.org/Haskell_for_multicores
It's trivial for a compiler to automatically parallelise it - for every binary operator evaluate the two operands in parallel - done.
Computing fib with memoisation from 1 will certainly be faster than (parallel) recursion without memoisation and data sharing.
An iterative fibonacci solution runs in linear time. Calculating the N'th fibonacci number requires O(N) serial operations.
A fully parallel, recursive solution without memoization requires that each value in the sequence is computed more than once. Consider the example of fib(4):
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
A quick google suggests that the time complexity of the recursive approach is O(2^N).
Absolutely nobody is under the impression that the naive parallel implementation of fib is actually useful code or the most efficient way to do it. You're missing the point if you're suggesting a different way to do it in the first place.
It's just something to use as a running example... like on the original article this whole thread is about.
I think maybe if there hadn't been such a vibe of "what, you don't know X?!?" then it would have just been an interesting fact to mention that parallelization demos often use fib, because it's an easy example to grok (though a confusing one if you already understand the faster method).
Fibonacci computations depend upon prior results, which is why it is a poor fit for parallelization in general. While, yes, it is possible to fork on every recurrence and join to wait for the result, the overhead of that is gigantic and dwarfs any benefits.
Just take a look at the code we’re talking about yourself. See the operator a + b between the two recursions? There are zero data or control dependencies between a and b. They can be perfectly distributed, which is why it’s been used as an example here.
Also read the note directed at the 'algorithms police' here https://cilk.mit.edu/programming/ which I think will pre-empt the point you're going to make next.
It starts two tasks, fib(4) and fib(3). It waits for them to complete. There are now 3 tasks, but 2 are running.
fib(4) starts two tasks, fib(3) (second edition) and fib(2). It waits for them to complete. There are now 5 tasks (fib(5), fib(4), fib(3), fib(3), and fib(2)), and 3 are running (fib(3), fib(3), and fib(2)).
fib(3) (the first one) starts two tasks, fib(2) and fib(1). It waits for them to complete. 7 tasks, 4 are running.
fib(3) (the other one) starts fib(2) and fib(1). It waits for them to complete. 9 tasks, 5 are running.
We keep going like this. Notice how many tasks are not running at any given time because they depend upon other tasks to complete. This is nowhere near an embarrassingly parallel problem.
For an actual embarrassingly parallel problem, consider something like "this 1GB slice of memory contains a continuous sequence of 64-bit floating point numbers. Please square each number in place."
This can be divided among any number of processes trivially, with actually zero coordination.
There's also "nearly embarassingly parallel," where a minor amount of coordination is required in a final step. You can parallelize "compute the max of an array of integers", for example, by splitting it into N chunks, having each one compute their own max, and then taking the max of the maxes.
But Fibonacci is nowhere close to those.
That said, I found a parallel solution that was interesting and should provide a speedup, but with a large increase in complexity of the code.
Otherwise you couldn't make performance comparisons between C, Rust, Go, Haskell, Julia, because they all compile to assembly
You're not using TypeScript to get faster JS execution. You're using TypeScript to get types in JS. Compare development speed and avoiding bugs together with performance in that case. Same for Clio.
[0]: https://clio-playground-pouyae.vercel.app/ with code:
fn fib n:
if n < 2: n
else: [n-1 n-2]
-> * await |fib|
-> *
console.log
sum
fn sum arr:
arr.reduce add 0
fn add a b:
a + b
export fn main args:
[5 6]
-> * await |fib|
-> * item: console.log itemA distributed programming language in this context means that the programming facilitates this paradigm so it's easy to do distributed programming with the language. In the case of Clio, it also means it is distributed by default, so you write code like normal and it's executed in a distributed fashion.
That being said, at first glance it doesn't look like Clio is using this, instead it's passing messages as you suggest. It might actually be interesting to use SharedArrayBuffers as a compilation target, as they're probably hard to use correctly manually. That being said, WebAssembly threads (https://github.com/WebAssembly/threads) may be more appropriate for this.
For completeness, Workers can also transfer memory (https://developer.mozilla.org/en-US/docs/Web/API/Transferabl...) with less security restrictions. They can also collaborate by accessing a shared database (https://developer.mozilla.org/en-US/docs/Web/API/IndexedDB_A...) though this is obviously slower than shared memory.
How's that possible? JS does not have a good reputation in sci prog, why would clio have?
There is plenty of ways of making JS handle any "scientific programming" you can throw at it. It'll probably run slower than what you can do by default in python-land or Julia, but since Clio seems to automatically parallize your code, it might have a chance.
What can be claimed though is that any general purpose programming language "can be made to" handle scientific programming. I'm not saying you should, but it's possible for sure.
Libraries like big.js for example make arbitrary-precision decimal arithmetic possible on JS, which many considered impossible to do in JS.
for example keras is a wrapper for tensorflow (c++). numpy relies on c if i understand this correctly.
The same is true of JS though, and most interpreted languages that have an escape hatch for FFI. The difficulty of getting it to work may vary.
My guess is it's enormous, but I could be wrong since contemporary JS engines do quite well with numeric computing.
But there's a wealth of scientific computing that can't be magically made to be parallel and the parallel equivalents are often slower due to duplicated arithmetic and overhead in setting up the computation (recursive computations are particularly bad about this) - finding a parallel evaluation strategy that is actually faster is nontrivial.
It's really not a safe assumption that parallel = faster.
As far as I can see, the arrow signifies function application. Why do you consider “a -> f” more intuitive than, say, “f(a)” or “f a”?
It is the pipe operator (F#, Elixir, Haxe, etc.). There is a proposal to add it to js too.
fun: x => x * 2
res: 4 -> fun
const R = require('ramda');
R.pipe(a,f,g,h)
That does it - I'm creating my own programming language (again) which is going to be a mashup of C++ and Lisp; I shall call it "Thee-Pluth-Pluth".