2 Common Questions I'd like to answer: 1) Why not just pass a vector pointer to the lateral distance function? Because load instructions under MIPS have a constant offset you can provide. By assuming how far away from the pointer the offset is, we can cover one special case in 1 cycle less and have all the other cases work in the same amount of cycles. Making a special case for the lateral distance function and then constantly repurposing it is an optimization! 2) Why don't you just use inline assembly? - I need my code to be in this exact spot for cache coherency and using inline assembly mips GCC style is too much of a pain. I wish there was a way to just write assembly?? But somehow there isn't.

In 5 years, Kaze will have moved on from coding entirely and will be building this game transistor-by-transistor to improve on the inefficient architecture of N64 cartridges.

"how much did you improve the performance?" "by roughly 2 fps." "what did it cost you?" "i can no longer read the code, let alone make any changes." "was it worth it?" "you bet"

Rule 1 of systems coding: "the compiler is smarter than you are" Rule 2: "except when it isn't"

Man, whatever glitches you miss when you release this are gonna be wild. You're playing with extremely volatile logic alchemy here, even more unsafe than Pokémon Gen 1.

i always find the most unreadable code is when they start utilizing undocumented bugs in hardware because the code your looking at even if you 100% understood it, is not doing what you think it does. or when they start using undocumented instructions that do a weird combination of things. this is what makes making emulators so hard to make.

I work in a codebase that is at least 60 years old. Looking at older versions written for IBM mainframes, everything looks like this. My favorite was, instead of having a boolean array for if a region had a particular property, they instead stored the machine code for "no-op" and "jump to function" where relevant and executed the array directly.

As a software engineer myself, this was an amazing implementation of optimization and horror story of indecipherable deep magic. Nice job as always 👍

It feels like every video takes me even deeper into a rabbithole with more and more cursed and even cleverer tricks. And it's always so interesting.

For anyone thinking of implementing this generally, note Kaze is optimising for his specific purpose on his specific system and his specific compiler, and is testing everything in Compiler Explorer. Don't start doing this stuff needlessly in your own code blindly just "because Kaze said faster". If you're not writing an optimised N64 game then you need to do the profiling, research, and proof work all over again. Plus you actually need to save 1 or 2 cycles, which is unlikely on any x86 computer made in the last 30 years.

in some old games that super optimizations in the mid to late 90s i saw that in their source code they use to keep 2 version. A more clean version for porting to other systems and a dirty one that was platform specific. I remember some games had both a C and ASM version in some cases.

Oh my god, this was amazing, the ending line "you're welcome" is pure comedy gold. I'm never gonna use any of this but I am sending this to as many people as I can.

Good video 👍 (it came out 2 minutes ago and theres no way i watched it all)

"This might get you fired from your job, but it makes our rambus go vroomvroom, so I'd say it's worth it." It's always worth it.

This reminds me of the story of Mel the "Real Programmer" from the jargon files. Utterly indecipherable code which nonetheless is so good it's practically magic.

There is something just beautiful in writing code that is optimized so "badly" that sometimes it doesn't even compile properly

The 'goto' part got me thinking the next step here would be to implement a N64 specific compiler

As someone who's intimately familiar with the RISC-V instruction set, it's interesting to see how MIPS, the N64's instruction set, is so similar that most optimizations would still apply to a RISC-V system. A stand-out example for me was the global pointer optimization avoiding a two-byte LUI-sequence at 4:11.

Most of the time I treat math functions as black boxes anyway, so the fact that an evil wizard built them with black magic doesn't bother me. Unless something goes wrong and I have to open the box...

i like the slow pan to the "This doesn't make sense" reply on the stackoverflow page

_Kaze's next video:_ "Now we're going to delve into the apocrypha of the forbidden Old Tongue spoken only by native R'lyehn because it'll save us a whole 3 cycles and regular code just won't cut it."

i love how i technically understand what i just saw while at the same time i don't understand the level of wizardry this guy is performing

I love insane code techniques like this, even if I don't understand totally normal code techniques

5:55 first answer on stack overflow is always one saying your question doesn't make sense. I'm surprised it wasn't marked as a duplicate.

DAMN those are some insane micro optimizations, when you said you sacrificed readability for performance, I didn't think it would be THAT bad xd

Kaze: Uses "goto" to swap logic for instruction caching Me: YOU WHAT?! Kaze: Overwrites functions with memcpy for a properly optimized call path to avoid bugs per console Me: *I AM CALLING THE POLICE!*

Personally, I see no problem sacrificing readability for performance, as long as you A document it, and B the performance gain is relevant for your use.

1:45 The lie you tell the compiler here is a neat trick, but I wonder of the cast can be avoided with an assume attribute instead to just tell the compiler that the value is in a valid range?

7:04 You can avoid this issue entirely by moving the decrement of the loop variable into the body of the loop so it executes *after* the loop condition and *before* the first loop iteration. This is also very useful for decrementing loops that use unsigned integers.

The footnote of "I use a custom GCC build" is insane enough on its own for a whole video

Back in the day running your for loops backwards was a huge time saver in JavaScript running under Internet Explorer 6. Because it was Internet Explorer. Just have to be careful the execution order of the items being looped through doesn't matter...

Re: 4 this is so cursed and amazing Re: 7 separating the "hot" and "cold" branches of a function is a good one. There are a few variants of this that may or may not help (usual caveats: depends on arch and runtime patterns). Instead of using "goto" it might be better to call a separate non-inline function. You can put all the "cold" branches in a separate section, so that more of your "hot" paths are in cache. In cases when the "hot" path is very small and common, you could also inline the hot path. Re: 13 at some point it is clearer to just go full asm :)

At this point you will end up rewriting SM64 on assembly for performance 😂

as a gamedev of intermediate skill, i feel like this video is expanding my brain at such a dangerous speed that it will be permanently damaged. perfect video, i'll watch as many of these as you make

I love your videos so much, optimization exactly like this is my favorite activity on the planet. Seeing a new video from you is like christmas coming early.

I love in-depth videos like these; great work!

Well, tbh the principles are more straightforward than that. When you write code, your very first objective is to make it produce the desired result or outcome. Second, you make it robust - you take into account edge cases and variations. Third, you optimize it. And you have to do it in that order specifically since there is no sense of optimizing a code that doesn't work. And when you optimize you basically sacrifice maintainability - aka you don't expect to change that code much ever again, it is the dead end.

I love these videos so much because I know nothing about coding but I watch them like I get it.

As someone who's coded games that fit in a few hundred bytes, I see this as an absolute win.

6:52 - same with 68000 - it has a "DBRA" instruction - "Decrement and Branch", which decrements and branch if not -1. However this means you MUST write: for ( i = count-1; i >= 0; i-- ) This will NOT produce DBRA (at least not with my version of GCC): for ( i = count; i > 0; i-- ) ...even if "i" is not used in the loop body! Instead it does a standard SUBQ+JNE which is slower. Same trick, but an annoyingly subtle MIPS-vs-68k difference.

I'm pretty sure casting a function pointer to another one with a different return type would be undefined behavior if you didn't build for a single platform. It's funny in a sense, you don't have to ever worry about undefined behavior since you can always test to see what the n64 does.

8:15 I work as a graphics programmer for an engine at my job and this style of coding is incredibly common on the low level parts of the rendering pipeline. I always thought the person who wrote these was insane, but now I finally understand. *They really are insane*

Local yoshi casts ancient voodoo magic in old videogame and create man-made horrors beyond our comprehension in Orlando, Florida.

You are legend, Kaze. I thought I was smart for using function pointers with duplicate functions to avoid if conditions, but this is on another level!

great video, i haven't cried this much in years.

I chose computer science because of you!

YES! This is how C/C++ was meant to be used!

I wish each of these videos had before and after benchmarks. I love seeing FPS gains or even microsecond gains.

Just as a potential idea you could "document" some of the hardest functions by writing tests against them, assuming you don't have any yet.

And so now we know why the N64 was the "less performant" console in spite of the lack of disc read times. To squeeze all the potential it had out of it, you had to be a fluent practitioner of the dark arts, on top of breaking several coding Geneva convention guidelines.

Hmm pretty interesting optimization techniques, most of the time idk whats actually happening but your explanation is very understandable, great video Kaze!

I've always loved just how cursed console optimizations are, good work!

Yay! New kaze video!

The abs and atan2 optimisations will come in handy some day. Thanks 😊

this was a beautiful video. thank you

An excellent video! I laughed so hard at some of these, partially bc I've had to do the same with microcontroller compilers. When you've got a dinky little 12 MIPS mcu, counting cycles can be important, and improperly handled casts and such by the compiler can eat into that.

This is the most interesting video series I've ever seen. I want more exactly like this for other games or pieces of software we're not meant to have the source code for.

It's scary to think, but it seems like that self modifying code trick could actually make a big impact in some real use cases. I mean you can potentially save millions of if-checks with it.

At some point it's clearer to write the exact procedure you want in assembly than to try to trick a compiler into generating the exact assembly you want with cryptic hacks. You have reached that point. 😛

I absolutely love videos like these, thank you

Kaze, I am a huge fan of optimization and "form fits function". Even though I don't understand most of what you are doing here - I love watching this content from you. Thank you and keep it up!

good video explaining deranged optimization specific to your hardware, love to see it

Kaze wants every every line of his code to be tagged with "WTF" code commentary by a 3rd party looking at the code. The same way Fast Inverse Square Root was commented on in Quake 3 code (Not Doom).

I've heard many people talk about decrementing loops being faster over the years, and many people also claim it's false, but this is the first time I've heard anyone so clearly explain that it's about the comparison against zero. It all makes sense now.

Kaze is sounding more like a villain every day I understood maybe 10% of the video but it was a good time regardless, looking forward to next time!

The compare with zero trick also works on the NES, SNES, and all other 6502-based systems. Whenever you do an arithmetic operation, it sets the equal and carry flags with an implicit comparison to 0.

The comment about your first ever programming undertaking reminded me of a elementary school friend i had who spent their time, at ten years of age, hacking mario world by simply editing the rom directly with a hex editor. Great video!

I love almost silly levels of optimizations like this!

This really feels like we're delving into the dark arts at this point, learning things mortal man was not meant to know & developing dark powers out of reach of the gods. All to make Mario run a little bit better!

Good Video. It came out 21 minutes ago so I have watched it all 😁

WOW, INCREDIBLE

I wonder if there are any things the compiler maintainers could do to make Kaze's life easier in implementing these optimizations.

... What I'm getting from this is that when you will be sent back in time to make the fully optimized Super Mario 64, they will either kick you out for writing this code or praise you for your genius.

Audibly said "Oh my fucking god" when you said self-modifyong code. You madman. You artist.

0:38 That brought a tear to my eye. It's so beautiful I'm speechless

Bro is approaching the Kolmogorov complexity for most performant m64 game

Had a coworker that wrote a small script in python cause it is "So easy and fast to write". When he used it he noticed it was too slow to be used at all (simple test-cases with inputsizes in the range of maybe 50 elements would work, we needed thousands). Then he spent weeks trying to make his python faster. He ended up writing it in C++ and was done in 2 weeks (and a couple thousand times faster program).

I need more videos like this

Best outro I've ever seen

First, great video, but I'd like to point out a few things for people who might not know them. A key thing that cannot be emphasized enough is that you need to measure whether these sorts of optimizations actually speed up your code. For example, the self-modifying code trick will often make your code slower since to make it work reliably you'll need to invalidate the icacheline (and flush the dcacheline if you used cached access), and the possible extra reads from RAM will often cost you more than you gain. Also, I think you know this, but for other people's benefit, you want to modify code while you're executing far away from it (MIPS cpus wont execute modified instructions if the instruction is already in the pipeline -- this isn't so bad for the VR4300, which only has a 5-stage pipline and is in-order scalar) and in bulk (so you can minimize the number of cache flushes needed). The more modern the CPU, the worse self-modifying code is in general. Also, if you need to do a ton of BS to get the compiler to output a specific sequence of instructions, perhaps you should just code the function or performance critical piece of code part in assembly. In the example of atan2s, it already has large portions of assembly, so making the code less fragile is probably worth it. For the struct Surface, 0x16 isn't 4 byte aligned, so the compiler should automatically insert the padding, so the two structs should have exactly the same layout, which agrees with the offsets in the code you show onscreen (although it could be more clear to explicitly show the padding).

I thought I was the only one doing cursed stuff for fun! Also thanks for the fast absi, that's quite common so it will help. ♥

man i could watch literal hours of these videos

"but we already decided to sacrifice readability in the intro" - so this is a good trick. LMAO

Wouldn't writing some functions entirely in assembly be more readable than having to inline some asm instructions here and there to force the compiler into producing the asm that you want? At least for short functions.

since readability is going out of the window, i think kaze should have a code copy of the engine before this dramatic changes, because when he released the source code of rtyi it will be so hard to read and tightly coupled to its function that no other hacker could made a new hack from that source code.

You need to write a compiler

the wizard has posted! Merry Christmas Kaze! :)

You just exploded heads of many cleancoders 🤯😜 In 8-bit assembly were not caches but pressing every cycle form hardware was a norm 😂 Nice tricks by they way 💪

On reverse loops, instead of looping fron N to 1, would it be useful to loop from N-1 to 0 with this? 'for (i = N; i--; )'

insane wizardry, good work!

wow this is a lot of work. Impressive.

I really hope he backed up the old codebase because wow, this optimizations are getting insane

Some really neat tricks in this video, but dude, honestly at a certain point it might be worth just hacking gcc to add a pass that does some of these transformations for you since they’re so mechanical 😂. Or even just a write preprocessor that takes sane C and spits out optimized C (you could do this with python’s pycparser for instance).

You’re insanely good at this

Outputs off-by-one error every 8787 angles got me so good

10:15 I know only one guy that ever tried to use self modifying code for performance gains. He gave up because debugging became nearly impossible

thank you kaze for ruining coding for someone somewhere at some point

You kind sir are insane and i love witnessing it

Once I was writing a loop in assembly that did two different things at several points based on a boolean state variable. Instead of checking the variable each time and branching I just wrote two variants of the loop and jumped between the equivalent point in the loop whenever I wanted to change the variable, eliminating said variable.

"required to beat GCC into submission" is one of the greatest comments lol