why are switch statements so HECKIN fast?
HTML-код
- Опубликовано: 6 окт 2023
- Support the channel and go try Brilliant RIGHT NOW at brilliant.org/LowLevelLearning for 30 days free and 20% off!
Should you use switch statements? What about if statements? Should you use NEITHER? What if I told you that if statements were WAY slower than switch statements. In this video, I'll tell you about why switch statements are HECKIN FAST.
🏫 COURSES 🏫 Check out my new courses at lowlevel.academy
🙌 SUPPORT THE CHANNEL 🙌 Become a Low Level Associate and support the channel at / lowlevellearning
Why Do Header Files Exist? • why do header files ev...
How Does Return Work? • do you know how "retur...
🔥🔥🔥 SOCIALS 🔥🔥🔥
Low Level Merch!: lowlevel.store/
Follow me on Twitter: / lowleveltweets
Follow me on Twitch: / lowlevellearning
Join me on Discord!: / discord 
Наука
Support the channel by trying Brilliant at brilliant.org/LowLevelLearning for FREE and get 20% off when you sign up! Thanks again Brilliant for sponsoring this video and your continued support of the channel!
I did not catch the perf difference. What is the perf difference?
Here's a few video ideas:
* Hardware bugs and their workarounds (e.g. F00F, FDIV, TAS on Amiga/Genesis, DPCM glitch on NES, etc)
* How to program in assembly without losing motivation (me irl 😭)
* How emojis are represented in binary
* Unicode errors in general (e.g. rÃ(C)sumÃ(C) (I don't know how to type the copyright symbol on my phone sorry!)
* Why it's so easy for a human to recognize spambots in chatrooms but computers can't do it well
* How an EXE file works
You don't even need a switch statement for enums in Java, you can make frankensteinian monsters known as an abstract enum. They're usually used for adding extra data for the enum members (with a custom constructor), but you can also add abstract methods to the enum, which you have to then implement for each member.
This leaves you at a simple method call on your enum variable without switching for possible values. 😂😂😂
I cant wait for neural link so i can learn everything you know lol
basically a hasmap lookup vs an array search, but at a low level
To add on: it’s like the hash function is computed at compile time! (iiuc)
Edit: Y’all just use Rust check and you don’t needa compile
@@joeystenbeck6697 this is something I would like to see @lowLevelLearning mention in the video. I haven't benchmarked it, but my gut feeling tells me the difference in runtime complexity is just pushed down to compile time, i.e. increasing time needed to compile the program in order to get a better performance in runtime. In some situations this is undesirable (or less desirable) and the program would be better off running a bit slower.
Beatrice can walk 14_88
@@PrivacyRevocation in 99% of the time you rather want longer compile times than longer run times. And I'd assume that if statements are more difficult to optimize?
@@PrivacyRevocation- Like .. when? When would it be better to have the program run slower so the compile would be faster?
I'm convinced, I'm switching to switch.
If only i could
You should in any case
@@PingSharp 😆
If I use it, I won't break. That's if I don't default.
Do not get convinced so easy, test and measure times, that's the only way to know which strategy is best
Embedded dev here. The compiler impressed me a couple years ago. I had a static constant std::map of enums to functors and i changed where it was used to a switch calling the functions directly and it compiled into an identical object file.
That’s nuts
Using the switch can also improve code safety by enabling the compiler warning/error for switch statement not handling all values in your enum.
So in future, when you add another value to your enum, the compiler will tell you about any switch statements you forgot to update
C99?
@@desertranger82, std::map implies C++.
doubtful. that means the compiler would have to have to elide the map entirely. maybe in a very simple case, but highly doubtful.
Yes, I was disappointed that he glossed over stuff referring to things as "magic numbers" and "a bunch of garbage".
The whole *point* of the video was to explain the details behind the switch statement.
The valid user input are letters: "c", "d", "e", "n", "q" (which he defined earlier in the video).
Note that the first letter "c" is ASCII 0x63 and the last letter is "q" is ASCII 0x71. Note that the span from "c" to "q" is 0x0e (i.e. 15 characters away).
The code at 7:51 shows a transformation and a check.
Line 123b sub eax, 0x63 ; this subtracts letter "c" from the entered letter, so the range of inputs is now indexed from 0.
Line 123e cmp eax, 0xe ; this compare checks if the input letter is past letter "q" since letter "q" is the 15th letter (i.e. 0xe) from letter "c"
At this point, the character range from "c" to "q" has been transformed to an index range of 0 to 14.
If the entered character is *OUTSIDE* this range the code terminates, bypassing the jump table stuff, and goes to process with the "invalid" code not shown in the video.
Line 1241 ja 12aa ;exit the jump table code block as the entered character is outside the range of the defined command characters.
If the entered character is *INSIDE* this range, it proceeds to the jump table code.
Line 1245 lea rdx,[rax*4+0x0] ;Load Effective Address. The index value is multiplied by 4, since each jump table location is a 4-byte offset added to the table's base location.
The code at 7:58 is really just the jump table values. (Unfortunately the disassembler produces nonsense code, but the offsets are valid.)
Rearranged, the offset values are given below and matched against the entered letter:
𝟶𝟶: 𝚏𝚏 𝚏𝚏 𝚏𝟸 𝟺𝟸 ; "𝚌" 𝚓𝚞𝚖𝚙 𝚝𝚘 𝙻𝚒𝚗𝚎 𝟷𝟸𝟿𝟼 𝙲𝚘𝚗𝚝𝚒𝚗𝚞𝚎
𝟶𝟷: 𝚏𝚏 𝚏𝚏 𝚏𝟸 𝟸𝚊 ; "𝚍" 𝚓𝚞𝚖𝚙 𝚝𝚘 𝙻𝚒𝚗𝚎 𝟷𝟸𝟽𝚎 𝙳𝚎𝚕𝚎𝚝𝚎
𝟶𝟸: 𝚏𝚏 𝚏𝚏 𝚏𝟸 𝟷𝚎 ; "𝚎" 𝚓𝚞𝚖𝚙 𝚝𝚘 𝙻𝚒𝚗𝚎 𝟷𝟸𝟽𝟸 𝙴𝚍𝚒𝚝
𝟶𝟹: 𝚏𝚏 𝚏𝚏 𝚏𝟸 𝟺𝚎 ; "𝚏" 𝚓𝚞𝚖𝚙 𝚝𝚘 𝚒𝚗𝚟𝚊𝚕𝚒𝚍 𝚌𝚘𝚍𝚎 𝚋𝚕𝚘𝚌𝚔
𝟶𝟺: 𝚏𝚏 𝚏𝚏 𝚏𝟸 𝟺𝚎 ; "𝚐" 𝚒𝚗𝚟𝚊𝚕𝚒𝚍
𝟶𝟻: 𝚏𝚏 𝚏𝚏 𝚏𝟸 𝟺𝚎 ; "𝚑" 𝚒𝚗𝚟𝚊𝚕𝚒𝚍
𝟶𝟼: 𝚏𝚏 𝚏𝚏 𝚏𝟸 𝟺𝚎 ; "𝚒" 𝚒𝚗𝚟𝚊𝚕𝚒𝚍
𝟶𝟽: 𝚏𝚏 𝚏𝚏 𝚏𝟸 𝟺𝚎 ; "𝚓" 𝚒𝚗𝚟𝚊𝚕𝚒𝚍
𝟶𝟾: 𝚏𝚏 𝚏𝚏 𝚏𝟸 𝟺𝚎 ; "𝚔" 𝚒𝚗𝚟𝚊𝚕𝚒𝚍
𝟶𝟿: 𝚏𝚏 𝚏𝚏 𝚏𝟸 𝟺𝚎 ; "𝚕" 𝚒𝚗𝚟𝚊𝚕𝚒𝚍
𝟷𝟶: 𝚏𝚏 𝚏𝚏 𝚏𝟸 𝟺𝚎 ; "𝚖" 𝚒𝚗𝚟𝚊𝚕𝚒𝚍
𝟷𝟷: 𝚏𝚏 𝚏𝚏 𝚏𝟸 𝟷𝟸 ; "𝚗" 𝚓𝚞𝚖𝚙 𝚝𝚘 𝙻𝚒𝚗𝚎 𝟷𝟸𝟼𝟼 𝙽𝚎𝚠
𝟷𝟸: 𝚏𝚏 𝚏𝚏 𝚏𝟸 𝟺𝚎 ; "𝚘" 𝚒𝚗𝚟𝚊𝚕𝚒𝚍
𝟷𝟹: 𝚏𝚏 𝚏𝚏 𝚏𝟸 𝟺𝚎 ; "𝚙" 𝚒𝚗𝚟𝚊𝚕𝚒𝚍
𝟷𝟺: 𝚏𝚏 𝚏𝚏 𝚏𝟸 ?? ; "𝚚" 𝚓𝚞𝚖𝚙 𝚝𝚘 𝙻𝚒𝚗𝚎 𝟷𝟸𝟾𝟿 𝚀𝚞𝚒𝚝
There is no particular reason that the offsets are negative, it's just that the compiler chose to put the jump table _after_ the code fragments.
In fact, referencing the offsets to the JUMP table *is* a bit odd.
Usually the base address for the jump table is the FIRST ROUTINE. (in this example the "New" routine at address 1266 is the first rountine...as shown at 8:52 )
And because it's first, It would have an offset of simply 0.
The rest of the routines are reference from there (the FIRST routine).
In the given code each entry point is just 12 bytes from the previous routine.
𝙹𝚞𝚖𝚙𝚁𝚘𝚞𝚝𝚒𝚗𝚎𝙱𝚊𝚜𝚎𝙰𝚍𝚍𝚛 𝚒𝚜 𝟷𝟸𝟼𝟼 (𝚒𝚗 𝚝𝚑𝚎 𝚐𝚒𝚟𝚎𝚗 𝚎𝚡𝚊𝚖𝚙𝚕𝚎 𝚊𝚝 𝟾:𝟻𝟸)
+𝟶 𝚏𝚘𝚛 "𝙽𝚎𝚠"
+𝟷𝟸 𝚏𝚘𝚛 "𝙴𝚍𝚒𝚝"
+𝟸𝟺 𝚏𝚘𝚛 "𝙳𝚎𝚕𝚎𝚝𝚎"
+𝟹𝟼 𝚏𝚘𝚛 "𝚂𝚝𝚘𝚙"
+𝟺𝟾 𝚏𝚘𝚛 "𝙲𝚘𝚗𝚝𝚒𝚗𝚞𝚎"
With those simpler and smaller numbers, the example would have been easier to follow, but we're at the mercy of the compiler (and crappy disassembler).
As was pointed out, if the cases are "sparse" then the jump table will have a lot of those "invalid" entries. It still executes very quickly, but just takes up some memory.
Input letters *OUTSIDE* the range are culled out and terminate quickly. Letters *INSIDE* the range all result in the jump code being executed, even if it is just results in an "invalid" stub.
Before everyone decides to switch to switch statements😊I think it’s good to point out that switch statement CAN be faster, but it really depends on the use case. Like you mentioned, when you only have a few conditions, if/else might actually be faster. Also in your example the gaps between the enum values are small, but when very large gaps are used, the compiler might opt for a different strategy, which can again be slower than a few if/else statements.
And finally, switch statements might be faster, but have their own caveats. Which can lead to slow development. It’s so easy to forget a break, which leads to an unexpected fall through, which can be real nasty bugs to trace. It’s easy to forget to handle the default case. Also in C/C++ switch statements cannot be used for strings, which is annoying to say the least. And the switch cases are not scoped, unless you add curly braces; which again can lead to unexpected behavior if used improperly.
Usually compiler issues warning about fall through. At least gcc does.
Also video explains why strings cannot be used in switch cases. You need a number for switch.
It really depends on the use case, squeezing more than 1 line under each case can be hard to read and ugly. And so often the conditions are not as simple as a case. So I think its use case can be quite narrow.
Seriously I don't understand why break statements are not a default on switch in all languages I have used. It blows my mind.
If you use enums, the gaps should be quite small. Generally I'm happy to let the compiler figure out if it thinks the switch is faster or not, but I prefer switches because I think it looks prettier and I sometimes like to know if I'm missing a value by looking at the warnings when I remove the default statement. (I tend to write java or rust more than C, so the precise warnings may be different.)
I would have imagined that modern compilers with optimizations turned on would be smart enough to choose to translate the if/switch to the appropriate assembly if/switch depending on the specific code.
Most of them are. Not sure what compiler he used with what settings. In some cases they can convert if-elses to jump table, like they do in case of switch. In some other cases they might decide to not generate jump table for switch, because multiple compares would be faster or much more memory efficient (in terms of produced code).
Yep, to many compilers it doesnt matter at all whether you make a switch or if statement. I guess the switch just happens to be easier to optimize so its more likely to be faster if we choose any random compiler. In addition to O(1) jump tables and O(n) if else chains some compilers actually uses hardcoded binary search to find the correct case by repeatedly cutting the range in half which is O(logn) in average. I guess that can be good middleground between those solution. Most compilers change the implementation for if and switch statements depending on the amount of items to be compared and the type of data being presented (consecutive numbers/something that translates to them like enums, random looking numbers without seemingly any pattern etc.)
You forget the human here.
If I have a long if-else chain that I carefully created with only fixed comparisons to a single variable
The compiler can optimize that to a jump table.
The next developer working in this file adds a if-else that breaks this pattern, and buum performance drops for no obvious reason (unless you know if this compiler optimization).
By using a switch I tell the next developer my intention, and she/he needs to make a conscious decision to change this concept.
They are, the if code is not optimized in any way
This is the correct answer.
People who write modern optimising compilers are generally smarter than the average programmer.
It's _relatively_ easy to look at an if-else cascade and analyse if it's evaluating equality on the same variable and is, therefore, functionally a switch statement.
One only need look at Python: Guido explicitly excludes a switch statement as he _knew_ this was possible.
In my first design review at Novell, my team lead said I should use a switch statement for true/false tests rather than if/else. So I coded both and looked at the generated code - they were identical.
Compilers since 20+ years ago have been smart enough to ignore your preferences as a source code writer and just do the right thing at the machine code level. I used enjoy trying to outsmart compilers, to make 3D renders run faster by studying the machine code output, but gave that up long ago. We have created tools smarter than ourselves!
If the if-else chain tests something that can be trivially changed to a switch, it's better to do so, simply because it communicates intent better, and gives more well-structured code. Or, put another way, a long, simplistic if-else chain is just a plain eyesore, IMHO.
It doesn't necessarily matter if the compiler can magically figure your intent out in this specific case; in other cases, bad code (which this smells like) can actively hinder it from figuring things out and making optimisations.
TL;DR: Don't make it any harder for other people to read your code than absolutely necessary, and don't expect your compiler to perform magic on weird code, even if it's _often_ able to.
To be fair, if the if-statement can easily be transformed into the switch statement as you did in the video, any reasonable compiler should output the same asm as the switch statement.
@@piisfun What? Modern compilers are perfectly capable of generating jump table from cascaded if statements as well as converting switch statement into series of comparision depending on whatever is faster in certain situation and are able to do it compiling much higher level language like C++.
Yeah, just put -O3
PSA: It does not matter.. modern compilers have agressive optimizers that transforms if to switch and switch to bit-tests whenever it is valid && profitable speed/size wise to do so.
Yeah I was going to ask about that in the comments, optimising compilers were my first thought
I don't really care about tabs vs spaces, but 8 spaces tab width hurts my soul 😭
the Linux kernel codebase actually use 8-width space or tabs (iirc)
I believe it's a method to prevent nesting. It gets unusable at the depth of 3, so it's motivating to extract and write separate functions/methods/classes.
@@moorscode that is actually the first positive thing I heard about such a big amount of spacing and it totally makes sense. Maybe I should try to get my coworkers machines to look that way xD
tabstops at 8 spaces is.... a very long-standing de-facto standard. I don't care what you set your indent level to, but on a modern computer, there's very little reason to make your editor necessarily use hard tabs of a different width, and plenty of reason (IMHO) to maintain the idea that tabs are 8 spaces (or rather, align you to a column number divisible by 8), for compatibility with existing things.
I know right.. i only use 2 spaces.
1. which compiler
2. what compiler options (if you have comparet on no optimization flags, then good luck, it's not even production code)
3. what language version.
This whole if / switch comparison makes litle sense, compilers this days will chop your code in sutch a way that you won't make heads and tails of it, so i assume adding -o3 will make bot comparable, but then again, you won't be able to read through ASM
I'm pretty sure same optimization applies to a sequence of IF statements on modern compilers. What optimization level is used here?
seeing the re-move of the value in eax it's obviously in debug mode, no compilers would output such thing outside -O0
This is what I was also thinking
When I was accelerating code by eliminating branches, gcc was already eliminating the lowest level if by using an optimal assembler instruction.
This is correct. Common subexpression elimination is one of the first optimizations I learned back in the 1970s while in college as it can be applied early while doing lifetime and flow analysis before code generation
This optimization can only be applied on if statements who conditionals strictly operate on integral types and never check said integral types against a range of other integers (e.g. > or
Great video as always. I understand the difference but only in abstract level so it's pretty cool to see how exactly it work under assembly.
Love your videos man, I know some of this stuff but it's a great refresher or intro for others keep them coming
This looks like a compiler's job to me
It really isn’t it’s all about how you want your code to run that’s why there are so many ways to do the same thing
you should use compiler explorer if you want to show whats going on in assembly, it has a much nicer view and will even highlight what gets translated into what assembly instructions.
I like your rectangular bracket styler theme, it helped me with understanding switch syntax a lot.
shouldn't the compiler be able to optimize the if tree to a switch like statement? (with -03 or -0fast)
I agree, but I'm not sure you can always rely on the compiler to do that on all platforms though
Trust, but check
So much this. At the end of the day if you didn't look at the compiler's assembly output you have no idea if your program is optimized
Very good. We learn today that switch statements in c is highly optimized. Thanks!
The trade off point between if and switch will depend on your target processor. A processor cannot look ahead with a jump table. Meaning it cannot keep the pipeline full. A processor may have branch prediction to try and keep the pipeline full. Lookup branch prediction and jump for your target processor. Only benchmarking will tell you the tradeoff point. Good luck.
I appreciate your explanation and comparison between if/else and switch statement.
As per Jason Turner, I would also almost always avoid using the default label when switching on an enum since you could forget to adjust the switch statement when a new value is added to that enum. This should always be configured to cause a warning in the compiler, but the warning won't work when a default label is present. And yes, you'll probably have to extract the switch statement to a new function so you can handle the default case outside of the switch if it falls through, but without that label.
Also another vote from me to use Compiler Explorer like Turner does when demonstrating assembly. It's just the best.
MISRA, for example, requires an explicit default. The alternative is that, unless intentional, the default should assert()... or just use a better static analysis tool/compiler, which will tell you when you have an unchecked enum value.
If this kind of error makes it into the wild, you have more serious process issues.
Perhaps in embedded land where unrecoverable errors are Really Bad™, but for most programs I would argue you should always have a default case that throws or asserts. Of course, I would never recommend a default case that just silently ignores the problem. Even better is when your compiler can catch the problem for you (a la Typescript).
MIND = BLOWN! What a great optimization, having seen that I can see bunches of ways to employ that to accelerate code flow in scenarios with complex nested comparisons. I would definitely want to wrap it with some sugar so its readable though.
Oh hey that's actually really cool! I've never seen someone explain how switches work at a byte level, and when you do it makes it really obvious why switches are so fast.
This will very likely be optimized out (for the if statement checks) if you tell the compiler to do any sort of optimization. Also, it's relevant to note that the hashing of the switch statement was so simple because you used a series of character comparisons of which each character was different. If you had multiple command inputs that matched even the first letter of the command, the switch statement would still branch.
But you showed a neat topic few know about, kudos to that
Please correct me if I'm wrong, but isn't this only true with optimizations turned off? I did a quick bit of playing around on compiler explorer before commenting and it was true there was a substantial difference between a switch and a if chain with optimizations turned off but if -O3 set both switch and if result in the exact same assembly.
It depends on how many cases you have
This. Decisions between if-else chains and switch statement should be based on what is more readable or what expresses the intend of your code better. Every major compiler is perfectly capable to see through switches and if statements and can transform one into the other if it thinks that's going to be faster. And generally the compiler will do a way better job at making this decision than the average programmer. The advice given out in this video is simply misleading and will make new programmers rewrite perfectly fine code because they now think that is will be faster (which it won't).
@@williamdrum9899 I did a bit more playing around this time with 9 cases instead of 3. The asm is almost identical, The compiler did switch to a different approach than before, this time it declared basically an array of length 26, one for each letter containing the start address of each case and then used the switch argument as the index to this array to find the correct case code, e.g. 'C' - 'A' = 2, 2 index in the array is the address for case 'C' which it then jumps to. This is the same for both if and switch. there is one small difference which is with the if version, there is a extra comparison at the begin which check the first if condition, if its matches then it skips everything I just mentioned. The switch version doesn't have this comparison but everything else is the same.
Not if your if statements greatly differ from one another
Yo this is actually so sick. I saw a comment saying what is basically is... But man am I glad I stayed around for the actual explanation this was great
actually an if else tree might get optimized into a jump table by the compiler if there are many branches, so using an if else tree or a switch really doesnt matter with an optimizing compiler. Though its good to know when to use what as it can make your code much more readable.
well perhaps, but people that care about such permeformance improvements are working with embedded devices like arduino etc. Everything is going to be quite basic.
keyword “might”.
@@Skyaidrules that's also the case with switches though
This depends on the nature of the if else tree. It can only perform the jump table optimization for if-else branches if 1) The conditionals only operate on basic integral types 2) The conditionals only test for equality or inequality, and doesn't use >= or
@@Joso997 Just because the device is limited, doesn't mean the compiler is.
Who else is interested in how the "magical value math" works ? The whole point of me watching this video was to understand this lol.
Jump/Hash tables are things I'm not sure I quite get, so me.
I just assumed it was like:
Table address = 1200
q = 71
d = 55
So it just reads the value (q) and adds it to 1200 and jumps to address 1271 and executes the code there. Actually he said this part contains a negative number(?) and uses that in conjunction with the table address to jmp to code. Close enough?
I think he went over this part too quickly or something.
@@user-zu1ix3yq2w he kinda explains how they jump to the exact switch statement that satisfies the condition. But there was a magic address that points to the statement in his explanation.
How it calculates the address to that statement was not explained and was mentioned as "magic". I clicked on the video title to know exactly about that, but it was mentioned as "magic math" here.
@@aneeshprasobhan Oh well. I think he should make another video explaining it. Obviously we could just look up jump tables and learn about them, but I'd prefer he just explained it in more depth. I've always found magic numbers fascinating. I think a jump table is a natural solution, one we would invent ourselves if we had been approaching these problems in assembly and using the goto statement, instead of using high(er) level languages.
I guess what I can say is, this jump table solution for switch statements (goto table[table_address+offset]) is better for (numerically) consecutive cases, and less so for cases that are "sparser," especially for memory management.
Seems to be like branchless programming. There is an Aussie guy on here that is really in to it.
I like that you supported your thesis with a reference to the assembly code. I would be even happier if you ran some test code to compare the time it takes to complete 100K of switch vs. if versions of code.
I think it boils down to a feature in the language. Switch statements have to have constants for the case statements. You can't use a variable in a case statement (i.e. CASE: ). So the values to be checked are all known at compile time, and the 'hashing' can be pre-calculated.
'If' statements however, could be comparing two variables whose values are not known at compile time. So even though in this example the value just happens to be a constant, the compiler doesn't have an easy way to go from assembling in each 'comparison' to trying to 'hash' if it just happens to be that one of the items being compared is a constant. Also, all the 'if' 'else if' clauses could be using completely different variables and values, whereas 'switch' statements the test parameter is always the same throughout all the 'case' statements.
Reminds me of the time I used a function pointer rather than a switch statement (20 years ago) did not do this, but instead searched down the list like the if statement. This was for a state machine with lots of states. I knew it was inefficient.
This switch-case example looks kind of like a function pointer. When I have a long-ish list of compares like this, I tend to check the assembly output for efficiency like was done here.
No measurements? The first step in optimization is measurement.
The second step is to turn on your compiler's optimization.
I learned something new and also realized some illustrations would be very helpful. Especially if to explain how to use an input in a table of negative numbers to subtract it and find which option to choose without it comparing two objects 🤨?
This was super cool. I got out of the habit of using switch statements but I'll start doing it more now.
I ran the if statements versions if O3 optimizations enabled with g++ compiler, and it got converted to the switch version !!
Compiler optimization is pretty dope
Nice! A very common place to optimize with switch is when parsing command line arguments. The problem is when you need to call strcmp or some function like that for every argument, you can't do that in a switch statement. A nice trick is to separate what can be solved with ifs vs switch and use the switch first, managing to even prevent the strcmp function calls.
I wonder if you could just run a switch statement over the first character and only then do the `strcmp` (and only compare with values that actually start with that character), but that would make the code look a little ugly. :(
@@ThePC007 That's actually a very good trick, for example gperf uses that trick to parse keywords to generate hash maps. I actually use it all the time when parsing command line arguments, I check if the first character is a dash '-', and only then I call strcmp from the second character, as most command line options will start with dashes.
To parse argument options you can hash argument values into a fixed size (per value) hash board buffer (long enough to hold your argument options) where you hash the string value and then memcmp() the two memory blocks to make sure the value is the same as you wanted.
Then you get an almost constant evaluation time.
@@informagico6331 That sound extremely efficient and fast, and probably the way to go for big production programs, but maybe an overkill if you're making a simple cli tool. Depending on the amount of available command line options, the simpler way could even be faster.
Yacc + lex. It's a long time I used them last, but if I remember correct Lex can make exactly such tables.
NGL I was not expecting much. But this is amazing. Not a single comparison.
Nice tutorial! I know its just a test program but you should consider to clear the optionbuf with 0 before you use it since there may be arbitrary values in it and it potentially can trigger your stop condition
He also has a 1byte buffer overflow since the length specifier in scanf("%4s", optionbuf) doesn't include the null byte and completely failed to consider compiler optimizations. This video can basically be deleted
Fun fact:
* Write some code in a function, doesn't matter what
* start a switch statement at the top of the function
* put a "}" at the end, to finish the switch
* sprinkle "case" statements in between the lines of your code wherever you want. Even inside loops, if staments, other switches etc.
This is legal C/C++ and it even works, although it makes no sense at all.
“Brilliant,a *free* and easy way, …, 20% off subscription” sure
I was afraid of for loops and used nothing but switch statements in my code. Then I finally learned for loops and have began rewriting a lot of my code to make it a whole lot better.
scanf("%4s", optionbuf), from man scanf:
An optional decimal integer which specifies the maximum field width. Reading of characters stops either when this maximum is reached or when a nonmatching character is found, whichever happens first. Most conversions discard initial white space characters (the exceptions are noted below), and these discarded characters don't count toward the maximum field width. ***String input conversions store a terminating null byte ('\0') to mark the end of the input; the maximum field width does not include this terminator.***
Also, your while loop condition is UB on the first iteration.
I always knew switch was the faster option after I learned Java but had no idea why until now. Thanks for this!
glad to hear THAT, because the program I've been writing has a switch/case block with (so far) 171 cases in it, and it'll probably end up with a lot more than that before I'm done
coding sites for awhile and this just made me want to dig deeper into assembly, maybe lol. Thanks for the video great information! *the more you know star*
Now I'm super interested to what does a match statement in rust compiles to
Thanks for the video, I think it would help a lot of people if you dived deeper into ASM to explain the differences between using ifs and switches. There are some things that really do need to be talked about in terms of what the computer and processor is ACTUALLY doing and switches and ifs are a perfect example.
PS. I had no idea people still had tabs as 8 spacing instead of 4 or even smaller. That is wild.
I remember learning about another benefit in my computer architecture class. Modern processors use tricks like out of order processing and branch prediction to improve performance. More branches = more wrong predictions and more operations performed that need to be discarded
I was looking all over for this kind of explanation and never found it, till you demonstrated...
So, thank you for finding the time to explain this topic so thoroughly.
Although I have a question.
What if you use if statements without the else keyword, does it change anything? I, for myself, don't think it would change because it would still have executed each if statement to compare the values.
What you are thinking is only applied in the worst case scenario, the nested if-else will break the checking once the there is a match case.
Awesome video, thanks! :3
I wonder whether the same holds true for rust if statements vs switch statements
It does -- play around with rust's match with compiler explorer, it's very smart
I still remember reading the AMD optimization manual like 20-ish years ago and figuring out how to use that to your advantage in so many ways. Even when you have simple string constants you can still take advantage of it by pre-hashing the strings, and there was another trick in there involving multiple if branches that could be compressed into a single switch by using the compiler's own optimizations to convert a test into a simple bit and then bitwise or them all together.
can you give me that resource to read?
@@sent4444 I can't directly link it, but just Duck the AMD optimization manual and you should find it. The Intel optimization manual is also a good resource. They both provide some really good tips if you're thinking of getting into writing assembly or a compiler or just improving your code from a higher level.
Amazing. I've always wondered how a switch...case worked at low level.
Some benchmarks would be nice to check if the performance really changes that much (probably not).
Any optimising compiler worth your time will produce identical code for either statement anyway. Usually it is able to transform the code into either lookup tables, trees of if & if/else statements, and often even branchless code. LLVM has been able to do all of this for a while now, as has GCC, and even MSVC has some capabilities here.
This guy is really being irresponsible by presenting his performance advice as true when it very rarely is, and not even measuring the difference.
@@codaaaaaaaaa and even if the compiler doesnt optimize in the vast majority of cases you dont even care as processors are extremely fast
Absolutely fascinating! 🤯 Thank you very much! This is the first explanation of why switch is preferred over if else that made sense to me.
The way I understood it from working in assembly is this: With a long chain of if-else you compare your input to each possibility. With a switch statement you're comparing nothing at all!
You may also have a look at CPU architecture, the scheduler load the instructions in a cache and do speculative out of order executions, which basically render this optimization useless. 😂
@@timmygilbert4102 Right. Would be interesting to test under which circumstances the benefits of branch prediction of if/else outweighs the gains of a switch statement. 🤔
@@sciencelab4225 there is a blog that test it, 1024 random if with no slowdown. Memory access is slower than compute, so reordering the instructions cache to feed the register memory and discarding false execution is faster than just querying the right branch. So if you don't have long switch statement or deep if tree, by witch you probably need another way to structure code, it's unlikely to even make a dent or show up in benchmark. It's only style choice.
It was the fastest in the era before caching
Wow, this is way advanced than I 💭
Thank you
you are awesome. you should do a playlist like Jason Turner only on Assembly (quick daily videos) and that'll be a huge success. Thx man.
That's actually awesome. Time to go restructure some of my Rust code.
The issue is mostly about difference in branch prediction misses. Anytime one branch goes differently than predicted every instruction in the pipeline after branch gets squashed. For instance ZEN2 that's 18 cycles with potentially 4 instructions decoded per cycle, and for all modern PC processors it seems to be on that ballpark.
The nested if statements can do that multiple times while calculated only does it once.
Damn. I just needed this since I've completely forgotten to use the switch statements.
Calling function pointers from array is quite similar, but should be somewhat faster.
Might be different for out of order execution, but when your cpu is piping in instructions, it will usually be processing multiple instructions at a time. But that means for an instruction like jne, your cpu may end up processing instructions right after the jump when in reality it needed to be processing instructions at the location specified by the jump instruction. When this happens, the cpu is forced to flush out the instructions and then continue from the correct location. Branch predictors can reduce this chance but that is an additional cost of if statements.
Exactly my thoughts 😊
I would imagine that a switch statement makes it easier for a compiler to optimize for branch prediction.
🤓 This is my comp sci degree speaking out, but there is a case where an if/else block might have a marginal performance benefit. If your input data is distributed in a way where one or two values are the overwhelming majority, with tertiary and onward values being exceedingly rare, it might prove just barely optimal to use an if/else tree rather than a switch.
The important point is that you *MUST* profile your code. Modern processors are just so complex that you just can't make any assumptions about performance anymore.
🤯
This is extremely cool!
nice! also im sure if i use a switch statement that turns out to be really short and use more cycles, the compiler might just optimise it into if/else for me
I must say Assembly language explanation is truly valuable and allow to reduce loop cycle it mean CPU time....Cool good work.
Compilers will likely be able to optimize ifs to the same code as the switch in such cases.
Would be cool a video about computed gotos and a comparison with using switch statements.
Because in many cases they translate directly to a single or very few assembly statements. However, given a properly designed compiler and language designed to be optimized, often IF statements can in select cases be translated to be as efficient as switch statements.
For small count of options, a jump table can have negative impact because branch predictor can run into difficulties to predict jump through the table. However, the compilers often transform this special edge cases into if-else series anyway.
If one option appears often then others, is is probably better to make if statement with likely attribute for this option and then use switch-case for other options
What do you mean with prediction? isn't it a number that goes into adding to the program counter value to jump for that specific branch location line?
I began programming in machine code, then assembly. Working down to the bare metal is the best way to understand how to write efficient code. I learned all these tricks from the start.
Reminds me of an array of function pointers but without the overhead of a call
Going to -O1 or -O2 could enable jump optimization and/or inlining and most of the code disappears in this example.
It looks more like a jump table than a hash table as others have opined. Also, this only works in certain cases, yes? if the range of the switch is too large (say, outside the range of a few alphabetical letters) then I think the switch statement resolves to a series of "if" statements. Great video, I'm loving all this geeky low-level stuff. I'm subscribed and continued success!
so basically the compiler converts the switch statement into a sort of hash table? that way it runs a hash on the condition and immediately jumps to the corresponding branch's address, correct?
yes, correct.
Very cool video, but I have some questions,
first of all what if I use a switch statement to compare a value to 0 and INT_MAX, then the jump table is gonna be pretty big sacrificing both on both storage and ram, which may actually matter for weak embedded systems
second compilers are pretty smart today so if you have a lot of if else statements after each other compering the same thing to something I'm pretty sure it's gonna optimize it away into a switch statement
For your first question, the compiler is smart enough to make it a branch. Chances are it will convert
switch (a){
case 0:
break;
case INT_MAX:
break;
default:
into
xor eax,eax
je IsZero
inc eax
je IsMaxInt
default:
ret
IsMaxInt:
ret
IsZero:
ret
(abusing the property that INT_MAX + 1 equals zero)
Hi. Can you also compare switch statements with array of function pointers? I understand that switch statements are faster, but how much faster? Because for large cases the array of func ptrs improve readability.
So what your saying is it oils down to a condition jump which can writen as if val = n then goto line y else fall through and run a similar test with a different n value, again exit to y if that is true.... everything can be expressed as an if statement once you undserstand fall through. Unfortanatly a fair number of languages don't seem to be able to suport it due to not being able to call to a line or have a title part way through a function. I suspect the the switch statement is the implementation that obviscated away behind a compiler. But when we get down to brass tacks, it's just a state machine.
Love your channel
There are 3 ways to do this and option 3 is the fastest and cleanest. That’s having an array with function pointers for each of the enum values.
Switch statements are also much more clean when you read code
It's more verbose
@@timmygilbert4102 well, I suppose we can't have everything. If I have to write more than two else statements, I prefer go for a switch
@@peyop5262In principle I agree it is cleaner, but I don't like the need for break.
@@cherubin7th break breaks everything, which is why I prefer if. Also in game making, whenever I have a switch I'll need to break it because exception happen, with a if it's just inserting or changing the test. Though nowadays I just pass a fonction or an object by reference, much cleaner.
I have recently started using switch() statements in interesting way:
Have two compares on both sides of &&?
Bit-pack compare bools into int as two bits and switch case on the int. (4x cases)
On three bools (8x cases) this is massively more simple and faster.
Making menu state for my digital watch on arduino and was wondering whichever is faster method. Thanks!
This was actually very confusing when I was younger, what a nostalgia trip.
What compiler and optimisation level did you use? I'm surprised that compiler didn't optimise it.
Ah yes the good old jump table. I remember playing ShenZhen IO (it's a game (if you can call it that) where you build digital circuits and code with a very simple RISC assembly) back in 2018. One of the levels was a sandwich making machine or something, and I had the idea to use a hard-coded jump table (using a ROM) to store the recipes and thereby cut down the number of instructions.
This is basically just that, but slightly more involved. Slightly.
Fantastic video.
Basically proof that switch statements are indeed magical since they teleport you based on the input lmao.
6:54 If you declare a variable and set it to optionbuf[0], would that make it possible to prevent all the duplicate movzx calls? Or do the mov calls prevent that optimization?
I assumed that it generated some sort of search tree. But this is linear time, it’s brilliant!
would that be a buffer overflow at 2:00? as in, scanf may write a null terminator as the fifth character, right?
do you use vim as your main editor what editor are you using???
one for one, a predicted if is faster than a switch. if you have more important values (such as a success vs error return) where the success performance is far more necessary, an if for the important value(s) first then do whatever with the rest. it allows for branch prediction then. Also, if your tables isnt dense it will be converted to an if-else tree anyways, Predicted branches are msotly just the instruction slot expense so single cycle - almost free.
Is this also true if we increase the compiler optimization?
I would expect an optimized compiler to handle if statements more efficiently than just comparing each value? 🤔
No, they'll be exactly the same if you allow optimizations in any sane compiler.
Remember, the compiler is officially allowed to do anything as long as you can't "notice" - and you have to follow certain rules set out by the standard to do any of that "noticing" in the first place.
Just that modern compilers already optimize all this stuff for you, so it really doesn't matter which one you use.
does this apply to c#'s pattern matching switches that it is faster than else if? In c# you can put there like if statements for cases for example you can make case for when it less then something and bigger than something and equal to something. I was wondering if it is still faster or if it is the same speed as else if statements because visual studio/rider keeps suggesting to use switch instead of else if?
Wow!
You won a subscriber!
First of all, use "gcc -O2 -S", and then analyze the resulting assembly code. The assembly code you have shown (the first one) most probably resulted from unoptimized compilation. my gcc 13.2.1 generates different code.
Second, use non valued enums (not assigning values to the enumeration identifiers), and the result will even be better.
And finally: switch was always supposed to be implemented by jump tables, but in some cases (like having only a few choices), the code generator could select a more appropriate (=faster) implementation.
hi, computer engineering student(hardware lol) here. switch statements are basically state machines on the hardware level(think of it like a recursive register that updates itself due to some conditions of the current state and whatever inputs/outputs) and they are quite fast as opposed to abunch of if statements/nested if statements as thats just a ton of multiplexers in a row and as great as a multiplexer is, they can have quite the long bit depth(the longest path a bit of information can take) its just more efficient to use a state machine which may only use a couple mulitplexers per clock cycle and register delay is much less than that of a mux.
How you got that assembly for the switch with gcc x86-64 ?? I get it only with clang x86-64.
Switch statement is also to do docotomy when values are dispersed.
We can also take advantage of both worlds, by doing if (most probable value) and switch on the other values.
Cool video. Are you using Sway or i3?