The discussion here might be relevant: A switch type function
If I have many cases, just say 20 cases,
it is a little difficult for me believe that if statements can be faster, because if I have to select the last case, I need to do like 19 if judges. Besides, the if else if else statements may be cumbersome somehow.
But if there is a select case thing in Julia, it can quickly jump to the last case without doing if statements.
Am I wrong or missing something?
Seems pretty quick:
julia> ex = :("last");
julia> for i in 50:-1:1
ex = :(x == $i ? $("value " * string(i)) : $ex)
end
julia> @eval f(x) = $ex
f (generic function with 1 method)
julia> @btime f(r[]) setup=(r=Ref(2))
1.166 ns (0 allocations: 0 bytes)
"value 2"
julia> @btime f(r[]) setup=(r=Ref(51))
1.166 ns (0 allocations: 0 bytes)
"last"
julia> ex
:(if x == 1
"value 1"
else
if x == 2
"value 2"
else
if x == 3
"value 3"
else
if x == 4
"value 4"
...
It’s quick but much more confusing.
@mcabbott isn’t saying that’s how you should write them, he’s just generating a very large set of if statements (by metaprogramming) which will perform exactly the same as handwritten ones, and then showing those are fast (and therefore handwritten ones are as well).
Perhaps using a Dict would be more convenient where the case is the key and the call is the value?
I believe the kind of pattern you show up top will be compiled to a switch and then jump table (via Julia and LLVM respectively), much like I assume a Fortran compiler could.
Edit: it doesn’t generate a jump table, but I wasn’t able to coax gfortran to create one either on Godbolt. If someone figures out how to, please let me know
Adapting that example:
step11(it) = print("step11", it)
step12(it) = print("step12", it)
function steps(it)
if it === 11
step11(it)
elseif it === 12
step12(it)
else
throw("illegal value $it")
end
return
end
@code_llvm steps(1)
clearly shows a jump table being constructed:
define void @julia_steps_214(i64 signext %0) #0 {
top:
%1 = alloca [2 x {}*], align 8
%gcframe3 = alloca [3 x {}*], align 16
%gcframe3.sub = getelementptr inbounds [3 x {}*], [3 x {}*]* %gcframe3, i64 0, i64 0
%.sub = getelementptr inbounds [2 x {}*], [2 x {}*]* %1, i64 0, i64 0
%2 = bitcast [3 x {}*]* %gcframe3 to i8*
call void @llvm.memset.p0i8.i32(i8* nonnull align 16 dereferenceable(24) %2, i8 0, i32 24, i1 false)
%thread_ptr = call i8* asm "movq %fs:0, $0", "=r"() #8
%ppgcstack_i8 = getelementptr i8, i8* %thread_ptr, i64 -8
%ppgcstack = bitcast i8* %ppgcstack_i8 to {}****
%pgcstack = load {}***, {}**** %ppgcstack, align 8
; @ REPL[3]:2 within `steps`
%3 = bitcast [3 x {}*]* %gcframe3 to i64*
store i64 4, i64* %3, align 16
%4 = getelementptr inbounds [3 x {}*], [3 x {}*]* %gcframe3, i64 0, i64 1
%5 = bitcast {}** %4 to {}***
%6 = load {}**, {}*** %pgcstack, align 8
store {}** %6, {}*** %5, align 8
%7 = bitcast {}*** %pgcstack to {}***
store {}** %gcframe3.sub, {}*** %7, align 8
switch i64 %0, label %L11 [
i64 11, label %L3
i64 12, label %L8
]
L3: ; preds = %top
; @ REPL[3]:3 within `steps`
; ┌ @ REPL[1]:1 within `step11`
call void @j_print_216({}* inttoptr (i64 140108222856496 to {}*), i64 signext 11) #0
; └
br label %L14
L8: ; preds = %top
; @ REPL[3]:5 within `steps`
; ┌ @ REPL[2]:1 within `step12`
call void @j_print_217({}* inttoptr (i64 140108217624080 to {}*), i64 signext 12) #0
; └
br label %L14
L11: ; preds = %top
; @ REPL[3]:7 within `steps`
%8 = call nonnull {}* @jl_box_int64(i64 signext %0)
%9 = getelementptr inbounds [3 x {}*], [3 x {}*]* %gcframe3, i64 0, i64 2
store {}* %8, {}** %9, align 16
store {}* inttoptr (i64 140108212808048 to {}*), {}** %.sub, align 8
%10 = getelementptr inbounds [2 x {}*], [2 x {}*]* %1, i64 0, i64 1
store {}* %8, {}** %10, align 8
%11 = call nonnull {}* @jl_apply_generic({}* inttoptr (i64 140108035749248 to {}*), {}** nonnull %.sub, i32 2)
call void @jl_throw({}* %11)
unreachable
L14: ; preds = %L8, %L3
%12 = load {}*, {}** %4, align 8
%13 = bitcast {}*** %pgcstack to {}**
store {}* %12, {}** %13, align 8
; @ REPL[3]:9 within `steps`
ret void
}
See Computed goto (or labels as values) in Julia? for more.
For a terser way of switching on values, have a look into https://github.com/thautwarm/MLStyle.jl:
using MLStyle
...
function steps_match(it)
@match it begin
11 => step11(it)
12 => step12(it)
_ => throw("illegal value $it")
end
return
end
I’ve verified that this also generates a switch at the LLVM level.
Thanks!
This looks like a solid answer, although I am not very clear what does the script you displayed mean. But I believe Julia should be smart enough to do jumping instead of doing a lot of unnecessary if judgements.
Just curious, why use ‘===’ in things like
if it === 11
why not just use “==” ?
Perhaps to ensure it’s an integer. 12 === 12.0
evaluates as false. (If you want info on the operator use ?===
in the REPL).
Thank you! You are absolutely right.
When writing patterns matching things, I sometimes use a macro like this:
function mkcond(cond)
if isexpr(cond, :call) && cond.args[1] == :(|)
return Expr(:(||),
mkcond(cond.args[2]),
mkcond(cond.args[3]))
else
return :(cond == $(esc(cond)))
end
end
macro case(cond, cases)
block = ret = Expr(:block, Expr(:(=), :cond, esc(cond)))
done = false
first = true
for case in cases.args
isa(case, LineNumberNode) && continue
isa(case, Expr) || error("Expected Expr, got $(typeof(case))a")
done && error("Extra statements after catchall")
if isexpr(case, :call) && case.args[1] == :(=>)
casecond = case.args[2]
casestmt = case.args[3]
if casecond == :(_)
push!(block.args, esc(casestmt))
done = true
continue
end
stmt = Expr(first ? :if : :elseif,
mkcond(casecond),
esc(casestmt))
push!(block.args, stmt)
block = stmt
first = false
else
error("Unknown stmt kind $(case)")
end
end
ret
end
Usage:
julia> function steps(it)
@case imode begin
11 => step11(it)
12 => step12(it)
(13 | 14) => whatever()
_ => error("Illegal imode value")
end
end
You can make the match syntax do whatever you want. Probably a good candidate for somebody to make a macro that defines a more extensive set of match syntaxes for various common situations.
There are also packages providing tuple-backed dictionaries. They are close to switch or if performance, but are more composable/reusable.
See Dictionaries.jl and OrderedCollections.jl.
What I frequently do is something like:
function steps(imode, it)
step(Val(imode), it)
end
function step(::Val{11}, it)
# The subroutine step11 from Fortran
end
function step(::Val{12}, it)
# The subroutine step12 from Fortran
end
function step(::Val{M}, it) where {M}
# Without this function, we'd get a MethodError instead
# (which might be just as useful).
error("Illegal imode value: ", M)
end
It might be slightly slower (about a microsecond) compared to an if
statement, but I find the syntax much nicer. It also makes it possible to support additional cases from external code.
@ToucheSir, regarding the LLVM switch business, do you think it is faster to use the MLStyle
package instead of the simple & clean chained ternaries solution by @mbauman in this post? (which was also linked above)
My Fortran is a bit rusty so apologies if I missed something, but I would do something like
function steps(it, imode)
function _select(m)
m == 11 && return step11(it)
m == 12 && return step12(it)
error("Illegal imode value")
end
_select(imode)
end
ie move the case
logic to a function and just use return
.
or if you don’t want to type return
multiple times and your brain is indentation agnostic:
function steps(it, imode)
function _select(m)
return if m == 11
step11(it)
elseif m == 12
step12(it)
end
error("Illegal imode value")
end
_select(imode)
end
With @code_llvm
, I see that if..elseif..else
chains are compiled into LLVM switch statements, at least for the simple cases I checked. Will the latter eventually be compiled into a jump table?
I’ve read elsewhere that if the cases are sparsely distributed, e.g. 1, 100, 400, 800, 1000, then a C compiler will compile the switch statement into something like a binary search rather than a jump table.
Probably missing something, but why not doing the chained ternaries that seem to be damn fast?
function steps(imode, it)
imode == 11 ? step11(it) :
imode == 12 ? step12(it) :
error("Illegal imode value")
end
I purposefully didn’t use ternaries because the original Fortran example had cases with multiple statements. Sure you could use begin ... end
there, but it erases any cleanliness benefits.
I haven’t verified whether your snippet or any of the ones below generate a switch, but I don’t have to either! Anyone can easily check for one just by using @code_llvm
. To confirm an actual jump table is being generated (which, again, I could get neither the Julia compiler or GFortran to do), simply use @code_native
and check for this this kind of pattern.
I am fine with chained ternaries, was just suggesting another option.
Generally, a C-like switch
is a very special case of control flow that can be handled with generic constructs, and not offering specialized syntax may be the right call. There are multiple solutions, so it is up to personal preference to pick one.