why are switch statements so HECKIN fast?

warning I'm about to blow your mind when making decisions with your data in C you basically have two options for the majority of the control flow in your program switch statements and if statements now a lot of new programmers struggle with which ones should they use and what have I told you switch statements are actually significantly faster than if statements in this video we're going to talk about how that works under the hood why switch is actually faster than if statements in most of the cases and if this all really matters let's dive into it let's say for example we're writing a program and we want to have a basic option menu where we iterate through a series of options that the user can give us and then we have to parse through which option did they give us and then take the appropriate action so for example maybe we have the stop command that says to stop the menu and quit the programs we use Q for the quit C for continue just means cycle the menu again n maybe we make a new object for our program maybe we're making a database program we do edit we do delete you know these are the various options we can add and obviously we're using an enum because using an enum allows us to use the word stop instead of the actual character the character can be thought of as like a magic value where if maybe we want to translate this program to another language where Q doesn't mean quit we can still use the keyword stop and instead make a separate enum for that language and change this maybe to like Z or something we have two primary options for the control flow of this program to run this menu and figure out what action do we take based on user input in our code we are going to need to create a buffer for the option that the user gives us and then we have to do some Logic on the first character of that buffer right and I'm creating four characters of buffer space just because maybe the user has a Unicode character set that has multiple values per character maybe we have multiple control characters like SL r/n and windows or just SL end for the enter key we're making a lot of room for effectively what ends up being one character and then we have to do some Logic on that one character and figure out what do we have to do and then take some appropriate action there are two ways we can do this we can do this with the if else tree as are seeing here or we can do it with the switch statement and I think a lot of new programmers really struggle with you know when do I do one or the other when is the most appropriate so here there's actually a significant difference in the way the program will process this code so when you do an if statement basically you have the if statement here and you have some condition you have to meet and we're saying here if the first value in the option buffer is equal to stop we do the stop action same with continue Etc when we say if if this condition gets met we will run the code here and the rest of these evaluations will not happen we will not check to see if option buff zero is equal to continue because we met this first one but if for example none of these are true so it does not equal stop it does not equal continue it does not equal new Etc it'll run all four of these evaluations here before we get down to the final evaluation to see if it equals delete we've run the number of instructions it takes to compare all these values before we get to delete and in certain cases maybe you're running on an embedded device that has really no room for errors in terms of Mis caches or maybe you just need the program to run quickly you are wasting a lot of Cycles by going through this entire list now how does this compare to the switch statement so let's say for example I have a switch statement here and I say that if the case new happens we print F you said new and then we move on with our day and then we do a break statement so let's kind of talk about the syntax of a switch statement so a switch statement here we give it the option buffer zero it has to take a literal as inputs at this time the option buffer value of zero is a literal value meaning it's just like a character it's a number and we're saying in the case that the value is new we say you said new in the case the value is stop continue or something else we have not defined in the statement to break and all break means is we go back and we leave the switch statement and then because we say while our option is not equal to stop this Loop will continue forever the reason why this is faster is actually a really really neat performance optimization that goes on under the hood in a switch statement versus an IFL statement before we keep going I want to get serious for a second I know a lot of you here maybe new programmers maybe you've written literally zero lines of code maybe you're in college trying to learn about computer science if you're looking for a free and easy way to learn about computer science data science and machine learning then I highly recommend brilliant.org brilliant.org is an easy way to learn about all these topics and their lessons are interactive brilliant is written in a way where you use the knowledge as you go through the system you learn as you go and you get to test yourself on that knowledge lessons and brilliant are bite-sized so if you only have time in between classes to learn something you can take a 10-minute class on brilliant and then move on with your day now to support the channel you can go and use my link right now www. brilliant.org larning for 30 days free and 20% off an annual subscription when you sign up thanks again brilliant for sponsoring this video now let's talk about what's going on under the hood when we execute the if version of this versus the switch statement version of this and why switch is actually a lot faster I've added a little bit of a code for the program to execute when option is evaluated if it equals stop we go to stop if it equals continue we go to continue Etc and all those functions all they do is they print the thing we said and obviously in our code we could actually handle that stuff later on in the program and then in Switcheroo I've done effectively the same thing but instead of using the if else tree I've converted it to a switch statement where we switch on the en of the case and then we handle the option accordingly now we're going to go look at the Iero the the if tree version and I want to show you under the hood what's actually happening in assembly now don't be afraid assembly isn't that bad it looks a little scary but I can actually explain to you what's going on here pretty quickly we run our call to scan F right here which actually gets the input from the user what we're doing is we're comparing eax what we're doing is we're moving and zero extending the bite pointer at this location into eax all that means we're grabbing the first BTE of our input and putting it into eax which is a 4 byte register in the CPU we are then going to compare Al to this value hex 71 and interesting what is hex 71 hex 71 is Q what is q q is our quit option so the code is going through and it's saying if these are not equal go to 1245 what's at 1245 well we move that bite again and we compare it to 63 what is 63 it's C our continue option so here in the if AO code you are seeing that if else trig get worked out it's just a series of jump not equals and then Compares jump not equals and then Compares and again like I said before if you're at the bottom of that tree if you're the last option then effectively we have to run through all these instructions all these very very long branch instructions that may invoke a cache Miss on your computer to get to that option now you could code your program in a way so that the least likely option is at the bottom but a lot of instances of this don't play out like that maybe you need maybe all of these happen at the same occurrence but you're going to miss out on all this performance here now how does that differ from the switch AR root State again like I said there's a little bit of magic going on under the hood that makes a little bit faster so same thing as before we are going to run our call to scan F we are going to pull out our value into eax so this is the lower first bite of our input but then we do something pretty weird we sign extended don't worry about that but then we subtract 63 in HEX from our value and we compare it to hex e so now we have this really really tiny number just a number that's up to 15 and then if we are below that so this is Jump above if we're below hex e what it does is it loads some magic value into RDX you may just see a bunch of garbage a bunch of fs and 42s but I see something pretty magic the jump table begins at this location here hex 2054 and because these numbers are packed little Indian they're actually in Reverse so the number actually is FF FF f242 now that is a negative number we can tell that because the first bit is set and that number actually translates into this number here now warning I'm about to blow your mind this number here that we saw in our jump table hex FF FF f242 is a very large number that is actually a negative number to convert that big number to its negative representation we go hex ffffff F the max size 32 bits can represent and we convert that by subtracting it and then adding one to its value so this is actually a negative hex dbe now what's going on here is the program takes the address of that jump table so 205 before and then it adds that value we've pulled from the jump table and then it jumps to that we jump RX so we go to the value of the jump table and we go to the address of the jump table we subtract one from the other and then we jump to it we can do that math calculation here and we see that the address is hex 1296 because we take the address of the jump table and subtract the value in the jump table which we got from our previous math calcul here and guess what hex 1296 is hex 1296 is one of the entries in our jump table it is the value of the address of the option where we run handle continue how cool is that dude the computer decided no we're not going to do if statements we're going to do a switch statement by doing some magical value math we will use our input from the user as an index into a table of negative numbers we will subtract that number from the address of that table and boom just go to that location it's exactly where you want it to go there is no comparison going on effectively this is O of end time and this is constant time obviously there's a little bigger of a constant having to set all this up and you know most of the time if you only have a couple of statements here like maybe we have two or three options here versus our if statement if we have two or three options here the performance difference is going to be extremely negligible but if we're getting into a scenario where we have maybe 10 or 20 options that we have to run through you will see a significant performance increase in the switch statement because we're not going to have to process all of these dead cases in the event that these are likely to happen at the same probability how cool is that computers are amazing assembly isn't hard if you like this video go watch this other video and figure out why void star pointers even exist cuz honestly I'm not that

Channel: Low Level Learning

Views: 389,831

Keywords: if statements, switch statements, c programming, c tutorial

Id: fjUG_y5ZaL4

Length: 11min 2sec (662 seconds)

Published: Sat Oct 07 2023