CODEWITHSUNDEEP
c++performanceswitch-statementmemory-address
user2015064
user2015064

Reputation:

Implement a switch statement using a jump table in C++

I am trying to improve my parser's speed. And switch-case, sometimes it's useful, but I see it's still slow. Not sure - if C++ supports this feature (address checkpoints (with additional parameter)), it's great!

Simple example :

enum Transport //MOTORBIKE = 1, CAR = 2,  ...  SHIP = 10
Transport foo = //unknown

    switch(foo)
{
    case MOTORBIKE : /*do something*/ break;
    case CAR : /*do something*/ break;
    //////////////////////////
    case SHIP : /*do something*/ break;
}

If the variable foo is SHIP, at least the program has to re-check the value up to ten times! -> It's still slow.

If C++ supports checkpoints :

Transport foo = //unknown
__checkpoint smart_switch;

goto (smart_switch + foo); //instant call!!!

smart_switch + MOTORBIKE : /*do something*/ goto __end;
smart_switch + CAR : /*do something*/ goto __end;
smart_switch + [...] : /*do something*/ goto __end;
////////////////////////////////////////////////////////////
smart_switch + SHIP : /*do something*/ goto __end;

__end : return 0;

It doesn't generate any jump tables, and then check per value. Maybe it doesn't work well with default case. The only thing is smart_switch + CAR -> smart_switch + SHIP may have different addresses so if C++ evaluate them as real addresses, the process will fail. So when compiling the compiler just has to convert them to real addresses.

Does C++ support this feature? And does it greatly improve speed & performance?

Upvotes: 1

Views: 7026

Answers (3)

user405725
user405725

Reputation:

What you are talking about is called a jump table. The jump table is usually an array of relative addresses where the program execution control can be transferred. Here is an example of how you can implement one:

#include <ctime>
#include <cstdlib>
#include <cstdio>

int main()
{
    static constexpr void* jump_table[] =
    {
        &&print_0, &&print_1, &&print_2,
        &&print_3, &&print_4, &&print_5
    };

    std::srand(std::time(nullptr));
    int v = std::rand();

    if (v < 0 || v > 5)
        goto out;

    goto *jump_table[v];

print_0:
    std::printf("zero\n");
    goto out;
print_1:
    std::printf("one\n");
    goto out;
print_2:
    std::printf("two\n");
    goto out;
print_3:
    std::printf("three\n");
    goto out;
print_4:
    std::printf("four\n");
    goto out;
print_5:
    std::printf("five\n");
    goto out;
out:
    return EXIT_SUCCESS;
}

However, I seriously doubt two things. The first doubt is that using jump table will make your program faster. An indirect jump is relatively expensive and is badly predicted by the hardware. Chances are that if you only have three values then you are better off simply comparing each of them using "if-then-else" statement. For a lot of sparse values (i.e. 1, 100, 250, 500 etc.), you are better off doing a binary search rather than blowing up the size of your table. In either case, this is just a head of a huge iceberg when it comes to switch statements. So unless you know all of the details and know where compiler did the wrong thing for your particular case, don't even bother trying to change switch to something else — you will never outsmart the compiler and will only make your program slower.

The second doubt is actually that switching is the bottleneck of your parser. Most likely it is not. So in order to save yourself a lot of valuable time, try profiling your code first to know for sure what is the slowest part of your program. Usually it goes in steps like this:

  1. Profile and find the bottleneck.
  2. Figure out why this is a bottleneck and come up with a reasonable idea of how to improve the code for speed.
  3. Try to improve the code.
  4. Go to step #1.

And there is no exit from this loop. Optimization is something you can spend your entire life doing. At some point, you will have to assume the program is fast enough and there are no bottlenecks :)

Also, I have written a more comprehensive analysis with in-depth (more or less) details on how switch statements are implemented by compilers and when and when not try to engage in trying to outsmart them. Please find the article here.

Upvotes: 7

Slava
Slava

Reputation: 44268

Yes C/C++ does support this feature, and it is in... standard switch. I have no idea where you get the idea that switch will check each value, but you are wrong. Yes I heard that some compilers can generate better code for pretty big cases (many variants like probably several hundreds), but I do not think that it is yours. For example following code compiled by gcc without any optimization: 

enum E { One, Two, Three, Four, Five };

void func( E e )
{
    int res;
    switch( e ) {
        case One : res = 10; break;
        case Two : res = 20; break;
        case Three : res = 30; break;
        case Four : res = 40; break;
        case Five : res = 50; break;
    }
}

generates following:

_Z4func1E:
.LFB0:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    %edi, -20(%rbp)
    movl    -20(%rbp), %eax
    cmpl    $4, %eax
    ja  .L1
    movl    %eax, %eax
    movq    .L8(,%rax,8), %rax
    jmp *%rax
    .section    .rodata
    .align 8
    .align 4
.L8:
    .quad   .L3
    .quad   .L4
    .quad   .L5
    .quad   .L6
    .quad   .L7
    .text
.L3:
    movl    $10, -4(%rbp)
    jmp .L1
.L4:
    movl    $20, -4(%rbp)
    jmp .L1
.L5:
    movl    $30, -4(%rbp)
    jmp .L1
.L6:
    movl    $40, -4(%rbp)
    jmp .L1
.L7:
    movl    $50, -4(%rbp)
    nop
.L1:
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:

As you can see it simply jumps into particular position without checking each value.

Upvotes: 5

naumcho
naumcho

Reputation: 19911

You can just build an array with function pointers and index at it by the enum

Upvotes: -1

Related Questions