Hacker News new | ask | show | jobs
by beeforpork 1905 days ago
Julia is such a wonderful language. There are many design decisions that I like, but most importantly to me, its ingenious idea of combining multiple dispatch with JIT compilation still leaves me in awe. It is such an elegant solution to achieving efficient multiple dispatch.

Thanks to everyone who is working on this language!

3 comments

Julia is the first language to really show that multiple dispatch can be efficient in performance-critical code, but I'm not really sure why: JIT concepts were certainly familiar to implementors of Common Lisp and Dylan.
I guess the reason is that Julia's type system and standard libraries really guide users to use types that the JIT can unbox as far as possible.
What does it mean exactly? Or what is novel here?
The combination. E.g multiple dispatch without JIT would be really slow as you are picking a method to run at runtime based on the type of all the function arguments.

That requires a linear search through a list of all possible combinations of input arguments.

In a single dispatch language like most object oriented languages, you can do a simple dictionary/hash table lookup. Much faster.

With the JIT Julia is able the optimize away most of these super slow lookups at runtime. Hence you get multiple dispatch for all functions but with fantastic performance. Nobody had done that before.

FWIW, Julia does segment its method tables into multiple layers depending upon size and type. Multiple dispatch is a strict superset of single-dispatch, and indeed the first layer is just a dictionary/hash table lookup on the first argument. If there's only one result there, you're done (and have the same ~cost for the same ~complexity).
Thanks, I didn't know that! Has it always been like that? I wondering where I got the idea that it was always a linear search from? Maybe that is just the conceptual way of explaining it.
This video is good explaining the idea behind multiple dispatch in Julia if you have time:

https://www.youtube.com/watch?v=kc9HwsxE1OY

It's like C++ template specialisation, but it happens when the compiler realises you need a particular version. Which may be at runtime, if you changed something.
Except the language can choose from suitable templates (eg instead of a generic matrix multiply template for floats, it can use a library like LAPACK) and does so in a systematic way.

It also has a feature (I can’t recall the name) which is a bit like fexprs (let’s say macros who’s inputs are the types of the arguments of a function) that can generate customised code (eg an FFT depending on the input size) on the fly.

I believe you're thinking of https://docs.julialang.org/en/v1/manual/metaprogramming/#Gen...

(but I don't find it helpful to compare to fexprs, which I think of as more about deferring evaluation, whereas generated functions are about "staged programming".)

I advise you to check Common Lisp CLOS and Dylan.
What the OP is talking about is julia's method-based JIT strategy coupling very well to multiple dispatch.

JIT is not new, multiple dispatch is not new, and multiple dispatch + JIT also isn't new, but nmo existing langauges combined them in a way that allows for the fantastic, efficient devirtualization of generic methods that julia is so good at.

This is why things like addition and multiplication are not generic functions in Common Lisp, it's too slow in CL because the CLOS is not able to efficiently devirtualize the dispatch. In julia, everything is a generic function, and we use this fact to great effect.

CLOS and Dylan laid a ton of important groundwork for these developments, but they're also not the same.

It’s not true that CLOS generic dispatch is slow: Robert Strandh and other have done a bunch of work showing that it’s possible to implement it efficiently without giving up the dynamic redefinition features that make CLOS such a nice system. There’s at least one video game project (Kandria) that’s been funding an implementation of these ideas so that generic functions can be used in a soft real-time system like a video game.

The really nice thing about CLOS, though, is that the meta-object protocol lets you choose an implementation of OOP that makes sense for your use-case.

Yes, I don't doubt at all that it's possible to make CLOS dispatch fast. What I'm saying is that because historically people using CLOS had to pay a (often negligible) runtime cost for dispatch, it limited the number of places developers were willing to allow generic dispatch.

Julia makes the runtime cost of (type stable) dispatch zero, and hence does not even give julia programmers an *option* to write non-generic functions (though it can be hacked in like with FunctionWrappers.jl). I'm not familiar with Strandh's work, but has it made the overhead of generic functions low, or has it completely eliminated it?

Another thing I'll mention is that Julia's type system is parametric, and we allow values (not just types) in our type parameters which is immensely useful for writing generic high performance code. You can specialize methods on matrices of complex integers separately from rank 5 arrays of rational Int8s for instance. This is not a capability that CLOS or Dylan has as far as I'm aware, though the common refrain is that you can do it with macros, but that neglects that it's rather hard to get right, and will have limited use because such macro implementations of type parameters won't be ubiquitious.

________________________________

To be clear though, I'm not hating on Common Lisp or CLOS. The Common Lisp ecosystem is awesome and can do all sorts of really cool things that I wish we had in julia. I'm mostly just pushing back on the notion that Julia doesn't do anything new or interesting.

In this context, I think there might be an argument to be made that Julia is to multiple dispatch (or multiple dispatch + JAOT) as the iPhone is to “touchscreen computers that can make phone calls”.

It’s not that it’s the first, but it seems to be the first where the use of multiple dispatch throughout the community was sufficiently pervasive to kick-start the emergence of the strong network effects we’re now seeing w/r/t composability.

I would not be surprised to see more languages working to emulate this kind of combination of multiple dispatch and JAOT compilation in the future.

Except everyone is forgetting that I also mentioned Dylan, from Apple, and whose goal was to be a system programming language for the Newton OS, with the Dylan team winning over the C++ one, but internal politics made the decision to go with the outcome of the C++ team alongside NewtonScript.
Languages with multiple dispatch aren't rare, but a language having it as the core language paradigm, combined with a compiler capable of completely resolving the method calls during compile time, and therefore able to remove all runtime costs of the dispatch, and a community that fully embraced the idea of creating composable ecosystems is something unique to Julia. I don't think anyone has scaled multiple dispatch to the level of Julia's ecosystem before.
Depends, most use SBCL instead of paying for Allegro or LispWorks, so the perception is skewed.
Common lisp’s typesystem is just not really as useful for this sort of thing. In particular it doesn’t have parameter used types so you can’t make eg a matrix of complex numbers. This breaks (1) a lot of the opportunity for optimisation by inlining (because you can’t assume that all the multiplications in your matrix{float} multiplication are regular float multiplications) or generic code (because you can’t have a generic matrix type and need a special float-matrix); and (2) opportunities for saving memory with generic data structures because the types must be associated to the smallest units and not the container (eg every object in a float matrix must be tagged with the fact that it is a float because in theory you could put a complex number in there and then you’d need to know to do a different multiplication operation).

I guess you could try to hack together some kind of templating feature to make new type-specific classes on the fly, but this won’t work well with subtyping. Your template goes system could probably have (matrix float) as a subclass of matrix, but not of (matrix real) or (matrix number). I think you’d lose too much in Common Lisp’s hodge-podge type system.

A big innovation of Julia was figuring out how to make generic functions and multiple dispatch work in a good way with the kind of generic data structures you need for good performance. And this was not a trivial problem at all. Julia’s system let’s you write generic numeric matrix code while still having float matrix multiplication done by LAPACK, which seems desirable.

The other thing is that Julia is a language where generic functions are a low-level thing all over the standard library whereas Common Lisp has a mix of a few generic functions (er, documentation is one; there are more in cltl2), a few “pre-clos” generic functions like mathematical functions, sequence functions and to some extent some array functions, and a whole lot of non-generic functions.

Hence why I also referred Dylan, which was designed as a system programming language for the Newton.
Wikipedia has a nice table [1] on the Multiple Dispatch page, that describes one studies' findings about the use of multiple dispatch in languages supporting it, in practice.

Although CLOS and others do support it, Julia seems to take the cake by most metrics, highlighting that it is a core paradigm of the language, more so than in the others.

Even better check Stanza language for modern version and interpretation of Lisp, Scheme and Dylan. It supports multi-method/multiple dispatches, hybrid dynamic and static typing, high and low level programming to name a few productive features.

[1]http://lbstanza.org/