Okay, so let's start.
Hi, I'm Fred Casto, I'm from Sousa.
And likely I've been interested in switched statements and how GCC optimizes switched statements.
So I've come here to tell you about what I've found on my journey.
And also to share one contribution I actually made to GCC switched statement optimizations.
Let's start with some definitions, so that we understand each other.
What will be important? Well, this will be important.
I expect you know what a switch statement in CS.
And the thing in parenthesis that determines which of the cases will execute.
Let's call that the index variable.
So this one important thing.
And the other important thing is the case range.
The case range, I basically mean the interval from the smallest case number to the highest case number.
And then this case range may have some holes in it.
Not sure if there's any technical term for this.
Meaning for example here we don't have case for in case 5.
If there are any holes in the case range and how many there are how big they are will be important for some of the optimizations.
So let's say you are the compiler and you run into a switch.
At some point during the compilation you have to break down the switch into some simpler statements.
And this is the situation we'll be dealing with in this talk.
And first I want to quickly mention the navel way of doing this.
You can break down the switch to a chain of if and else statements.
You just go through all the cases and for each one ask if i is equal to its number.
This works but in the worst case you go through all the cases.
So you go through many conditionals which is not efficient in terms of CPU cycles.
And before we discuss smart database of doing this I want to show you two specific switches.
And I want to think about how you would optimize this.
How would you rewrite this to something more efficient and something that isn't a switch.
I will tell you what GCC will in its current version do with this which is at the end.
So eventually we will find out how GCC takes advantage of those.
So let's now go through the major switch optimizations in GCC.
The one I want to focus on the most is switch conversion.
This is an optimization that was contributed by Martin Jambor who is also from Susan.
And the scenario where we would use switch conversion is such.
You have a switch like this one that only assigns constants to some variables.
In this case it is the variable x.
That may sound niche but I think pretty useful case to optimize.
And the idea is that you take these constants.
You put them in an array and then you use the variable name index variable to index the array.
What you then get is instead of many conditionals you get just a memory read which is nice.
One thing to know is that you actually also have to include some bounce checks so that you don't end up doing them out of bounce memory read.
Let's take this a bit further.
What if we could get even of that memory read?
Well it turns out we can and GCC is able to do this in the case where x turns out to be a linear function of i.
Which is how obvious this is but you can compute x by multiplying i by free and adding 5.
And GCC can recognize this and instead of the memory read you have seen any instead of the array.
Just insert the necessary numerical operations, the multiplication and addition.
And one thing I forgot to mention in the previous case with the basics which conversion.
This optimization can handle some holes in the case range but there mustn't be too many.
In the case of this thing we need to transformation this flavor of switch conversion.
There mustn't be any holes in the case range.
So that was the switch conversion.
I also want to show you the other major switch optimizations.
The most general of this and now we are giving the realm of switches which only assign constants to some variables.
The most general optimization is the decision tree optimization.
Basically this is a direct upgrade in most cases I think of the knife approach we've seen.
Here you basically take the case range.
You split it at some point and you ask in which of the resulting sections of the case range is i.
And then you do this again recursively and again you can visualise this as a tree and eventually end up in the code that you want to execute.
So this is nice. This gets us from worst case linear time to worst case algorithmic time.
But yeah this is like the most basic thing we can do.
Usually we want to apply some more powerful techniques at the expense of them not being entirely general.
So one of these is the jump table optimization optimization.
This thing to understand jump tables.
We have to look at the problem at the assembler level and the core concept is an indirect jump.
What you do to go to the appropriate case to the appropriate code block is that you do an indirect jump indexed by the index variable.
You have a table of target locations and you index this table by i in this case.
It's kind of similar in concept to the switch conversion but this time we're jumping not reading from memory.
So this is pretty powerful and there's one prerequisite and that's again that's the case range doesn't have too many holes in it.
And to finish our turn from through the major gcc switch optimizations there's also a bit test.
This one is pretty specific most contributed by regesail.
We have a switch where many cases are pointing to a single code block.
To this side effectively if you want to execute a thing A or thing B.
We would like to efficiently check if I is in a set of all these case numbers.
And the I think pretty smart idea is to use a bit vector for this.
Meaning that you take a binary number and you put once at the positions which correspond to the numbers you want to represent in the set.
And then you do some bit by operations and you can efficiently find out if i indeed is in the set.
So those are the major switch optimizations and as I promised now I want to show you the switches from the beginning what happens to them.
Now that you know about switch conversion you might guess that this is exactly the case where you would want to apply it.
You are just assigning constants to some variable x.
But there's a problem and that's the case range.
It is two spars, there's too many holes in the case range.
But we see a pattern here. We see that the case numbers are actually powers of two.
So what if we could switch on the exponents of the powers of two instead of the numbers themselves?
Well that would be pretty nice.
It would lead us to a switch like this which this is very much processable by switch conversion.
The case range actually in this case scenario is completely contiguous.
But one thing we have to do is that we at runtime have to compute the base two logarithm of the index variable.
Which may seem like it would be a problem.
But since all the relevant values are exact, well, are powers of two.
And we have some fancy instructions on modern CPUs.
This actually is pretty fast. You can do this in like one or two instructions.
Usually.
And yeah, this is my humble contribution to GCC spiritual premises.
This is what I did.
And this is how it looks if one eventually switch conversion runs.
You get some bounce checks which I left out, logarithm and memory read.
And I also want to show you the second switch.
Let one gets reduced to almost only logarithm.
Because that is what it was basically computing and I have left through the switch statement.
So I think it's pretty neat that GCC can now recognize this.
And just insert a computation for logarithm.
I want to do show you some future work, but I'm running up to time.
So, recap, this is what you've seen. Switch conversion, this entry is just tables and it tests.
I hope you learned something.
And are now more excited about optimizing switch statements. Thank you.
Do I have some time for questions?
Okay.
So there were two questions.
The first one was if this works with other logaritms.
No, this only works with base to logarithm.
I don't think that this would work with like base free logarithm.
Maybe with powers of two, but that would.
How open would an opponent practice?
So the question is, no, this works only with base to logarithm.
And the second question was if this also works with chains of if else.
And it does because, yeah, what I didn't mention, GCC also optimizes chains of if else into switches internally.
So this is also applicable if you write this as if else chain.
Last one.
Okay.
I saw you, okay.
So you say two decisions, right?
First, yes.
Jump, jump, jump.
And all modern hyper, jump, hyper, traffic, traffic, traffic, traffic.
So you should avoid always to assist.
It is just never predicted in a lot of hyper.
If it means like, single times, right?
And the better hyper is essentially never predicted correctly.
So, well, multiplication is the important thing for performance, right?
And it does not work in that process.
There is no good solution.
Yeah.
And well, there is no good solution expected.
And then next month I'll be here for some further.
And it is no good solution.
So, best we have, GCC.
Okay.
And in GCC, we do have a truck type specific,
Markov thinging to decide whether to use this thing.
Okay.
So basically, everything will switch to decisions.
We always in the next couple of days.
Because it's just so much better.
Okay.
So to repeat for people watching the recording,
I understood correctly.
This was a correction to my client.
This is the basic thing.
And this is better.
It's not, it's the June table.
It's not the modern thing.
It's the 10, 20 years old.
It does not have any advantage.
It is only different functions.
Okay.
It's always well.
Yeah.
It does work.
That's good thing, right?
It's good work.
Yeah.
So what I've learned from the audience is this, this technique is old.
And isn't as fast as I was saying.
And will be very, very obsolete.
Okay.
Thank you.
I think that, yes, GCC doesn't decide.
On the, depending on how big this switch is,
it will do decision trees,
even if it can see that it could do a jump table.
But yeah, I don't know more details about this.
Thanks.
Okay.
So there's all the questions.
Sorry.
Again, thank you for your attention.
Thank you.