6 ms·

Finding the best sine function for Nintendo 64 [video]

184 points by codetrotter 3y ago

DigiDigiorno 3y ago
I like Kaze's content. There is something fun about how hacky and ridiculous it is to put that much effort into Super Mario 64 optimizations and brand new levels. This video is more technical than the others, but I suggest checking out his other videos if the idea of Super Mario 64 development piques your interest.
accrual 3y ago
Now that SM64 has been fully reversed and can be compiled back to a bit-perfect ROM, I wonder if there would be any merit in replacing the default lookup table with Kaze's new function(s): - 200 microseconds saved - 33333 microseconds per frame -> 0.6% of time saved - 1KB of RAM saved - Looked really cool doing it (Kaze's words & I agree)
- dietrichepp 3y ago
  The question here is whether the new, optimized SM64 implementation is CPU-bound in the first place. Games on the N64 are often limited by memory bandwidth, which is taken up by rasterization, and SM64 was something of a special case—compiled with optimizations turned off due to GCC bugs. After recompiling with optimizations enabled, and maybe after swapping in newer versions of the RSP microcode, my guess is that further improvements to CPU efficiency would have very limited returns.
  - nstbayless 3y ago
    One of the big optimizations Kaze makes is to remove a huge lookup table, which greatly reduces cache/memory usage.
    - smcl 3y ago
      That's kinda interesting - I imagine a lookup table was introduced as as an optimisation in the first place. I'm at work and I've had meetings so I haven't seen the linked video (or one of the ones where Kaze patched some functions in to get SM64 running at a constant 60fps) but I'm really keen to do so when meetings subside :) These little self-contained optimisation problems are really appealing, especially when someone smart has done something cool and innovative
  - epcoa 3y ago
    SM64 was compiled with gcc or mipspro?
  - monocasa 3y ago
    > Games on the N64 are often limited by memory bandwidth, which is taken up by rasterization So a lot of that is overstated, IMO. The N64 was in most cases the first system with a modern memory hierarchy game developers had come across. From my experiments, rdram is dozens of cycles away from the CPU at least, so it's pretty easy to be memory bound without coming close to saturating the little more than ~200MB/sec memory bandwidth the system is capable of sustaining. Remember too the context of the mid 90s, where the previous Nintendo console had single cycle access to main memory[0]. So you'd see crazy stuff like loop unrolling into 16KB of straight code with no branches despite the CPU only having a 16KB instruction cache, guaranteeing that you just flushed everything else. Similarly the GPU seemed really hampered by it's small FIFO at basically the ROP stage which meant that the RMW of both color and z buffers meant a lot of pipeline stalls. I think a lot of the benefit of switching to z sort late in the system's cycle had less to do with overall memory bandwidth, but instead the fact that you don't have to wait on memory just to then blit out the pixel. There's no z to check against, so you know that yes, as soon as the pixel hits the ROP stage, the GPU can just write it to memory (assuming alpha isn't involved). And that's not to shit of the devs in question; it wasn't until probably the last half of the PS2 era that the industry as a whole really internalized how to approach true long tail memory hierarchies. I certainly hadn't despite being able to regurgitate the textbook definitions involved. I guess what I'm saying: hey demo scene coders, there's a bunch of untapped power in this system with weird hangups. : ) [0] Yes, the memory system of the SNES is hard to talk about in broad strokes like this with FastROM/SlowROM, wait states on cart mem accesses, etc, but 'single cycle' is the right order of magnitude for this discussion.
    - dietrichepp 3y ago
      Maybe that’s right, memory bandwidth is not the right explanation. But the rasterization itself is still often a big bottleneck, and maybe chalking it up to fill rate limitations is more explicatory. This is based on my limited observations writing my own N64 code and trying different scenes that put different amounts of load on the RDP—varying the load on the RDP was by far the easiest way to get framerate drops. If the CPU load is relatively constant, if the RSP load is relatively constant, then explaining it as running into fill rate limitations seems like a good theory to me. I’m a little skeptical that there’s “huge” untapped power in this system, given the performance of some later games like World Driver Championship (1999). There’s certainly a lot of processing power across the CPU, RSP, and RDP, but given how heterogeneous the system is, and how many weird hangups there are, I have doubts that we’re going to see something much better come out of the demoscene community. You need a lot of appetite for a long-term project in order to make something impressive on the N64, and while we have better emulators and compilers now, it’s hard to compete against someone in the 1990s who got to spend multiple years on the system full-time, with the support of a team and from the console developers. There are some tricks I can imagine using, like spending more time with the RDP in single-cycle mode, or rendering just the fields to get 480i at the cost of 240p, but there are just so many thorny problems to deal with. This is speaking as someone who participates both in the demoscene (I was just in Boston for @party), and N64 homebrew (you can find me on the Discord).
  - nwallin 3y ago
    > The question here is whether the new, optimized SM64 implementation is CPU-bound in the first place. Games on the N64 are often limited by memory bandwidth, which is taken up by rasterization, Your premise is correct but your conclusion is wrong. The CPU and the "GPU" (the RSP, Reality Signal Processor, was not actually a GPU, but for the purposes of this discussion it's close enough) shared memory bandwidth. If the CPU was using memory bandwidth, it was stealing memory bandwidth from the GPU, slowing down rasterization. The thing to make better was to reduce the total amount of bytes the CPU sends to/from main memory. If you could reduce the number of bytes the CPU sends to/from RAM, that gave the GPU more memory bandwidth, and that would improve GPU performance. CPU time was irrelevant. This changes a lot of what you think about when you think about performance optimization. -Os is substantially faster than -O2, for instance. Loop unrolling is always a loss, even for small fixed size loops. Temporary variables are bad; if you can do a thing by manipulating an existing variable and then de-manipulating it, and that prevents it from spilling onto the stack, that will improve performance. Lots of optimizations a normal programmer and/or the compiler does will make the CPU faster but the extra RAM bandwidth used will slow down the GPU. > After recompiling with optimizations enabled, and maybe after swapping in newer versions of the RSP microcode, my guess is that further improvements to CPU efficiency would have very limited returns. He's actually done this, it is not a hypothetical. The original game got 20FPS. (ballpark) He recompiled with optimizations enabled and was getting 30FPS. (ballpark) He performed a bunch of other code optimizations and got this up to 60FPS. So there were enormous returns still on the table.
- nstbayless 3y ago
  Kaze has expressed intent to produce a patch for sm64 with all the optimizations he's found after he releases his overhaul hack.
- 22c 3y ago
  Kaze has essentially been doing that for his own ROM hack, not just this improvement but a bunch of others that have enabled the game to run at a consistent 60fps. I believe he's mainly working on the ROM hack at the moment but has talked about releasing a patch to backport all the 100% SM64 compatible fixes to the main game.
- kibwen 3y ago
  Kaze has already done so, and picking the low-hanging fruit results in much greater improvements than the optimizations shown here (which frees up less than one millisecond per frame). Here's the previous video with explanations and video demonstration of their improvements: https://www.youtube.com/watch?v=t_rzYnXEQlE https://www.youtube.com/watch?v=t_rzYnXEQlE
nsajko 3y ago
The video is very well produced and engaging, however (from skimming it), it seems that all the implementation methods it presents are suboptimal. The N64 CPU had an FPU, so it seems obvious that the best method, from both a speed and accuracy (or whichever is deemed more important) standpoint would be the same method that's used in all the libms in libcs like Glibc, musl or LLVM-libc, or in the standard libraries of languages like Go or Java: approximation using a polynomial. This polynomial is not derived analytically, rather it's found using an iterative algorithm, traditionally using the Remez algorithm, but also see my WIP project here: https://gitlab.com/nsajko/FindMinimaxPolynomial.jl https://gitlab.com/nsajko/FindMinimaxPolynomial.jl.
- lifthrasiir 3y ago
  > This polynomial is not derived analytically, rather it's found using an iterative algorithm, traditionally using the Remez algorithm, but also see my WIP project here: https://gitlab.com/nsajko/FindMinimaxPolynomial.jl https://gitlab.com/nsajko/FindMinimaxPolynomial.jl. Is this your independent attempt? Because I think RLIBM did the essentially same thing recently [1]. [1] https://arxiv.org/pdf/2104.04043.pdf https://arxiv.org/pdf/2104.04043.pdf
  - nsajko 3y ago
    One difference is that their approach doesn't scale to 64-bit floats AFAIK. My code and their approach are actually quite different, with different goals, different places where they're smart and different places where they could be improved. I hope to improve my code based on their ideas when I finally read their papers, however I still have plenty of my own that I want to implement. See also this thread from twenty days ago, someone asked me basically the same thing, linking an earlier paper by Lim and Nagarakatte (et al): https://news.ycombinator.com/item?id=36201197 https://news.ycombinator.com/item?id=36201197
    - lifthrasiir 3y ago
      Cool! I think the RLIBM approach is indeed fresh and has potentials, but I was never sure if it can be generalized to domains past binary32 when we are looking for correctly rounded results. I guess it's a fundamental difference between RLIBM and your algorithm---you don't guarantee correctly rounded results, right?
levodelellis 3y ago
Fantastic video
abnercoimbre 3y ago
It's almost criminal Kaze isn't really welcome at most tech conferences because he plays fire with Nintendo's IP. A huge audience is missing out learning to do these things themselves, so my plug is we're running an indie conference [0] with Kaze as the featured speaker. We should follow in his footsteps. [0] https://handmadecities.com/boston https://handmadecities.com/boston
- psychphysic 3y ago
  I find him a bit abrasive even though I enjoy his videos (and actually submitted this a couple days ago). It's alot of cool work, but the way he presents it to laymen is kind of annoying. Even if he had never heard of data orientated design in the original video series (where he claims to not know what its called when you organise data to improve throughput) he should by now because clearly he does huge amounts of research. (Case in point at 9:30[0] he talks about localised memory patterns as though he's the first to come up with it). Again, love his work, watch every video and even submit to HN because I think others would. But that doesn't mean he's not very annoying. [0] https://youtu.be/xFKFoGiGlXQ?t=570 https://youtu.be/xFKFoGiGlXQ?t=570
  - Snarwin 3y ago
    > Case in point at 9:30[0] he talks about localised memory patterns as though he's the first to come up with it This seems like an uncharitable interpretation to me. When he says "I'm not sure if anyone else has ever used this approach," it's pretty clear from context that the "approach" he's referring to is interleaving the sine and cosine tables to improve cache usage. And he doesn't even claim to be the first to come up with it, just to have independently discovered it.
    - psychphysic 3y ago
      Just telling you why even as a fan I can see why he rubs people the wrong way. If you look at previous HN threads on his content many have similar complaints. Every one loves the content and premise of revisiting SM64. Many don't like the presentation. If anything I think I'm being charitable assuming it's optimized for the lay public.
dvh 3y ago
The logical next step is creating virtual machine and brute force generate function with less then 27 instructions and see if it produces something close to sine. Let it run for few months and surely it will find something.
bruce343434 3y ago
A lot of calculations and informed guesses and words like "could" "would" "should" but no benchmarks. Disappointing. With things like these, especially once you start to involve not-really-deterministic things like cache, you need to do integration testing of performance through benchmarks, not back-of-the-napkin calculations of how many instructions you are executing. > Mario "could" walk in a different direction than he is pointing in But did he? Was that a real, noticable problem or just theoretical?
CyborgCabbage 3y ago
Another cool N64 project, Portal N64 https://youtu.be/eN_-V7PDKAo https://youtu.be/eN_-V7PDKAo
contravariant 3y ago
If you're using a square root anyway it's also possible to only fit the part between 0 and pi/4, and use the square root to calculate the sine or cosine (whichever is greater). However you need to be a bit careful that you return exactly sqrt(1/2) at pi/4 otherwise you get a discontinuity.

184 points by codetrotter 3y ago

I like Kaze's content. There is something fun about how hacky and ridiculous it is to put that much effort into Super Mario 64 optimizations and brand new levels. This video is more technical than the others, but I suggest checking out his other videos if the idea of Super Mario 64 development piques your interest.

accrual 3y ago

Now that SM64 has been fully reversed and can be compiled back to a bit-perfect ROM, I wonder if there would be any merit in replacing the default lookup table with Kaze's new function(s): - 200 microseconds saved - 33333 microseconds per frame -> 0.6% of time saved - 1KB of RAM saved - Looked really cool doing it (Kaze's words & I agree)

dietrichepp 3y ago
The question here is whether the new, optimized SM64 implementation is CPU-bound in the first place. Games on the N64 are often limited by memory bandwidth, which is taken up by rasterization, and SM64 was something of a special case—compiled with optimizations turned off due to GCC bugs. After recompiling with optimizations enabled, and maybe after swapping in newer versions of the RSP microcode, my guess is that further improvements to CPU efficiency would have very limited returns.
- nstbayless 3y ago
  One of the big optimizations Kaze makes is to remove a huge lookup table, which greatly reduces cache/memory usage.
  - smcl 3y ago
    That's kinda interesting - I imagine a lookup table was introduced as as an optimisation in the first place. I'm at work and I've had meetings so I haven't seen the linked video (or one of the ones where Kaze patched some functions in to get SM64 running at a constant 60fps) but I'm really keen to do so when meetings subside :) These little self-contained optimisation problems are really appealing, especially when someone smart has done something cool and innovative
- epcoa 3y ago
  SM64 was compiled with gcc or mipspro?
- monocasa 3y ago
  > Games on the N64 are often limited by memory bandwidth, which is taken up by rasterization So a lot of that is overstated, IMO. The N64 was in most cases the first system with a modern memory hierarchy game developers had come across. From my experiments, rdram is dozens of cycles away from the CPU at least, so it's pretty easy to be memory bound without coming close to saturating the little more than ~200MB/sec memory bandwidth the system is capable of sustaining. Remember too the context of the mid 90s, where the previous Nintendo console had single cycle access to main memory[0]. So you'd see crazy stuff like loop unrolling into 16KB of straight code with no branches despite the CPU only having a 16KB instruction cache, guaranteeing that you just flushed everything else. Similarly the GPU seemed really hampered by it's small FIFO at basically the ROP stage which meant that the RMW of both color and z buffers meant a lot of pipeline stalls. I think a lot of the benefit of switching to z sort late in the system's cycle had less to do with overall memory bandwidth, but instead the fact that you don't have to wait on memory just to then blit out the pixel. There's no z to check against, so you know that yes, as soon as the pixel hits the ROP stage, the GPU can just write it to memory (assuming alpha isn't involved). And that's not to shit of the devs in question; it wasn't until probably the last half of the PS2 era that the industry as a whole really internalized how to approach true long tail memory hierarchies. I certainly hadn't despite being able to regurgitate the textbook definitions involved. I guess what I'm saying: hey demo scene coders, there's a bunch of untapped power in this system with weird hangups. : ) [0] Yes, the memory system of the SNES is hard to talk about in broad strokes like this with FastROM/SlowROM, wait states on cart mem accesses, etc, but 'single cycle' is the right order of magnitude for this discussion.
  - dietrichepp 3y ago
    Maybe that’s right, memory bandwidth is not the right explanation. But the rasterization itself is still often a big bottleneck, and maybe chalking it up to fill rate limitations is more explicatory. This is based on my limited observations writing my own N64 code and trying different scenes that put different amounts of load on the RDP—varying the load on the RDP was by far the easiest way to get framerate drops. If the CPU load is relatively constant, if the RSP load is relatively constant, then explaining it as running into fill rate limitations seems like a good theory to me. I’m a little skeptical that there’s “huge” untapped power in this system, given the performance of some later games like World Driver Championship (1999). There’s certainly a lot of processing power across the CPU, RSP, and RDP, but given how heterogeneous the system is, and how many weird hangups there are, I have doubts that we’re going to see something much better come out of the demoscene community. You need a lot of appetite for a long-term project in order to make something impressive on the N64, and while we have better emulators and compilers now, it’s hard to compete against someone in the 1990s who got to spend multiple years on the system full-time, with the support of a team and from the console developers. There are some tricks I can imagine using, like spending more time with the RDP in single-cycle mode, or rendering just the fields to get 480i at the cost of 240p, but there are just so many thorny problems to deal with. This is speaking as someone who participates both in the demoscene (I was just in Boston for @party), and N64 homebrew (you can find me on the Discord).
- nwallin 3y ago
  > The question here is whether the new, optimized SM64 implementation is CPU-bound in the first place. Games on the N64 are often limited by memory bandwidth, which is taken up by rasterization, Your premise is correct but your conclusion is wrong. The CPU and the "GPU" (the RSP, Reality Signal Processor, was not actually a GPU, but for the purposes of this discussion it's close enough) shared memory bandwidth. If the CPU was using memory bandwidth, it was stealing memory bandwidth from the GPU, slowing down rasterization. The thing to make better was to reduce the total amount of bytes the CPU sends to/from main memory. If you could reduce the number of bytes the CPU sends to/from RAM, that gave the GPU more memory bandwidth, and that would improve GPU performance. CPU time was irrelevant. This changes a lot of what you think about when you think about performance optimization. -Os is substantially faster than -O2, for instance. Loop unrolling is always a loss, even for small fixed size loops. Temporary variables are bad; if you can do a thing by manipulating an existing variable and then de-manipulating it, and that prevents it from spilling onto the stack, that will improve performance. Lots of optimizations a normal programmer and/or the compiler does will make the CPU faster but the extra RAM bandwidth used will slow down the GPU. > After recompiling with optimizations enabled, and maybe after swapping in newer versions of the RSP microcode, my guess is that further improvements to CPU efficiency would have very limited returns. He's actually done this, it is not a hypothetical. The original game got 20FPS. (ballpark) He recompiled with optimizations enabled and was getting 30FPS. (ballpark) He performed a bunch of other code optimizations and got this up to 60FPS. So there were enormous returns still on the table.
nstbayless 3y ago
Kaze has expressed intent to produce a patch for sm64 with all the optimizations he's found after he releases his overhaul hack.
22c 3y ago
Kaze has essentially been doing that for his own ROM hack, not just this improvement but a bunch of others that have enabled the game to run at a consistent 60fps. I believe he's mainly working on the ROM hack at the moment but has talked about releasing a patch to backport all the 100% SM64 compatible fixes to the main game.
kibwen 3y ago
Kaze has already done so, and picking the low-hanging fruit results in much greater improvements than the optimizations shown here (which frees up less than one millisecond per frame). Here's the previous video with explanations and video demonstration of their improvements: https://www.youtube.com/watch?v=t_rzYnXEQlE https://www.youtube.com/watch?v=t_rzYnXEQlE

nsajko 3y ago

The video is very well produced and engaging, however (from skimming it), it seems that all the implementation methods it presents are suboptimal. The N64 CPU had an FPU, so it seems obvious that the best method, from both a speed and accuracy (or whichever is deemed more important) standpoint would be the same method that's used in all the libms in libcs like Glibc, musl or LLVM-libc, or in the standard libraries of languages like Go or Java: approximation using a polynomial. This polynomial is not derived analytically, rather it's found using an iterative algorithm, traditionally using the Remez algorithm, but also see my WIP project here: https://gitlab.com/nsajko/FindMinimaxPolynomial.jl https://gitlab.com/nsajko/FindMinimaxPolynomial.jl.

lifthrasiir 3y ago
> This polynomial is not derived analytically, rather it's found using an iterative algorithm, traditionally using the Remez algorithm, but also see my WIP project here: https://gitlab.com/nsajko/FindMinimaxPolynomial.jl https://gitlab.com/nsajko/FindMinimaxPolynomial.jl. Is this your independent attempt? Because I think RLIBM did the essentially same thing recently [1]. [1] https://arxiv.org/pdf/2104.04043.pdf https://arxiv.org/pdf/2104.04043.pdf
- nsajko 3y ago
  One difference is that their approach doesn't scale to 64-bit floats AFAIK. My code and their approach are actually quite different, with different goals, different places where they're smart and different places where they could be improved. I hope to improve my code based on their ideas when I finally read their papers, however I still have plenty of my own that I want to implement. See also this thread from twenty days ago, someone asked me basically the same thing, linking an earlier paper by Lim and Nagarakatte (et al): https://news.ycombinator.com/item?id=36201197 https://news.ycombinator.com/item?id=36201197
  - lifthrasiir 3y ago
    Cool! I think the RLIBM approach is indeed fresh and has potentials, but I was never sure if it can be generalized to domains past binary32 when we are looking for correctly rounded results. I guess it's a fundamental difference between RLIBM and your algorithm---you don't guarantee correctly rounded results, right?

levodelellis 3y ago

Fantastic video

abnercoimbre 3y ago

It's almost criminal Kaze isn't really welcome at most tech conferences because he plays fire with Nintendo's IP. A huge audience is missing out learning to do these things themselves, so my plug is we're running an indie conference [0] with Kaze as the featured speaker. We should follow in his footsteps. [0] https://handmadecities.com/boston https://handmadecities.com/boston

psychphysic 3y ago
I find him a bit abrasive even though I enjoy his videos (and actually submitted this a couple days ago). It's alot of cool work, but the way he presents it to laymen is kind of annoying. Even if he had never heard of data orientated design in the original video series (where he claims to not know what its called when you organise data to improve throughput) he should by now because clearly he does huge amounts of research. (Case in point at 9:30[0] he talks about localised memory patterns as though he's the first to come up with it). Again, love his work, watch every video and even submit to HN because I think others would. But that doesn't mean he's not very annoying. [0] https://youtu.be/xFKFoGiGlXQ?t=570 https://youtu.be/xFKFoGiGlXQ?t=570
- Snarwin 3y ago
  > Case in point at 9:30[0] he talks about localised memory patterns as though he's the first to come up with it This seems like an uncharitable interpretation to me. When he says "I'm not sure if anyone else has ever used this approach," it's pretty clear from context that the "approach" he's referring to is interleaving the sine and cosine tables to improve cache usage. And he doesn't even claim to be the first to come up with it, just to have independently discovered it.
  - psychphysic 3y ago
    Just telling you why even as a fan I can see why he rubs people the wrong way. If you look at previous HN threads on his content many have similar complaints. Every one loves the content and premise of revisiting SM64. Many don't like the presentation. If anything I think I'm being charitable assuming it's optimized for the lay public.

dvh 3y ago

The logical next step is creating virtual machine and brute force generate function with less then 27 instructions and see if it produces something close to sine. Let it run for few months and surely it will find something.

bruce343434 3y ago

A lot of calculations and informed guesses and words like "could" "would" "should" but no benchmarks. Disappointing. With things like these, especially once you start to involve not-really-deterministic things like cache, you need to do integration testing of performance through benchmarks, not back-of-the-napkin calculations of how many instructions you are executing. > Mario "could" walk in a different direction than he is pointing in But did he? Was that a real, noticable problem or just theoretical?

CyborgCabbage 3y ago

Another cool N64 project, Portal N64 https://youtu.be/eN_-V7PDKAo https://youtu.be/eN_-V7PDKAo

contravariant 3y ago

If you're using a square root anyway it's also possible to only fit the part between 0 and pi/4, and use the square root to calculate the sine or cosine (whichever is greater). However you need to be a bit careful that you return exactly sqrt(1/2) at pi/4 otherwise you get a discontinuity.