Finding the best sine function for Nintendo 64 [video]

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

One of the big optimizations Kaze makes is to remove a huge lookup table, which greatly reduces cache/memory usage.

SM64 was compiled with gcc or mipspro?

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

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

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

I'm not claiming anything extraordinary, though, most or all of what I said is well known in the field.

Yeah, turns out I missed that part of the video. So the author, in fact, knew that minimax approximation is a thing, however he only tried to do it by hand! It's a bit silly to try to optimize a polynomial for minimizing the maximum error and then complain when the result predictably does worse in a completely different metric. What he should have tried is taking some tool for minimax approximation, like Sollya (Remez-based, also offers other functionality), and then try too look for a minimax that would additionally satisfy his other constraints. Sollya allows a weighted approximation, so he could have tried constraining the polynomial to specifically be more accurate around zero, π/2 and π. NB: My WIP package will be even more flexible than Sollya's remez and offer more direct ways to specify such constraints, due to the completely different approach.

FWIW, Sollya's Remez algorithm takes intermediate floating-point accuracy into account. At the very least, one should start by such a polynomial and then try to tweak it by hand, not just drag coefficients around from scratch. Numerics isn't “just messing around with numbers” as he claims; it's a large field with lots of cleverness.

As a quick example (using Maple, though, not Sollya): f(x) = x * (1.020875931 + x * (-0.0683760152 - x * 0.1122036320)) gives f(0) = 0 (exactly), f(Pi/2) = 1 (to at least nine decimal digits) and has a max error around 0.0019, significantly better than his hand-tweaked one (max error 0.007). For comparison, his fourth-order function has 0.002787 and the Bhaskara formula has about 0.0016. I don't know how many bytes it needs in MIPS assembly, but I normally count function speed in cycles :-)

If you allow a divide between two second-degree polynomials, like in the Bhaskara function, you can go down an order of magnitude in error, of course at extra cycle cost.