为什么 `switch` 这么慢？

Question

在字节码解释循环中，经过多次测试，我惊讶地发现使用 switch 是最糟糕的选择。调用函数指针数组，或使用 gcc 的计算 goto 扩展总是快 10~20%，计算的 goto 版本是最快的。我已经使用带有 97 条指令的真实玩具 VM 和下面粘贴的迷你假 VM 进行了测试。

为什么使用 switch 最慢？

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <inttypes.h>
#include <time.h>

enum {
    ADD1 = 1,
    ADD2,
    SUB3,
    SUB4,
    MUL5,
    MUL6,
};

static unsigned int number;

static void add1(void) {
    number += 1;
}

static void add2(void) {
    number += 2;
}

static void sub3(void) {
    number -= 3;
}

static void sub4(void) {
    number -= 4;
}

static void mul5(void) {
    number *= 5;
}

static void mul6(void) {
    number *= 6;
}

static void interpret_bytecodes_switch(uint8_t *bcs) {
    while (true) {
        switch (*bcs++) {
        case 0:
            return;
        case ADD1:
            add1();
            break;
        case ADD2:
            add2();
            break;
        case SUB3:
            sub3();
            break;
        case SUB4:
            sub4();
            break;
        case MUL5:
            mul5();
            break;
        case MUL6:
            mul6();
            break;
        }
    }
}

static void interpret_bytecodes_function_pointer(uint8_t *bcs) {
    void (*fs[])(void) = {
        NULL,
        add1,
        add2,
        sub3,
        sub4,
        mul5,
        mul6,
    };
    while (*bcs) {
        fs[*bcs++]();
    }
}

static void interpret_bytecodes_goto(uint8_t *bcs) {
    void *labels[] = {
        &&l_exit,
        &&l_add1,
        &&l_add2,
        &&l_sub3,
        &&l_sub4,
        &&l_mul5,
        &&l_mul6,
    };
    #define JUMP goto *labels[*bcs++]
    JUMP;
l_exit:
    return;
l_add1:
    add1();
    JUMP;
l_add2:
    add2();
    JUMP;
l_sub3:
    sub3();
    JUMP;
l_sub4:
    sub4();
    JUMP;
l_mul5:
    mul5();
    JUMP;
l_mul6:
    mul6();
    JUMP;
    #undef JUMP
}

struct timer {
    clock_t start, end;
};

static void timer_start(struct timer *self) {
    self->start = clock();
}

static void timer_end(struct timer *self) {
    self->end = clock();
}

static double timer_measure(struct timer *self) {
    return (double)(self->end - self->start) / CLOCKS_PER_SEC;
}

static void test(void (*f)(uint8_t *), uint8_t *bcs) {
    number = 0;
    struct timer timer;
    timer_start(&timer);
    f(bcs);
    timer_end(&timer);
    printf("%u %.3fs\n", number, timer_measure(&timer));
}

int main(void) {
    const int N = 300000000;
    srand((unsigned)time(NULL));
    uint8_t *bcs = malloc(N + 1);
    for (int i = 0; i < N; ++i) {
        bcs[i] = rand() % 5 + 1;
    }
    bcs[N] = 0;
    for (int i = 0; i < 10; ++i) {
        printf("%d ", bcs[i]);
    }
    printf("\nswitch\n");
    test(interpret_bytecodes_switch, bcs);
    printf("function pointer\n");
    test(interpret_bytecodes_function_pointer, bcs);
    printf("goto\n");
    test(interpret_bytecodes_goto, bcs);
    return 0;
}

结果

~$ gcc vm.c -ovm -std=gnu11 -O3
~$ ./vm
3 4 5 3 3 5 3 3 1 2 
switch
3050839589 2.866s
function pointer
3050839589 2.573s
goto
3050839589 2.433s
~$ ./vm
3 1 1 3 5 5 2 4 5 1 
switch
3898179583 2.871s
function pointer
3898179583 2.573s
goto
3898179583 2.431s
~$ ./vm
5 5 1 2 3 3 1 2 2 4 
switch
954521520 2.869s
function pointer
954521520 2.574s
goto
954521520 2.432s

下面贴出代码-O3优化后的相关反汇编

interpret_bytecodes_switch:
.L8:
    addq    , %rdi
    cmpb    , -1(%rdi)
    ja  .L8
    movzbl  -1(%rdi), %edx
    jmp *.L11(,%rdx,8)
.L11:
    .quad   .L10
    .quad   .L12
    .quad   .L13
    .quad   .L14
    .quad   .L15
    .quad   .L16
    .quad   .L17
.L16:
    leal    (%rax,%rax,4), %eax
    jmp .L8
.L15:
    subl    , %eax
    jmp .L8
.L14:
    subl    , %eax
    jmp .L8
.L13:
    addl    , %eax
    jmp .L8
.L12:
    addl    , %eax
    jmp .L8
.L10:
    movl    %eax, number(%rip)
    ret
.L17:
    leal    (%rax,%rax,2), %eax
    addl    %eax, %eax
    jmp .L8

interpret_bytecodes_function_pointer:
    pushq   %rbx
    movq    %rdi, %rbx
    subq    , %rsp
    movzbl  (%rdi), %eax
    movq    [=12=], (%rsp)
    movq    $add1, 8(%rsp)
    movq    $add2, 16(%rsp)
    movq    $sub3, 24(%rsp)
    movq    $sub4, 32(%rsp)
    movq    $mul5, 40(%rsp)
    testb   %al, %al
    movq    $mul6, 48(%rsp)
    je  .L19
.L23:
    addq    , %rbx
    call    *(%rsp,%rax,8)
    movzbl  (%rbx), %eax
    testb   %al, %al
    jne .L23
.L19:
    addq    , %rsp
    popq    %rbx
    ret

interpret_bytecodes_goto:
    movzbl  (%rdi), %eax
    movq    $.L27, -72(%rsp)
    addq    , %rdi
    movq    $.L28, -64(%rsp)
    movq    $.L29, -56(%rsp)
    movq    $.L30, -48(%rsp)
    movq    $.L31, -40(%rsp)
    movq    $.L32, -32(%rsp)
    movq    $.L33, -24(%rsp)
    movq    -72(%rsp,%rax,8), %rax
    jmp *%rax
.L33:
    movl    number(%rip), %eax
    leal    (%rax,%rax,2), %eax
    addl    %eax, %eax
    movl    %eax, number(%rip)
    movzbl  -1(%rdi), %eax
    movq    -72(%rsp,%rax,8), %rax
.L35:
    addq    , %rdi
    jmp *%rax
.L28:
    addl    , number(%rip)
    movzbl  -1(%rdi), %eax
    movq    -72(%rsp,%rax,8), %rax
    jmp .L35
.L30:
    subl    , number(%rip)
    movzbl  -1(%rdi), %eax
    movq    -72(%rsp,%rax,8), %rax
    jmp .L35
.L31:
    subl    , number(%rip)
    movzbl  -1(%rdi), %eax
    movq    -72(%rsp,%rax,8), %rax
    jmp .L35
.L32:
    movl    number(%rip), %eax
    leal    (%rax,%rax,4), %eax
    movl    %eax, number(%rip)
    movzbl  -1(%rdi), %eax
    movq    -72(%rsp,%rax,8), %rax
    jmp .L35
.L29:
    addl    , number(%rip)
    movzbl  -1(%rdi), %eax
    movq    -72(%rsp,%rax,8), %rax
    jmp .L35
.L27:
    rep ret

Answer 1

您正在执行微基准测试。现代 CPU 的微基准测试可能会受到各种随机或不可预测的影响。执行时间实际上差别很小。但是，为了使代码具有可比性，您结合了开关和函数调用，这在现实生活中不会发生在时间关键代码中。

Answer 2

当你发布汇编代码时，我正在写一个很长的答案...
基本上，goto 版本使用更多 "code" 来防止每次迭代中的一些（或单个）指令。它类似于大小与速度优化。

由于您的 "real work" 可以忽略不计，因此它在基准测试中产生了足够的差异，但在现实世界中，该指令将变得可以忽略不计。

Answer 3

switch 是最慢的，因为它必须管理 default 个案例，这可能会添加一个您未实现的额外边界测试。

switch 还处理更一般的情况，其中 case 值没有按如此简单的顺序排列，为此可能需要额外的计算。

为什么 `switch` 这么慢？

Why is `switch` so slow?

c

goto

function-pointers

switch-statement