This is a repost of a rather old blog entry. John Myles White has subsequently become one of Julia's most prolific core developers, having created and contributed a variety of very high quality stats and machine learning packages for (and in) Julia:
The moral of the story might be that John puts his money where is mouth is. He thought Julia was awesome and now he's done a huge amount to make it even more so.
Actually being fast is not the point; naive fib is used because it's a very well known algorithm, easy to implement consistently across multiple languages, that heavily exercises both function calls and numeric addition.
In other words, as much as a 10-line program can be, it's a reasonable proxy for a language's performance on algorithmic code.
Also, it's a reasonable low bar to begin with for a college-educated programmer (not that all programmers need to be college-educated), because the Fibonacci sequence in mathematics (and in everyday language) is commonly defined in its recursive form, so it's likely that people will be familiar with it.
That kind of thing does happen when the stakes get high enough. There are a lot of rumors (and some evidence) of special-cased "cheating" on commonly used benchmarks, including the 3dMark GPU benchmarks, SPEC CPU benchmarks, even SunSpider JS benchmarks.
Both Nvidia and ATI have been caught cheating at graphics benchmarks. Their drivers would detect when the benchmark programs were being run, and go through lower quality fast paths. You can google "quack.exe" for details on one particularly famous case.
It tests how well the compiler deals with function calls, and that's it. Useless for measuring a language's overall speed (as are all micro-benchmarks).
Fibonacci is O(log n) or so in the best case, not quite O(1). Of course you can do a simple table lookup if you're limiting yourself to 32 or 64-bit numbers, but you can go far beyond that.
There's a formula from analysis that gives you the Nth Fibonacci number in closed form. It involves a couple of exponentials, which you can compute to a given accuracy in bounded time.
You obviously haven't tried doing this or you wouldn't suggest this as a way to actually compute Fibonacci numbers. Here's a definition in Julia (hey, why not) of a closed form Fibonnaci function:
Oops. Those aren't integers. I guess we could round, but at some point we might be rounding to the wrong integer. In fact, once you get up to 63, this happens and worse still, at 64 you get an infinite answer.
Here's a simple, reasonably efficient iterative Fibonacci function in Julia:
function ifib(n)
j, k = 1, 1
for l = 3:n
j, k = k, j+k
end
return k
end
We know this one works up to the limits of Int64 range:
julia> for n = 1:10
println(fib(n))
end
1
1
2
3
5
8
13
21
34
55
Using a doubly recursive algorithm for Fibonacci is indeed silly, but it's a good toy test of recursion performance.
But, although it gives close answers up to cfib(604) (after which it throws an exception) it still gives slightly inexact answers starting at 308061521170129 (cfib(71)), which is between 2⁴⁸ and 2⁴⁹. I'd expect it to make it a few items further before going astray, since it's presumably doing floating-point calculations with 53 bits of mantissa that are supposed to be rounded to less than half an ulp.
For exact answers, you clearly can't do better than O(N) (where N is the magnitude of the input parameter, not its length in bits) because the output is of size O(N). But for approximate answers, you can.
I agree about the uses for doubly recursive Fibonacci!
Unfortunately, this approximate value is off by 1066512995643 (~1 trillion), so it's hard to see how it would be useful. Actually, it's hard to think of good uses for computing Fibonacci numbers in general :-)
No need for a table lookup. There is a closed form formula. Of course this is only as accurate as your float precision. You can get out pretty far, though, with some clever rounding.
I can understand the need for new programming languages to be continually developed, especially with differing power continuums. So I have nothing against this post, or Julia itself.
But when someone advertises that they want x feature and y feature in one language, such that the respective languages of x and y are essentially obsolete, I get a little skeptical. I'm certainly not the type of person who tries to vaguely advocate all languages are more or less the same and it's just taste; not at all.
But I think there are reasons why it's intrinsically difficult to design a language to have both the speed of C and the abstraction power of Lisp, for example. Things come at a price; this doesn't mean there isn't generally a clear victor for what you're trying to do, just that getting a paragon of linguistic design is very difficult.
But his test of Julia is promising, though honestly I'd really like to see a speed comparison on at least 100 lines of code, preferably a full application really.
It is hard ... OpenDylan (http://opendylan.org/) manages to mostly pull it off when the right type information is available. It could be smarter at times, but it does pretty well.
In a recent test for someone, they had code running in C++ in 0.5 seconds, Dylan in 0.6.
Our major performance loss in OpenDylan comes when there's still too much generic dispatch going on, but that can usually be reduced through various mechanisms. (And as I said above, there's still avenues where the compiler could do better.)
Another interesting implementation is Gambit Scheme which manages to pull off some really impressive feats of compilation for performance once you declare '(not safe)' although it is still fast with safety enabled.
* Dylan was designed at Apple and then later a partnership of Apple, CMU and Harlequin in the 1990s
* Harlequin's implementation of Dylan was spun off to another company when they failed. It was then called Functional Developer.
* Functional Developer was open sourced in 2004 as Open Dylan.
Since then, the development was moving rather slowly, the documentation was still in the 1996-era Framemaker documents, etc.
I decided to help really revive it and we've since done the 2011.1 and 2012.1 releases and are working on the 2013.1 release now. The documentation has been brought forward into the modern era, the website updated, new libraries are being written, etc. I've spent a large amount of time over the past 15 months or so to make a lot of that happen.
As for strengths:
* A pretty great compiler that can do a lot of optimizations.
* Multiple dispatch. As StefanKarpinski says in another comment, it is a great thing.
* A condition system like Common Lisp.
* Everything is an object, so multiple dispatch integrates very cleanly.
* I like the macro system. It is more like syntax-case than full macros, but I find it pretty useful.
* Everything is pretty clean and consistent. There aren't a lot of strange edge cases and the code is really pretty readable.
* The compilation model lets a lot of existing tools work with the compiled code. I'm able to use Instruments on OS X, perf on Linux, etc to analyze performance and so on.
* We have a lot of documentation as a result of having formerly been an expensive commercial product.
Weaknesses:
* Small community.
* Some things are still written with 1990s expectations and need some love, like atomic operations and some aspects of the numerical model.
* Some other nits that would get ironed out pretty quickly with a larger community.
* Marketing hangover from the 1990s in terms of people thinking Dylan is old, dead, etc. We've contemplated just changing the name on a future release to make it more clear that we're moving forward.
As for Lisps ... SBCL and Clozure CL are great implementations. :)
With under a week of work, we could probably be up and running on iOS with Open Dylan. I even have the start of some aspects of a Dylan / Objective-C bridge, but that needs a fair bit more work. Talk to us if you're interested.
I should also point out that I completely agree that is intrinsically difficult to design a language to have both the speed of C and the abstraction power of Lisp. That is part of why the job that Jeff Bezanson, who is largely responsible for Julia's amazing performance, has done is so incredible.
It's hard to explain until you start using it, but ubiquitous, fast, expressive multiple dispatch is a truly amazing programming paradigm. I'm not entirely sure how it hasn't been adopted as the core paradigm of any mainstream language in the past.
Not at all. I've done a lot of C, Matlab, Perl, Ruby and R, although I've also dabbled in Java, JavaScript, C++, Scala and Python. Definitely a polyglot of "pragmatic" languages. Julia was influenced most strongly by Lisp (Scheme in particular), Matlab, C, Python, Ruby and Perl. If you (or anyone else reading this) have questions looking through the manual, drop an email to the julia-users@googlegroups.com list, or me personally.
I have just started going through the docs a bit. I am interested in 2 things. One, programs that interface with other commands -- essentially rewriting large shell programs in a "better" language. I saw the section on "external commands" and that looks very promising. Are there any other links or sample programs I can check out. Would Julia be just as good as say Ruby in this respect ?
Is there a readline interface ?
Second, I haven't yet come across an ncurses interface yet.
Thanks.
edit: Just came across your article "Shelling out sucks".
| In my followup post, I will describe how Julia makes constructing and executing pipelines of external commands as safe as Python’s subprocess and as convenient as shelling out.
I could not find a link to the followup. Do you have something ?
Miles Lubin and Iain Dunning gave an excellent presentation at MIT's IAP tutorial on Julia in January where they benchmarked rather non-trival code for doing linear programming in a variety of languages:
https://github.com/JuliaLang/julia-tutorial/blob/master/NumericalOptimization/presentation.pdf
http://bit.ly/VQ9rDd (shortened version since that's cut off)
See page 7, "Simplex Benchmarks". Essentially, they implemented the basics you need to do a fast simplex linear programming algorithm in each of C++, Julia, Matlab and Python. Their results were in line with the Julia home page benchmarks:
Julia is between 1-2x slower than good C/C++ code.
PyPy and Matlab are 10-20x slower.
Python is 80-400x slower.
Am I the only one with hopes of Julia actually evolving into a general purpose programming language?
With almost C++ level performance and homoiconicity it seems really sweet and I'd love to see it used instead of Go. Though 1-indexed arrays are definitely annoying as fuck...
baremodule MyWay
ref(x::AbstractArray, i::Int) = Base.ref(x,i+1)
ref(args...) = Base.ref(args...)
end
is not that far away (I'm oversimplifying a little, but not much).
However, please don't do this as it breaks coherence within the community. I found 1-based indexes annoying at first, but have grown quite fond of them since.
1-based arrays are one of the more lambasted traits of Lua (an otherwise supremely elegant language), and as a long-time C/C++ programmer, I personally find 0-based arrays very natural.
However what I've found from doing lots of Lua programming, is that I just don't notice very much in practice.
To some degree, at least, I guess this reflects that one writes different sorts of code in different programming languages. The sort of offset-based address calculations one might do a lot in C just don't seem to happen very much in Lua.
So while my natural inclination is to dislike 1-based arrays, I no longer consider them an automatic demerit....
"Mainly, Regex and Binary indexes are zero-based, List and Tuple are one-based."
I don't remember now but one of the collections in stdlib is zero-based too. It's much worse to be inconsistent than to choose 0 or 1-based indexes for everything.
Can anyone venture a guess on how successful this will be ? Given that R is pretty widespread right now, and Scipy/Numpy/Blaze is looking to win in the future (with the Darpa funding for Continuum[1]).
Wonder if Julia was considered for the Darpa grant.
Wow, the list of modules has gotten very respectable since the first time I heard about Julia.
I have one concern though: how well-tested are they? There's one really prominent contributor (John Myles White), who has written a rather large number of packages. But there are only a limited number of bug-free LOCs that a human can write in a given time-span.
So Julia might well be a better language than R, but is it standard library as reliable? And how much time will it take until it becomes as trusted as that of R?
Julia's benchmarks just turned me off. They are ignoring the "reasonable idioms" of each language, and specifically focusing only on RECURSIVE and ITERATIVE algos. And also ignoring other competing peers like lua based GSL Shell.
Please read
https://groups.google.com/forum/#!topic/julia-dev/2MJQ_uADH4...
> Julia's benchmarks just turned me off. They are ignoring the "reasonable idioms" of each language, specifically focusing only on RECURSIVE and ITERATIVE algos.
I read the benchmarks as an invitation to experiment (which I am) - not as a call to language war; if it doesn't float your boat, then that's cool (but you might want to check it out again in a year or two). Your concerns are specifically addressed on the front page in the benchmark discussion (http://julialang.org):
"These benchmarks, while not comprehensive, do test compiler performance on a range of common code patterns, such as function calls, string parsing, sorting, numerical loops, random number generation, and array operations. It is important to note that these benchmark implementations are not written for absolute maximal performance (the fastest code to compute fib(20) is the constant literal 6765). Rather, all of the benchmarks are written to test the performance of specific algorithms, expressed in a reasonable idiom in each language. ... The point of these benchmarks is to compare the performance of specific algorithms across language implementations, not to compare the fastest means of computing a result, which in most high-level languages relies on calling C code."
We all know C compilers make fast machine code, so it seems kind of silly to tediously write apple-oranges benchmarks in ways which will usually just end up benchmarking language X FFI anyway. Excepting BLAS stuff (as noted) pure Julia is within 2x of C, and that is really the take-home message of the benchmarks.
Here's why these small, hot-point benchmarks matter: the reasonable idiom in Julia is to rewrite slow algorithms in the same language. See this recent contribution for a great example of what is possible:
This combination of meta-programming expressiveness with speed in one language is really quite profound. Among other things, I think it will go a long way towards reducing the impedance-mismatch between "C core developers" and "end-user" communities in other technical computing environments (see NumPy,R).
Julia has a beautiful, small, and stunningly accessible language implementation in C (isolated C++ for LLVM stuff); and it is certainly pragmatic by using BLAS,FFTW, etc. where appropriate --- but the numerical core is defined in Julia itself, and - IMHO - that is a very fundamental shift for building an open-source computing environment and community.
(LuaJIT is a masterpiece and it would be cool to see it in the benchmarks, but there are many reasons why I personally have no interest in numerical work using Lua)
I don't think many projects with such a horrible() distribution system succeeded in the past.
()horrible for package maintainers. Try to create a package from this... There are no releases. I don't see any use of DESTDIR. And bundled libraries are also a major setback. It seems like the developers want to make it as hard as possible to distribute their software.
And I see more and more software going this direction. :(
https://github.com/johnmyleswhite/BloomFilters.jl https://github.com/johnmyleswhite/Calculus.jl https://github.com/johnmyleswhite/Clustering.jl https://github.com/HarlanH/DataFrames.jl https://github.com/johnmyleswhite/DimensionalityReduction.jl https://github.com/JuliaStats/Distributions.jl https://github.com/johnmyleswhite/FileFind.jl https://github.com/JuliaStats/GLM.jl https://github.com/johnmyleswhite/Graphs.jl https://github.com/johnmyleswhite/KLDivergence.jl https://github.com/JuliaStats/LM.jl https://github.com/johnmyleswhite/Languages.jl https://github.com/johnmyleswhite/Loss.jl https://github.com/doobwa/MCMC.jl https://github.com/johnmyleswhite/NHST.jl https://github.com/johnmyleswhite/Optim.jl https://github.com/johnmyleswhite/RDatasets.jl https://github.com/johnmyleswhite/Resampling.jl https://github.com/johnmyleswhite/TextAnalysis.jl https://github.com/johnmyleswhite/kNN.jl
The moral of the story might be that John puts his money where is mouth is. He thought Julia was awesome and now he's done a huge amount to make it even more so.