How Julia Uses Multiple Dispatch to Beat Python
See for yourself
Julia
Julia is a new language. It’s simple to learn, and extremely fast. (Almost as fast as C.) Many people believe that Julia will become a dominant programming language, especially for machine learning and scientific computing.
There is a lot of hype about Julia. Beyond speed, Meta-programming and multiple dispatch are a few of Julia’s useful programming tools that make the language exciting.
But a word of caution. If you learn Julia and then program in other languages you will find yourself thinking: This would be so much simpler in Julia. This happens to me when I code in Python. I love Python, but for certain things, like the effectiveness of multiple dispatch, Julia gives Python a beatdown.
How Multiple Dispatch Beats Python
What is Multiple Dispatch
Multiple dispatch is a simple concept: Functions can have multiple definitions as long as each definition restricts the types of the arguments differently. It is perhaps one of the best features of the Julia language.
Surprisingly, it is not clear that Julia creators anticipated its usefulness. Years after Julia’s release, one of them gave a presentation called “The Unreasonable Effectiveness of Multiple Dispatch” [1]. (The talk presents how the Julia community used multiple dispatch with surprising results.)
To keep things simple going forward, my examples will technically be single dispatch to help readers make sense of the ways Julia leverages dispatch. Multiple dispatch is the same concept extended to multiple function arguments. Many languages have some form of dispatch but the things that make multiple dispatch great in Julia are that it is used everywhere, and that it is fast, so there’s no performance penalty for using it.
As a simple example of dispatch, consider the following:
function sort(x::Array{String, 1})
...
endfunction sort(x::Array{Int, 1})
...
endfunction sort(x::Array{Bool, 1})
...
end
The notation x::Array{String, 1} means that x is required to be a 1 dimensional array of strings. If each of these definitions had an implementation, it would leave us with a single function, sort, that we could call on arrays of strings, integers or bools and it would treat each case differently. (Integers might be sorted smallest to largest, strings might be sorted alphabetically and booleans might be returned with the false values first.) Which implementation to call is determined at runtime with a lookup table. This is how most functions work in the Julia base.
Slash Nested If-Statements
The hypothetical sort function above illustrates how sometimes developers need a function that acts slightly differently on different arguments. This method of defining functions eliminates the typical argument parsing if-statement tree.
To implement multi-type functionality without multiple dispatch, you would either need three different function names and an if-statement tree to decide which one to call, or you would need a single function with if-statements inside that determine which functionality to execute. Python packages usually go with the second option.
As a simplified example of this, consider the following: We need a function, f, to square its input and then compute its value mod 4. Assume speed is important.
In addition, assume that we always need f to output an integer, but its input, x, can be a String, Float64, or Int64, and we won’t know the type of x until runtime. In Python, this is solved with:
def f_py(x):
if type(x) == string:
x = float(x)
if type(x) == float:
x = ceil(x)
return x**2 % 4In Julia, we could write a function that looked like the Python function above:
function f_jl(x)
if isa(x, String)
x = parse(Float64, x)
end
if isa(x, Float64)
x = ceil(Int64,x)
end
return x^2 % 4
endHowever, we would be better off writing the following. We can even use Julia’s alternate function definition syntax to make it extra compact.
# Alternate function definition syntaxf(x::Int64) = x^2 % 4
f(x::Float64) = f(ceil(Int64, x))
f(x::String) = f(parse(Float64, x))
This collection of definitions does the same thing as the Python function f_py. However, the action of f on x depends on the type of x. Each of the definitions specifies what f will do with a particular type.
- If
fis passed anInt64, it will square it and mod by four. - If
fis passed aFloat64, it will compute the integer ceiling above the float and callfon that integer. This invokes the integer version offdescribed in 1. - If
fis passed aString, it will convert it to aFloat64, then callfon the float, which will invoke the float version off, described in 2. As we already saw, theFloat64version converts to anInt64, and calls theInt64version off.
I ran these functions on an array with 3 million elements of mixed types. This dispatched function finished in 0.039 seconds which was 50 times faster than f_py. Furthermore, the dispatched version is twice as fast as “Python-like” Julia. From this example we see how the dispatched version slashed if-statements and ran extremely fast.
To explain this speedup, Julia is fundamentally faster than Python, but in addition to this, dispatch is even faster here is because the correct version of f is determined at runtime (with the same speed as a lookup table), and this avoids millions of if-statement evaluations.
Knock Out Redundancy
Multiple dispatch on its own is fundamentally faster, but Julia doesn’t stop there. The Julia compiler is amazing with dispatch. When the compiler can infer the types of all variables, it translates dispatched functions into extremely efficient LLVM code, optimized for the each specific type. In fact, the Julia compiler will even remove lines of code for you.
To see how this works, consider the following Julia function definitions:
function bigger_floats(x::Real)
return tentimes(x)
endtentimes(x::AbstractFloat) = 10.0x
tentimes(x::Real) = false
The function bigger_floats accepts any type that is a subtype of Real (Int64, Float64, etc.). If the supplied argument is a subtype of AbstractFloat (Float64, Float32, etc.) it is multiplied by 10.0 and returned. If it isn’t a subtype of AbstractFloat it simply returns false.
When the compiler puts together a Float64 version of bigger_floats it will use optimizations designed exactly for Float64 computation to make bigger_floats extremely fast.
When using Julia, we can see the compiled LLVM code with the @code_llvm macro. (LLVM is a high level assembly language.) When the function bigger_float is called on a Float64 , the compiled version looks like this:
julia> @code_llvm bigger_floats(10.0); @ none:2 within `bigger_floats'
define double @julia_bigger_floats_17646(double) {
top:
; ┌ @ none:1 within `tentimes'
; │┌ @ float.jl:405 within `*'
%1 = fmul double %0, 1.000000e+01
; └└
ret double %1
}
LLVM looks a little strange, but you can get the gist of it. It is doing something within the tentimes function that uses the * operator like we would expect. The last line is ret double %1 which presumably means “return a variable”. Nothing too special here.
However when the function bigger_float is called on an Int64 , the compiled version looks like this:
julia> @code_llvm bigger_floats(1); @ none:2 within `bigger_floats'
define i8 @julia_bigger_floats_17645(i64) {
top:
ret i8 0
}
At first glance this is much shorter than the other definition. Furthermore, even though in pure Julia, the bigger_floats function calls the timesten function, the compiled code has no mention of the timesten function at all! All it does is return 0! The Julia compiler inferred that when bigger_floats is called on Int64 variables, the timesten function will just return true and so it eliminated the timesten function from the compiled version.
This means that when developers write unnecessary code into Julia, the compiler can eliminate parts of it! Amazing!
Thus, when Julia code is properly annotated with type information, the compiler can deduce the optimal construction of each function and produce a huge performance boost. This is a huge part of the reason that proper Julia runs like C.
Uppercut Development Time
There are a few ways that multiple dispatch speeds up development. In this article, we’ll consider the case where a programmer writes some code and realizes later that it needs to work for more kinds of input.
As an example, let’s imagine that a developer needs to count the number of lines of code in a file. In Python, you might write a function like this:
def countlines(fname):
fstream = open(fname)
num_lines = len(fstream.readlines())
fstream.close()
return num_linesWe can write Julia that looks almost exactly the same:
function countlines(fname::String)
fstream = open(fname)
num_lines = length(readlines(fstream))
close(fstream)
return num_lines
end(These two implementations are close to the same speed. I ran them on a large directory of files and the mean compute time was 8ms for Python and 5ms for Julia. Don’t forget that this Julia had no type annotations.)
Let’s assume that the developer uses this function in multiple places, and later it becomes clear that they need the function to operate on different kinds of input as well. In this case, they want the function to handle a single file, a list of files, and have the capacity to filter files by extension.
Because we assumed the countlines function is used in several places, it will be helpful if when the function is redefined it acts exactly the same way it used to act and also gains new functionality for other inputs. This way, the developer can avoid having to rewrite old code that was working before.
It is possible to rework old code by changing function names, but this has the possibility of introducing errors into the code. In a large complicated code base switching function names could be bad, especially if the code is collaborative.
If you don’t want to change function names in the code, the Python solution is usually to use *args and **kwargs. It might look something like this:
def countlines(*args):
if len(args) == 1:
files = args[0]
if isinstance(files, list):
return sum([filelines(f) for f in files])
if isinstance(files, str):
return filelines(files)
else:
raise Exception("Unsupported data format")
if len(args) == 2:
files, ext = args
if isinstance(files, list):
filtered = [f for f in files if f.endswith(ext)]
return sum([filelines(f) for f in filtered])
if isinstance(files, str):
if files.endswith(ext):
return filelines(files)
else:
return 0
else:
raise Exception("Unsupported data format")
else:
raise Exception("Unsupported data format")
def filelines(file):
fstream = open(fname)
num_lines = len(fstream.readlines())
fstream.close()
return num_linesThis is a common Python solution and it gets the job done. However, it is a little clunky—difficult to read, difficult to test, etc.
To be fair, Python has the potential to be much cleaner and faster than my scrappy Python above. An elegant example of this was contributed by :
def get_total_lines_of_all_files(*files, ext=""):
total_lines = [
get_total_lines_in_file(each_file)
for each_file in filter_files_by_extension(*files, file_extension=ext)
]
return sum(total_lines)
def filter_files_by_extension(*files, file_extension=""):
if file_extension:
return [
each_file
for each_file in files
if each_file.endswith(file_extension)
]
return files
def get_total_lines_in_file(file_name: str):
with open(file_name, 'r') as file_handler:
return len(file_handler.readlines())However, no matter how you approach the problem in Python, you end up with a new function, whose interaction with the existing codebase is untested. This requires extra work, especially when the code is more complex than the simple example here.
Extending functionality is much easier in Julia. The function definitions below have the exact same functionality as the previously defined Python function.
function countlines(fname::String)
fstream = open(fname)
num_lines = length(readlines(fstream))
close(fstream)
return num_lines
endfunction countlines(files::Array{String, 1})
return sum(map(countlines, files))
endfunction countlines(files::Array{String, 1}, ext::String)
filtered = filter(x->endswith(x, ext), files)
return countlines(filtered)
endfunction countlines(file::String, ext::String)
return endswith(file, ext) ? countlines(file) : 0
end
(Note: The bool ? statement1 : statement2 syntax means execute statement1 if bool is true and execute statement2 otherwise.)
Notice that the original definition of countlines is the same. This is the beauty of Julia. To extend functionality, you don’t touch your original definitions. You extend functionality and still be sure that the codebase will work before you updated countlines. In this case, you only need to test the new definitions. Also, in my opinion, the Julia version is easier to read.
It is easy to see that the multiple dispatch method is much nicer than redefining a function’s internals. This aspect of multiple dispatch is the one I miss most when I code in Python.
Conclusion
Multiple dispatch smashes Python. It leads to faster, more compact code that is easier to develop. It’s a clear victory for Julia. Before I get carried away praising Julia, it’s important to remember a few things. Julia is a great language, but it has issues too. Slow compile times, a lack of mature packages and slow adoption by programmers show how Julia is still years behind Python in maturity. Python is more than 25 years old, and it shows [2].
Still, it’s worth learning Julia. (But take the Julia hype with a grain of salt.) That said, if you are interested in learning Julia and you know Python, I wrote an article focused on helping Python programmers learn key Julia concepts. (One of the examples may look familiar *wink wink*.) Best of luck!
References
[1] S. Karpinski, The Unreasonable Effectiveness of Multiple Dispatch (2019), JuliaCon
[2] G. van Rossum, A Brief Timeline of Python (2009), The History of Python
