6 ms·
I made something similar (temporal distribution rather than spatial) an it was 70x slower than javascript, how slow compared to JS is clio?
by dvh 6y ago
I made something similar (temporal distribution rather than spatial) an it was 70x slower than javascript, how slow compared to JS is clio?
- speedgoose 6y agoI wrote the fib example in plain JavaScript without async, just old recursively in a loop, and it ran twice as slow compared to Clio. It's not a very high quality benchmark, but the overhead doesn't seem bad on tiny examples.
- deleted 6y ago[deleted]
- SamBam 6y agoSince Clio compiles to JS, that speed up must be available in vanilla JS as well. Is it the use of web workers that makes that twice as fast?
- chrisseaton 6y agoClio has automatic parallelisation. JavaScript does not.
- mcherm 6y agoHow is generation of fibonacci numbers parallelized? I mean, I can think of some ways to do it but I have trouble believing that any compiler could generate them.
- chrisseaton 6y ago> How is generation of fibonacci numbers parallelized? 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!
- throwaway4good 6y agoReally? Can you expand on that? I have seen Fibonacci being the poster child of the usefulness of memoization and maybe tail recursion, but never parallelization.
- chrisseaton 6y ago> I have seen Fibonacci being the poster child of the usefulness of memoization and maybe tail recursion, but never parallelization. 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 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.
- johnday 6y agoThe reason `fib` is a useful benchmark here is not because `fib` is an inherently parallel problem, but because the functionality is obvious and it's easy to parallelise. Computing fib with memoisation from 1 will certainly be faster than (parallel) recursion without memoisation and data sharing.
- firebacon 6y agoInteresting to consider the total complexity of that approach though. 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) You can see, that if we run this in parallel, the value of fib(1) has to be calculated twice. As the tree of operation branches out, more and more duplicate calculations are required. A quick google suggests that the time complexity of the recursive approach is O(2^N).
- 6y ago
- wccrawford 6y agoSo far as I can tell, they typically "parallelize" it by not memoizing it. It looks like they actually calculate the whole thing recursively, twice. 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. https://stackoverflow.com/a/16464865/388173 https://stackoverflow.com/a/16464865/388173
- nonameiguess 6y agoGreat link and I like the mention of the fact there is actually an analytical formula for the Fibonacci number as well that allows computing it in constant time. Unfortunately, machine precision issues make it nearly impossible to accurately calculate anything large enough to be worth the speedup you get as there is no practical way to store enough of the digits in square root of 5, so you need a symbolic algebra implementation that can compute an exact answer and reduce it to a natural number.
- vlovich123 6y agoWhy symbolic algebra vs infinite precision floating point which is comparatively much cheaper computationally (& memory wise too?)?
- cepher 6y agoI know that a parallel prefix algorithm [1] can be used to calculate fib(n), since we can use repeated matrix multiplications (a formulation appropriate for a prefix sum algorithm). The computation time can be O(n/p + log p), where p is the number of processors. However, I’m not sure what other approaches there are. [1] https://en.m.wikipedia.org/wiki/Prefix_sum https://en.m.wikipedia.org/wiki/Prefix_sum
- capableweb 6y agoThis language compiles to JavaScript, so it's 0x slower than JavaScript. Comparing similarly named functions between Clio and vanilla JS obviously wouldn't be fair as the feature-set between the two are not equal.
- elwell 6y agoThe benchmark should be based on idiomatic code in both languages for a same (or similar) input -> output.
- capableweb 6y agoYou could do that but then your comparison is obviously biased and not very useful.
- kangalioo 6y agoArguing that two programming languages must be considered to have the same performance just because they compile down to the same technology, is flawed. Otherwise you couldn't make performance comparisons between C, Rust, Go, Haskell, Julia, because they all compile to assembly
- capableweb 6y agoI'm not saying you can't, I'm saying that since the code that eventually gets executed the same way just one layer down, it's not useful to JUST consider the performance. 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.
- spenczar5 6y agoOk, but I still want to know how much of a performance tax I am paying to know whether it’s the right tool for the job. If it’s a thousand times slower, maybe that overwhelms the benefits of extra features.