CODEWITHSUNDEEP
coptimizationswitch-statementlookup-tableslow-memory
Brian Crafton
Brian Crafton

Reputation: 476

How much code space does a switch statement take?

I am actually surprised I could not find this question already asked. I am wondering how much code space a switch statement takes and if using a const lookup table would be more efficient for my needs. 

    typedef struct container{
    type1 a;
    type2 b;
    type3 c;
}container;

static container d;
//option A
void foo(int num)
{
    void* x;
    switch (num)
    {
    case 1:
      x = &d->a;
      break;
    case 2:
      x = &d->b;
      break;
    case 3:
      x = &d->c;
      break;
    default:
      x = NULL;
      break;
    }
    // do something with x
}
// option B
const void* lookup_table[] = {
    d.a,
    d.b,
    d.c,
    NULL
};

void foo(int num)
{
    void* x = lookup_table[num];
    // do something with x
}

How would the switch statement break down into assembly, and how much larger would it be in code space? Is it worth using the lookup table rather than using the switch statement?

Upvotes: 0

Views: 1385

Answers (4)

box
box

Reputation: 3246

As already stated by others, modern optimizing compilers will try themselves to choose a good strategy to compile switches into more efficient code. Hans Wennborg gave a talk at the 2015 LLVM Developers’ Meeting about the recent switch lowering improvements which gives you a short introduction to this topic.

So better let the compiler do its work and decide for the most readable solution than the one you think is most efficient.

If you want to see what code Clang produces for your switch file, you can use -S or -S -emit-llvm.

Upvotes: 0

chux
chux

Reputation: 153537

A different way of looking at the post:

void foo(int num) { void* x; switch (num)... copes well with num outside the range 1,2,3.

void foo(int num) { void* x = lookup_table[num]; has undefined behavior when num is outside the range of 0,1,2,3.

Some might then say num range is not the issue. But that was not stated in the post. And so it is with code maintenance - lots of unstated, implied and sometimes falsely assumed conditions.

Is it worth using the lookup table rather than using the switch statement?

For worth of maintenance, I'd go with the switch().

Upvotes: 1

rici
rici

Reputation: 241771

If you can rewrite the switch as a simple lookup into a lookup table, that's may be the best solution, particularly if the possible indices are dense, since it is also probably more readable. (If the possible indices are not dense, you could either waste space or use a more sophisticated lookup technique: two-level tables, hash table, binary search into a sorted list. These may be better than the switch statement, but will be less readable.) A good compiler will try hard to match the efficiency, though, and some of them will produce exactly the same code as you did.

But in the usual case that you need to more than just lookup a value, the switch statement is almost certainly better. A good compiler will compile the switch statement into one of the above mentioned strategies, and it may know more than you do about the optimal solution given the details of the target platform.

In particular, turning a switch statement into an indexed lookup of a function pointer and then calling through the function pointer is likely to be significantly slower than the switch statement because of the overhead of calling the function. With the switch statement, the compiler is likely to generate a branch table, in which the lookup code will be very similar to your handbuilt code, but what's done after the lookup is a simple branch rather than a function call.

Upvotes: 2

Basile Starynkevitch
Basile Starynkevitch

Reputation: 1

The question has no precise meaning. An optimizing compiler is (very often) at least compiling an entire function (and often, an entire translation unit) at once.

Read this paper by R.Sayle on compiling switches. You'll learn that there are several competing strategies for that (jump tables, balanced trees, conditional moves, hash jump tables, etc....) and several of them can be combined.

Trust your optimizing compiler to make a good enough choice to compile your switch code. For GCC, compile with gcc -Wall -O2 -march=native perhaps adding -fverbose-asm -S (and/or replacing -O2 with -O3) if you want to look inside the generated assembler. Learn also about gcc -flto -O3 etc...

Of course, for benchmarking purposes and for production code, you should always ask your compiler to optimize.

Notice that as an extension (accepted also by Clang/LLVM...) GCC has labels as values (with indirect gotos). With them, you could force usage of jump tables, or have some threaded code. That won't always make your code faster (e.g. because of branch prediction).

Upvotes: 1

Related Questions