Skip to content

introduce labeled continue syntax inside a switch expression #8220

Closed
Closed
introduce labeled continue syntax inside a switch expression#8220
Labels
acceptedThis proposal is planned.proposalThis issue suggests language modifications. If it also has the "accepted" label then it is planned.
Milestone
0.14.0

Description

@andrewrk
andrewrk
opened on Mar 12, 2021

Background

The goto keyword was removed in #630. This remains the right call because all the control flow in Zig can be expressed in a better way: continue to goto backwards, and break to goto forwards.

However, in C, there is another concept, called "computed goto". This is described in #5950 and briefly discussed in #2162. This concept is not currently possible in Zig. It is possible to model the desired semantics with existing control flow features quite simply, but it is not possible to obtain the desired machine code, even in optimized builds.

Problem Statement

For example (godbolt link):

const Inst = extern struct {
    tag: Tag,

    const Tag = extern enum {
        add,
        addwrap,
        alloc,
        alloc_mut,
        alloc_inferred,
        alloc_inferred_mut,
        anyframe_type,
        array_cat,
        array_mul,
        array_type,
        array_type_sentinel,
        indexable_ptr_len,
    };
};

export fn entry(inst_list_ptr: [*]const Inst, inst_list_len: usize, map: [*]u32) void {
    const inst_list = inst_list_ptr[0..inst_list_len];
    for (inst_list) |inst, i| {
        map[i] = switch (inst.tag) {
            .add => analyze_add(inst),
            .addwrap => analyze_addwrap(inst),
            .alloc => analyze_alloc(inst),
            .alloc_mut => analyze_alloc_mut(inst),
            .alloc_inferred => analyze_alloc_inferred(inst),
            .alloc_inferred_mut => analyze_alloc_inferred_mut(inst),
            .anyframe_type => analyze_anyframe_type(inst),
            .array_cat => analyze_array_cat(inst),
            .array_mul => analyze_array_mul(inst),
            .array_type => analyze_array_type(inst),
            .array_type_sentinel => analyze_array_type_sentinel(inst),
            .indexable_ptr_len => analyze_indexable_ptr_len(inst),
        };
    }
}

extern fn analyze_add(inst: Inst) u32;
extern fn analyze_addwrap(inst: Inst) u32;
extern fn analyze_alloc(inst: Inst) u32;
extern fn analyze_alloc_mut(inst: Inst) u32;
extern fn analyze_alloc_inferred(inst: Inst) u32;
extern fn analyze_alloc_inferred_mut(inst: Inst) u32;
extern fn analyze_anyframe_type(inst: Inst) u32;
extern fn analyze_array_cat(inst: Inst) u32;
extern fn analyze_array_mul(inst: Inst) u32;
extern fn analyze_array_type(inst: Inst) u32;
extern fn analyze_array_type_sentinel(inst: Inst) u32;
extern fn analyze_indexable_ptr_len(inst: Inst) u32;

In the generated machine code, each prong ends up jumping back to the loop condition, before getting re-dispatched to the next prong:

.LBB0_3:
        xor     edi, edi
        call    analyze_add
        jmp     .LBB0_15
.LBB0_4:
        mov     edi, 1
        call    analyze_addwrap
        jmp     .LBB0_15

The reason this machine code is not what we desire is described in this paper in the section "Direct Threading" and "The Context Problem":

Mispredicted branches pose a serious challenge to modern processors because they threaten to starve the processor of instructions. The problem is that before the destination of the branch is known the execution of the pipeline may run dry. To perform at full speed, modern CPUs need to keep their pipelines full by correctly predicting branch targets.

This problem is even worse for direct call threading and switch dispatch. For these techniques there is only one dispatch branch and so all dispatches share the same BTB entry. Direct call threading will mispredict all dispatches except when the same virtual instruction body is dispatched multiple times consecutively.

They explain it in a nice, intuitive way here:

Another perspective is that the destination of the indirect dispatch branch is unpredictable because its destination is not correlated with the hardware pc. Instead, its destination is correlated to the vPC. We refer to this lack of correlation between the hardware pc and vPC as the context problem. We choose the term context following its use in context sensitive inlining [#!Grove_Chambers_2002!#] because in both cases the context of shared code (in their case methods, in our case virtual instruction bodies) is important to consider.

So the problem statement here is that we want to be able to write zig code that outputs machine code that matches this Direct Threading pattern. In one sense, it is an optimization problem, since we can model the same semantics with other language constructs and other machine code. But in another sense, it is more fundamental than an optimization problem, because Zig is a language that wants to generate optimal machine code, meaning it is possible to write Zig code that generates machine code equivalent or better to what you could write by hand.

In short summary, we want to be able to express zig code where each switch prong jumps directly to the next prong, instead of all switch prongs sharing the same indirect jump, in order to benefit the branch predictor.

Research Dump

Can LLVM Do the Optimization?

In this example (godbolt link), I changed the loop to while(true) and manually inlined the continue expression into each switch prong, with a continue. It does not get much simpler than this; we are practically begging LLVM to do the optimization.

const Inst = extern struct {
    tag: Tag,

    const Tag = extern enum {
        add,
        addwrap,
        alloc,
        alloc_mut,
        alloc_inferred,
        alloc_inferred_mut,
        anyframe_type,
        array_cat,
        array_mul,
    };
};

export fn entry(inst_list_ptr: [*]const Inst, inst_list_len: usize, map: [*]u32) void {
    const inst_list = inst_list_ptr[0..inst_list_len];
    var i: usize = 0;
    while (true) {
        const inst = inst_list[i];
        switch (inst.tag) {
            .add => {
                map[i] = analyze_add(inst);
                i += 1;
                if (i < inst_list_len) continue;
            },
            .addwrap => {
                map[i] = analyze_addwrap(inst);
                i += 1;
                if (i < inst_list_len) continue;
            },
            .alloc => {
                map[i] = analyze_alloc(inst);
                i += 1;
                if (i < inst_list_len) continue;
            },
            .alloc_mut => {
                map[i] = analyze_alloc_mut(inst);
                i += 1;
                if (i < inst_list_len) continue;
            },
            .alloc_inferred => {
                map[i] = analyze_alloc_inferred(inst);
                i += 1;
                if (i < inst_list_len) continue;
            },
            .alloc_inferred_mut => {
                map[i] = analyze_alloc_inferred_mut(inst);
                i += 1;
                if (i < inst_list_len) continue;
            },
            .anyframe_type => {
                map[i] = analyze_anyframe_type(inst);
                i += 1;
                if (i < inst_list_len) continue;
            },
            .array_cat => {
                map[i] = analyze_array_cat(inst);
                i += 1;
                if (i < inst_list_len) continue;
            },
            .array_mul => {
                map[i] = analyze_array_mul(inst);
                i += 1;
                if (i < inst_list_len) continue;
            },
        }
        break;
    }
}

extern fn analyze_add(inst: Inst) u32;
extern fn analyze_addwrap(inst: Inst) u32;
extern fn analyze_alloc(inst: Inst) u32;
extern fn analyze_alloc_mut(inst: Inst) u32;
extern fn analyze_alloc_inferred(inst: Inst) u32;
extern fn analyze_alloc_inferred_mut(inst: Inst) u32;
extern fn analyze_anyframe_type(inst: Inst) u32;
extern fn analyze_array_cat(inst: Inst) u32;
extern fn analyze_array_mul(inst: Inst) u32;

Snippet of assembly:

.LBB0_3:
        mov     dword ptr [r14 + 4*rbx], eax
        inc     rbx
        cmp     rbx, r15
        jae     .LBB0_4
.LBB0_1:
        mov     eax, dword ptr [r12 + 4*rbx]
        jmp     qword ptr [8*rax + .LJTI0_0]
.LBB0_2:
        xor     edi, edi
        call    analyze_add
        jmp     .LBB0_3
.LBB0_6:
        mov     edi, 2
        call    analyze_alloc
        jmp     .LBB0_3
.LBB0_5:
        mov     edi, 1
        call    analyze_addwrap
        jmp     .LBB0_3
.LBB0_7:
        mov     edi, 3
        call    analyze_alloc_mut
        jmp     .LBB0_3

Here, LLVM actually figured out the continue expression was duplicated N times, and un-inlined it, putting the code back how it was! So crafty.

EDIT: New Discovery

It does not get much simpler than this

Wrong!

After typing up this whole proposal, I realized that I did not try that optimization with using an "end" tag in the above code. Here is the case, modified (godbolt link):

const Inst = extern struct {
    tag: Tag,

    const Tag = extern enum {
        end,
        add,
        addwrap,
        alloc,
        alloc_mut,
        alloc_inferred,
        alloc_inferred_mut,
        anyframe_type,
        array_cat,
        array_mul,
    };
};

export fn entry(inst_list: [*]const Inst, map: [*]u32) void {
    var i: usize = 0;
    while (true) {
        const inst = inst_list[i];
        switch (inst.tag) {
            .end => return,
            .add => {
                map[i] = analyze_add(inst);
                i += 1;
                continue;
            },
            .addwrap => {
                map[i] = analyze_addwrap(inst);
                i += 1;
                continue;
            },
            .alloc => {
                map[i] = analyze_alloc(inst);
                i += 1;
                continue;
            },
            .alloc_mut => {
                map[i] = analyze_alloc_mut(inst);
                i += 1;
                continue;
            },
            .alloc_inferred => {
                map[i] = analyze_alloc_inferred(inst);
                i += 1;
                continue;
            },
            .alloc_inferred_mut => {
                map[i] = analyze_alloc_inferred_mut(inst);
                i += 1;
                continue;
            },
            .anyframe_type => {
                map[i] = analyze_anyframe_type(inst);
                i += 1;
                continue;
            },
            .array_cat => {
                map[i] = analyze_array_cat(inst);
                i += 1;
                continue;
            },
            .array_mul => {
                map[i] = analyze_array_mul(inst);
                i += 1;
                continue;
            },
        }
        break;
    }
}

extern fn analyze_add(inst: Inst) u32;
extern fn analyze_addwrap(inst: Inst) u32;
extern fn analyze_alloc(inst: Inst) u32;
extern fn analyze_alloc_mut(inst: Inst) u32;
extern fn analyze_alloc_inferred(inst: Inst) u32;
extern fn analyze_alloc_inferred_mut(inst: Inst) u32;
extern fn analyze_anyframe_type(inst: Inst) u32;
extern fn analyze_array_cat(inst: Inst) u32;
extern fn analyze_array_mul(inst: Inst) u32;

Two example prongs from the machine code:

.LBB0_2:
        mov     edi, 1
        call    analyze_add
        mov     dword ptr [r14 + rbx], eax
        add     rbx, 4
        mov     eax, dword ptr [r15 + rbx]
        jmp     qword ptr [8*rax + .LJTI0_0]
.LBB0_3:
        mov     edi, 2
        call    analyze_addwrap
        mov     dword ptr [r14 + rbx], eax
        add     rbx, 4
        mov     eax, dword ptr [r15 + rbx]
        jmp     qword ptr [8*rax + .LJTI0_0]

It's perfect! This is exactly what we wanted.

This compromises the entire proposal. I will still post the proposal but this new discovery makes it seem unnecessary, since, in fact, we are hereby observing #2162 already implemented and working inside LLVM.

Real Actual Use Case

Here's one in the self-hosted compiler:

zig/src/zir_sema.zig

Line 30 in e9a038c

switch (old_inst.tag) {

This switch is inside a loop over ZIR instructions. In optimized builds, we noticed non-trivial amount of time spent in the overhead of this dispatch, when analyzing a recursive comptime fibonacci function call.

This pattern also exists in:

  • The tokenizer
  • The parser
  • astgen
  • sema (this is the linked one above)
  • codegen
  • translate-c
  • zig fmt

(pretty much in every stage of the pipeline)

Other Possible Solution: Tail Calls

Tail calls solve this problem. Each switch prong would return foo() (tail call) and foo() at the end of its business would inline call a function which would do the switch and then tail call the next prong.

This is reasonable in the sense that it is doable right now; however there are some problems:

  • As far as I understand, tail calls don't work on some architectures.
    • (what are these? does anybody know?)
  • I'm also concerned about trying to debug when doing dispatch with tail calls.
  • It forces you to organize your logic into functions. That's another jump that
    maybe you did not want in your hot path.

Proposal

I propose to add continue :label expression syntax, and the ability to label switch expressions. Here is an example:

const Inst = extern struct {
    tag: Tag,

    const Tag = extern enum {
        end,
        add,
        addwrap,
        alloc,
        alloc_mut,
        alloc_inferred,
        alloc_inferred_mut,
        anyframe_type,
        array_cat,
        array_mul,
    };
};

export fn entry(inst_list: [*]const Inst, map: [*]u32) void {
    var i: usize = 0;
    sw: switch (inst_list[i].tag) {
        .end => return,
        .add => {
            map[i] = analyze_add(inst_list[i]);
            i += 1;
            continue :sw inst_list[i].tag;
        },
        .addwrap => {
            map[i] = analyze_addwrap(inst_list[i]);
            i += 1;
            continue :sw inst_list[i].tag;
        },
        .alloc => {
            map[i] = analyze_alloc(inst_list[i]);
            i += 1;
            continue :sw inst_list[i].tag;
        },
        .alloc_mut => {
            map[i] = analyze_alloc_mut(inst_list[i]);
            i += 1;
            continue :sw inst_list[i].tag;
        },
        .alloc_inferred => {
            map[i] = analyze_alloc_inferred(inst_list[i]);
            i += 1;
            continue :sw inst_list[i].tag;
        },
        .alloc_inferred_mut => {
            map[i] = analyze_alloc_inferred_mut(inst_list[i]);
            i += 1;
            continue :sw inst_list[i].tag;
        },
        .anyframe_type => {
            map[i] = analyze_anyframe_type(inst_list[i]);
            i += 1;
            continue :sw inst_list[i].tag;
        },
        .array_cat => {
            map[i] = analyze_array_cat(inst_list[i]);
            i += 1;
            continue :sw inst_list[i].tag;
        },
        .array_mul => {
            map[i] = analyze_array_mul(inst_list[i]);
            i += 1;
            continue :sw inst_list[i].tag;
        },
    }
}

extern fn analyze_add(inst: Inst) u32;
extern fn analyze_addwrap(inst: Inst) u32;
extern fn analyze_alloc(inst: Inst) u32;
extern fn analyze_alloc_mut(inst: Inst) u32;
extern fn analyze_alloc_inferred(inst: Inst) u32;
extern fn analyze_alloc_inferred_mut(inst: Inst) u32;
extern fn analyze_anyframe_type(inst: Inst) u32;
extern fn analyze_array_cat(inst: Inst) u32;
extern fn analyze_array_mul(inst: Inst) u32;

The new labeled continue syntax is syntactically unambiguous at a glance that it jumps to a switch expression, because it is the only form where continue accepts an operand. More details:

  • labeled continue with an operand on a loop would be a compile error
  • labeled break with a switch would be OK.

How to Lower this to LLVM

Note: I wrote this section before the EDIT: New Discovery section.

One idea I had was to put the switchbr instruction inside each prong. I did some LLVM IR surgery to try out this idea (godbolt link):

SwitchProngAdd:                                     ; preds = %WhileBody
  %9 = load i64, i64* %i, align 8
  %10 = load i32*, i32** %map, align 8
  %11 = getelementptr inbounds i32, i32* %10, i64 %9
  %12 = bitcast %Inst* %inst to i32*
  %13 = load i32, i32* %12, align 4
  %14 = call i32 @analyze_add(i32 %13)
  store i32 %14, i32* %11, align 4
  %15 = load i64, i64* %i, align 8
  %16 = add nuw i64 %15, 1
  store i64 %16, i64* %i, align 8
  %17 = load i64, i64* %i, align 8
  %18 = load %Inst*, %Inst** %inst_list, align 8
  %19 = getelementptr inbounds %Inst, %Inst* %18, i64 %17
  %20 = getelementptr inbounds %Inst, %Inst* %19, i32 0, i32 0
  %a20 = load i32, i32* %20, align 4
  switch i32 %a20, label %SwitchElse18 [
    i32 0, label %SwitchProngEnd
    i32 1, label %SwitchProngAdd
    i32 2, label %SwitchProngAddWrap
    i32 3, label %SwitchProngAlloc
    i32 4, label %SwitchProngAllocMut
    i32 5, label %SwitchProngAllocInferred
    i32 6, label %SwitchProngAllocInferredMut
    i32 7, label %SwitchProngAnyframeType
    i32 8, label %SwitchProngArrayCat
    i32 9, label %SwitchProngArrayMul
  ]

SwitchProngAddWrap:                                     ; preds = %WhileBody
  %21 = load i64, i64* %i, align 8
  %22 = load i32*, i32** %map, align 8
  %23 = getelementptr inbounds i32, i32* %22, i64 %21
  %24 = bitcast %Inst* %inst to i32*
  %25 = load i32, i32* %24, align 4
  %26 = call i32 @analyze_addwrap(i32 %25)
  store i32 %26, i32* %23, align 4
  %27 = load i64, i64* %i, align 8
  %28 = add nuw i64 %27, 1
  store i64 %28, i64* %i, align 8
  %29 = load i64, i64* %i, align 8
  %30 = load %Inst*, %Inst** %inst_list, align 8
  %31 = getelementptr inbounds %Inst, %Inst* %30, i64 %29
  %32 = getelementptr inbounds %Inst, %Inst* %31, i32 0, i32 0
  %a32 = load i32, i32* %32, align 4
  switch i32 %a32, label %SwitchElse18 [
    i32 0, label %SwitchProngEnd
    i32 1, label %SwitchProngAdd
    i32 2, label %SwitchProngAddWrap
    i32 3, label %SwitchProngAlloc
    i32 4, label %SwitchProngAllocMut
    i32 5, label %SwitchProngAllocInferred
    i32 6, label %SwitchProngAllocInferredMut
    i32 7, label %SwitchProngAnyframeType
    i32 8, label %SwitchProngArrayCat
    i32 9, label %SwitchProngArrayMul
  ]

The machine code for the prongs looks like this:

<snip>
.LBB0_8:                                # %SwitchProngAnyframeType
        mov     edi, r12d
        call    analyze_anyframe_type
        mov     dword ptr [r14 + 4*rbx], eax
        mov     eax, dword ptr [r15 + 4*rbx + 4]
        add     rbx, 1
        jmp     qword ptr [8*rax + .LJTI0_7]
.LBB0_9:                                # %SwitchProngArrayCat
        mov     edi, r12d
        call    analyze_array_cat
        mov     dword ptr [r14 + 4*rbx], eax
        mov     eax, dword ptr [r15 + 4*rbx + 4]
        add     rbx, 1
        jmp     qword ptr [8*rax + .LJTI0_8]
.LBB0_10:                               # %SwitchProngArrayMul
        mov     edi, r12d
        call    analyze_array_mul
        mov     dword ptr [r14 + 4*rbx], eax
        mov     eax, dword ptr [r15 + 4*rbx + 4]
        add     rbx, 1
        jmp     qword ptr [8*rax + .LJTI0_9]
<snip>

Pretty nice. This is exactly what we want - there is an indirect jump in each prong directly to the next prong. But the problem is that even though we should have the same jump table 9 times, LLVM duplicates the jump table 9 times:

.LJTI0_0:
        .quad   .LBB0_1
        .quad   .LBB0_2
        .quad   .LBB0_3
        .quad   .LBB0_4
        .quad   .LBB0_5
        .quad   .LBB0_6
        .quad   .LBB0_7
        .quad   .LBB0_8
        .quad   .LBB0_9
        .quad   .LBB0_10
.LJTI0_1:
        .quad   .LBB0_1
        .quad   .LBB0_2
        .quad   .LBB0_3
        .quad   .LBB0_4
        .quad   .LBB0_5
        .quad   .LBB0_6
        .quad   .LBB0_7
        .quad   .LBB0_8
        .quad   .LBB0_9
        .quad   .LBB0_10
<snip>

The duplicated jump tables are problematic, because in reality there could reasonably be about 150-200 instruction tags, which makes the jump table 600-800 bytes. This is fine; for example my L1 cache size is 256 KiB. But I wouldn't want to multiply that jump table by 200! It would be 156 KiB just for the jump tables alone. That would wreak havoc on the cache.

Unless this improves upstream, the best strategy to lower this language feature will be for Zig to manually create the jump table itself instead of relying on LLVM to do it, using LLVM's ability to take the address of basic blocks and put them into an array. This will essentially generate the same code that you would get in Clang if you used computed goto in the traditional way.

How to Lower this in Self-Hosted Backends

We have lots of options here. It would be quite straightforward, since we have full control over AIR, as well as the backend code generation.

OK But Is The Perf Actually Good?

I don't know. I think realistically in order to benchmark this and find out if the machine code performs better we have to implement it first.

Activity

  1. andrewrk
    added
    proposalThis issue suggests language modifications. If it also has the "accepted" label then it is planned.
    on Mar 12, 2021
  2. andrewrk
    added this to the 0.8.0 milestone on Mar 12, 2021

  3. andrewrk commented on Mar 12, 2021

    @andrewrk
    andrewrk
    on Mar 12, 2021
    MemberAuthor

    EDIT: New Discovery

    And here it is in idiomatic zig form, no duplicated code or anything:

    const Inst = extern struct {
    tag: Tag,

    const Tag = extern enum {
        end,
        add,
        addwrap,
        alloc,
        alloc_mut,
        alloc_inferred,
        alloc_inferred_mut,
        anyframe_type,
        array_cat,
        array_mul,
    };
};

export fn entry(inst_list: [*]const Inst, map: [*]u32) void {
    var i: usize = 0;
    while (true) : (i += 1) {
        const inst = inst_list[i];
        map[i] = switch (inst.tag) {
            .end => return,
            .add => analyze_add(inst),
            .addwrap => analyze_addwrap(inst),
            .alloc => analyze_alloc(inst),
            .alloc_mut => analyze_alloc_mut(inst),
            .alloc_inferred => analyze_alloc_inferred(inst),
            .alloc_inferred_mut => analyze_alloc_inferred_mut(inst),
            .anyframe_type => analyze_anyframe_type(inst),
            .array_cat => analyze_array_cat(inst),
            .array_mul => analyze_array_mul(inst),
        };
    }
}

extern fn analyze_add(inst: Inst) u32;
extern fn analyze_addwrap(inst: Inst) u32;
extern fn analyze_alloc(inst: Inst) u32;
extern fn analyze_alloc_mut(inst: Inst) u32;
extern fn analyze_alloc_inferred(inst: Inst) u32;
extern fn analyze_alloc_inferred_mut(inst: Inst) u32;
extern fn analyze_anyframe_type(inst: Inst) u32;
extern fn analyze_array_cat(inst: Inst) u32;
extern fn analyze_array_mul(inst: Inst) u32;

    It generates the ideal machine code.

  4. sighoya commented on Mar 13, 2021

    @sighoya
    sighoya
    on Mar 13, 2021

    @andrewrk

    Did you consider indirectbr?

  5. Techcable commented on Mar 15, 2021

    @Techcable
    Techcable
    on Mar 15, 2021
    Contributor

    Interestingly enough, C# has this feature with its goto case statement.

    Although the use cases are limited to certian situations. In those cases it can make a big difference. Interpreters and VMs are definitely a target audience for Zig, and low level code has plenty of other state machines where these sorts of dispatch tables might need this optimization.

    As someone expressed in #2162, sometimes computed goto can be slower than a regular switch statement in a loop. It would be odd to have performance pitfalls around these sorts of switch statements. I think Zig usually likes to make these performance choices explicit.

    On the other hand, this is generally considered a must-have optimization for fast interpreter implementations. In CPython it gives about a 15-20% speedup.

    @sighoya

    Did you consider indirectbr?

    That is exactly how clang implements it :) In fact, this feature is the reason indirectbr was added to LLVM in the first place

  6. andrewrk commented on Mar 23, 2021

    @andrewrk
    andrewrk
    on Mar 23, 2021
    MemberAuthor

    So I want to use this in semantic analysis of Zig self-hosted compiler. Here is:

    LLVM does not figure out how to generate the machine code that I want, and I suspect it would be a perf improvement. My plan is to implement this in order to benchmark it, and then we can make a decision, armed with some data.

  7. andrewrk commented on Mar 26, 2021

    @andrewrk
    andrewrk
    on Mar 26, 2021
    MemberAuthor

    Check out https://dino-lang.github.io/learn/dino.pdf, section 3.1 "Byte Code Dispatch"

  8. Mouvedia commented on Mar 26, 2021

    @Mouvedia
    Mouvedia
    on Mar 26, 2021

    As prior art I found PowerShell which uses break—instead of continue in this proposal—to jump to the switch's label.

  9. haberman commented on Apr 30, 2021

    @haberman
    haberman
    on Apr 30, 2021

    An argument for tail calls

    Based on my experience with https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html, I would strongly recommend offering guaranteed tail calls as one tool available to interpreter writers (I'm not arguing against other options).

    Getting the replicated decode/dispatch (as described above) is important, but it's only one part of the story. We also have to worry about the code quality for the operation itself -- the code that actually does the work.

    Optimizers struggle to generate good code when the entire interpreter is in one big function. In particular, they struggle to keep the most important state in registers. Mike Pall talked about this problem here: http://lua-users.org/lists/lua-l/2011-02/msg00742.html

    If each operation is in a separate function, with the most important state propagated in arguments (passed in registers on modern architectures), and each operation tail calling the next, we can get much better code out of the compiler. With this pattern, there is no switch() at all, just a call into a table of function pointers.

    Addressing open questions on Tail Calls

    To answer the questions above:

    As far as I understand, tail calls don't work on some architectures.
    (what are these? does anybody know?)

    For LLVM, musttail currently appears to be totally unsupported on powerpc (32 and 64). On ARM32 it runs into problems in some cases. There is a bit more information about this here: https://gcc.gnu.org/pipermail/gcc/2021-April/235903.html

    I don't know if these problems are fundamental or if they just need proper bug fixes.

    I'm also concerned about trying to debug when doing dispatch with tail calls.

    If you mean stack traces, I don't think tail calls leave any less of a stack trace than a traditional switch()-based dispatch. In both cases the stack tells you where you are, but not where you've been.

    It forces you to organize your logic into functions. That's another jump that
    maybe you did not want in your hot path.

    I think efficiency argues for tail calls, not against them. The tail call pattern does not create any unnecessary jumps. I'll elaborate a bit on this point.

    Tail calls generate code comparable to hand-written assembly

    Take this example from the article of implementing the "ADDVN" operation from LuaJIT, which aims to match this hand-written assembly code.

    The C compiler output almost exactly matches the hand-written assembly. It does not contain any jumps except the jump to the next operation, which is inherently necessary.

    When you are implementing byte code dispatch, you have a fundamental choice of whether to use replicated dispatch or shared dispatch. There are tradeoffs here, and the LuaJIT source discusses these tradeoffs a bit).

    Tail calls can support both options very naturally. All we have to do is flip the dispatch() function between noinline and always_inline: here is an example. For both patterns, the resulting code is comparable to hand-written assembly: it does not contain any extraneous or unnecessary jumps.

    Caveats

    I should mention one significant downside to this pattern: callee-save registers are not available to these functions without spilling them to the stack first. This means, in effect, that if we want the fastest code we can only use about half the registers. We also pay a steep price when making any non-tail call.

    Both of these problems can be solved if you also offer some specialized calling conventions (these are mostly supported in LLVM already). I can go into this more if you are interested. With the right calling conventions, I believe this pattern can generate code that even the most talented assembly language programmers would have a hard time beating.

  10. ifreund commented on Apr 30, 2021

    @ifreund
    ifreund
    on Apr 30, 2021
    Member

    @haberman note that zig already allows forcing tail calls with the @call() builtin: https://ziglang.org/documentation/master/#call

  11. haberman commented on Apr 30, 2021

    @haberman
    haberman
    on Apr 30, 2021

    @ifreund that is great news, thanks for the info. :)

  12. andrewrk
    modified the milestones: 0.8.0, 0.9.0 on May 19, 2021

  13. andrewrk commented on Sep 15, 2021

    @andrewrk
    andrewrk
    on Sep 15, 2021
    MemberAuthor

    I'm inclined to accept this proposal. Regardless of performance improvements, this provides a useful, intuitive tool for control flow. Another observation is that when the operand of continue :sw operand is comptime-known, this would be lowered as a direct jump to another switch prong, effectively providing the desired control flow requested in #5950.

    This even would allow someone to implement Duff's Device in zig:

    fn send(to: *volatile u32, from_start: [*]u32, count: u32) void {
    var from = from_start;
    var n = (count + 7) / 8;
    sw: switch (count % 8) {
        0 => {
            to.* = from[0];
            from += 1;
            continue :sw 7;
        },
        7 => {
            to.* = from[0];
            from += 1;
            continue :sw 6;
        },
        6 => {
            to.* = from[0];
            from += 1;
            continue :sw 5;
        },
        5 => {
            to.* = from[0];
            from += 1;
            continue :sw 4;
        },
        4 => {
            to.* = from[0];
            from += 1;
            continue :sw 3;
        },
        3 => {
            to.* = from[0];
            from += 1;
            continue :sw 2;
        },
        2 => {
            to.* = from[0];
            from += 1;
            continue :sw 1;
        },
        1 => {
            to.* = from[0];
            from += 1;
            n -= 1;
            if (n > 0) continue :sw 0;
        },
    }
}

    Reference example in C:

    send(to, from, count)
register short *to, *from;
register count;
{
    register n = (count + 7) / 8;
    switch (count % 8) {
    case 0: do { *to = *from++;
    case 7:      *to = *from++;
    case 6:      *to = *from++;
    case 5:      *to = *from++;
    case 4:      *to = *from++;
    case 3:      *to = *from++;
    case 2:      *to = *from++;
    case 1:      *to = *from++;
            } while (--n > 0);
    }
}

    With #7224 it could even be shortened to this:

    fn send(to: *volatile u32, from_start: [*]u32, count: u32) void {
    var from = from_start;
    var n = (count + 7) / 8;
    sw: switch (count % 8) {
        inline 0...7 => |remainder| {
            to.* = from[0];
            from += 1;
            if (remainder == 1) {
                n -= 1;
                if (n <= 0) break :sw;
            }
            continue :sw @as(u3, remainder) -% 1;
        },
    }
}

    What's interesting about this is that it lowers to the same machine code as the C version, even in debug mode.

  14. andrewrk
    added
    acceptedThis proposal is planned.
    on Sep 16, 2021

  15. 57 remaining items

  16. matklad
    added 2 commits that reference this issue on Sep 9, 2024

    vsr: refactor commit_dispatch loop

    7c381e6

    vsr: refactor commit_dispatch loop

    7a9cfb6
  17. LiterallyVoid
    added 2 commits that reference this issue on Sep 11, 2024

    Add langref docs for labeled switch

    dbc3a8f

    Add langref docs for labeled switch

    32c9b09
  18. matklad
    added 3 commits that reference this issue on Sep 11, 2024

    vsr: refactor commit_dispatch loop

    33a7582

    vsr: refactor commit_dispatch loop

    df3024c

    vsr: refactor commit_dispatch loop

    ce77a5f
  19. andrewrk
    added a commit that references this issue on Sep 13, 2024

    Labeled switch documentation (#21383)

    cf69154
  20. DivergentClouds
    added a commit that references this issue on Sep 24, 2024

    Labeled switch documentation (ziglang#21383)

    04a950a
  21. kprotty
    added a commit that references this issue on Nov 12, 2024

    vsr: refactor commit_dispatch loop

    1a792f3

  22. acgaudette commented on Mar 13, 2025

    @acgaudette
    acgaudette
    on Mar 13, 2025

    does zig have any particular idiom for emulating C-like semi-destructured goto control flow?

    e.g. I imagined the following would compile; it does not:

    const Label = enum(comptime_int) { INIT, A, B };

goto: switch (@as(Label, .INIT)) {
.INIT => {
    const result_of_some_logic = true;

    if (result_of_some_logic)
        continue :goto .A
    else
        continue :goto .B;
},
.A => {
    // ...
},
.B => {
    // ...
},
}

    all operands to continue :goto are known at compile time. if the underlying enum type is changed to something runtime compatible, this compiles OK. overall it feels a little awkward though.

    the idea here is not too far off from the common while (true) idiom, I am thinking: bend a structured control flow keyword out of shape a little in order to improve overall readability.

  23. mlugg commented on Mar 13, 2025

    @mlugg
    mlugg
    on Mar 13, 2025
    Member

    Labeled switch is essentially a looping construct, so isn't implicitly comptime-evaluated. Unlike while and for, it doesn't have an inline variant; you can't do the control flow at comptime whilst doing the stuff inside at runtime. This restriction exists for simplicity; we might loosen it in the future.

    That's why Label needs to be a runtime type; the continue :goto are lowered to runtime jumps rather than affecting how the code is compiled (comptime control flow). (Of course, the optimizer can and avoid avoid redundant jumps.)

    Note that you can make the enum valid at runtime simply by omitting the backing type entirely (i.e. just enum { INIT, A, B }).

  24. acgaudette commented on Mar 13, 2025

    @acgaudette
    acgaudette
    on Mar 13, 2025

    thank you for clarifying! I was feeling a little skittish around the codegen. in the end I suppose this is a reasonable approximation of the C behavior.

  25. jburgy
    added 2 commits that reference this issue on Apr 21, 2025

    Use ziglang/zig#8220 which landed in 0.14

    2fc4a44

    Merge pull request #7 from jburgy/use-switch-continue

    b9963a9
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    acceptedThis proposal is planned.proposalThis issue suggests language modifications. If it also has the "accepted" label then it is planned.

    Type

    No type

    Projects

    No projects

      Milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions