Closed stevengj closed 8 years ago
Yes, there doesn't seem to be an issue for this, but we should definitely have it.
How would switch work in Julia?
I think it would be a good start to reserve (or preferably deprecate) some keywords. Currently one can use switch
, case
, and fallthrough
as variable names. I am not sure about that fallthrough
like in go is useful enough to be included, but the always forgotten break;
in C is annoying.
Some early discussion, for reference: https://groups.google.com/d/topic/julia-users/pnEqF5w4GJY/discussion
Go's switch
statement seems like a good model, though I would tend to allow only values rather than conditionals as case
s (focusing on the application to computed goto
-like semantics rather than mere syntactic sugar for if-then-else), and to start with probably only values of the integer and string types that LLVM directly supports switching on (or values that can easily be converted to those types e.g. by reboxing).
I'll add shameless plug for the @match
macro in https://github.com/kmsquire/Match.jl, which creates relatively efficient switch-like code already (obviously using if
statements, not the LLVM intrinsic), and has a lot more features.
@match c begin
1 => "one"
2 => "two"
_ => "something else"
end
produces
quote # none, line 1:
begin # none, line 2:
if (c==1) # line 379:
"one"
else # /home/kmsquire/.julia/v0.3/Match/src/matchmacro.jl, line 381:
begin # line 3:
if (c==2) # line 379:
"two"
else # /home/kmsquire/.julia/v0.3/Match/src/matchmacro.jl, line 381:
begin # line 4:
"something else"
end
end
end
end
end
end
While the generated code is generally good, code generation itself can sometimes be slow, so I'd love to have support for something equivalent (and more feature full than the proposed switch
statement) in the parser/compiler.
@kmsquire, the match macro is great, and we should probably use =>
in any switch
syntax too, but as you say it is not a replacement for a computed-goto switch statement. However, the existence of the Match
package may free us from having to implement too much "fancy" functionality (pattern matching etc.) in the Julia switch
.
LLVM is able to optimize a series of elseifs testing integers into a computed goto, so this feature is not that urgent.
@JeffBezanson, is that supposed to happen with the version of LLVM we are using now? I don't see it... e.g.
function foo(x)
if x == 1
7
elseif x == 2
8
elseif x == 3
9
elseif x == 4
10
elseif x == 5
11
elseif x == 6
12
elseif x == 7
13
elseif x == 8
14
elseif x == 9
15
elseif x == 10
16
elseif x == 11
17
else
0
end
end
code_native(foo, (Int,))
just emits a long chain of comparisons on my machine.
I'll also add a shameless plug for the @switch
macro that now lives in Lazy.jl. It doesn't have any kind of pattern matching, but code generation may be faster, and it's pretty flexible nonetheless.
LLVM builtin speedup aside, it'd be great to have a first class @match
functionality (ala @kmsquire Match.jl).
[pao: code quoting of macro name]
@JeffBezanson, I can't find any evidence of this if-else optimization on Google. Can you give me a pointer to where it might be, and why we aren't seeing it?
This seems to be optimized to a lookup table:
function foo(x)
if x == 1
x * 7
elseif x == 2
x * 8
elseif x == 3
x * 9
elseif x == 4
x * 10
elseif x == 5
x * 11
elseif x == 6
x * 12
elseif x == 7
x * 13
elseif x == 8
x * 14
elseif x == 9
x * 15
elseif x == 10
x * 16
elseif x == 11
x * 17
else
x * 0
end
end
code_native(foo, (Int,))
(edit: also seems to work with y =
instead of x *
in the conditionals, although this should be equivalent to the original code)
@simonster, nice! Weird that my first example doesn't emit a lookup table, though.
The following example doesn't work:
function foo(x)
if x == 1
x * 7
elseif x == 2
x * 8
elseif x == 3
x * 9
elseif x == 4
x * 10
elseif x == 5
x * 11
elseif x == 16
x * 12
elseif x == 71
x * 13
elseif x == 8
x * 14
elseif x == 9
x * 15
elseif x == 10
x * 16
elseif x == 11
x * 17
else
x * 0
end
end
code_native(foo, (Int,))
Or maybe it's generating a combination of a lookup table and if-else chain?
Some built-in pattern matching features would be nice to have. @match is great but for interactive use on REPL, code generation is rather slow.
I just tried @simonster's above example on the current master (with both LLVM 3.3 and 3.5), and I get a chain of cmp
/jne
statements. Has something changed since?
It doesn't work for me anymore either. It looks like it did in Julia 0.2.1 but doesn't in 0.3.
I see this thread has been dormant for a while. Although certain chains of ifelse statements may once have been optimisable to computed gotos, they are nonetheless deeply inelegant and error-prone (and I understand they don't currently optimise correctly). The introduction of some kind of switch statement, whether based on Match.jl, Lazy.jl or some other mechanism, would improve code readability, thereby likely reduce inadvertent errors, and add a useful and commonly used tool into the language, as well as speeding up code if they used LLVM's built in computed goto functionality.
@quinnj, that package is just syntactic sugar for a bunch of if val == label
statements, and doesn't address the low-level issue of interfacing LLVM's computed-goto or switch instruction functionality.
Thanks for the suggestion, @quinnj - that's obviously a possibility. I guess my feeling is that if switch remained as several(!) add-in packages, it will never be optimised and continue instead to be translated into a series of ifelse statements as @stevengj points out.
Reply to https://github.com/JuliaLang/julia/issues/18285#issuecomment-243469083
Some of these are difficult to implement via macros.
I don't think so
often more concise than an elseif sequence
Can be handled with macro
can ensure there are no duplicates, or no overlapping ranges
Can also be handled with macro. Having a syntax doesn't help. Will likely have runtime overhead unless we restrict the condition to constant. And this behavior may not be wanted.
can ensure all cases are handled, in particular for enums
Can be hanled with macro.
can implicitly produce an error if a case isn't handled, without having to explicitly call throw
Can be handled with macro.
can be extended to handle types, not just integer-like values; type inference can be taught about this
Lowering to elseif
in a macro can trivially handle this. Type inference doesn't need to know anything special about it.
This is a Julep suggested by @StefanKarpinski during this julia-users group discussion. Originally posted at #18285, moved here at @yuyichao's suggestion
Julia lacks a C-style switch statement. This issue has come up before on various fora. Unsurprisingly, Julia also lacks pattern matching, a useful generalization of case and switch, which has been implemented as a macro for Julia.
This proposal is concerned with using switch statements over integral (isbits) types to exploit the ability of LLVM's switch instruction to provide a branch table implementation of switch, which is more performant than a sequence of if-else
conditionals. It should be amenable to supporting extended switch and pattern capabilities in the future; for that reason I'll suggest using adding the case
keyword to introduce the form. If it's desired that the statement only be used as a C style switch and that pattern matching be introduced separately, perhaps switch
is the better choice.
I'll skip the arguments in around whether to include such a feature at all; interested readers can review some of those arguments in the context of Python or Lua, as the arguments on both sides would be similar for Julia.
If we'd like to subsume this in a future pattern matching Julia extension, I suggest a syntax influenced by the Match.jl macro, replacing @match
with the keyword case
, and adding a new keyword of
to use instead of begin
. I chose of
because that's used in many other languages that use case
, and because Julia constructs like if/for/while
don't require a begin
for their end
.
case case_expr of
case0 => expr0
case1 => expr1
.
.
.
caseNMinusOne => exprNMinusOne
else => exprN
end
The optional else
at the end could be replaced by _
or even otherwise
or default
, at the cost of using more keywords.
Each case above could be preceded by an of
if that syntax is preferable. It strikes me as a little wordy but it's a syntax used in other languages and perhaps people find it more readable.
case case_expr
of case0 => expr0
of case1 => expr1
.
.
.
of caseNMinusOne => exprNMinusOne
else => exprN
end
n = rand(0:32)
function print_if_lt_3(n)
case n of
0 => println("zero")
1 => println("one")
2 => println("two")
else => println("too big")
end
end
Should be semantically equivalent to
n = rand(0:32)
function print_if_lt_3(n)
if n == 0
println("zero")
elseif n == 1
println("one")
elseif n == 2
println("two")
else
println("too big")
end
end
An example with enums
@enum Dir north northeast east southeast south southwest west northwest
function degree_of_dir(d)
case d of
north => 90
northeast => 45
east => 0
southeast => 315
south => 270
southwest => 225
west => 180
northwest => 135
end
end
The intent is that @enum
should work well with this case
statement, which means that the conversion to the enum's Int value should be implicit, as above.
Having done some experiments with clang++, I'm less convinced that there is a performance argument for the inclusion of a switch statement that maps to LLVM's switch. At least in C++ on OS-X , I'm not seeing better performance. I ran with -emit-llvm and confirmed (I'm not an LLVM IR expert, but I can fake my way through and I saw switch where I expected it) that switch was being generated, but I hardly saw any difference at all in a CPU bound (all compute was switching too) benchmark.
I still like switch and pattern matching, but the argument in theory for better performance of switch doesn't appear in practice. Anyone have benchmarks showing switch is O(1) vs O(n)?
@yuyichao I'm not quite sure why this was closed. While there may not be major performance enhancements (and as far as I'm aware, we're not sure about this), introducing a switch statement into core Julia still seems like a hugely desirable thing to do, as it is a very common pattern, and will reduce errors in coding multiple if-else statements.
Ah, okay, I thought you'd closed that one instead.
It would be nice to have a
switch
-like statement, exploiting LLVM's built-in switch instruction, since this can greatly enhance performance of look-up tables (which are not uncommon in inner loops), compared to chains ofif-else
statements (or aDict
of functions).I feel like I've mentioned this to @JeffBezanson, before, but can't find an issue for it.