Forem: Aleksandar Milenkovic

Switch Case: Peak Performance

Aleksandar Milenkovic — Mon, 09 Mar 2026 18:25:39 +0000

	This blog is sponsored and supported by Voxgig.

	Motivated and inspired by Decl. In development and soon to be open-sourced.

Switch Case: Peak Performance
- About Author
- Motivation
- Source Code
- Introduction
- Switch Case Optimization
- Direct JMP Instruction Optimization
- Break vs Return
- Benchmark Results and Conclusion
- Linux Perf Stats

About Author

My name is Aleksandar Milenkovic. I am a senior software engineer at Voxgig and a self-driven coder, an autodidact, that creates software and improves its quality at any level.

If you have any feedback or questions, feel free to reach out to me via LinkedIn.

Motivation

Having worked on the implementation of the programming language, Decl for quite a long time now - I needed to squeeze the water out of the stone in terms of all the complier optimizations for the switch case statement out there as any operation in Decl is exclusively determined by a switch case being a dynamic programming language where all the variables and declarations are essentially of any type.

For example, the following code in Decl requires as many as three JMP instructions before any other operations are done.

v = 1 + 1;

// Translates into

Value v = plus(makeNumber(1), makeNumber(1));

// plus(Value left, Value right); JMP, JMP // Is left a number? Is right a number?
// v.~Value(); JMP // Is v an object to be released?

Without the properly optimized switch case statement, this results in about 9 assembly instructions at face value!

In my opinion, I understood that we can do much better than that and that this is not feasible for millions upon millions of operations that can transpire in Decl, and so here we are!

I hope you find all of the information in this article useful and applicable to your code in order to reach that peak performance via micro optimization.

Source Code

The source code of this blog is all in one file, at the Github repository where it is also hosted. The code contains the main function running all the benchmarks in order.

Introduction

This article is the final conclusion of S2S Compilers: Understanding Switch Case Statements blog.

It is here that we finally get to fully and truly optimize the switch case statement so that the developer is confident of using such optimizations in their codebase without the excruciating pain of complexity, and nightmare maintenance problems and concerns each time there is, all but, a small addition to the code logic.

The main focus of the S2S Compilers: Understanding Switch Case Statements blog is to get the readers up to speed of what the switch case is and to contextualize various implementations that the developer can attempt in order to reach the peak performance.

Our conclusion of the previous blog was:

Although there is a lot to unpack in this blog, the best approach is to use the switch statement, as the GCC compiler has a hard time optimizing the high-level C implementations as discussed above. If you're determined to optimize further and want to remove any redundant ASM instructions that may impact your code, consider using 6.17.2 Extended Asm | Assembler Instructions with C Expression Operands, which allows you to craft your assembly from the ground up - untouched by the optimizations such as -O1, -O2, or -O3.

Contrary to the statement above - after doing some research, I have finally managed to put together a jump table generated by the high-level switch case statement that truly uses the smallest number of assembly instructions overall without any necessity of crafting any assembly code from the group up as previously concluded.

Without further ado, let's dive in and speed up our code!

Switch Case Optimization

In the previous blog, we have primarily focused on the following switch case implementation.

void _switch_run(unsigned int type) {

  volatile int r; // NOTE: preventing compiler from optimizing it out

  switch(type) {
    case 0: {
      r = 0;
      break;
    }
    case 1: {
      r = 1;
      break;
    }
    case 2: {
      r = 2;
      break;
    }
    case 3: {
      r = 3;
      break;
    }
    case 4: {
      r = 4;
      break;
    }
    case 5: {
      r = 5;
      break;
    }
    case 6: {
      r = 6;
      break;
    }
    case 7: {
      r = 7;
      break;
    }
    case 8: {
      r = 8;
      break;
    }
    case 9: {
      r = 9;
      break;
    }
    case 10: {
      r = 10;
      break;
    }
    default: {
      r = 11;
      break;
    }
  }

}

Generating the following assembly code:

_switch_run:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        cmp     DWORD PTR [rbp-20], 10
        ja      .L2
        mov     eax, DWORD PTR [rbp-20]
        mov     rax, QWORD PTR .L4[0+rax*8]
        jmp     rax
.L4:
        .quad   .L14
        .quad   .L13
        .quad   .L12
        .quad   .L11
        .quad   .L10
        .quad   .L9
        .quad   .L8
        .quad   .L7
        .quad   .L6
        .quad   .L5
        .quad   .L3
.L14:
        mov     DWORD PTR [rbp-4], 0
        jmp     .L15 # break
.L13:
        mov     DWORD PTR [rbp-4], 1
        jmp     .L15
.L12:
        mov     DWORD PTR [rbp-4], 2
        jmp     .L15
.L11:
        mov     DWORD PTR [rbp-4], 3
        jmp     .L15
.L10:
        mov     DWORD PTR [rbp-4], 4
        jmp     .L15
.L9:
        mov     DWORD PTR [rbp-4], 5
        jmp     .L15
.L8:
        mov     DWORD PTR [rbp-4], 6
        jmp     .L15
.L7:
        mov     DWORD PTR [rbp-4], 7
        jmp     .L15
.L6:
        mov     DWORD PTR [rbp-4], 8
        jmp     .L15
.L5:
        mov     DWORD PTR [rbp-4], 9
        jmp     .L15
.L3:
        mov     DWORD PTR [rbp-4], 10
        jmp     .L15
.L2: # Default Case Label
        mov     DWORD PTR [rbp-4], 11
        nop
.L15: # Break Label
        nop
        pop     rbp
        ret

This switch case, while safe due to the default case, can be barely optimized further due to its dangerous nature.

For instance, we can never (even theoretically) optimize out the conditional JUMP that precedes the actual direct JMP of our switch case table.

        cmp     DWORD PTR [rbp-20], 10
        ja      .L2
        mov     eax, DWORD PTR [rbp-20]
        mov     rax, QWORD PTR .L4[0+rax*8]
        jmp     rax

This is due to the following concerns:

Removing the if statement and CMP is more performant but the cost on the programmer's side of things is that the programmer has to make their code very strict with covering all the possible values and cases since this eliminates the default case. Note that if the subscript is out of bounds - the programmer is going to end up with Segmentation fault (core dumped) at runtime. All in all, this can lead to premature optimization.

Here is the exact log from valgrind, showing that the program cannot jump to the invalid address.
valgrind -s ./out.out
==49387== Jump to the invalid address stated on the next line
==49387==    at 0x0: ???
==49387==    by 0x1097BC: main (in /src/out.out)
==49387==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==49387== 
==49387== 
==49387== Process terminating with default action of signal 11 (SIGSEGV)
==49387==  Bad permissions for mapped region at address 0x0
==49387==    at 0x0: ???
==49387==    by 0x1097BC: main (in /src/out.out)

We can effectively eliminate this concern by using a strict range of enumeration values where we cover each and every case.

For the safety of our code at runtime, this restriction is absolutely crucial for the elimination of the CMP and JA overhead, which can indeed be considered huge overhead in the grand scheme of things.

enum class V {
    NUM,
    STRING,
    ARR,
    DICT,
    FUNC,
};

int __switch_case(V v) {
    volatile int i = 0;

    switch(v) {
        case V::NUM: {
            i = 1;
            break;
        }
        case V::STRING: {
            i = 2;
            break;
        }
        case V::ARR: {
            i = 3;
            break;
        }
        case V::DICT: {
            i = 4;
            break;
        }
        case V::FUNC: {
            i = 5;
            break;
        }
        default: {
            break;
        }
    }
    return i;

}

Generating the following assembly output:

__switch_case(V):
        mov     DWORD PTR [rsp-4], 0
        cmp     edi, 4
        ja      .L22
        mov     edi, edi
        jmp     [QWORD PTR .L24[0+rdi*8]]
.L24:
        .quad   .L28
        .quad   .L27
        .quad   .L26
        .quad   .L25
        .quad   .L23
.L28:
        mov     DWORD PTR [rsp-4], 1
.L22:
        mov     eax, DWORD PTR [rsp-4]
        ret
.L27:
        mov     DWORD PTR [rsp-4], 2
        jmp     .L22
.L26:
        mov     DWORD PTR [rsp-4], 3
        jmp     .L22
.L25:
        mov     DWORD PTR [rsp-4], 4
        jmp     .L22
.L23:
        mov     DWORD PTR [rsp-4], 5
        jmp     .L22

Direct JMP Instruction Optimization

Let's get to the crux of the matter and optimize out the following before our actual direct JMP.

        mov     DWORD PTR [rsp-4], 0
        cmp     edi, 4
        ja      .L22

This GCC-specific implementation will do the trick.

int _switch_case(V v) {
    volatile int i = 0;

    switch(v) {
        case V::NUM: {
            i = 1;
            break;
        }
        case V::STRING: {
            i = 2;
            break;
        }
        case V::ARR: {
            i = 3;
            break;
        }
        case V::DICT: {
            i = 4;
            break;
        }
        case V::FUNC: {
            i = 5;
            break;
        }
        default: {
            __builtin_unreachable();
        }
    }

    return i;

}

🚧 Note

The __builtin_unreachable() function is a non-standard, compiler-specific builtin function (available in GCC and Clang).

For more information, refer to 7.12 Other Built-in Functions Provided by GCC.

What the __builtin_unreachable() function does is that it informs the compiler that the control flow will never reach that point in the program, which means that the compiler can safely remove dead code given that we will never reach the default (out-of-bounds) case having covered each and every enumeration value of enum class V.

📘 Note

The C++ Programming Language plays a huge role here as it gives us the ability to strictly specify the type of the enumeration range so that no runtime faults can be caused. With enum class being of static type, this validation, needless to say, is done at compile time.

For more detailed overview, refer to C++ Language | Enumeration declaration.

As a result, we get the following assembly output.

_switch_case(V):
        mov     DWORD PTR [rsp-4], 0
        mov     edi, edi
        jmp     [QWORD PTR .L15[0+rdi*8]]
.L15:
        .quad   .L19
        .quad   .L18
        .quad   .L17
        .quad   .L16
        .quad   .L14
.L19:
        mov     DWORD PTR [rsp-4], 1
.L20:
        mov     eax, DWORD PTR [rsp-4]
        ret
.L18:
        mov     DWORD PTR [rsp-4], 2
        jmp     .L20
.L17:
        mov     DWORD PTR [rsp-4], 3
        jmp     .L20
.L16:
        mov     DWORD PTR [rsp-4], 4
        jmp     .L20
.L14:
        mov     DWORD PTR [rsp-4], 5
        jmp     .L20

It is absolutely safe to say that we have successfully eliminated the overhead of CMP and JA by literally removing those two assembly instructions altogether. Now, we jump straight to (no pun intended) the respective label of the jump table.

Break vs Return

While you may think that we are through with the optimization of our switch case, there is one last touch to hit the peak performance of the switch case statement.

This is the break label of the switch case statement that makes a JMP to get out of the switch case so that we don't possibly get stuck in an infinite loop.

This is the .L20 label that the code needs to jump to where there is the final RET instruction that pops the return address off the stack (of the initial CALL instruction).

_switch_case(V):
        mov     DWORD PTR [rsp-4], 0
        mov     edi, edi
        jmp     [QWORD PTR .L15[0+rdi*8]]
.L15:
        .quad   .L19
        .quad   .L18
        .quad   .L17
        .quad   .L16
        .quad   .L14
.L19:
        mov     DWORD PTR [rsp-4], 1
.L20:
        mov     eax, DWORD PTR [rsp-4]
        ret
.L18:
        mov     DWORD PTR [rsp-4], 2
        jmp     .L20
.L17:
        mov     DWORD PTR [rsp-4], 3
        jmp     .L20
.L16:
        mov     DWORD PTR [rsp-4], 4
        jmp     .L20
.L14:
        mov     DWORD PTR [rsp-4], 5
        jmp     .L20

What if we can reduce the number of assembly instructions by removing the JMP where the compiler produces the assembly output similar to the following for each and every switch case label?

.L14:
        mov     DWORD PTR [rsp-4], 5
        mov     eax, DWORD PTR [rsp-4]
        ret

This is made possible with the following C/C++ code implementation.

int _switch_case_return(V v) {
    volatile int i = 0;

    switch(v) {
        case V::NUM: {
            i = 1;
            return i;
        }
        case V::STRING: {
            i = 2;
            return i;
        }
        case V::ARR: {
            i = 3;
            return i;
        }
        case V::DICT: {
            i = 4;
            return i;

        }
        case V::FUNC: {
            i = 5;
            return i;
        }
        default: {
            __builtin_unreachable();
        }
    }
    return i;
}

This produces cleaner assembly with no extra JMP instruction of the break label whatsoever.

_switch_case_return(V):
        mov     DWORD PTR [rsp-4], 0
        mov     edi, edi
        jmp     [QWORD PTR .L6[0+rdi*8]]
.L6:
        .quad   .L10
        .quad   .L9
        .quad   .L8
        .quad   .L7
        .quad   .L5
.L10:
        mov     DWORD PTR [rsp-4], 1
        mov     eax, DWORD PTR [rsp-4]
        ret
.L9:
        mov     DWORD PTR [rsp-4], 2
        mov     eax, DWORD PTR [rsp-4]
        ret
.L8:
        mov     DWORD PTR [rsp-4], 3
        mov     eax, DWORD PTR [rsp-4]
        ret
.L7:
        mov     DWORD PTR [rsp-4], 4
        mov     eax, DWORD PTR [rsp-4]
        ret
.L5:
        mov     DWORD PTR [rsp-4], 5
        mov     eax, DWORD PTR [rsp-4]
        ret

📘 Keep in mind!

It is important to keep in mind that the return statement terminates the rest of the code execution (as it makes it unreachable) so make sure to code your logic carefully!

With all of our functions implemented, let's put them into practice by benchmarking its results under heavy scenarios by wrapping them into very extensive loops. This is usually a common practice to benchmark your code in general.

Benchmark Results and Conclusion

Assembly instruction count can matter, but latency, branching, and memory behavior are usually more important.

Let's benchmark all of the functions above and see the differences for ourselves!

📘 Note

Note that, as opposed to Computed GOTO: Goto Jump Table with Labels in the previous blog, all of our functions can now be inlined. So while we are safely using our switch case, we are also capitalizing on all the optimizations that the compiler itself can make.

#include <iostream>

#include <cassert>

#include <ctime>

#define start_time clock_t s_t_a_r_t = clock();

int main() {

  const size_t TEST_BOUNDARY = 1000000;

  const size_t RANGE = 100;


  std::cout << "START: SWITCH_CASE_CONDITION DEFAULT BREAK" << std::endl;
  {

    double _SUM = 0;
    volatile V _t = V::NUM;

    for(size_t i = 0; i < RANGE; i++) {
        start_time;
        for(size_t i = 0; i < TEST_BOUNDARY; i++) {
            assert(__switch_case(_t) != 0);
        }
        _SUM += static_cast<double>(clock() - s_t_a_r_t) / CLOCKS_PER_SEC;
    }

    std::cout << _SUM/RANGE << std::endl;

  }
  std::cout << "END: SWITCH_CASE_CONDITION DEFAULT BREAK" << std::endl;


  std::cout << "START: SWITCH_CASE_CONDITION DEFAULT UNREACHABLE" << std::endl;
  {

    double _SUM = 0;
    volatile V _t = V::NUM;

    for(size_t i = 0; i < RANGE; i++) {
        start_time;
        for(size_t i = 0; i < TEST_BOUNDARY; i++) {
            assert(_switch_case(_t) != 0);
        }
        _SUM += static_cast<double>(clock() - s_t_a_r_t) / CLOCKS_PER_SEC;
    }

    std::cout << _SUM/RANGE << std::endl;

  }
  std::cout << "END: SWITCH_CASE_CONDITION DEFAULT UNREACHABLE" << std::endl;

  std::cout << "START: SWITCH_CASE_CONDITION UNREACHABLE AND RETURN AS OPPOSED TO BREAK" << std::endl;
  {

    double _SUM = 0;
    volatile V _t = V::NUM;

    for(size_t i = 0; i < RANGE; i++) {
        start_time;
        for(size_t i = 0; i < TEST_BOUNDARY; i++) {
            assert(_switch_case_return(_t) != 0);
        }
        _SUM += static_cast<double>(clock() - s_t_a_r_t) / CLOCKS_PER_SEC;
    }

    std::cout << _SUM/RANGE << std::endl;

  }
  std::cout << "END: SWITCH_CASE_CONDITION UNREACHABLE AND RETURN AS OPPOSED TO BREAK" << std::endl;

  return 0;
}

This benchmark produces the following output after we compile it with g++ and the -O1 optimizations:

g++ switch_case_performance_peak.cpp -o out.out -O1 && ./out.out

START: SWITCH_CASE_CONDITION DEFAULT BREAK
0.00063072
END: SWITCH_CASE_CONDITION DEFAULT BREAK
START: SWITCH_CASE_CONDITION DEFAULT UNREACHABLE
0.00055233
END: SWITCH_CASE_CONDITION DEFAULT UNREACHABLE
START: SWITCH_CASE_CONDITION UNREACHABLE AND RETURN AS OPPOSED TO BREAK
0.00052462
END: SWITCH_CASE_CONDITION UNREACHABLE AND RETURN AS OPPOSED TO BREAK

As our ultimate reward, we get to break down the great results of our micro optimization efforts!

📘 Note

The difference between using break and return might seem negligible but it is, after all, an improvement in performance as we have optimized out the redundant JMP for the break label as detailed out above.

Linux Perf Stats

START: SWITCH_CASE_CONDITION DEFAULT BREAK
0.001588
END: SWITCH_CASE_CONDITION DEFAULT BREAK

 Performance counter stats for './out.out':

            162,15 msec task-clock                       #    0,988 CPUs utilized             
                 2      context-switches                 #   12,334 /sec                      
                 1      cpu-migrations                   #    6,167 /sec                      
               137      page-faults                      #  844,877 /sec                      
         191667732      cpu_atom/cycles/                 #    1,182 GHz                         (7,47%)
         327598821      cpu_core/cycles/                 #    2,020 GHz                         (90,06%)
         520210064      cpu_atom/instructions/           #    2,71  insn per cycle              (8,70%)
        1949203244      cpu_core/instructions/           #   10,17  insn per cycle              (90,06%)
         159155942      cpu_atom/branches/               #  981,513 M/sec                       (8,71%)
         649344343      cpu_core/branches/               #    4,004 G/sec                       (90,06%)
            207986      cpu_atom/branch-misses/          #    0,13% of all branches             (8,71%)
              5015      cpu_core/branch-misses/          #    0,00% of all branches             (90,06%)
             TopdownL1 (cpu_core)                 #      0,4 %  tma_backend_bound      
                                                  #      0,0 %  tma_bad_speculation    
                                                  #     11,3 %  tma_frontend_bound     
                                                  #     88,3 %  tma_retiring             (90,06%)
             TopdownL1 (cpu_atom)                 #      4,5 %  tma_bad_speculation    
                                                  #     57,9 %  tma_retiring             (8,70%)
                                                  #      8,5 %  tma_backend_bound      
                                                  #      8,5 %  tma_backend_bound_aux  
                                                  #     29,0 %  tma_frontend_bound       (8,71%)

       0,164053653 seconds time elapsed

       0,159006000 seconds user
       0,005000000 seconds sys

START: SWITCH_CASE_CONDITION DEFAULT UNREACHABLE
0.00135889
END: SWITCH_CASE_CONDITION DEFAULT UNREACHABLE

 Performance counter stats for './out.out':

            139,22 msec task-clock                       #    0,989 CPUs utilized             
                 3      context-switches                 #   21,548 /sec                      
                 3      cpu-migrations                   #   21,548 /sec                      
               137      page-faults                      #  984,042 /sec                      
         198806298      cpu_atom/cycles/                 #    1,428 GHz                         (4,58%)
         276323001      cpu_core/cycles/                 #    1,985 GHz                         (93,94%)
         398268584      cpu_atom/instructions/           #    2,00  insn per cycle              (5,34%)
        1684695478      cpu_core/instructions/           #    8,47  insn per cycle              (93,94%)
         109741029      cpu_atom/branches/               #  788,247 M/sec                       (5,35%)
         526065442      cpu_core/branches/               #    3,779 G/sec                       (93,94%)
            249023      cpu_atom/branch-misses/          #    0,23% of all branches             (5,34%)
              9850      cpu_core/branch-misses/          #    0,01% of all branches             (93,94%)
             TopdownL1 (cpu_core)                 #      0,4 %  tma_backend_bound      
                                                  #      0,0 %  tma_bad_speculation    
                                                  #      3,9 %  tma_frontend_bound     
                                                  #     95,7 %  tma_retiring             (93,94%)
             TopdownL1 (cpu_atom)                 #      4,6 %  tma_bad_speculation    
                                                  #     44,6 %  tma_retiring             (5,34%)
                                                  #      9,5 %  tma_backend_bound      
                                                  #      9,5 %  tma_backend_bound_aux  
                                                  #     41,3 %  tma_frontend_bound       (5,34%)

       0,140714902 seconds time elapsed

       0,136607000 seconds user
       0,003988000 seconds sys

START: SWITCH_CASE_CONDITION UNREACHABLE AND RETURN AS OPPOSED TO BREAK
0.00140369
END: SWITCH_CASE_CONDITION UNREACHABLE AND RETURN AS OPPOSED TO BREAK

 Performance counter stats for './out.out':

            143,29 msec task-clock                       #    0,987 CPUs utilized             
                 4      context-switches                 #   27,915 /sec                      
                 4      cpu-migrations                   #   27,915 /sec                      
               135      page-faults                      #  942,140 /sec                      
         234326956      cpu_atom/cycles/                 #    1,635 GHz                         (4,26%)
         273776908      cpu_core/cycles/                 #    1,911 GHz                         (93,60%)
         512019762      cpu_atom/instructions/           #    2,19  insn per cycle              (5,61%)
        1680687481      cpu_core/instructions/           #    7,17  insn per cycle              (93,60%)
         158185875      cpu_atom/branches/               #    1,104 G/sec                       (5,71%)
         524454946      cpu_core/branches/               #    3,660 G/sec                       (93,60%)
             35045      cpu_atom/branch-misses/          #    0,02% of all branches             (5,70%)
             21299      cpu_core/branch-misses/          #    0,01% of all branches             (93,60%)
             TopdownL1 (cpu_core)                 #      0,8 %  tma_backend_bound      
                                                  #      0,4 %  tma_bad_speculation    
                                                  #      2,7 %  tma_frontend_bound     
                                                  #     96,1 %  tma_retiring             (93,60%)
             TopdownL1 (cpu_atom)                 #      0,1 %  tma_bad_speculation    
                                                  #     50,8 %  tma_retiring             (5,70%)
                                                  #      3,4 %  tma_backend_bound      
                                                  #      3,4 %  tma_backend_bound_aux  
                                                  #     45,7 %  tma_frontend_bound       (5,70%)

       0,145156837 seconds time elapsed

       0,142083000 seconds user
       0,003001000 seconds sys

S2S Compilers: Understanding Switch Case Statements

Aleksandar Milenkovic — Thu, 27 Mar 2025 14:03:47 +0000

S2S Compilers: Understanding Switch Case Statements

	This blog is sponsored and supported by Voxgig.

	Motivated and inspired by Decl. In development and soon to be open-sourced.

S2S Compilers: Understanding Switch Case Statements
- About Author
- Introduction
- Motivation
- Source Code
- Prerequisites
- Background
- GCC Options
- Headers and Macros
- Switch case VS If-else
- If-else statement
- Switch Case
- Benchmarking the two
- Out-of-Bounds Benchmark
- Turning a switch case into a jump table
- Is there a limit for the values of a switch case?
- Breaking switch case: Non-packed values
- Multiple Jump Tables
- If-else as a jump table
- If-else with logical || operator as a jump table
- Implementing Switch Case
- Jump Table with function pointers
  - Implementation
  - Benchmark Result 1
  - Benchmark Result 2
- Computed GOTO: Goto Jump Table with Labels
  - No optimization flags
  - With -O2 optimizations
  - Switch Case with -O1 optimizations
  - No Inline
  - Inlining Computed GOTO
  - Switch Go Macro
  - Computed GOTO: C++ Statement Expression
  - Local Label Concern
  - Inlining Switch Case
  - GCC Loop Optimization
  - Computed GOTO: RAII Concerns
  - Customizing _switch_go
  - Benchmark
  - Default Case: Can we do without it?
- Conclusion
- References

About Author

My name is Aleksandar Milenkovic. I am a senior software engineer at Voxgig and a self-driven coder, an autodidact, that creates software and improves its quality at any level.

If you have any feedback or questions, feel free to reach out to me via LinkedIn.

Introduction

Source-to-source compilers transpile the source code of a program and generate it into another language (target language). The target is typically a high-level language that is supported by all platforms so that the compatibility is not a problem.

If you are turning your source code into languages such as C or C++, it is required to have great understanding and knowledge of C/C++. Since these languages also have compilers be it GNU Compiler Collection or Clang, we have to do a lot of digging and researching around their features and functionalities. There is a lot of benefit in that once the target codebase grows and developers start reusing the target source as a component rather than referring back to the source language code. For more context, also check out Wikipedia | Source-to-source compiler | Programming language implementations.

In a lot of cases, we start benchmarking a lot of the target source code generated by our S2S compiler and comparing to the plain C/C++. We start finding a lot of improvements we can make for the target source itself. The goal is the quality and performance of the target source.

As the first instalment of this series, we dive into the usage of the switch case, optimizing it, comparing it to if-else, implementing our own switch case with all of the assembly conversions and benchmarks to back it all up. We use GCC (GNU Compiler Collection) and cover some of its commands in detail.

Even if you are not interested in S2S Compilers as a C/C++ developer, this blog still comes in handy with all of the examples and information.

This blog series is named S2S (Source-to-source) Compilers as all of the code and content is motivated by building a S2S Compiler that takes in the source language and translates it into C++. By benchmarking and analyzing the target source (C++), I have realized how many improvements there are to make. More on the motivation in the following section.

Motivation

As a senior software engineer for Voxgig, we have been building SDKs in various programming languages. For our utilities, this brought about a lot of performance concerns as we port from one language to another, we would try to make the two and more implementations as close as possible side by side. That led us into the waters of language-specific implementations where we have pushed to use the most out of each language so as to make it as performant as possible for the developer using the SDK in the respective language. For example, the C++ implementation is going to have more focus on the performance since it is harder to optimize code compared to Python, Ruby, or JavaScript.

At the same point in time while at Voxgig, I have been building a dynamic programming language that transpiles into C++, I have been doing a lot of research and have benchmarked plenty of C++ code in order to hit the maximum runtime performance of the target language (C++).

All of this work was motivated by the dynamic programming language called, Decl; soon to be open-sourced.

To be frank, the reason for C++ as the target language is that it is much easier to build a garbage collector by just implementing reference counter in the wrapper class. The state of dynamically allocated objects is determined by implicit destructors of C++, again, with the reference counting implementation. However, we won't cover any of that in this blog but stay ready for the next instalment :).

All of the knowledge that I have acquired turned out to be very useful for me and, most of all, our team.

If you are interested in building SDKs for one or even more programming languages, please contact Voxgig.

Again, huge thanks to Voxgig for enabling me to put in the time for this research and writing the blog.

Source Code

The source code of this blog is all in one file, at the Github repository where it is also hosted. The code contains the main function running all the benchmarks in order.

Prerequisites

Background

This blog is intended for C/C++ programmers who have the essential knowledge of assembly. Nonetheless, if you haven't had any experience of assembly before, read on and see how you get on!

GCC Options

You can use the following gcc command to dissect assembly code:

gcc src/main.cpp -g -o output.s -masm=intel -fverbose-asm -S -Werror

As the Using the GNU Compiler Collection Documentation indicates, we use -fverbose-asm to "put extra commentary information in the generated assembly code to make it more readable".

For example,

#include <stdio.h>


int main() {
  int i = 0;


  printf("%d\n", i);
  printf("%d%d\n", i, i);

  return 0;
}

Generates the following assembly output with comments indicating the line number and its content.

main:
.LFB0:
        .file 1 "main.cpp"
        .loc 1 4 12
        .cfi_startproc  
        endbr64 
        push    rbp     #
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        mov     rbp, rsp        #,
        .cfi_def_cfa_register 6
        sub     rsp, 16 #,
# main.cpp:5:   int i = 0;
        .loc 1 5 7
        mov     DWORD PTR -4[rbp], 0    # i,
# main.cpp:8:   printf("%d\n", i);
        .loc 1 8 9
        mov     eax, DWORD PTR -4[rbp]  # tmp84, i
        mov     esi, eax        #, tmp84
        lea     rax, .LC0[rip]  # tmp85,
        mov     rdi, rax        #, tmp85
        mov     eax, 0  #,
        call    printf@PLT      #
# main.cpp:9:   printf("%d%d\n", i, i);
        .loc 1 9 9
        mov     edx, DWORD PTR -4[rbp]  # tmp86, i
        mov     eax, DWORD PTR -4[rbp]  # tmp87, i
        mov     esi, eax        #, tmp87
        lea     rax, .LC1[rip]  # tmp88,
        mov     rdi, rax        #, tmp88
        mov     eax, 0  #,
        call    printf@PLT      #
# main.cpp:11:   return 0;
        .loc 1 11 10
        mov     eax, 0  # _5,
# main.cpp:12: }
        .loc 1 12 1
        leave
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc

We also use -masm=dialect with intel to produce code optimized for the most current Intel processors but in this case we are using Intel ASM Syntax for the assembly generation. I do personally prefer this syntax branch.

For the assembly examples, we use the Compiler Explorer as demangling identifiers for the assembly comes in built-in and makes the code more readable and easier to follow. The Complier Explorer also allows you to follow the code by hovering over a line or scrolling to source, pointing you directly to the assembly conversion. Anyway, see what works best for you!

We will have two snippets where we introduce the C high-level source code and show the generated assembly code so we can make comparisons and draw conclusions - even so subtle in some cases. But don't forget that any assembly instruction can make a difference.

Headers and Macros

For benchmarking, we pretty much use printf and clock() defined as the following macros.

#include <stdio.h>
#include <time.h>

#define start_time clock_t s_t_a_r_t = clock();
#define end_time printf("[CPU Time Used: %f]\n", (double)(clock() -          s_t_a_r_t) / CLOCKS_PER_SEC);

Switch case VS If-else

Let's start by comparing the if-else to the switch statement. Note that in most of the examples we don't use any optimization flags by default since we need the most accurate assembly translation line by line, keeping our code "clean" in that we can also accurately benchmark our implementations.

For example, if we turn on the -O1 flag, the compiler, if finds appropriate, will generate a jump table even in the if-else example as it determines the values are densely packed. For more information, please refer to Using the GNU Compiler Collection | 3.12 Options That Control Optimization.

🚧 Terminology

Beware that the "packed" word is used in relation to jump tables and has nothing to do with C Packed Structures.

You might find the following code examples, for a lack of a better word, dumb since we are just having integers that are assigned based on their value so why can't we just go with:

r = type;

or just use the Using the GNU Compiler Collection | 6.18.11 Case Ranges.

Well, that wouldn't be the point of this blog. The individual r=0, r=1, ..., r=n are supposed to represent our code blocks executed at the point they are reached. Another reason is that we wanted to trick the compiler into generating separate, most simple, labels for each of the conditions.

The whole point is to make assembly output smaller so that we can focus on the important assembly instructions at hand such as CALL, CMP, JMP, etc.

The reason behind naming our parameter type is that in the context of creating a dynamic programming language where the current member value is wrapped in a union, you would want an enum in the switch case to most efficiently determine which member is active to apply certain operations against. Check out Union-like classes.

If-else statement

The following is the if-else chain of statements comparing the unsigned integers 0 through 10.

📘 Note

In the examples like this, we use the volatile keyword in order to prevent the compiler from eliminating our code in some cases where the -O1 (level-1), -O2 (level-2) or -O3 (level-3) optimizations are added, which is a set/collection of optimization flags for the C/C++ code. For more information, see Using the GNU Compiler Collection | 3.12 Options That Control Optimization.

We are not going to go into too much details on these flags in this blog particularly due to the fact that even if individual flags are specified, most optimizations are completely disabled if an -O level is not set. Thereby, it is much harder to see under the hood of these gcc optimizations and is entirely another discussion for another day.

void _if_run(unsigned int type) {

  volatile int r; // NOTE: preventing compiler from optimizing it out

  if(type == 0) {
    r = 0;
  } else if(type == 1) {
    r = 1;
  } else if(type == 2) {
    r = 2;
  } else if(type == 3) {
    r = 3;
  } else if(type == 4) {
    r = 4;
  } else if(type == 5) {
    r = 5;
  } else if(type == 6) {
    r = 6;
  } else if(type == 7) {
    r = 7;
  } else if(type == 8) {
    r = 8;
  } else if(type == 9) {
    r = 9;
  } else if(type == 10) {
    r = 10;
  } else {
    r = 11;
  }

}

To stay consistent with the switch case example, we use the unsigned int that represents the range of 0 to 4,294,967,295. The reason being is the switch case must start from 0 for the jump table to get generated effectively. Since in C, it is not possible to have array subscripts below 0. This also helps with the switch case in order to have only one CMP instruction before the JMP instructions so that it can decide whether to jump straight to the default or go on to the jump table where goto jumps to the corresponding label.

For example, this code takes two CMP instructions.

void _cmp(int t) {
    if(t < 0 || t > 5) {
        return;
    }
}

_cmp:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], edi
        cmp     DWORD PTR [rbp-4], 0
        js      .L19
        cmp     DWORD PTR [rbp-4], 5
        jmp     .L16
.L19:
        nop
.L16:
        pop     rbp
        ret

Whereas

void _cmp(unsigned int t) {
    if(t > 5) {
        return;
    }
}

Only one:

_cmp:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], edi
        cmp     DWORD PTR [rbp-4], 5
        pop     rbp
        ret

In the assembly output of the C high-level code, we can see that for each statement the GCC compiler uses CMP, which is of course O(1) in the best case given that we match the first condition.

On the other hand, if none match - the point to get to else equates to the time complexity of O(n) being the worst case. The average time complexity would really depend on what the code does and how frequently the value to compare proceeds further into the statement, which means more CMPs before the condition is met.

This is where the switch case comes in to save the day with the average time complexity of O(1) but we have to make sure that the switch case is optimized into a jump table, which we cover in the next section.

_if_run:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        cmp     DWORD PTR [rbp-20], 0
        jne     .L32
        mov     DWORD PTR [rbp-4], 0
        jmp     .L44
.L32:
        cmp     DWORD PTR [rbp-20], 1
        jne     .L34
        mov     DWORD PTR [rbp-4], 1
        jmp     .L44
.L34:
        cmp     DWORD PTR [rbp-20], 2
        jne     .L35
        mov     DWORD PTR [rbp-4], 2
        jmp     .L44
.L35:
        cmp     DWORD PTR [rbp-20], 3
        jne     .L36
        mov     DWORD PTR [rbp-4], 3
        jmp     .L44
.L36:
        cmp     DWORD PTR [rbp-20], 4
        jne     .L37
        mov     DWORD PTR [rbp-4], 4
        jmp     .L44
.L37:
        cmp     DWORD PTR [rbp-20], 5
        jne     .L38
        mov     DWORD PTR [rbp-4], 5
        jmp     .L44
.L38:
        cmp     DWORD PTR [rbp-20], 6
        jne     .L39
        mov     DWORD PTR [rbp-4], 6
        jmp     .L44
.L39:
        cmp     DWORD PTR [rbp-20], 7
        jne     .L40
        mov     DWORD PTR [rbp-4], 7
        jmp     .L44
.L40:
        cmp     DWORD PTR [rbp-20], 8
        jne     .L41
        mov     DWORD PTR [rbp-4], 8
        jmp     .L44
.L41:
        cmp     DWORD PTR [rbp-20], 9
        jne     .L42
        mov     DWORD PTR [rbp-4], 9
        jmp     .L44
.L42:
        cmp     DWORD PTR [rbp-20], 10
        jne     .L43
        mov     DWORD PTR [rbp-4], 10
        jmp     .L44
.L43:
        mov     DWORD PTR [rbp-4], 11
.L44:
        nop
        pop     rbp
        ret

Switch Case

In case(no pun intended) you are wondering why we are not using the enum keyword and the enumeration values, that is to demonstrate that those enums are essentially unsigned int and are starting from 0. So if you are using enum, the assembly outputs are gonna be exactly the same when it comes to the switch statement. If you are looking for this enum version of the code, please check out _switch_enum_run at the Github repository source code or Default Case: Can we do without it section.

For example,

#include <stdio.h>
#include <assert.h>

enum N {
    N0,
    N1,
    N2,
    N3,
};

int main()
{

    assert(sizeof(unsigned int) == sizeof(N0));
    // Cast to unsigned int
    assert((unsigned int)N0 == 0);
    // No need to cast if not necessary
    assert(N0 == 0);

    return 0;
}

🚧 Note

Please understand that I am not advising casting enums in any shape or form.

If you are using func(enum T), always use one of the enum values directly - not unsigned int unless your function is func(unsigned int). It doesn't necessarily take a toll on the runtime performance but it is a bit unconventional in the high-level code.

The following is a simple switch case of 0 through 10 with the default case.

void _switch_run(unsigned int type) {

  volatile int r; // NOTE: preventing compiler from optimizing it out

  switch(type) {
    case 0: {
      r = 0;
      break;
    }
    case 1: {
      r = 1;
      break;
    }
    case 2: {
      r = 2;
      break;
    }
    case 3: {
      r = 3;
      break;
    }
    case 4: {
      r = 4;
      break;
    }
    case 5: {
      r = 5;
      break;
    }
    case 6: {
      r = 6;
      break;
    }
    case 7: {
      r = 7;
      break;
    }
    case 8: {
      r = 8;
      break;
    }
    case 9: {
      r = 9;
      break;
    }
    case 10: {
      r = 10;
      break;
    }
    default: {
      r = 11;
      break;
    }
  }

}

_switch_run:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        cmp     DWORD PTR [rbp-20], 10
        ja      .L2
        mov     eax, DWORD PTR [rbp-20]
        mov     rax, QWORD PTR .L4[0+rax*8]
        jmp     rax
.L4:
        .quad   .L14
        .quad   .L13
        .quad   .L12
        .quad   .L11
        .quad   .L10
        .quad   .L9
        .quad   .L8
        .quad   .L7
        .quad   .L6
        .quad   .L5
        .quad   .L3
.L14:
        mov     DWORD PTR [rbp-4], 0
        jmp     .L15 # break
.L13:
        mov     DWORD PTR [rbp-4], 1
        jmp     .L15
.L12:
        mov     DWORD PTR [rbp-4], 2
        jmp     .L15
.L11:
        mov     DWORD PTR [rbp-4], 3
        jmp     .L15
.L10:
        mov     DWORD PTR [rbp-4], 4
        jmp     .L15
.L9:
        mov     DWORD PTR [rbp-4], 5
        jmp     .L15
.L8:
        mov     DWORD PTR [rbp-4], 6
        jmp     .L15
.L7:
        mov     DWORD PTR [rbp-4], 7
        jmp     .L15
.L6:
        mov     DWORD PTR [rbp-4], 8
        jmp     .L15
.L5:
        mov     DWORD PTR [rbp-4], 9
        jmp     .L15
.L3:
        mov     DWORD PTR [rbp-4], 10
        jmp     .L15
.L2: # Default Case Label
        mov     DWORD PTR [rbp-4], 11
        nop
.L15: # Break Label
        nop
        pop     rbp
        ret

These instruction are pretty straightforward to comprehend. First, we have the CMP instruction that checks if the unsigned integer is in the bounds of 10. As noted above, this is the deciding instruction for whether to jump straight to the default case.

cmp     DWORD PTR [rbp-20], 10
ja      .L2

JA is a jump when the comparison is unsigned. This makes sense given that we are using unsigned int to compare.

Roughly, the C equivalent of this code is the following:

void _switch_run(unsigned int type) {
  if(type > 10) {
    goto L2;
  }
  // ...
}

Finally, we get to the jump table:

        mov     eax, DWORD PTR [rbp-20]
        mov     rax, QWORD PTR .L4[0+rax*8]
        jmp     rax
.L4:
        .quad   .L14
        .quad   .L13
        .quad   .L12
        .quad   .L11
        .quad   .L10
        .quad   .L9
        .quad   .L8
        .quad   .L7
        .quad   .L6
        .quad   .L5
        .quad   .L3

We can see that the compiler has essentially generated the .L4, a static array of labels that represent the code blocks that we defined in our switch case. The cost of this JMP is constant O(1).

In C, this code is roughly equivalent to the following, which is covered thoroughly in the Implementing Switch Case section.

static void* cases[] = {
  &&l00,
  &&l01, 
  &&l02,
  &&l03,
  &&l04,
  &&l05,
  &&l06,
  &&l07,
  &&l08,
  &&l09,
  &&l10,
};


// CMP For the default case: "cmp     DWORD PTR [rbp-20], 10"
if(v > 10) {
  goto _default;
}

goto *cases[v];

volatile int r;

l00: {
   r = 0;
   goto defer; // break
 }
l01: {
   r = 1;
   goto defer; // break
 }
l02: {
   r = 2;
   goto defer; // break
 }
/* ... */
l10: {
     r = 10;
     goto defer;
   }


_default: {
   r = 11;
   goto defer; // break
}

// For us, defer serves as the alternative to where the "break" keyword jumps to as far as the switch case and jump table
defer: {
     return;
   }

Benchmarking the two

Finally, let's put our code to use and benchmark to demonstrate our assembly breakdown at runtime.

We are going to use the value of 10 since that is the last condition of the two statements. That way, we are forcing the worst case of if-else and confirming that the switch case is the constant time complexity: O(1).

int main() {
  volatile unsigned int value = 10; // NOTE: preventing compiler from optimizing it out
  {
    printf("_switch_run\n");
    for(int i = 0; i < 10; i++) {
      start_time;

      for(int i = 0; i < 1000000; i++) {
        _switch_run(value);
      }

      end_time;
    }
    printf("_switch_run\n");
  }

  {
    printf("_if_run\n");
    for(int i = 0; i < 10; i++) {
      start_time;

      for(int i = 0; i < 1000000; i++) {
        _if_run(value);
      }

      end_time;
    }
    printf("_if_run\n");
  }

  return 0;
}

The code produces the following output:

_switch_run
[CPU Time Used: 0.002417]
[CPU Time Used: 0.002171]
[CPU Time Used: 0.002241]
[CPU Time Used: 0.002250]
[CPU Time Used: 0.002212]
[CPU Time Used: 0.002244]
[CPU Time Used: 0.002201]
[CPU Time Used: 0.002209]
[CPU Time Used: 0.002329]
[CPU Time Used: 0.002238]
_switch_run
_if_run
[CPU Time Used: 0.005600]
[CPU Time Used: 0.005801]
[CPU Time Used: 0.005637]
[CPU Time Used: 0.005700]
[CPU Time Used: 0.005804]
[CPU Time Used: 0.005658]
[CPU Time Used: 0.005693]
[CPU Time Used: 0.005757]
[CPU Time Used: 0.005792]
[CPU Time Used: 0.005832]
_if_run

Out-of-Bounds Benchmark

Let's see what's the case if we provide the value that matches none of our conditions.

With the switch case, that would be the default label and with the if-else set: the else statement.

int main() {
  volatile unsigned int value = 11; // NOTE: preventing compiler from optimizing it out
  {
    printf("_switch_run\n");
    for(int i = 0; i < 10; i++) {
      start_time;

      for(int i = 0; i < 1000000; i++) {
        _switch_run(value);
      }

      end_time;
    }
    printf("_switch_run\n");
  }

  {
    printf("_if_run\n");
    for(int i = 0; i < 10; i++) {
      start_time;

      for(int i = 0; i < 1000000; i++) {
        _if_run(value);
      }

      end_time;
    }
    printf("_if_run\n");
  }

  return 0;
}

In this particular scenario, the switch comes out victorious again but even by a larger margin, as we can see from the following results.

_switch_run
[CPU Time Used: 0.001884]
[CPU Time Used: 0.001813]
[CPU Time Used: 0.001726]
[CPU Time Used: 0.002118]
[CPU Time Used: 0.001847]
[CPU Time Used: 0.001746]
[CPU Time Used: 0.001817]
[CPU Time Used: 0.001675]
[CPU Time Used: 0.001713]
[CPU Time Used: 0.001679]
_switch_run
_if_run
[CPU Time Used: 0.005802]
[CPU Time Used: 0.005815]
[CPU Time Used: 0.005619]
[CPU Time Used: 0.005913]
[CPU Time Used: 0.005581]
[CPU Time Used: 0.005722]
[CPU Time Used: 0.005725]
[CPU Time Used: 0.005770]
[CPU Time Used: 0.005779]
[CPU Time Used: 0.005683]
_if_run

This is due to the fact that out of all this code for the _switch_run:

_switch_run:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        cmp     DWORD PTR [rbp-20], 10
        ja      .L18
        mov     eax, DWORD PTR [rbp-20]
        mov     rax, QWORD PTR .L20[0+rax*8]
        jmp     rax
.L20:
        .quad   .L30
        .quad   .L29
        .quad   .L28
        .quad   .L27
        .quad   .L26
        .quad   .L25
        .quad   .L24
        .quad   .L23
        .quad   .L22
        .quad   .L21
        .quad   .L19

It is only this portion of the code that actually runs:

_switch_run:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        cmp     DWORD PTR [rbp-20], 10
        ja      .L18
.L18:
        mov     DWORD PTR [rbp-4], 11
        nop

Once the CMP matches and JA jumps to .L18, that is the end of our function lifetime. In other words, it doesn't even use the jump table.

Turning a switch case into a jump table

The GCC compiler is not always going to turn a switch case into a jump table. Only when there are multiple cases does the compiler (even consider to) make that optimization.

For example, if we take this code into consideration with its respective assembly output.

void _switch_test(unsigned int type) {
  volatile int r; // NOTE: preventing compiler from optimizing it out

  switch(type) {
    case 0: {
      r = 0;
      break;
    }
    case 1: {
      r = 1;
      break;
    }
    case 2: {
      r = 2;
      break;
    }
    case 3: {
        r = 3;
        break;
    }
    default: {
        r = 11;
        break;
    }
  }
}

This is basically an if-else statement, which we can tell by the CMP and JE(Jump if Equal) instructions. There is an interesting detail that all of these values are compared backwards - from 3 rather than from 0 as opposed to the if-else example.

_switch_test:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        cmp     DWORD PTR [rbp-20], 3
        je      .L18
        cmp     DWORD PTR [rbp-20], 3
        ja      .L19
        cmp     DWORD PTR [rbp-20], 2
        je      .L20
        cmp     DWORD PTR [rbp-20], 2
        ja      .L19
        cmp     DWORD PTR [rbp-20], 0
        je      .L21
        cmp     DWORD PTR [rbp-20], 1
        je      .L22
        jmp     .L19
.L21:
        mov     DWORD PTR [rbp-4], 0
        jmp     .L23
.L22:
        mov     DWORD PTR [rbp-4], 1
        jmp     .L23
.L20:
        mov     DWORD PTR [rbp-4], 2
        jmp     .L23
.L18:
        mov     DWORD PTR [rbp-4], 3
        jmp     .L23
.L19:
        mov     DWORD PTR [rbp-4], 11
        nop
.L23:
        nop
        pop     rbp
        ret

Even by enabling the -O3 optimizations, this code is not turned into a jump table.

The GCC compiler decides whether to generate a jump table given there is enough densely packed values.

So for this code, we do get the jump table generated.

void _switch_test(unsigned int type) {
  volatile int r; // NOTE: preventing compiler from optimizing it out

  switch(type) {
    case 0: {
      r = 0;
      break;
    }
    case 1: {
      r = 1;
      break;
    }
    case 2: {
      r = 2;
      break;
    }
    case 3: {
        r = 3;
        break;
    }
    case 4: {
        r = 4;
        break;
    }
    default: {
        r = 11;
        break;
    }
  }
}

There is our jump table by the name of .L20!

_switch_test:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        cmp     DWORD PTR [rbp-20], 4
        ja      .L18
        mov     eax, DWORD PTR [rbp-20]
        mov     rax, QWORD PTR .L20[0+rax*8]
        jmp     rax
.L20:
        .quad   .L24
        .quad   .L23
        .quad   .L22
        .quad   .L21
        .quad   .L19
.L24:
        mov     DWORD PTR [rbp-4], 0
        jmp     .L25
.L23:
        mov     DWORD PTR [rbp-4], 1
        jmp     .L25
.L22:
        mov     DWORD PTR [rbp-4], 2
        jmp     .L25
.L21:
        mov     DWORD PTR [rbp-4], 3
        jmp     .L25
.L19:
        mov     DWORD PTR [rbp-4], 4
        jmp     .L25
.L18:
        mov     DWORD PTR [rbp-4], 11
        nop
.L25:
        nop
        pop     rbp
        ret

With all of that being said, there is a way to force generating a jump at all times by specifying --param case-values-threshold=1 as one of the GCC command options.

According to Using the GNU Compiler Collection Documentation:

case-values-threshold
- The smallest number of different values for which it is best to use a jump-table instead of a tree of conditional branches. If the value is 0, use the default for the machine.
-fno-jump-tables
- Do not use jump tables for switch statements even where it would be more effi- cient than other code generation strategies. This option is of use in conjunction with ‘-fpic’ or ‘-fPIC’ for building code that forms part of a dynamic linker and cannot reference the address of a jump table. On some targets, jump tables do not require a GOT and this option is not needed.

📘 Note

The closest "opposite" to case-values-threshold probably is -fno-jump-tables where no matter the number of values/cases, that block is turned into a series of CMP and JMP instructions.

As a side note, there is the option called -fjump-tables that I managed to dig out of Using the GNU Compiler Collection Documentation but I am assuming it is the default option since I couldn't find any description of it and it is the -fno-jump-tables, if specified, that overrides it.

gcc src/main.cpp -Werror -g -o output.s -masm=intel -fverbose-asm -S --param case-values-threshold=1

Even if we have a switch case such as the following.

void _switch_test(unsigned int type) {
  volatile int r; // NOTE: preventing compiler from optimizing it out

  switch(type) {
    case 0: {
      r = 0;
      break;
    }
    case 1: {
      r = 1;
      break;
    }
    default: {
        r = 11;
        break;
    }
  }
}

The output is:

_switch_test:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        cmp     DWORD PTR [rbp-20], 1
        ja      .L18
        mov     eax, DWORD PTR [rbp-20]
        mov     rax, QWORD PTR .L20[0+rax*8]
        jmp     rax
.L20:
        .quad   .L21
        .quad   .L19
.L21:
        mov     DWORD PTR [rbp-4], 0
        jmp     .L22
.L19:
        mov     DWORD PTR [rbp-4], 1
        jmp     .L22
.L18:
        mov     DWORD PTR [rbp-4], 11
        nop

From this, we can conclude that using a jump table for as few as 1, 2, or 3 values is redundant and rather impractical at the same time.

For example, the following code is pragmatically and assembly-wise much more effective since there is simply CMP and JE and it doesn't abuse the data segment in the case of inlining the same function. For more on the latter, see Inlining Switch Case.

enum class Value {
    Number,
    String,
    Array,
    Dict,
    Iterator,
    // ...
};

void _iterate(Value type) {
    if(type != Value::Iterator) {
        throw std::runtime_error("not an iterator");
    }
    /* Handle the iterator instance */
    return; 
}

Is there a limit for the values of a switch case?

Since a jump table is basically a static array, there should be some limit of how many values we can pack into that jump table.

There is no particular way to explicitly test when the jump table isn't used in case there are thousands upon thousands of cases - unless we want to torture our computer and buy a new one any time soon so we can use a script like this.

if __name__ == '__main__':
  code = '''
void __switch_test(unsigned int type) {
  volatile int r; // NOTE: preventing compiler from optimizing it out

  switch(type) {
  ''';
  for i in range(0, 100000):
      code += 'case ' + str(i) + ':{ \n' + ' r=' + str(i) + ';\n break;\n}\n'

  code += 'default: {\n r = 11;\n break;\n}\n'
  code += '}'
  code += '}'

  print(code)

python3 generate.py > _out.c && gcc _out.c -g -o output.s -masm=intel -fverbose-asm -S

To answer the question in the title, there is no limit for the GCC compiler not to make it a jump table given that all the values are densely packed.

As long as there is memory, the output is going to be a jump table. Please, check out Using the GNU Compiler Collection | 4.12 Statements.

There are some options to consider for restricting the usage of jump tables.

-fno-jump-tables
- Do not use jump tables for switch statements even where it would be more efficient than other code generation strategies. This option is of use in conjunction with ‘-fpic’ or ‘-fPIC’ for building code that forms part of a dynamic linker and cannot reference the address of a jump table. On some targets, jump tables do not require a GOT and this option is not needed.
jump-table-max-growth-ratio-for-size
- The maximum code size growth ratio when expanding into a jump table (in percent). The parameter is used when optimizing for size.
jump-table-max-growth-ratio-for-speed
- The maximum code size growth ratio when expanding into a jump table (in percent). The parameter is used when optimizing for speed.

Same as the compiler not using the jump table in the example above, note that with -fno-jump-tables, the GCC compiler creates a set of CMP and JMP instructions in reverse order to the original values defined.

Breaking switch case: Non-packed values

This is a rather weird use case for the switch statement but worth exploring to see what happens if we get "out of the way of the packed values".

void _switch_unpacked(unsigned int type) {
  volatile int r; // NOTE: preventing compiler from optimizing it out

  switch(type) {
    case 0: {
      r = 0;
      break;
    }
    case 1: {
      r = 1;
      break;
    }
    case 2: {
      r = 2;
      break;
    }
    case 3: {
        r = 3;
        break;
    }
    case 4: {
        r = 4;
        break;
    }
    case 5: {
        r = 5;
        break;
    }
    case 30: {
        r = 30;
        break;
    }
    default: {
        r = 11;
        break;
    }
  }
}

The GCC compiler handles this code in a very interesting way. It fills all the cases in between 4 and 30 with blanks. These all lead to the same .L18 default case jump.

_switch_unpacked:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        cmp     DWORD PTR [rbp-20], 30
        ja      .L18
        mov     eax, DWORD PTR [rbp-20]
        mov     rax, QWORD PTR .L20[0+rax*8]
        jmp     rax
.L20:
        .quad   .L26
        .quad   .L25
        .quad   .L24
        .quad   .L23
        .quad   .L22
        .quad   .L21
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L18
        .quad   .L19
.L26:
        mov     DWORD PTR [rbp-4], 0
        jmp     .L27
.L25:
        mov     DWORD PTR [rbp-4], 1
        jmp     .L27
.L24:
        mov     DWORD PTR [rbp-4], 2
        jmp     .L27
.L23:
        mov     DWORD PTR [rbp-4], 3
        jmp     .L27
.L22:
        mov     DWORD PTR [rbp-4], 4
        jmp     .L27
.L21:
        mov     DWORD PTR [rbp-4], 5
        jmp     .L27
.L19:
        mov     DWORD PTR [rbp-4], 30
        jmp     .L27
.L18:
        mov     DWORD PTR [rbp-4], 11
        nop
.L27:
        nop
        pop     rbp
        ret

It is rational to think that if we say 100 instead of 30, the compiler doesn't waste too much space with all the blanks that point to the default case and instead needs to use another CMP instruction. This is exactly the case.

void _switch_unpacked(unsigned int type) {
  volatile int r; // NOTE: preventing compiler from optimizing it out

  switch(type) {
    /* ... */
    case 5: {
        r = 5;
        break;
    }
    case 100: {
        r = 100;
        break;
    }
    default: {
        r = 11;
        break;
    }
  }
}

We have two CMP:

First CMP: The value is above 5 and jump to check (CMP) if it is 100

            cmp     DWORD PTR [rbp-20], 5
            ja      .L18

    # ...
    .L18:
            cmp     DWORD PTR [rbp-20], 100
            je      .L27
            jmp     .L19
    ```



- Second `CMP`: Checks if the value is above `5` - if that's _true(sets the zero flag)_, jump to the `default`. Otherwise, proceed with the jump table where all of the values are _still_ packed.

  -

 ```assembly
            cmp     DWORD PTR [rbp-20], 5
            ja      .L19
            mov     eax, DWORD PTR [rbp-20]
            mov     rax, QWORD PTR .L21[0+rax*8]
            jmp     rax
    .L21:
            .quad   .L26
            .quad   .L25
            .quad   .L24
            .quad   .L23
            .quad   .L22
            .quad   .L20
    # ...
    .L19:
            mov     DWORD PTR [rbp-4], 11
            nop
    ```






```assembly
_switch_unpacked:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        cmp     DWORD PTR [rbp-20], 5
        ja      .L18
        cmp     DWORD PTR [rbp-20], 5
        ja      .L19
        mov     eax, DWORD PTR [rbp-20]
        mov     rax, QWORD PTR .L21[0+rax*8]
        jmp     rax
.L21:
        .quad   .L26
        .quad   .L25
        .quad   .L24
        .quad   .L23
        .quad   .L22
        .quad   .L20
.L18:
        cmp     DWORD PTR [rbp-20], 100
        je      .L27
        jmp     .L19
.L26:
        mov     DWORD PTR [rbp-4], 0
        jmp     .L28
.L25:
        mov     DWORD PTR [rbp-4], 1
        jmp     .L28
.L24:
        mov     DWORD PTR [rbp-4], 2
        jmp     .L28
.L23:
        mov     DWORD PTR [rbp-4], 3
        jmp     .L28
.L22:
        mov     DWORD PTR [rbp-4], 4
        jmp     .L28
.L20:
        mov     DWORD PTR [rbp-4], 5
        jmp     .L28
.L27:
        mov     DWORD PTR [rbp-4], 100
        jmp     .L28
.L19:
        mov     DWORD PTR [rbp-4], 11
        nop
.L28:
        nop
        pop     rbp
        ret

These two CMPs may appear to be a little unoptimized since they do pretty much the same thing. So let's go ahead and turn on the -O1 optimizations:

_switch_unpacked:
        cmp     edi, 5
        ja      .L2
        ja      .L3
        mov     edi, edi
        jmp     [QWORD PTR .L5[0+rdi*8]]
.L5:
        .quad   .L10
        .quad   .L9
        .quad   .L8
        .quad   .L7
        .quad   .L6
        .quad   .L4
.L2:
        cmp     edi, 100
        jne     .L3
        mov     DWORD PTR [rsp-4], 100
        ret
.L3:
        mov     DWORD PTR [rsp-4], 11
        ret

Multiple Jump Tables

If we think more and more about the case of "Using the non-packed values", the compiler cannot keep using the CMP instructions in the ranges such as [0, 1, 2, 3, 4, 5, 100, 101, 102, 103, 104, 105]. We can deduce that there are actually two sets of packed values there: 0...5 and 100...105.

Because they are two entirely separate sets, there must be an additional CMP instruction between them to check the out-of-bounds ranges and whether to jump to the default case.

Let's back up our thinking in the following example.

void _switch_unpacked(unsigned int type) {
  volatile int r; // NOTE: preventing compiler from optimizing it out

  switch(type) {
    case 0: {
      r = 0;
      break;
    }
    case 1: {
      r = 1;
      break;
    }
    case 2: {
      r = 2;
      break;
    }
    case 3: {
        r = 3;
        break;
    }
    case 4: {
        r = 4;
        break;
    }
    case 5: {
        r = 5;
        break;
    }
    case 100: {
        r = 100;
        break;
    }
    case 101: {
        r = 101;
        break;
    }
    case 102: {
        r = 102;
        break;
    }
    case 103: {
        r = 103;
        break;
    }
    case 104: {
        r = 104;
        break;
    }
    case 105: {
        r = 105;
        break;
    }
    default: {
        r = 11;
        break;
    }
  }
}

In this assembly output, there are two jump tables - separated by their respective CMP instructions.

.L29: 0...5 range jump table
.L22: 100...105 range jump table

_switch_unpacked:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        cmp     DWORD PTR [rbp-20], 5
        ja      .L18
        jmp     .L37
.L35:
        mov     eax, DWORD PTR [rbp-20]
        sub     eax, 100
        cmp     eax, 5
        ja      .L20
        mov     eax, eax
        mov     rax, QWORD PTR .L22[0+rax*8]
        jmp     rax
.L22:
        .quad   .L27
        .quad   .L26
        .quad   .L25
        .quad   .L24
        .quad   .L23
        .quad   .L21
.L37:
        cmp     DWORD PTR [rbp-20], 5
        ja      .L20
        mov     eax, DWORD PTR [rbp-20]
        mov     rax, QWORD PTR .L29[0+rax*8]
        jmp     rax
.L29:
        .quad   .L34
        .quad   .L33
        .quad   .L32
        .quad   .L31
        .quad   .L30
        .quad   .L28
.L18:
        cmp     DWORD PTR [rbp-20], 105
        ja      .L20
        cmp     DWORD PTR [rbp-20], 100
        jnb     .L35
        jmp     .L20
.L34:
        mov     DWORD PTR [rbp-4], 0
        jmp     .L36
.L33:
        mov     DWORD PTR [rbp-4], 1
        jmp     .L36
.L32:
        mov     DWORD PTR [rbp-4], 2
        jmp     .L36
.L31:
        mov     DWORD PTR [rbp-4], 3
        jmp     .L36
.L30:
        mov     DWORD PTR [rbp-4], 4
        jmp     .L36
.L28:
        mov     DWORD PTR [rbp-4], 5
        jmp     .L36
.L27:
        mov     DWORD PTR [rbp-4], 100
        jmp     .L36
.L26:
        mov     DWORD PTR [rbp-4], 101
        jmp     .L36
.L25:
        mov     DWORD PTR [rbp-4], 102
        jmp     .L36
.L24:
        mov     DWORD PTR [rbp-4], 103
        jmp     .L36
.L23:
        mov     DWORD PTR [rbp-4], 104
        jmp     .L36
.L21:
        mov     DWORD PTR [rbp-4], 105
        jmp     .L36
.L20:
        mov     DWORD PTR [rbp-4], 11
        nop
.L36:
        nop
        pop     rbp
        ret

If-else as a jump table

With no extra optimizations such as -O1, -O2 or -O3, the if-else statement is a set of CMP and JMP instructions checking each value as detailed out above.

Much to our surprise, if the conditional values are compared via the equal-to operator and are densely packed, the -O1 optimizations can do their magic and turn the if-else statements into a jump table.

gcc src/main.cpp -g -o output.s -masm=intel -fverbose-asm -S -O1

void _if_run(unsigned int type) {

  volatile int r; // NOTE: preventing compiler from optimizing it out

  if(type == 0) {
    r = 0;
  } else if(type == 1) {
    r = 1;
  } else if(type == 2) {
    r = 2;
  } else if(type == 3) {
    r = 3;
  } else if(type == 4) {
    r = 4;
  } else if(type == 5) {
    r = 5;
  } else if(type == 6) {
    r = 6;
  } else if(type == 7) {
    r = 7;
  } else if(type == 8) {
    r = 8;
  } else if(type == 9) {
    r = 9;
  } else if(type == 10) {
    r = 10;
  } else {
    r = 11;
  }

}

_if_run:
        cmp     edi, 10
        ja      .L85
        mov     edi, edi
        jmp     [QWORD PTR .L87[0+rdi*8]]
.L87:
        .quad   .L97
        .quad   .L96
        .quad   .L95
        .quad   .L94
        .quad   .L93
        .quad   .L92
        .quad   .L91
        .quad   .L90
        .quad   .L89
        .quad   .L88
        .quad   .L86
.L97:
        mov     DWORD PTR [rsp-4], 0
        ret
.L96:
        mov     DWORD PTR [rsp-4], 1
        ret
.L95:
        mov     DWORD PTR [rsp-4], 2
        ret
.L94:
        mov     DWORD PTR [rsp-4], 3
        ret
.L93:
        mov     DWORD PTR [rsp-4], 4
        ret
.L92:
        mov     DWORD PTR [rsp-4], 5
        ret
.L91:
        mov     DWORD PTR [rsp-4], 6
        ret
.L90:
        mov     DWORD PTR [rsp-4], 7
        ret
.L89:
        mov     DWORD PTR [rsp-4], 8
        ret
.L88:
        mov     DWORD PTR [rsp-4], 9
        ret
.L86:
        mov     DWORD PTR [rsp-4], 10
        ret
.L85:
        mov     DWORD PTR [rsp-4], 11
        ret

In my opinion, this optimization may be overkill if you are an old-school person who looks at their assembly after compiling this and saying, "Wait! I didn't use a switch case. Why is there a jump table?". For that reason, we must always stay up-to-date with the features of GCC.

📘 optimize (level, …)

Optimally in some cases, we can also declare a certain function to be level-1-optimized so that there is a clear indication in our code that the function is optimized, leaving the rest of the code with no extra optimizations if not needed. This attribute is especially effective for faster compilation times.
void _if_run (unsigned int) __attribute__ ((optimize (1)));
Even without -O1, our function is selectively optimized.
gcc src/main.cpp -g -o output.s -masm=intel -fverbose-asm -S
For more, see 6.4.1.1 Common Function Attributes | optimize (level, …).

If-else with logical || operator as a jump table

If appropriate, the compiler goes as far as to turn a series of logical OR operators of an if-else statement into a jump table given that uses the equal-to operators. From the assembly output, the way it is able to accomplish that is it looks at it as a switch case with the following:

case 0: case 1: case 2: case 3: case 4: case 5: case 6: ...

So the following if-else case is turned into a jump table with the -01 optimizations.

void _run_if(unsigned int type) {
    volatile int v;
    if(type == 1 || type == 2 || type == 3  || type == 4 || type == 5 || type == 6 || type == 7){
        v = 1;
    } else if(type == 8 || type == 9 || type == 10) {
        v = 2;
    } else if(type == 11) {
        v = 3;
    } else if(type == 12) {
        v = 4;
    } else if(type == 13) {
        v = 5;
    } else {
        v = 11;
    }
}

Assembly output code:

_run_if(unsigned int):
        cmp     edi, 13
        ja      .L2
        mov     edi, edi
        jmp     [QWORD PTR .L4[0+rdi*8]]
.L4:
        .quad   .L2
        .quad   .L8
        .quad   .L8
        .quad   .L8
        .quad   .L8
        .quad   .L8
        .quad   .L8
        .quad   .L8
        .quad   .L7
        .quad   .L7
        .quad   .L7
        .quad   .L6
        .quad   .L5
        .quad   .L3
.L8:
        mov     DWORD PTR [rsp-4], 1
        ret
.L7:
        mov     DWORD PTR [rsp-4], 2
        ret
.L6:
        mov     DWORD PTR [rsp-4], 3
        ret
.L5:
        mov     DWORD PTR [rsp-4], 4
        ret
.L3:
        mov     DWORD PTR [rsp-4], 5
        ret
.L2:
        mov     DWORD PTR [rsp-4], 11
        ret

We can even force turning the following into a jump table with:

-O1 --param case-values-threshold=1

🚧 Note

Generally speaking, the programmer should use the --param case-values-threshold=1 parameter carefully and for a good reason since it applies to all of your code.

This parameter was previously covered in the Turning a switch case into a jump table section.

void _run_if(unsigned int type) {
    volatile int v;
    if(type == 1 || type == 2 || type == 3  || type == 4 || type == 5 || type == 6 || type == 7){
        v = 1;
    } else if(type == 8 || type == 9 || type == 10) {
        v = 2;
    } else {
        v = 11;
    }
}

Implementing Switch Case

In this section, we are gonna cover two possible implementations in C but not use the switch keyword.

For the sake of simplicity, we won't be embedding assembly via 6.17.2 Extended Asm | Assembler Instructions with C Expression Operands. Even though we don't use assembly directly, we can come pretty close to the jump table implementation as the GCC compiler sees it.

The first example is taken from the Wikipedia | Branch table.

"Another simple example, this time demonstrating a jump table rather than a mere branch table. This allows program blocks outside of the currently active procedure/function to be called:"

Jump Table with function pointers

#include <stdio.h>
#include <stdlib.h>

typedef void (*Handler)(void);    /* A pointer to a handler function */

/* The functions */
void func3 (void) { printf( "3\n" ); }
void func2 (void) { printf( "2\n" ); }
void func1 (void) { printf( "1\n" ); }
void func0 (void) { printf( "0\n" ); }

Handler jump_table[4] = { func0, func1, func2, func3 };

int main (int argc, char **argv) {
    int value;

    /* Convert first argument to 0-3 integer (modulus) */
    value = atoi(argv[1]) % 4;

    /* Call appropriate function (func0 thru func3) */
    jump_table[value]();

    return 0;
}

As it implies, this is a jump table rather than a mere branch table. This jump table consists of function pointers instead labels. Labels directly use JMP instructions while the function call like this (since function pointers cannot be inlined) uses the CALL instruction. In the simplest terms, CALL pushes the address of the instruction onto the stack. This value is often referred to as the return address. Once the CALL instruction is executed, the RET instruction pops the return address off the stack. As a result, JMP instructions are faster than CALL since jumps don't involve pushing and popping via the LIFO (Last-In-First-Out) stack. For more information, check out x86 assembly language.

🚧 Note

Another major disadvantage is that, compared to labels, we cannot pass variables from the outer scopes that easily unless we pass them to function arguments as pointers, which generates into more MOV instructions before the function CALL.

It is important to note that this kind of function pointer call cannot be inlined even with the -O1, -O2 or -O3 optimizations.

To prove this point, let's time the following implementation.

Implementation

typedef void (*Handler)(volatile int*);

void func3 (volatile int* r) { *r = 3; }
void func2 (volatile int* r) { *r = 2; }
void func1 (volatile int* r) { *r = 1; }
void func0 (volatile int* r) { *r = 0; }


void func_pointer_jump_table(unsigned int type) {

  // NOTE: we use static here since we don't want this array to be initialized per call. Like this, it is preserved between function invocations.
  static Handler jump_table[4] = { func0, func1, func2, func3 };

  type = type % 4;

  volatile int r;

  jump_table[type](&r);

}

int main() {
  {
    std::cout << "func_pointer_jump_table" << std::endl;
    for(int i = 0; i < 10; i++) {
      start_time;

      for(int i = 0; i < 1000000; i++) {
        func_pointer_jump_table(0);
      }

      end_time;
    }
    std::cout << "func_pointer_jump_table" << std::endl;

  }
  return 0;
}

Benchmark Result 1

func_pointer_jump_table
[CPU Time Used: 0.005723]
[CPU Time Used: 0.005588]
[CPU Time Used: 0.005661]
[CPU Time Used: 0.005637]
[CPU Time Used: 0.005622]
[CPU Time Used: 0.005693]
[CPU Time Used: 0.005615]
[CPU Time Used: 0.005656]
[CPU Time Used: 0.005703]
[CPU Time Used: 0.005668]
func_pointer_jump_table

We can deduce that this performance is almost identical to the worst case of if-else statements. However, it can be a bit improved with the modulo operator replaced with an if statement where we can check the index (unsigned int) value is in bounds.

Benchmark Result 2

void func_pointer_jump_table(unsigned int type) {

  // NOTE: We use static here since we don't want this array to be initialized per call. Like this, it is preserved between function invocations.
  static Handler jump_table[4] = { func0, func1, func2, func3 };

  // type = type % 4; // Replace with the CMP instruction
  if(type > 3) {
    // ... Default case
    return;
  }

  int r;

  jump_table[type](&r);

}

int main() {
  {
    std::cout << "func_pointer_jump_table" << std::endl;
    for(int i = 0; i < 10; i++) {
      start_time;

      for(int i = 0; i < 1000000; i++) {
        func_pointer_jump_table(0);
      }

      end_time;
    }
    std::cout << "func_pointer_jump_table" << std::endl;

  }
  return 0;
}

func_pointer_jump_table
[CPU Time Used: 0.005522]
[CPU Time Used: 0.005371]
[CPU Time Used: 0.005440]
[CPU Time Used: 0.005628]
[CPU Time Used: 0.005685]
[CPU Time Used: 0.005464]
[CPU Time Used: 0.005547]
[CPU Time Used: 0.005558]
[CPU Time Used: 0.005492]
[CPU Time Used: 0.005472]
func_pointer_jump_table

Given the benchmark results, we are slightly faster than the modulo operator.

In assembly,

type = type % 4;

translates into

and     DWORD PTR [rbp-20], 3

if(type > 3) {
  // ... Default case
  return;
}

translates into

cmp     DWORD PTR [rbp-20], 3
ja      .L48

In the end, this is a good example to showcase the concept on a higher-level but definitely not the the main choice when it comes to implementing our own switch case.

Covered in the next section, the closest implementation to the switch case is using Using the GNU Compiler Collection | 6.18.3 Labels as Values.

Computed GOTO: Goto Jump Table with Labels

According to Using the GNU Compiler Collection | 6.18.3 Labels as Values, we have the luxury of actually making labels part of the data structures as long as they are the void* pointers. We can reference them with the unary operator &&.

Let's look at the following implementation:

void _switch_go(unsigned int v) {

  // As mentioned before, we keep the array preserved between function invocations.
  static void* cases[] = { // Jump Table
    &&l00,
    &&l01, 
    &&l02,
    &&l03,
    &&l04,
    &&l05,
    &&l06,
    &&l07,
    &&l08,
    &&l09,
    &&l10,
  };


  // CMP For the default case - also implemented by the switch case
  if(v > 10) {
    goto _default;
  }

  // Jumps to the entry
  goto *cases[v];

  volatile int r;

  l00: {
       r = 0;
       goto defer; // break
     }
  l01: {
       r = 1;
       goto defer; // break
     }
  l02: {
       r = 2;
       goto defer; // break
     }
  l03: {
         r = 3;
         goto defer; // break
       }
  l04: {
         r = 4;
         goto defer; // break
       }
  l05: {
         r = 5;
         goto defer;
       }
  l06: {
         r = 6;
         goto defer;
       }
  l07: {
         r = 7;
         goto defer;
       }
  l08: {
         r = 8;
         goto defer;
       }
  l09: {
         r = 9;
         goto defer;
       }
  l10: {
         r = 10;
         goto defer;
       }


  _default: {
       r = 11;
       goto defer; // break
  }

  // For us, defer serves as the alternative to where the "break" keyword jumps to as far as the switch case and jump table
  defer: {
         return;
       }
}

The assembly of the code above is:

cases.1:
        .quad   .L49
        .quad   .L51
        .quad   .L52
        .quad   .L53
        .quad   .L54
        .quad   .L55
        .quad   .L56
        .quad   .L57
        .quad   .L58
        .quad   .L59
        .quad   .L60
_switch_go:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        cmp     DWORD PTR [rbp-20], 10
        ja      .L63
        mov     eax, DWORD PTR [rbp-20]
        mov     rax, QWORD PTR cases.1[0+rax*8]
        nop
        jmp     rax
.L49:
        mov     DWORD PTR [rbp-4], 0
        jmp     .L50
.L51:
        mov     DWORD PTR [rbp-4], 1
        jmp     .L50
.L52:
        mov     DWORD PTR [rbp-4], 2
        jmp     .L50
.L53:
        mov     DWORD PTR [rbp-4], 3
        jmp     .L50
.L54:
        mov     DWORD PTR [rbp-4], 4
        jmp     .L50
.L55:
        mov     DWORD PTR [rbp-4], 5
        jmp     .L50
.L56:
        mov     DWORD PTR [rbp-4], 6
        jmp     .L50
.L57:
        mov     DWORD PTR [rbp-4], 7
        jmp     .L50
.L58:
        mov     DWORD PTR [rbp-4], 8
        jmp     .L50
.L59:
        mov     DWORD PTR [rbp-4], 9
        jmp     .L50
.L60:
        mov     DWORD PTR [rbp-4], 10
        jmp     .L50
.L63:
        nop
        mov     DWORD PTR [rbp-4], 11
        nop
.L50:
        nop
        pop     rbp
        ret

If we compare the switch case assembly from the example above, they are pretty identical in essence:

_switch_run:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        cmp     DWORD PTR [rbp-20], 10
        ja      .L2
        mov     eax, DWORD PTR [rbp-20]
        mov     rax, QWORD PTR .L4[0+rax*8]
        jmp     rax
.L4:
        .quad   .L14
        .quad   .L13
        .quad   .L12
        .quad   .L11
        .quad   .L10
        .quad   .L9
        .quad   .L8
        .quad   .L7
        .quad   .L6
        .quad   .L5
        .quad   .L3
.L14:
        mov     DWORD PTR [rbp-4], 0
        jmp     .L15 # break
.L13:
        mov     DWORD PTR [rbp-4], 1
        jmp     .L15
.L12:
        mov     DWORD PTR [rbp-4], 2
        jmp     .L15
.L11:
        mov     DWORD PTR [rbp-4], 3
        jmp     .L15
.L10:
        mov     DWORD PTR [rbp-4], 4
        jmp     .L15
.L9:
        mov     DWORD PTR [rbp-4], 5
        jmp     .L15
.L8:
        mov     DWORD PTR [rbp-4], 6
        jmp     .L15
.L7:
        mov     DWORD PTR [rbp-4], 7
        jmp     .L15
.L6:
        mov     DWORD PTR [rbp-4], 8
        jmp     .L15
.L5:
        mov     DWORD PTR [rbp-4], 9
        jmp     .L15
.L3:
        mov     DWORD PTR [rbp-4], 10
        jmp     .L15
.L2: # Default Case Label
        mov     DWORD PTR [rbp-4], 11
        nop
.L15: # Break Label
        nop
        pop     rbp
        ret

After all, the _switch_go function becomes difficult to maintain once we start having nested switch cases. This is when the programmer needs to be extremely cautious with the goto statements. If you insist on it, you can always write additional unit tests!

No optimization flags

_switch_go
[CPU Time Used: 0.002202]
[CPU Time Used: 0.002200]
[CPU Time Used: 0.002201]
[CPU Time Used: 0.002200]
[CPU Time Used: 0.002362]
[CPU Time Used: 0.002200]
[CPU Time Used: 0.002203]
[CPU Time Used: 0.002283]
[CPU Time Used: 0.002202]
[CPU Time Used: 0.002202]
_switch_go

With `-O2` optimizations

_switch_go
[CPU Time Used: 0.001712]
[CPU Time Used: 0.001755]
[CPU Time Used: 0.001662]
[CPU Time Used: 0.001691]
[CPU Time Used: 0.001976]
[CPU Time Used: 0.001709]
[CPU Time Used: 0.001746]
[CPU Time Used: 0.001774]
[CPU Time Used: 0.001760]
[CPU Time Used: 0.001691]
_switch_go

Switch Case with `-O1` optimizations

If we inline the _switch_run and optimize it with -O1, we are able to spot the significance.

static inline void _switch_run(unsigned int type) {
    /* ... */
}

_switch_run
[CPU Time Used: 0.000762]
[CPU Time Used: 0.000784]
[CPU Time Used: 0.000733]
[CPU Time Used: 0.000734]
[CPU Time Used: 0.000734]
[CPU Time Used: 0.000734]
[CPU Time Used: 0.000734]
[CPU Time Used: 0.000772]
[CPU Time Used: 0.000733]
[CPU Time Used: 0.000734]
_switch_run

No Inline

Without inline, we get the performance similar to the _switch_go.

_switch_run
[CPU Time Used: 0.001754]
[CPU Time Used: 0.001754]
[CPU Time Used: 0.001702]
[CPU Time Used: 0.001661]
[CPU Time Used: 0.001987]
[CPU Time Used: 0.001691]
[CPU Time Used: 0.001739]
[CPU Time Used: 0.001660]
[CPU Time Used: 0.001660]
[CPU Time Used: 0.001770]
_switch_run

This, however, depends if the compiler is able to inline a function. See -Winline.

The fact of the matter is it is possible for the compiler to inline the switch case function as opposed to the computed goto, which is covered in the next section.

Inlining Computed GOTO

🚧 Optimization Problems

The most critical downside of this implementation is that it is hard for the GCC compiler to optimize _switch_go.

To attempt to inline the Computed GOTO, we can use static inline in the function definition.

static inline void _switch_go(unsigned int v) {
  /* ... */
}

After benchmarking this code with the -O1 to try to inline it, the performance is, more or less, the same as the function without the inline.

int main() {
  volatile unsigned int value = 10;
  {
    printf("_switch_go\n");
    for(int i = 0; i < 10; i++) {
      start_time;

      for(int i = 0; i < 1000000; i++) {
        _switch_go(value);
      }

      end_time;
    }
    printf("_switch_go\n");
  }
}

_switch_go
[CPU Time Used: 0.001755]
[CPU Time Used: 0.001804]
[CPU Time Used: 0.001731]
[CPU Time Used: 0.001754]
[CPU Time Used: 0.001712]
[CPU Time Used: 0.001721]
[CPU Time Used: 0.001756]
[CPU Time Used: 0.001711]
[CPU Time Used: 0.001755]
[CPU Time Used: 0.001727]
_switch_go

.L112:
        mov     edi, DWORD PTR [rsp+28]
        call    _switch_go
        sub     ebx, 1
        jne     .L112
        call    clock

The bottom line is it cannot be inlined.

According to 6.18.3 Labels as Values,

The &&foo expressions for the same label might have different values if the containing function is inlined or cloned. If a program relies on them being always the same, `attribute((noinline,noclone)) should be used to prevent inlining and cloning. If &&foo` is used in a static variable initializer, inlining and cloning is forbidden.

We ca verify this by the following code:

static inline void _switch_go (unsigned int) __attribute__((always_inline));

error: function 'void _switch_go(unsigned int)' can never be copied because it saves address of local label in a static variable

error: function 'void _switch_go(unsigned int)' can never be inlined because it contains a computed goto

The best option here would be to add -Winline to the gcc compilation command.

According to Using the GNU Compiler Collection | 3.9 Options to Request or Suppress Warnings,

-Winline

Warn if a function that is declared as inline cannot be inlined. Even with this option, the compiler does not warn about failures to inline functions declared in system headers. The compiler uses a variety of heuristics to determine whether or not to inline a function. For example, the compiler takes into account the size of the function being inlined and the amount of inlining that has already been done in the cur- rent function. Therefore, seemingly insignificant changes in the source program can cause the warnings produced by ‘-Winline’ to appear or disappear.

gcc src/main.cpp -g -o output.s -masm=intel -fverbose-asm -S -O1 -Winline


<source>: In function 'void _switch_go(unsigned int)':
<source>:191:20: warning: function 'void _switch_go(unsigned int)' can never be copied because it saves address of local label in a static variable [-Winline]
  191 | static inline void _switch_go(unsigned int v) {
      |                    ^~~~~~~~~~
<source>: In function 'int main()':
<source>:191:20: warning: inlining failed in call to 'void _switch_go(unsigned int)': function not inlinable [-Winline]
<source>:549:19: note: called from here
  549 |         _switch_go(value);
      |         ~~~~~~~~~~^~~~~~~
ASM generation compiler returned: 0
<source>: In function 'void _switch_go(unsigned int)':
<source>:191:20: warning: function 'void _switch_go(unsigned int)' can never be copied because it saves address of local label in a static variable [-Winline]
  191 | static inline void _switch_go(unsigned int v) {
      |                    ^~~~~~~~~~
<source>: In function 'int main()':
<source>:191:20: warning: inlining failed in call to 'void _switch_go(unsigned int)': function not inlinable [-Winline]
<source>:549:19: note: called from here
  549 |         _switch_go(value);
      |         ~~~~~~~~~~^~~~~~~

Therefore, we have to consider other approaches such as 6.18.2 Locally Declared Labels and 6.18.1 Statements and Declarations in Expressions in case we need to get the value out of the nested block scope.

Switch Go Macro

Let's wrap the _switch_go inside of the macro with local labels.

#define __switch_go(type) { \
    __label__ l00, l01, l02, _default, defer; \
    static void* jtable[] = {&&l00, &&l01, &&l02}; \
    if((unsigned int)type > 2) goto _default; \
    goto* jtable[type]; \
    volatile int r; \
    l00: { \
        r = 0; \
        goto defer; \
    } \
    l01: { \
        r = 1; \
        goto defer; \
    } \
    l02: { \
        r = 2; \
        goto defer; \
    } \
    _default: { \
        r = 11; \
        goto defer; \
    } \
    defer: { \
    } \
    }

int main() {
  volatile unsigned int value3 = 2;
  {
    printf("__switch_go\n");
    for(int i = 0; i < 10; i++) {
      start_time;

      for(int i = 0; i < 1000000; i++) {
        __switch_go(value3);
      }

      end_time; 
    }
    printf("__switch_go\n");
  }
}

After benchmarking it, there is a significant speed up.

__switch_go
[CPU Time Used: 0.000851]
[CPU Time Used: 0.000759]
[CPU Time Used: 0.000760]
[CPU Time Used: 0.000714]
[CPU Time Used: 0.000795]
[CPU Time Used: 0.000771]
[CPU Time Used: 0.000789]
[CPU Time Used: 0.000781]
[CPU Time Used: 0.000733]
[CPU Time Used: 0.000771]
__switch_go

We get the same performance as inlining switch case because An Inline Function is As Fast As a Macro.

Getting the value out of the statement expression while using local labels is a bit tricky but possible:

#define switch_go(type) ({ \
    __label__ l01, l02, l03, _default, defer; \
    static void* jtable[] = { &&l01, &&l02, &&l03 }; \
    volatile int r; \
    if((unsigned int)type > 2) goto _default; \
    goto *jtable[type]; \
    l01: {\
       r = 1; \
       goto defer; \
    } \
    l02: {\
      r = 2; \
      goto defer; \
    } \
    l03: {\
     r = 3; \
     goto defer; \
    } \
    _default: { \
      r = 11; \
      goto defer; \
    } \
    defer: { \
    } \
    r; \
})

Computed GOTO: C++ Statement Expression

According to 6.18.1 Statements and Declarations in Expressions,

In G++, the result value of a statement expression undergoes array and function pointer decay, and is returned by value to the enclosing expression. For instance, if A is a class, then

        A a;

        ({a;}).Foo ()

constructs a temporary A object to hold the result of the statement expression, and that is used to invoke Foo. Therefore the this pointer observed by Foo is not the address of a.

class Foo {
    public:
        Foo() = default;


        Foo(const Foo&) {
            std::cout << "Foo()::COPY" << std::endl;
        }

        Foo(Foo&&) {
            std::cout << "Foo()::MOVE" << std::endl;
        }

        Foo&operator=(const Foo&) {
            std::cout << "Foo::operator=()::COPY" << std::endl;
            return *this;
        }
        Foo&operator=(Foo&&) {
            std::cout << "Foo::operator=()::MOVE" << std::endl;
            return *this;
        }


};

#define switch_go(type) ({ \
    __label__ l01, l02, l03, _default, defer; \
    static void* jtable[] = { &&l01, &&l02, &&l03 }; \
    Foo r; \
    if((unsigned int)type > 2) goto _default; \
    goto *jtable[type]; \
    l01: {\
       r = Foo(); \
       goto defer; \
    } \
    l02: {\
      r = Foo(); \
      goto defer; \
    } \
    l03: {\
     r = Foo(); \
     goto defer; \
    } \
    _default: { \
      r = Foo(); \
      goto defer; \
    } \
    defer: { \
    } \
    r; \
})

// Output:
// ---switch Go---
// Foo::operator=()::MOVE
// Foo()::COPY
// ---switch Go---

Local Label Concern

Local Labels, as the name suggests, are local. Meaning that a jump table is generated per individual block - each time we use our macro. The code above generates one jump table since we are in the loop.

The following isn't ideal unless we have a particular use case for it. For example, using it in extensive loops or function calls is a great trade-off.

int main() {
  __switch_go(value);
  __switch_go(value);
  __switch_go(value);
  return 0;
}

We get three jump tables.

jtable.1:
        .quad   .L124
        .quad   .L125
        .quad   .L126
jtable.2:
        .quad   .L120
        .quad   .L121
        .quad   .L122
jtable.3:
        .quad   .L116
        .quad   .L117
        .quad   .L118

Inlining Switch Case

The same assembly code is generated when inlining the switch case. When the compiler finds inappropriate to inline the switch case (and, thus, creating another jump table), it replaces it with the CALL instruction.

🚧 Note

In the case of the __switch_go macro, we are forcing the creation of a jump table each time since we are explicitly using local labels whereas with the switch case inlining - the compiler makes a better decision and doesn't waste the data segment memory with jump tables at all times. This is particularly significant if the jump table is very large. As noted above, we can always track this with the -Winline option.

Nevertheless, as mentioned if we use the __switch_go only when we need to - it is a great trade-off.

Consider the following code.

int main() {
  {
    printf("_switch_run\n");
    for(int i = 0; i < 10; i++) {
      start_time;

      for(int i = 0; i < 1000000; i++) {
        _switch_run(value);
      }

      end_time;
    }

    _switch_run(value);
    _switch_run(value);
    _switch_run(value);

    printf("_switch_run\n");
  }
  return 0;
}

The _switch_run within the loop generates:

.L125:
        mov     eax, DWORD PTR [rsp+4]
        cmp     eax, 10
        ja      .L111
        jmp     [QWORD PTR .L113[0+rax*8]]
.L113:
        .quad   .L123
        .quad   .L122
        .quad   .L121
        .quad   .L120
        .quad   .L119
        .quad   .L118
        .quad   .L117
        .quad   .L116
        .quad   .L115
        .quad   .L114
        .quad   .L112

Whereas for the three _swith_run functions outside of the loop, we have

_switch_run:
        cmp     edi, 10
        ja      .L36
        mov     edi, edi
        jmp     [QWORD PTR .L38[0+rdi*8]]
.L38:
        .quad   .L48
        .quad   .L47
        .quad   .L46
        .quad   .L45
        .quad   .L44
        .quad   .L43
        .quad   .L42
        .quad   .L41
        .quad   .L40
        .quad   .L39
        .quad   .L37
.L143:
        mov     edi, DWORD PTR [rsp+28]
        call    _switch_run
        mov     edi, DWORD PTR [rsp+28]
        call    _switch_run
        mov     edi, DWORD PTR [rsp+28]
        call    _switch_run
        mov     edi, OFFSET FLAT:.LC3
        call    puts
        mov     edi, OFFSET FLAT:.LC4
        call    puts
        mov     ebp, 10

Compiler output with -Winline:

<source>: In function 'int main()':
<source>:94:20: warning: inlining failed in call to 'void _switch_run(unsigned int)': call is unlikely and code size would grow [-Winline]
   94 | static inline void _switch_run(unsigned int type) {
      |                    ^~~~~~~~~~~
<source>:527:18: note: called from here
  527 |       _switch_run(value);
      |       ~~~~~~~~~~~^~~~~~~
<source>:94:20: warning: inlining failed in call to 'void _switch_run(unsigned int)': call is unlikely and code size would grow [-Winline]
   94 | static inline void _switch_run(unsigned int type) {
      |                    ^~~~~~~~~~~
<source>:526:18: note: called from here
  526 |       _switch_run(value);
      |       ~~~~~~~~~~~^~~~~~~
<source>:94:20: warning: inlining failed in call to 'void _switch_run(unsigned int)': call is unlikely and code size would grow [-Winline]
   94 | static inline void _switch_run(unsigned int type) {
      |                    ^~~~~~~~~~~
<source>:525:22: note: called from here
  525 |           _switch_run(value);
      |           ~~~~~~~~~~~^~~~~~~
ASM generation compiler returned: 0
<source>: In function 'int main()':
<source>:94:20: warning: inlining failed in call to 'void _switch_run(unsigned int)': call is unlikely and code size would grow [-Winline]
   94 | static inline void _switch_run(unsigned int type) {
      |                    ^~~~~~~~~~~
<source>:527:18: note: called from here
  527 |       _switch_run(value);
      |       ~~~~~~~~~~~^~~~~~~
<source>:94:20: warning: inlining failed in call to 'void _switch_run(unsigned int)': call is unlikely and code size would grow [-Winline]
   94 | static inline void _switch_run(unsigned int type) {
      |                    ^~~~~~~~~~~
<source>:526:18: note: called from here
  526 |       _switch_run(value);
      |       ~~~~~~~~~~~^~~~~~~
<source>:94:20: warning: inlining failed in call to 'void _switch_run(unsigned int)': call is unlikely and code size would grow [-Winline]
   94 | static inline void _switch_run(unsigned int type) {
      |                    ^~~~~~~~~~~
<source>:525:22: note: called from here
  525 |           _switch_run(value);
      |           ~~~~~~~~~~~^~~~~~~

GCC Loop Optimization

It is interesting to observe that with the -O1 optimization or deeper, gcc does a pretty good job of inlining a function for more efficient assembly code when necessary. For instance, expensive loops.

Given the following function:

inline void _switch_run(unsigned int) {
  // ...
}

int main() {
  volatile int c = 1;

  for(int i = 0; i < 1; i++) {
    _switch_run(c);
  }

  return 0;
}

Inlining in this case doesn't really pay off so we get the following warning:

<source>:5:14: warning: inlining failed in call to '_switch_run': call is unlikely and code size would grow [-Winline]
    5 |  inline void _switch_run(unsigned int type) {
      |              ^~~~~~~~~~~
<source>:69:12: note: called from here
   69 |            _switch_run(c);

However, if we have a loop such as:

int main() {
  volatile int c = 1;

  for(int i = 0; i < 10; i++) {
    _switch_run(c);
  }

  return 0;
}

gcc is fine with inlining it as well as nested loops:

for(int i = 0; i < 10; i++) {
  for(int j = 0; j < 100; j++) {
    _switch_run(c);
  }

}

Both of the loops above could be considered loops with parameters determined at compile time since i = 0 and i < 10 thus the compiler can make a decision whether the loop is expensive and inline the function/s in it.

For example, if we have a value that cannot be determined at compile time - the compiler goes ahead and inlines it as it is unknown how expensive the loop is going to be.

int main() {
  volatile int c = 1;
  volatile int n = 1;

  for(int i = 0; i < n; i++) {
    _switch_run(c);
  }

  return 0;
}

main:
        mov     DWORD PTR [rsp-4], 1
        mov     DWORD PTR [rsp-8], 1
        mov     eax, DWORD PTR [rsp-8]
        test    eax, eax
        jle     .L2
        mov     edx, 0
        jmp     .L17
.L15:
        mov     DWORD PTR [rsp-12], 0
.L16:
        add     edx, 1
        mov     eax, DWORD PTR [rsp-8]
        cmp     eax, edx
        jle     .L2
.L17:
        mov     eax, DWORD PTR [rsp-4]
        cmp     eax, 10
        ja      .L3
        mov     eax, eax
        jmp     [QWORD PTR .L5[0+rax*8]]
.L5:
        .quad   .L15
        .quad   .L14
        .quad   .L13
        .quad   .L12
        .quad   .L11
        .quad   .L10
        .quad   .L9
        .quad   .L8
        .quad   .L7
        .quad   .L6
        .quad   .L4

Computed GOTO: RAII Concerns

According to the GCC documentation,

Unlike a normal goto, in GNU C++ a computed goto will not call destructors for objects that go out of scope.

This is a big concern if we are jumping to computed gotos that are defined outside of the current scope. Therefore, we can't treat computed gotos as normal gotos.

Similar to the long jump, treating computed gotos loosely can result in unpredictable bugs in our code like this.

This is relevant to our discussion as there can definitely be nested switch cases.

switch(type) {
  case 0: {
    r = 0;

    switch(type1) {
      case 0: {
        // ...
        break;
      }
      default: {}
    }
  break;
  }
  // ...
}

On a higher level. we can roughly translate this into:

{
    __label__ l01, l02, l03, _default, defer; 
    static void* jtable[] = { &&l01, /* ... */ };
    if((unsigned int)type > 2) goto _default;
    goto *jtable[type];
    l01: {
       r = 0;
       {
            __label__ l01, l02, l03, _default, defer; 
            static void* jtable[] = { &&l01, /* ... */ };
            if((unsigned int)type1 > 2) goto _default;
            goto *jtable[type1]; // This line is important in order to check there are no RAII problems where the scope that is, at least, one level up doesn't get cleaned up.
            l01: {
                // ...
                goto defer;
            }
            _default: {
                // ...
                goto defer;
            }
            defer:
       }
       goto defer;
    }
    // ...
    _default: {
      // ...
      goto defer;
    }
    defer:
}

Now, consider the following code in C++:

Source Code

For the full source code of these two examples, refer to computed_goto_jmp.cpp and computed_goto_jmp.c.

int main() {

  volatile int c = 0;

  static void* table[] = { &&foo, &&bar, &&zoo };

  goto *table[0];


  foo: {
       S s;

       if(c == 100) return 0;

       c++;
       goto bar; // OK
       // goto *table[1]; // LEAK
       // goto *table[0]; // LEAK
       // goto foo; // OK

     }

  bar: {
         S s;
       }


  {
    S s;
    {
      S s;

      static void* _table[] = { &&_exit };

      // s.~S(); // NOTE: Calling this for the outer scope is a problem
      // NOTE: ONLY LEAKS WHEN THE COMPUTED GOTO BLOCK ISN'T DEFINED IN THE CURRENT SCOPE WHERE IT IS SUPPOSED TO BE RELEASED.

      // goto *table[2]; // LEAK
      // goto zoo; // OK - STILL, A NORMAL GOTO
      // goto _exit; // OK

      goto *_table[0]; // OK

      _exit: {
         return 0;
       }

    }
  }

zoo: {}

  return 0;
}

Using valgrind, it is fairly easy to conclude that there will be no leaks whatsoever as long as the computed goto is defined in the current scope where it is essentially jumped to. The edge case is jumping to a computed goto that is defined in the outer static table.

In C, it is very much possible to achieve and/or replicate this behavior and use case using the __cleanup__ attribute. For more, check out the cleanup (cleanup_function).

static inline S create_s(int n) {
  S s;

  s.data = malloc(sizeof(int)*1);

  *s.data = n;

  return s;
}

void test_goto() {
  volatile int c = 0;

  static void* table[] = { &&foo, &&bar };

  goto *table[0];


  foo: {
      S s __attribute__ ((__cleanup__(clean_up_S))) = create_s(1);

      static void* _table[] = { &&_exit };

       if(c == 100) return;

       c++;
       // goto bar; // OK
       // goto *table[1]; // LEAK
       // goto *table[0]; // LEAK
       // goto foo; // OK

       goto *_table[0]; // OK

      _exit: {
        S s __attribute__ ((__cleanup__(clean_up_S))) = create_s(1);
         return;
       }

     }

  bar: {
        S s __attribute__ ((__cleanup__(clean_up_S))) = create_s(1);
       }

  return;
}

For the full source code of these two examples, refer to computed_goto_jmp.cpp and computed_goto_jmp.c.

Customizing _switch_go

🚧 Note

This section is purely experimental and substandard.

You are free to skip it and read on if you are not interested.

What if we can find a way to optimize this implementation even more?

The only instruction that comes to mind is CMP before the assembly gets to the jump table. This has previously been mentioned in the Switch Case in the beginning of this blog.

cmp     DWORD PTR [rbp-20], 10
ja      .L17

Roughly being equivalent to:

if(type > 10) {
    goto L17;
}

Now, if we just remove that if statement - we remove the CMP. This can result in faster code.

void _switch_go(unsigned int v) {

  // As mentioned before, we keep the array preserved between function invocations.
  static void* cases[] = {
    &&l00,
    &&l01,
    &&l02,
    &&l03,
    &&l04,
    &&l05,
    &&l06,
    &&l07,
    &&l08,
    &&l09,
    &&l10,
  };


  // CMP For the default case - also implemented by the switch case
  /*
  if(v > 10) {
    goto _default;
  }
  */

  goto *cases[v];

  volatile int r;
  // ...
}

The output code now contains no CMP instructions.

_switch_go:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        mov     eax, DWORD PTR [rbp-20]
        mov     rax, QWORD PTR cases.1[0+rax*8]
        nop
        jmp     rax

Compared to:

_switch_go:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        cmp     DWORD PTR [rbp-20], 10
        ja      .L64
        mov     eax, DWORD PTR [rbp-20]
        mov     rax, QWORD PTR cases.1[0+rax*8]
        nop
        jmp     rax

Benchmark

The benchmark, without the CMP instruction, gives us about 22% faster code with no optimizations.

_switch_go
[CPU Time Used: 0.001753]
[CPU Time Used: 0.001714]
[CPU Time Used: 0.001712]
[CPU Time Used: 0.001713]
[CPU Time Used: 0.001713]
[CPU Time Used: 0.001755]
[CPU Time Used: 0.001713]
[CPU Time Used: 0.001712]
[CPU Time Used: 0.001747]
[CPU Time Used: 0.001711]
_switch_go

🚧 Warning

Removing the if statement and CMP is more performant but the cost on the programmer's side of things is that the programmer has to make their code very strict with covering all the possible values and cases since this eliminates the default case. Note that if the subscript is out of bounds - the programmer is going to end up with Segmentation fault (core dumped) at runtime. All in all, this can lead to premature optimization.

Here is the exact log from valgrind, showing that the program cannot jump to the invalid address.
valgrind -s ./out.out
_switch_go
==49387== Jump to the invalid address stated on the next line
==49387==    at 0x0: ???
==49387==    by 0x1097BC: main (in /src/out.out)
==49387==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==49387== 
==49387== 
==49387== Process terminating with default action of signal 11 (SIGSEGV)
==49387==  Bad permissions for mapped region at address 0x0
==49387==    at 0x0: ???
==49387==    by 0x1097BC: main (in /src/out.out)

Default Case: Can we do without it?

🚧 Note

This section is purely experimental and substandard.

You are free to skip it and read on if you are not interested.

In the Customizing _switch_go section, we talk about the CMP instruction that determines whether the value is out of bounds and jumps to the default case. To optimize even more, we removed that instruction by implementing a switch case of our own using labels but let's attempt to do the same for the switch statement. If you are still confused, please make sure to read Implementing Switch Case.

Our strategy here is to cover all the enumerations values so that the default case does not exist and, perhaps, no CMP instruction.

enum N {
    N0,
    N1,
    N2,
    N3,
    N4,
    N5,
    N6,
    N7
};

void _switch_default_case(enum N type) {
    volatile int r;

    switch(type) {
        case N0: {
            r = 0;
            break;
        }
        case N1: {
            r = 1;
            break;
        }
        case N2: {
            r = 2;
            break;
        }
        case N3: {
            r = 3;
            break;
        }
        case N4: {
            r = 4;
            break;
        }
        case N5: case N6: case N7: {
            r = 1000;
            break;
        }
    }
}

Even with practically covering all of the enumerations, we still end up with the CMP.

cmp     DWORD PTR [rbp-20], 7
ja      .L22

Without this CMP, the code is too obscure (prone to security breach) where someone can technically use unsigned int to get the subscript out of bounds. This results in Segmentation fault (core dumped) at runtime. This is explained in great detail in the Computed GOTO: Goto Jump Table with Labels and Customizing _switch_go.

_switch_default_case:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        cmp     DWORD PTR [rbp-20], 7
        ja      .L22
        mov     eax, DWORD PTR [rbp-20]
        mov     rax, QWORD PTR .L16[0+rax*8]
        jmp     rax
.L16:
        .quad   .L21
        .quad   .L20
        .quad   .L19
        .quad   .L18
        .quad   .L17
        .quad   .L15
        .quad   .L15
        .quad   .L15
.L21:
        mov     DWORD PTR [rbp-4], 0
        jmp     .L14
.L20:
        mov     DWORD PTR [rbp-4], 1
        jmp     .L14
.L19:
        mov     DWORD PTR [rbp-4], 2
        jmp     .L14
.L18:
        mov     DWORD PTR [rbp-4], 3
        jmp     .L14
.L17:
        mov     DWORD PTR [rbp-4], 4
        jmp     .L14
.L15:
        mov     DWORD PTR [rbp-4], 1000
        nop
.L14:
.L22:
        nop
        pop     rbp
        ret

Also note that for:

case N5: case N6: case N7: {
    r = 1000;
    break;
}

The GCC compiler recognizes the same label (.L15) and uses it to fill the three entries in the jump table:

.L16:
        .quad   .L21
        .quad   .L20
        .quad   .L19
        .quad   .L18
        .quad   .L17
        .quad   .L15
        .quad   .L15
        .quad   .L15

Conclusion

Although there is a lot to unpack in this blog, the best approach is to use the switch statement, as the GCC compiler has a hard time optimizing the high-level C implementations as discussed above. If you're determined to optimize further and want to remove any redundant ASM instructions that may impact your code, consider using 6.17.2 Extended Asm | Assembler Instructions with C Expression Operands, which allows you to craft your assembly from the ground up - untouched by the optimizations such as -O1, -O2, or -O3.

If you are interested, we can try to do that as a follow-up blog. But keep in mind that your codebase then becomes a nightmare to maintain, especially with nested switch statements.

Thank you for reading! Feel free to leave any feedback in the comments!

References

Building a simple but advanced Jsonic language using Python

Aleksandar Milenkovic — Wed, 26 Jul 2023 20:23:11 +0000

Blog on LinkedIn

Prerequisites

Source code for this blog
Python support

Layout of this guide

Motivation
Introduction
Character Stream
Prefix Checking (peek, current, advance)
Recursive Descent
Error handling
Skipping white space
Imports
From Back-end To Front-end
The Object Scope
Flags
Method Chaining
Interpreting empty object
Scoping
Expressions
Wrapping up Method Chaining
Conclusion
References

Source code for this blog:

Source Code

the little utility library we use:

utility library

Python Support

In this blog, we use Python v3.8.x but you can use v3.5 or greater. Note that the type annotation has been supported since 3.5.

This blog is a good quick start for any developer interested in building the first prototype of their own language. Advanced Python skills are, of course, optimal.

Motivation

While working for Voxgig, I have taken a lot of interest in how a prototype of cue language we have been using for our model-driven applications works behind the scenes. Just the basics of it. But even the basics seemed complicated in my eyes. So I wanted to make it seem simple and sharpen up my understanding of the language along the way. This has worked wonders for me in many ways. From why we can write

foo:bar:zoo: 1

to why JavaScript throws an error on:

console.log('hi!')
(10 + 10) * 1


/*
 * Uncaught TypeError: console.log(...) is not a function
     at <anonymous>:3:1
*/

Introduction

As developers, we’d always like to try our hand at building and customizing our own toolkit – whether that is out of curiosity or out of necessity.

This blog will give you some guidelines and basic knowledge on how to build your own basic language, in our case a Jsonic language, and customize it to your needs. A Jsonic Language is a JSON-like language with fun but useful syntax features such as expressions, scoping, calling functions, etc.

Upon reading this blog, not only will you understand the basics of how to build an advanced Jsonic language but you will use simple algorithms to do so, which will increase productivity and decrease confusion!

The prototype of our language is in Python but we try to be as abstract as possible so that you can pick a language of your choice to build your own version of this language. Of course, things like garbage collectors are built-in so we won’t cover that if you want to work with languages like C.

Character Stream

To cut right to the chase, we will leave out the implementation of the CharStream class and just demonstrate its functionality. You have the source code as your friend – in fact, the CharStream class is very straightforward and is the core of our project to begin with.

char_stream = CharStream("welcome!")
char_stream.peek() == 'w' # True
char_stream.advance() 
char_stream.peek() == 'e' # True

For prefix checking, we use peek() and current methods of the CharStream class and then consume characters with advance() that moves one character ahead and returns the current one.
Compare it to Python built-in iter:

stream = iter("welcome")

next(stream) == 'w'

next(stream) == 'e' # it is 'e' now - there isn't really a way to check the current char but not advance

Prefix checking

If the character stream peeks for a certain character, we could easily determine the type of that token right away, roll with it until the while loop is done, and just evaluate it.

We will be applying scanning, parsing and evaluation all in one go and on the fly – that's to say we are not going to generate Lexer and AST per ser. Instead, we jump straight to interpreting our object.

For a start:

def interpret_obj(char_stream: CharStream, advance: bool, ...):
  if advance:
    char_stream.advance()
  skip_space(char_stream)
  if char_stream.peek().isdigit():
    value = ''
    while char_stream.peek().isdigit():
      value += char_stream.advance()
    skip_space(char_stream)
    return int(value, 10) # base 10
...

      Snippet 1

Here, the bool advance parameter will be a help because each time we match a certain character, we might forget to consume it – so we pass True and, if necessary, False.

We come back to this logic to sort out identifiers and also introduce the flags.

def scan_id(char_stream: CharStream, advance: bool):
  if advance:
    char_stream.advance()
  value = ''
  if not char_stream.peek().isalpha():
    raise SyntaxError("Expected an identifier to start with an alpha")
  while char_stream.peek().isalpha() or char_stream.peek().isdigit():
    value += char_stream.advance()
  return value

def interpret_obj(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  ...
  elif char_stream.peek().isalpha() and flags.temFlag:
    identifier = scan_id(char_stream, False)
    skip_space(char_stream) # clear up the following white space
    if flags.isKey:
      return identifier
    if identifier not in scope.keys():
      raise NameError(identifier + " not defined!")
    return scope[identifier]
  ...

      Snippet 2

What’s more, utils.Map is similar to typical dict except that its values are not accessed just using obj['key1'] but using either obj.key1 or obj['key1'] which is, more JavaScript-like.

Check out the Python docs on setattr, getattribute and getitem, dict. More on Flags – on Flags section.

RECURSIVE DESCENT

Our little language will only use one main algorithm and still be good enough to support advanced syntax features such as: scoping, method chaining, expressions, and calling functions.

In this series, we prioritize typical JSON data that is: null, Number, String, Object, and Array.

However, this guide only shows you how to support Numbers as it is easier to make complete sense of it and you can use those same methods to scan the other types. They will easily fit the rest of the code – you just need to write a few conditions to identify those types.

For example, Arrays start with the character [ and end with ] while strings start and end with ".

Don't sweat it! This is a blog series so there will be more to come.

Error handling

It is important to detect the syntax errors. The way to handle them is by throwing exceptions!

Throwing exceptions for this kind of algorithm is ideal as it will stop all the recursive calls up to the base call no matter the depth.

Skipping white-space

To skip the white space, we simply peek for ' ' or '\n' and advance to the next character.

def skip_space(char_stream: CharStream):
  while not char_stream.is_over() and (char_stream.peek() == ' ' or char_stream.peek() == '\n'):
    char_stream.advance() # consume the white space

      Snippet 3

Imports

In this blog, we use: sys, utils and parser.

import sys # built-in python sys module
import utils # this-project-specific set of utilities – see examples: https://github.com/BeAllAround/py_utils
from parser import CharStream # library that will help us with scanning/lexical analysis

      Snippet 4

We recommend that you write your own back-end libraries as much as you can. It makes your language open to bigger features like merging nested objects such as: { a: 1, { b: 2 } } and others.

From back-end to front-end

For us, the front-end would be scanning and parsing the text so that we could evaluate it with the back-end modules:

front-end – scanning and parsing
back-end – evaluation
front-end + back-end – interpretation

Python itself is the back-end engine of this language for its built-in error handling system and methods under the hood of dict, str, list such as add, eq, getitem, etc. but we are going to take a step back and focus on the modules that are not built-in.

When scanning and parsing, we have to think about the evaluation. That is when utilities come into play depending on what we want to do.

A great example would be the deep extend function for merging objects.

merge({foo: {a: 1}}, {foo: {b:2}}) => {foo: {a: 1, b: 2}}

With that in mind, we would need a function to merge two objects, as the ones in the example above.

utils.deep_update(obj1, obj2)

The Object Scope

The aim of our language would be interpreting the object. Now that we know how to apply the prefix checking, we are all set to kick off!

If we try to interpret: "{1: 1}"

def interpret_obj(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  if advance:
    char_stream.advance();
  ...
  elif char_stream.peek() == '{':
    obj = {}
    while True:
      key = interpret_obj(char_stream, True, scope, utils.Map({'temFlag': True, 'isKey': True,}) ) # key == 1
      skip_space(char_stream)
      if char_stream.peek() == ':':
        value = interpret_obj(char_stream, True, obj, utils.Map({'temFlag': True, 'isKey': False,}) )
        utils.deep_update(obj, { key: value }) # obj now equals to "{1: 1}" – see docs: https://github.com/BeAllAround/py_utils
        if char_stream.peek() == '}':
          char_stream.advance() # eat '}'
          skip_space(char_stream)
          return obj
        elif char_stream.peek() == ',':
          continue
        else:
          raise SyntaxError("Unexpected char " + char_stream.current)
      else:
        raise SyntaxError("Unexpected char " + char_stream.current)
  else:
    raise SyntaxError("Unexpected char " + char_stream.current)

      Snippet 5

Flags

To enable and register features, we could simply use an instance of utils.Map that will contain the flags for us to use.

We could pass Booleans to our function but that would be very hard to maintain.

Compare the following two snippets:

def interpret_obj(char_stream: CharStream, ..., flags: utils.Map):
  ...
    value = interpret_obj(char_stream, ..., utils.Map({'temFlag': True, 
                                                   'isKey': False,}) )
  ...

      Snippet 6

def interpret_obj(char_stream: CharStream, ..., temFlag = False, isKey = False):
  ...
    value = interpret_obj(char_stream, ..., True, False)
  ...

      Snippet 7

As you can see, the former significantly improves readability and would simplify adding new flags as you pick up new features.

Still, this approach isn’t great and would require a bit of refactoring, which we can look at in the next volume of this series.

Method Chaining

For method chaining, we will need another infinite loop that breaks if none of our existing conditions match.

value_ptr – is just an array of one element that tries to mimic a pointer in Python or other scripting languages that don’t really have an equal.

It will help us achieve the following:

a = 1
def modify_a(a):
  a = 2
modify_a(a)
> a # still 1 but we need it to be 2

      Snippet 8

But at least, it mimics pointers in that regard:

a = [ 1 ]
def modify_a(value_ptr):
  value_ptr[0] = 2
modify(a)
> a[0] # our main value is now 2

      Snippet 9

def chain_obj(char_stream: CharStream, value_ptr: list, scope: dict):
  while True:
    if callable(value_ptr[0]) and char_stream.peek() == '(':
      args = [] # a place to store the evaluated arguments

      # evaluating "func()"
      cs = CharStream(char_stream.source, char_stream.c)
      char_stream.advance()
      skip_space(char_stream) # evaluate "func(  )"
      if char_stream.peek() == ')':
        char_stream.advance() # eat ')'
    skip_space(char_stream)
    value_ptr[0] = value_ptr[0]() # evaluate the function with no arguments passed
    continue
      else:
        char_stream.set_cs(cs) # reset the char stream to last matched '('
      while True:
        args.append(parse_obj(char_stream, True, scope, utils.Map({'temFlag': True, 'isKey': False,}) )
    if char_stream.peek() == ',':
      continue
    elif char_stream.peek() == ')':
      char_stream.advance() # eat ')'
      skip_space(char_stream)
      value_ptr[0] = value_ptr[0](*args) # evaluate the function with x number of arguments passed
      break
    else:
      raise SyntaxError("Unexpected char while evaluating a function: " + char_stream.current)

    elif type(value_ptr[0]) == dict and char_stream.peek() == '.':
      identifier = scan_id(char_stream, True)
      skip_space(char_stream)
      value_ptr[0] = value_ptr[0][identifier]
      continue

    else:
      break

      Snippet 10

This code implements obj.a.b, obj.a().b, func(1, 2), "func()() - calling functions" and vice versa depending on what you want to do.
Since our language does not support function definition, we need to pass in Python functions. After all, this will come in handy as you can add up any Python code and use it from the language code itself.
Formally, we provide some "context".

For example:

def json_export():
  scope =  {'func': lambda x,y: x+y,} # our language can call functions
  default_flags = utils.Map({})
  utils.export_json( interpret_obj(CharStream('{' + input() + '}'), False, scope, default_flags) )
  # Note that 'utils.export_json' is a custom alternative to 'json.dump' from Python Standard Library
  # more details on that here: https://docs.python.org/3/library/json.html

      Snippet 11

While on the point of printing out our final object, there is an interesting detail to point out. That is, Python actually uses sys.stdout.write(obj.repr() + '\n') to convert an object to a string and, then, show it to the console.

In this snippet, we used utils.export_json just that print uses single quotation marks to encode Python strings. "a" will be 'a' – which isn't standard JSON.

Generating out the JSON data for reuse:

To further customize our formatting, you could code your own object_to_string function:

def object_to_string(obj: dict):
  # handle obj
  return str(...)

# Afterwards, you can add it up like this:
print(object_to_string(interpret_obj(CharStream('{' + input() + '}'), False, scope, default_flags)))

      Snippet 12

To get a better sense of how you could format your object with somewhat a simple set of rules, check out the implementation of utils.export_json from the source code.

To enable the method chaining, we would turn a part of the code from Snippet 5 into:

...
  if char_stream.peek() == ':':
    value = interpret_obj(char_stream, True, scope, utils.Map({ 'isKey': False, 'temFlag': True, }) )
    value_ptr = [ value ]
    chain_main(char_stream, value_ptr, scope)
    value = value_ptr[0]
    utils.deep_update(obj, { key: value }) 
...

      Snippet 13

Or we could wrap it inside a single function for reusability.

def interpret_obj_and_chain(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  value = interpret_obj(char_stream, advance, scope, flags)
  value_ptr = [ value ]
  chain_obj(char_stream, value_ptr, scope)
  return value_ptr[0] # return the final value

      Snippet 14

Now, a part of Snippet 5 translates into

...
if char_stream.peek() == ':':
  value = interpret_obj_and_chain(char_stream, True, scope, utils.Map({'temFlag': True, 'isKey': False,}) )
  utils.deep_update(obj, { key: value })
...

      Snippet 15

Interpreting empty object

There is a special case we have yet to set. That is, interpreting {}

Let's turn a piece of Snippet 5 into

def interpret_obj(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  ...
  elif char_stream.peek() == '{':
    obj = {}
    # interpreting "{}"
    cs = CharStream(char_stream.source, char_stream.c)
    char_stream.advance()
    skip_space(char_stream) # with this, we can interpret "{  }"
    if char_stream.peek() == '}':
      char_stream.advance() # eat '}'
      skip_space(char_stream)
      return obj
    else:
      char_stream.set_cs(cs) # trace the char_stream back to last matched '{' and proceed
  ...

      Snippet 16

Scoping

Scoping, most of all, enables you to use the predefined context as detailed in Snippet 11.

To make sure we don’t mutate our context, we are going to make a copy of it into obj_scope and, from then on, use it as a dictionary to get items from.

Let’s work on Snippet 5 a bit further.

def interpret_obj(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  ...
  elif char_stream.peek() == '{':
    obj = {}
    obj_scope = {}
    ...
    utils.deep_update(obj_scope, scope)
    ...
      if char_stream.peek() == ':':
        value = interpret_obj_and_chain(char_stream, True, obj_scope, utils.Map({ 'temFlag': True, 'isKey': False, }) )
        utils.deep_update(obj_scope, { key: value })
        utils.deep_update(obj, { key: value })
      ...
    ...
  ...

      Snippet 17

Expressions

For a start, think of it as a desk calculator! We first have to handle basic arithmetic operations: multiplication, division, addition, and subtraction.

Consider: (3 + 3) * ( 3 * 3)

To achieve this, we need to prioritize multiplication and division over addition and subtraction; expr revolving around term with term revolving around prim.

In computer science, the term is Operator-precedence parser or just precedence.

def expr(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  left = term(char_stream, advance, scope, flags)
  while True:
    if char_stream.peek() == '+':
      left += term(char_stream, True, scope, flags)
    elif char_stream.peek() == '-':
      left -= term(char_stream, True, scope, flags)
    else:
      return left

def term(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  left = prim(char_stream, advance, scope, flags)
  while True:
    if char_stream.peek() == '*':
      left *= prim(char_stream, True, scope, flags)
    elif char_stream.peek() == '/':
      left /= prim(char_stream, True, scope, flags)
    else:
      return left

def prim(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  if advance:
    char_stream.advance()
  skip_space(char_stream)
  if char_stream.peek() == '(': # enable ((2 * 2) + 1)  
    value = expr(char_stream, True, scope, flags)
    if char_stream.peek() != ')':
      raise SyntaxError("Missing ')'")
    char_stream.advance() # eat ')'
    skip_space(char_stream)
    return value 
  return interpret_obj_and_chain(char_stream, False, scope, flags) # use the complete variant of interpret_obj with method chaining

      Snippet 18

Our function can be illustrated using either AST or Parse Tree.

Visually, we have:

To cap it off, let’s replace interpret_obj_and_chain with this new function!
Back to Snippet 5:

def interpret_obj(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  ...
  elif char_stream.peek() == '{':
    ...
      if char_stream.peek() == ':':
        value = expr(char_stream, True, obj_scope, utils.Map({ 'temFlag': True, 'isKey': False, }) )
        ...
    ...
  ...

      Snippet 19

Additionally, don’t forget to call expr from chain_obj as well – particularly instead of interpret_obj when getting a function arguments.

For example, interpreting { f: func(1+1, 2*2) } would require:

args.append( expr(char_stream, True, scope, utils.Map({'temFlag': True, 'isKey': False,}) )

Wrapping Up Method Chaining

Now, if we write {c: {b: 1, d: {a: 21}}, d1: (c.d.a)*2+1 } – that works giving us the correct result. But what if we tried to write ((c.d).a) instead of just (c.d.a). Well, that easy to implement! If you retrace your steps back to prim – you will find the part that matches parentheses and hit the nail on the head! That’s the block of code we need to work on!

def prim(char_stream: CharStream, advance: bool, scope: dict, flags: utils.Map):
  ...
  if char_stream.peek() == '(': # enable ((2 * 2) + 1)  
    value = expr(char_stream, True, scope, flags)
    value_ptr = [ value ]
    if char_stream.peek() != ')':
      raise SyntaxError("Missing ')'")
    char_stream.advance() # eat ')'
    skip_space(char_stream)
    chain_obj(char_stream, value_ptr, scope) # just enable method-chaining
    value = value_ptr[0] # the final value
    return value
  ...

      Snippet 20

Next, go ahead and try (c.d).a !

Because of our recursion logic, we also must not forget to check for unmatched characters if there are extra characters, which should produce an error - for example: {}}, ()) and similar.

In that case, we have:

def interpret_object(stream: CharStream, scope: dict): 
    default_flags = utils.Map({})
    obj = interpret_obj(stream, False, scope, default_flags)
    if not stream.is_over():
        raise SyntaxError('unmatched ' + stream.current)
    return obj

def main():
    text = CharStream(r'''{}''')
    # text = Char_stream(r'''{}}''') # we now get "SyntaxError('unmatched }')"
    scope = { 'func': lambda x,y: x+y, 'func1': lambda: print('hi!'), }

    obj = interpret_object(text, scope)
    utils.export_json(obj)

      Snippet 21

Conclusion

Understanding how programming languages work opens up many opportunities in the computer science world by introducing you to natural language processing, pattern matching, evaluation, compilers, interpreters, etc.

It helps you picture how each expression you have written is processed before you even hit the enter key trying to run just a few lines of code – it can inspire you to put the programming language you are using under the microscope for the first time.

There is plenty of room to structure and improve our code. One of the ways is to lean towards OOP, which is exactly what the next volume will be about – one step at a time!

We wish you luck with the prototype of your language and look forward to sharing more advanced guidance with you soon.

Let us know about any typos and your takeaways in the comments.

Forem: Aleksandar Milenkovic

Switch Case: Peak Performance

Table Of Contents

About Author

Motivation

Source Code

Introduction

Switch Case Optimization

Direct JMP Instruction Optimization

Break vs Return

Benchmark Results and Conclusion

Linux Perf Stats

S2S Compilers: Understanding Switch Case Statements

S2S Compilers: Understanding Switch Case Statements

Table Of Contents

About Author

Introduction

Motivation

Source Code

Prerequisites

Background

GCC Options

Headers and Macros

Switch case VS If-else

If-else statement

Switch Case

Benchmarking the two

Out-of-Bounds Benchmark

Turning a switch case into a jump table

Is there a limit for the values of a switch case?

Breaking switch case: Non-packed values

Multiple Jump Tables

If-else as a jump table

If-else with logical || operator as a jump table

Implementing Switch Case

Jump Table with function pointers

Implementation

Benchmark Result 1

Benchmark Result 2

Computed GOTO: Goto Jump Table with Labels

No optimization flags

With -O2 optimizations

Switch Case with -O1 optimizations

No Inline

Inlining Computed GOTO

Switch Go Macro

Computed GOTO: C++ Statement Expression

Local Label Concern

Inlining Switch Case

GCC Loop Optimization

Computed GOTO: RAII Concerns

Customizing _switch_go

Benchmark

Default Case: Can we do without it?

Conclusion

References

Building a simple but advanced Jsonic language using Python

Prerequisites

Layout of this guide

Source code for this blog:

the little utility library we use:

Python Support

Motivation

Introduction

Character Stream

Prefix checking

RECURSIVE DESCENT

Error handling

Skipping white-space

Imports

From back-end to front-end

The Object Scope

Flags

Method Chaining

Interpreting empty object

Scoping

Expressions

Wrapping Up Method Chaining

Conclusion

References

With `-O2` optimizations

Switch Case with `-O1` optimizations