4 Billion If Statements | Prime Reacts
HTML-код
- Опубликовано: 21 янв 2024
- Recorded live on twitch, GET IN
/ theprimeagen
Become a backend engineer. Its my favorite site
boot.dev/?promo=PRIMEYT
This is also the best way to support me is to support yourself becoming a better backend engineer.
Reviewed video: andreasjhkarlsson.github.io/j...
By: Andreas Karlsson
MY MAIN YT CHANNEL: Has well edited engineering videos
/ theprimeagen
Discord
/ discord
Have something for me to read or react to?: / theprimeagenreact
Kinesis Advantage 360: bit.ly/Prime-Kinesis
Hey I am sponsored by Turso, an edge database. I think they are pretty neet. Give them a try for free and if you want you can get a decent amount off (the free tier is the best (better than planetscale or any other))
turso.tech/deeznuts - Наука
programmers in 1969: send a spaceship to the moon with only 4KB of RAM
programmers in 2024: i need 30GB to check if a number is even or odd
😂😂😂
The power of optimization and deoptimization
@@falconheavy595 yes. i wont argue it, but yes.
You can't send a spaceship to the moon, you need a moonship for that, duh.
The benefit of AI is that it would never write this.
The drawback of AI is that it would never write this.
Dynamic meta programming optimization - Take the number, write the single line of code to check that number to a file, compile it, run it.
In case the challenge was "not to use aby math, just IFs" (not sure), we could just set a list like odd_array = [1,3,5,7,9] and check IF the last digit of the input number is in odd_array. Number is odd IF it is, else it's even.
But it would not be funny and challenging, lol.
Loved his solution.
@smanzoli depending if it is unsigned, you can just bit mask the least significant bit and check if it is equal to 1. If it is, return true in isodd. Else return false.
This should also work with 2's complement representations as well.
If we are going with all negative numbers are not odd, we simply have to check ifNegative before checking the odd process explained before.
built-in caching by checking if the if statement already exists in the file before writing to it and compiling
@@TJackson736 sounds like math. No math allowed
@@youtubeenjoyer1743 the math behid that is not that complicated, its more theory heavy tbh but yeah kinda genius ngl
conclusion:
9:16
If windows says you can't compile a 40gb file you say yes you can
never stop stopping
but would other operating systems be chill with it? because we all know that windows is gay and everyone should convert to linux.
@@lordender_kitty_official 1. homophobic intent, please fix yourself
2. bro who do you think uses linux???
@@cewla3348 how do you know he isnt gay?
@@treanttrooper6349 because he’s using gay as a negative adjective, which is homophobic. Read his damn comment.
I took my first programming class in high school and one of my assignments was to write a program that let you select a month/year and the program displayed the calendar layout for that month. I proceeded to write out every possible calendar layout for each combination of days in the month and starting day of the week all chained together with if statements.
After a few hours of copy pasting calendars and moving around the numbers my program was ready to be printed and passed in. Yes my teacher graded our programs by hand with pen and paper. After several minutes of the printer chugging along nonstop my classmates began to notice the monstrosity I had created. My teacher was not happy when I handed in 100+ pages.
He didn’t know what a loop was 🤣🫵
@@andarba2148 I think we learned loops the following week 😭
bruh there is no way 💀
@@dboss112 RiP
@@dboss112I love stories where the teacher is the one learning lessons.
I love that the guy used modulo in python to generate the first file
The algorithm wasn't self-hosting yet. This article was about the bootstrapping process. Python will now replace its current implementation of % with this one and see 10x performance increases.
@@davidboeger6766 a bit wise AND would be a far better implementation
@@davidboeger6766 Do something along the lines of this 💁🏻♀
iseven = True
for n in range(4294967296):
print(n,"is even" if iseven else "is odd")
iseven = not iseven
Substitute in your actual code in the print statement.
@@KleptomaniacJames The correct way is to go in batches of two. i is even, i + 1 is odd.
before doing that I would first check if the compiler doesnt already do that for me and keep my good maintainable code@@KleptomaniacJames
paid by the lines
"I've written over four billion lines of code." - Every programming resume ever.
now make that an npm package for the world to depend on
😂
That's too cruel
`node_modules` about to bloat harder than a black-hole with the mass of all observable galaxies
now that is true evil
For the universe to depend on
Using the slowest programming language to automate writing 4 billion if statements in the fastest programming language. That is gangster.
Indeed
actually haskell and especially lisp programmers build real-time programs by embedding low level languages, a high level representation, and building a compiler between the low level and high level representation.
someone really saw Yandere-Dev's code and said "bet"
Now I needs a part 2 comparing the performance of a 4 billion switch statement
Actually, it could be a lot faster if the switch statement gets compiled to a jump table.
It would be a jump table with 4 billion entries one byte each as per how most compilers work. Obviously optimization could do bits or with two cases change to a conditional jump or even just recognize its simplifiable to a parity condition.
@@Ipanienko No. Memory access times will kill the performance.
That was the first thing out of my mouth, "Ya know, a switch statement would be faster..."
"All unauthorized distribution of this source code will be persecuted to the fullest extent of the law" 💀
why not create an api call to chatgpt for every number?
What are you? Elon Musk?
@@macchiato_1881Tesla's co-founder and CEO. Elon is inventor and maverick entrepreneur
This is Elon Musk
Careful, someone might steal your startup idea!
@@darekmistrz4364 lmao he did not cofound tesla
In theory you could have several 1000 people try out this program then record all there inputs then reorganize the ifs so that more common numbers are higher up in the if list to optimize it
Reminds me of the story Chandler Carruth told about optimizing some C++ code written by Ken Thompson: ruclips.net/video/nXaxk27zwlk/видео.html
@@user-sv3dc5nz8w definetly this. I would happy to give some memory to program so it can run faster.
Apply some bitwise magic and the storage requirements go down to 0.5GB
@@knutharald9814 ... what?
@@user-sv3dc5nz8wAside from 2 and 3 ALL primes have the form 6n+1 or 6n-1; no need to store _every_ number.
I think theo said it best, when he said: Imagine showing this to a programmer 15-20 years ago. They would have an aneurysm.
if it works, don't fix it
because people actually cared about performance, and sizes back then (when the program must fit on a 1.4 MB floppy or you have to write an installer, size of everything mattered)
we now live in a world where with a processor, memory, and busses run 400x faster still takes the same amount of time to determine if "hte" is a word or not.
Yeah Gigabyte was not a unit of measurement back then so a 330 GB “program” is incomprehensible
@@berniecat8756
In 2004? It would certainly be. We had DVDs back then which had 4.8 gigabytes.
Um... Guys. 20 years ago was 2004. We had multi GB games back then. And 500gb hard drives.
Halo 2 and half life 2 came out 20 years ago
YOU MIGHT NOT LIKE IT, BUT THIS IS WHAT PEAK ENGINEERING LOOKS LIKE
Yandere sim dev style?
No matter how many times I hear this story I keep laughing out loud. This guy better be a writer as a side hustle.
3:30 *"What could go wrong?"* is really THE fundamental question that drives the entire IT industry.
Rust Programmer: Writes 4 billion if statements.
Rust Compiler: "Cannot use moved value. Value moved in first if statement."
Thats easy to solve just use python to put .clone() behind every one that will fix it
Integers in Rust implement Copy. Meaning they shouldn't have that problem.
A rust programmer would always use a match statement anyway
@@Codotaku time to
match bool {
true => { /* ... */ },
false => { /* ... */ },
}
match and enumeration with assigned discriminate value is the recipe.
This software is written and optimized for next gen hardware. You can't expect that your 10y old 4760k with 16GB of ram will be supported forever.
This is unavoidable progress, it's time for an upgrade
so true
16 gb ram - a NOT old PC. Old PC - it's a max 8 gb.
Yes, I use really old pc...
@@WHEELESMe with 4G of RAM and a 5th gen i5
@@lockl00p27 Me with a 1GB ram laptop i found in the trash with who knows what processor
@@tl5429just neofetch and google it?
You could achieve this by training 4 billion pigeons to peck a button if their number comes up.
Hear me out: trained pigeons with robotic hands working for humans and producing goods while they live in paradise. Way better than AGI.
My favorite compiler. Python.
Just as Ross van der Gussom envisioned.
I'd have a foot pedal mapped to SHIFT if i was programming DirectX
Genius
I have left click mapped to my scroll wheel and all I do is play Old School Runescape.
and then they will ask you, why you only train your left leg on leg days
windows leaves some of the memory mapped pages in RAM even after quitting the program. So next time you run the program, it does not have to load all of them from disk, that's the magic why it's faster than loading from the disk. On a cold start will be much slower.
(40 - 32 Gb)/800 Mb s⁻¹= 10 s, so that explains it pretty neatly.
This reminds me of some advice I got at uni, if you have to jump through a lot of hoops to do something you might be doing it wrong. (paraphrasing a bit here but it applies)
True, unless you're trying to win a hoop jumping competition.
Borrow Checker : "Finally, someone who appreciates my work!"
@@nathanielalderson9111 and I'm sure your users will appreciate that explanation when your software doesn't work because 'well the API to do the thing I'm trying to do is made in a way I find inconvenient, so until they refactor it how I want I'm not making anything'
You can either complain about the world being imperfect or put in the work to make it better. You are the only variable that you can control, blaming external factors can't solve much of anything but it can break a hell of a lot. Sure, you *can* give european politicians the right to dictate the hardware on the devices you (and everyone else) are allowed to buy, or you can just stop buying from Apple - which of those routes has more knock-on cobras?
@@nathanielalderson9111 because the lifepsan of the joke is shorter than the length of time we've been churning out shitty sub-par software and it's quite hard to keep laughing all the while you keep getting kicked in the balls because it's always [someone-else]'s fault.
More generally because this 'I'll just force the rest of the world to change because I know I'm right and don't need to rethink anything' philosophy is just plain really fucking annoying. Once yesterday's parody becomes today's philosophy it's kinda hard to laugh at the parody anymore.
@@robonator2945 good grief man!
Go away! Go take your bitterness and harshness elsewhere.
No, seriously. Go get some therapy. Programming is always going to be a headache, and it really sounds like you either need to deal with some heavy stuff, or find a way to let it go.
Aggressively attacking (with words) a random on the net just shows me that you also have the attitude of "I'll change the world because I'm right" attitude that you seem to think I have, from a freaky dumb joke.
Go kick rocks.
Average YandereDev script
In 5-10 years the compiler will notice that you could optimize all this with a mod function. He's just ahead of his time.
Ah but optimization was turned off. I wonder if the compiler *actually would* notice if optimization *was* turned on.
Dang that’s bad….
Ever heard of a switch statement? That’d clean that right up
"The CIA wants you to think ifelse is the same as switch"
- Terry Davis
Switch? What are we, gay?!
What a Chad.
Hats off, my dude.
That article is a work of art
"And they call me a madman."
"Who created 4 billions if statements. "
"I'm a survivor. "
I love how those programs that generate the code to check if the number is odd or even, always have a "x % 2 == 0" somewhere
From the title I thought we'd be reviewing YandereDev's code lmfao
The logical evolution of this program would be, to publish it as a npm library which uses performant C library under the hood. I'd bet it would get 100k+ downloads within a year - if we figure out a nice, short and catchy name for it!
StEven.
Saint Even, written by Steven,
answer the holy question: Is this thing even?
The 4GB file size limitation in the Windows PE file format is an artifact of its design and also how the Windows loader handles loading binary files. However, you can load multiple EXEs and DLLs into main memory that are each up to 4GB in size. The Windows loader performs a LOT of work when it loads a PE file into memory, including spending time remapping addresses in the code section so that the code inside executes properly. So to get it to compile, they could have broken up the file into multiple 4GB DLLs and then...loaded all of them with each one dependent upon the next one.
this is absolutely deranged, and I mean in in the best possible way. I love it
Pushing the limits of computing!
Imagine the CPU franticly trying to pre-execute all those alternative code paths right from the start.
No need to pre execute, it's comparing a register with an immediate, so there is nothing to wait for, the only limitation should be how fast the CPU can load the code
@@Jason9637 my dude. Most of us don't understand assembly so most wouldn't be able to predict that.
But that means with 4 billion comparisons, there are 4 billion data chunks to compare, and assuming they're all integers that should mean each input for comparison is 4 bytes.
That means 4 billion comparisons would result in 16 gigabytes of data flow through the CPU, which means you'd better have a lot of ram. I'm not even going to bother thinking about floats or strings
@@FLMKane That's not at all how this works. The CPU doesn't need to store every value in system memory then wait for it. Maybe it would be helpful to learn the basics of assembly (it's really not that hard)
0:28 You should see some of the code I've seen in our core business critical systems...
I’m ashamed to say, it took me a few rewatches until I grasped every step in this article.
Most important is that you enjoyed it (probably?)
Amazing solution! Now we just need a JS version so we can add this to npm!
That's some NPM worthy algorithm. Hats off
Couldnt stop thinking that finding this as an npm package would not seem unimaginable to me.
still faster than python
Python programers when they see this: 😡😡😡😡😠👺👺👺👺🤬🤬😡🤬👺👺👺👺😡🤬🤬🤬🤬👺🤬🤬👺😡😡😡😠😠😡😠😠😠
Why are we calling Guido van Rossum Ross van der Gussom? Is this a meme i missed?
This code is STILL more efficient than the code game devs make today
Wow. That was fun. Reminded me of what programming was all about when i was younger. That guy deserves respect.
"This is where the machines can rise up" 😂
Loving these challenges!
Here I was thinking an "is-even" would be done well enough just by returning the inverse of the final bit of the number.
This is so much better!
And now we just need another 4 Billion of these and another function that determines which of them to use to get a universal modulo function. It's just that easy.
The person who rote the article woke up and chose violence with no witnesses, 11/10
Imagine if we used that compiling power to check any useful info instead of odd and even numbers 😢
Laughed so hard I almost snorted my coffee :-) classic episode, thanks again primeagen
Modified this for fun. Did a while loop with with a fll where the odd node pointed to the even node and vice versa and just moved to the next node and added one if the number didn't match. Not as impressive, but still a fun way to do it in the spirit of doing almost no math.
I think you could short-circuit this and jump directly to the address where the comparison for the input number is done.
Then, you can pre-compute the result.
Then, you can pack this, because the result is always just a bit.
PROFIT!
This is essentially a lookup table, which is essentially a switch-statement, which is definitely not 4 billion if-statements
The thing is that he specifically turned off all optimisations, otherwise the if blocks would have gotten compiled down to jump tables
I like the idea that at the end of it all there's some variation of
"else: return x%2==0"
Just in case there are any numbers not covered by the 4gb if statement.
Aint no way even as a beginner i ain't writing that much if statements. Too lazy
If you wrote one entire if statement per second, it would take you 138 years.
@@jerichaux9219 that’s a short time to finally solve isEven
You write a program to generate the program. Simple 🙂
You come the right way. If you're lazy, you can make a great code lol
I needed this! Thank you❤❤😂😂😂😂
You also wrote a program like this once and that's one thing beautiful about learning how to program.
This might be my new favorite piece of programming media ever
I strongly suspect the speed came from the CPU's branch prediction. After a few iterations, it would realise all previous cases are false and start pre-loading page after page of the code for the false paths only. Eventually, when the correct number rolled around, it would be true and, therefore, a prediction miss, but it only needs to go back and re-evaluate the true branch once and then quit the program.
This is the funniest goddamn thing i've seen all week. People don't even know how efficient if statements are compared to switch statements or even if else statements.
Funny ;-)
Reminds me when I started to learn to program using the manual for C64 back in the days. I wrote a text-based adventure game using like only if, goto, print and input. Storage took up two sides of a cassette tape and the game wasnt long at all. Nevermind that when you played you had to type in the exact correct string to move on in the game.
7:28 WIN32 and their handles, messages, dwords was designed by a polish engineer who first introduced the idea of dynamically defining APIs with just prefixes.
I kinda did the opposite, a much more compact program than you would expect: In computer studies at school (mid-80's), we were allowed to bring our own computers in if we had one. I had my ZX Spectrum and all the Commodore and Atari fanboys laughed. The teacher set a task to write the most interesting 1-line program that we could. Fortunately, not only was the Spectrum perfectly happy with multi-statement lines, you could actually Poke a 'return' address from an imaginary GoSub which was a line number and statement index. I can't remember what I made it do, but it was basically a whole simple program, with conditionals and branching, in one line. ;-)
Hmm, I think we can go larger, we use compression to store the machine code pull out the section we need and set the instruction pointer to it. What could go wrong. Or maybe we could generate the next if statement at the end of the last one.
"Can we have O(1) code mom?"
Mom: "We have O(1) code at home"
The O(1) code:
I am just new in programming(start in the end of 2022 with C++, and now from November 2023 use C#), but that sounds so crazy😵
this made me laugh so hard, thank you sir! : D
The funny thing is that in the latest code generator he uses the modulo operator :)
I came across this problem myself, I sufficed for mod 2 like any other normal person, 1 line to read number, an if statement to determine what the result of mod 2 of the input was *dab*
I happen to know what the problem is of why the line number error. Somewhere there is a part that noone bothered to change for 32 bit to 64 bit in the compile process, so it ran into the limit due the 32bit. How do I know? I tried to write a 6GB csv file on 32 bit Linux and it failed because it could not store the line number by around 4 GB
This is much better than bitmasking the int, and using that as a boolean. I am truly humbled by this genius gigachad.
this is a fantastic video!
Reminds me of making PHP code that wrote javascript functions for each column dynamically based on the type of column because javascript didn't like polymorphic sorts.
Tried to do this in Rust with a 4 billion item long match statement that covered the entirety of u32, sadly I do not have enough ram or knowhow to get that working. Macros let you get around the whole 4gb file size limit but that's my limit.
However with u16 it took something like 200ns to work out if a number was odd or even.
No language feature can let you get around the 4GB limit of .exe files. That's just a Windows limitation.
4:20 "Compiler limit of 16777215" // this is also the same amount of possibilities for RGB 0-255, interesting.
Respect for going through that whole ordeal tho
Yup,that recursive function sitting in the corner.
The pronuciation of strtoul was spot on :D
dude i need MORE from this Blabbin' guy! I can't believe he hasnt got more posts up fuck he's funny
having not yet finished the video I think the solution to the line limit problem is fairly obvious. make separate executables for each possible number. convert the number to a string and then call the file associated with that number.
You all laugh at this, but some form of this is actually _really_ highly performant for ab-initio quantum chemistry.
It has really complicated numerical algorithms for the integrator, which if unrolled may be gigabytes of code, but the unrolled code runs on GPU an order of magnitude faster.
I love chat jippity
You don't even need modulo for this. Bit mask the input with bit wise & 1 and checking if it's >0 works.
Probably faster than running the division instruction that gets run when you do a modulo operation.
That's how modulo is actually implemented- bitwise ands for powers of 2 and "magic number" multiplication for the rest
This is beautiful!
When dealing with python nesting limitations, all you need to do is believe. Convert it to single if statements, when when Python still says no, write your own mapping python interpreter in C (or python)
Combine the python and c program to count up to the number flipping an odd/even boolean. Does it run faster or slower? I wonder if you give it to ChatGPT and ask it to optimize whether it can. Can the compiler optimize it?
*ahem*
For those new to programming, the correct way to check if something is odd in Python is:
listNum = list(num)
odds = ["1", "3", "5", "7", "9"]
if listNum[-1] in odds:
return "Odd"
else:
return "Even"
This is pure genius
It reminds me an article about key pressing digesting...
7:25 I think you should get a pedal that you can map to a specific button like caps lock and/or shift, that way you are not causing problems with your hands. After all your feet are just laying around being lazy.
for the problem you mentioned at 7:25 - consider getting a shift key foot pedal.
This is pure madness. I like it 🤣
Once worked with guy, we were supposed to convert data to a flexible third-party api, and different customers had different needs. He started coding, and his approach was code with lots and lots of if-statements. I had to step in and build a more abstract per-customer configurable solution that didn't involve hundreds of if-statements per customer.
But I'm sorry I had to watch this to the end... :-/
i would've tried to make multiple dlls to call from the main program, so we check every number every time, just in case, one can never be too sure
“Are these the world’s crispiest fries? Let’s find out.”
:Starts evaluating with this program and sits there waiting for an answer until video abruptly cuts off (stream ended with blue screen: memory overflow):
My first thought would be reading the final bit of the input's binary code, 0 even 1 odd. This man went above and beyond with his dedication to one method.
most interesting 10 minutes of 2024
Whilst on the topic of bad solutions. You could do it with recursion. Define base cases, and subtract 2 till we get to the base cases.
These articles are so fun and very well written compared to the geniuses at the ny post who came up with such bangers as “Reddit user praised after refusing to swap airplane seats with pregnant woman”
fun fact... u cn write a 3-4 line code to get that abomination of aa list of IFs.. and then copy paste it in the code to quickly write thousands of lines of code