switch expression

[stevengj]

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 of if-else statements (or a Dict of functions).

I feel like I've mentioned this to @JeffBezanson, before, but can't find an issue for it.

[StefanKarpinski]

Yes, there doesn't seem to be an issue for this, but we should definitely have it.

[ivarne]

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.

[kmsquire]

Some early discussion, for reference:
https://groups.google.com/d/topic/julia-users/pnEqF5w4GJY/discussion

[stevengj]

Go's switch statement seems like a good model, though I would tend to allow only values rather than conditionals as cases (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).

[kmsquire]

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.

[stevengj]

@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.

[JeffBezanson]

LLVM is able to optimize a series of elseifs testing integers into a computed goto, so this feature is not that urgent.

[stevengj]

@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.

[MikeInnes]

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.

[cmcbride]

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]

[stevengj]

@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?

[simonster]

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)

[stevengj]

@simonster, nice! Weird that my first example doesn't emit a lookup table, though.

[stevengj]

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?

[reactivetype]

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.

[simonbyrne]

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?

[simonster]

It doesn't work for me anymore either. It looks like it did in Julia 0.2.1 but doesn't in 0.3.

[richardreeve]

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]

@richardreeve, do checkout the Switch.jl package.

[stevengj]

@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.

[richardreeve]

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.

[yuyichao]

Reply to #18285 (comment)

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.

[bpr]

Proposal

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.

Syntax

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

Examples

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.

[bpr]

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)?

[richardreeve]

@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.

[yuyichao]

Because of #18285

[richardreeve]

Ah, okay, I thought you'd closed that one instead.