4 Billion If Statements | Prime Reacts
ฝัง
- เผยแพร่เมื่อ 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 - วิทยาศาสตร์และเทคโนโลยี
![[LIVE] : ONE ลุมพินี 63 | คู่เอก "ยอดภูผา vs โซเนอร์"](http://i.ytimg.com/vi/RGVmBsegKEI/mqdefault.jpg)
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
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.
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 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
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
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.
paid by the lines
"I've written over four billion lines of code." - Every programming resume ever.
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..."
someone really saw Yandere-Dev's code and said "bet"
"All unauthorized distribution of this source code will be persecuted to the fullest extent of the law" 💀
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: th-cam.com/video/nXaxk27zwlk/w-d-xo.html
A better approach is to pre-calculate. We can do it for every number using our first version from the article. Then embed the results into an array of 2**32 items.
@@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?
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...
No matter how many times I hear this story I keep laughing out loud. This guy better be a writer as a side hustle.
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
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
YOU MIGHT NOT LIKE IT, BUT THIS IS WHAT PEAK ENGINEERING LOOKS LIKE
Yandere sim dev style?
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.
3:30 *"What could go wrong?"* is really THE fundamental question that drives the entire IT industry.
My favorite compiler. Python.
Just as Ross van der Gussom envisioned.
You could achieve this by training 4 billion pigeons to peck a button if their number comes up.
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?!
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.
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
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.
What a Chad.
Hats off, my dude.
From the title I thought we'd be reviewing YandereDev's code lmfao
Amazing solution! Now we just need a JS version so we can add this to npm!
"And they call me a madman."
"Who created 4 billions if statements. "
"I'm a survivor. "
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.
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?
Wow. That was fun. Reminded me of what programming was all about when i was younger. That guy deserves respect.
this is absolutely deranged, and I mean in in the best possible way. I love it
Pushing the limits of computing!
That article is a work of art
0:28 You should see some of the code I've seen in our core business critical systems...
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.
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)
still faster than python
I needed this! Thank you❤❤😂😂😂😂
Loving these challenges!
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
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?)
That's some NPM worthy algorithm. Hats off
Couldnt stop thinking that finding this as an npm package would not seem unimaginable to me.
Laughed so hard I almost snorted my coffee :-) classic episode, thanks again primeagen
Why are we calling Guido van Rossum Ross van der Gussom? Is this a meme i missed?
The person who rote the article woke up and chose violence with no witnesses, 11/10
This code is STILL more efficient than the code game devs make today
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.
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!
this made me laugh so hard, thank you sir! : D
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.
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
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.
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.
this is a fantastic video!
This might be my new favorite piece of programming media ever
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.
You also wrote a program like this once and that's one thing beautiful about learning how to program.
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 pure madness. I like it 🤣
This is beautiful!
"This is where the machines can rise up" 😂
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😵
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
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 amazing
This is much better than bitmasking the int, and using that as a boolean. I am truly humbled by this genius gigachad.
it's OS 'magic'.. that jump multiple block of mapped memory, to find a proper one. Mapped file is used by Memory Manager and split into blocks to fast access.
Also ALL 'if' are linear, so system can do proper predictions. It will take much... much longer if this "if"s ware more random.
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.
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”
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.
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.
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.
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.
dude i need MORE from this Blabbin' guy! I can't believe he hasnt got more posts up fuck he's funny
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.
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... :-/
The pronuciation of strtoul was spot on :D
I loved to pratice string manipulation without saving the results in a variable. If I need the result I had to rewrite the whole code again and again and again😂
The funny thing is that in the latest code generator he uses the modulo operator :)
Imagine if we used that compiling power to check any useful info instead of odd and even numbers 😢
Respect for going through that whole ordeal tho
This is pure genius
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)
6:14 We need long long long(or int128_t I suppose). what exfat and ntfs, if an fs could support 2 ^ 128 - 1 bytes/blocks/etc. then it's next level
I was actually naive enough to attempt something like this. Around 1992 I began learning C. My only experience before this was with gwbasic. I wanted to display a bit maped picture and wrote a basic program to create a C source that was just a bunch putpixel calls, one for each pixel of a 640x480 image.
Just a have lookup table for that if statement. It'll greatly reduce the waiting.
This one made my day 😂😂
i just started learning python the other day.... shouldn't you be able to use bitwise comparison and if the final bit is 1 its odd and if its 0 its even?
for the problem you mentioned at 7:25 - consider getting a shift key foot pedal.
"Can we have O(1) code mom?"
Mom: "We have O(1) code at home"
The O(1) code:
most interesting 10 minutes of 2024
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
Say what you will about deoptimization but it's allowing us to make a whole lot of technology. And we're also looking backward and optimizing ground-up whilst keeping the knowledge of what's possible which we gained by shipping to production on save, and saving on alt tab.
I see a few ways to optimize this a little bit further:
1. make it multi threaded and run it on a 32 core CPU.
2. implement it as a compute shader and take advantage of the massively parallel design of GPUs. Get an NVidia RTX 4090 to run the program.
3. take advantage of the cloud. Create a website where users can enter any number, and have each request processed on a bunch of AWS machines.
4. the ultimiate solution would be to have it implemented directly in specialized hardware (remove one core of those intel CPUs, we don't need that many, and replace it with a 4B-gates dedicated even/odd detector).
Thank you study time. Mvp of the video and maybe the whole stream
1:47 😂. the way he said what he said gives me chills.... this guy is the coldest and most badass TH-camr😂
Oh my goodness, I just died!! 😂🤣😂🤣👏👏👏