Live data from Hacker News

Finding the best sine function for Nintendo 64 [video]

youtube.com

11–20 of 47 posts

Re: Finding the best sine function for Nintendo 64 [video]

#11
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.

Re: Finding the best sine function for Nintendo 64 [video]

#13
post #11

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…

> 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.

Is this your independent attempt? Because I think RLIBM did the essentially same thing recently [1].

[1] https://arxiv.org/pdf/2104.04043.pdf

Re: Finding the best sine function for Nintendo 64 [video]

#14

Earlier quoted context omitted.

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 fu…

> 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 me…

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).

Re: Finding the best sine function for Nintendo 64 [video]

#15
post #11

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…

> 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 . Is this your independent attempt? Because I think RLIBM did the essentially same thing recently [1]. [1] https://arxiv.org/pdf/2104.04043.pdf

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

Re: Finding the best sine function for Nintendo 64 [video]

#16
post #15

Earlier quoted context omitted.

> 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 . Is this your independent attempt? Because I think RLIBM did the essentially same thing recently [1]. [1] https://arxiv.org/pdf/2104.04043.pdf

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…

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?

Re: Finding the best sine function for Nintendo 64 [video]

#17
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

Re: Finding the best sine function for Nintendo 64 [video]

#18
post #11

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…

I really don't think you can claim that the solution is suboptimal. Kaze has clearly spent a lot of time on this and has a real code to show for it. You're just theorizing that it's bad without providing any real evidence.

Re: Finding the best sine function for Nintendo 64 [video]

#19
post #11

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…

Polynomial approximation was used throughout the video, and minimax was one of the final methods. Timestamp is sometime around 18:00. There seemed to be numerical issues with the approximation producing sin values above 1.0.

Re: Finding the best sine function for Nintendo 64 [video]

#20

Earlier quoted context omitted.

> 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 me…

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…

In one of Kaze's older videos [1], he tracks both CPU and RCP time over various optimisations. The numbers make it pretty apparent that you can get significant RDP performance gains by reducing the amount of CPU bandwidth and/or improving it's access locality.

The N64 is a unified memory system, and memory stalls triggered by the CPU will slow RDP down.

The N64's memory controller appears to be very simple. As I understand it, if one sub-component attempts to access a DRAM row that is closed (DRAM rows are 2KB long), then the entire memory controller stalls for ~100ns as the RDRAM chip closes the previous row (writing out any dirty changes) and opens the new row.

The controller doesn't appear to do any reordering to optimise access patterns. If multiple components are accessing the same 1MB bank simultaneously, you can hit pathological bad cases were the entire system slows down, as the memory controller is continually stalling for 100ns at a time while the memory chips close and reopen rows.

Which is why some games can enable a high resolution mode when the memory expansion pack is present. They often don't need the extra 4MB of ram, but simply being able to strategically spread their data across eight different banks instead of four banks can massively improve performance.

[1] https://www.youtube.com/watch?v=t_rzYnXEQlE

Post reply on HN