Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Finding the best sine function for Nintendo 64 [video]

youtube.com

Post reply on HN
Print view View original

31–40 of 47 posts

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

#31

Post by psychphysic »

Snarwin wrote: post #30
psychphysic wrote: post #25

Earlier quoted context omitted.

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

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

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.

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

#32

Post by nsajko »

tyg13 wrote: post #19
nsajko wrote: 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.

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.

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

#33

Post by nsajko »

lifthrasiir wrote: post #16
nsajko wrote: post #15

Earlier quoted context omitted.

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?

> I guess it's a fundamental difference between RLIBM and your algorithm---you don't guarantee correctly rounded results, right?

Yes, but note that the linked package doesn't even attempt to implement a polynomial approximation (for use in software), rather it just finds the coefficients of a polynomial. Another WIP package of mine will use FindMinimaxPolynomial to actually implement the approximation (with source code output etc), however even that package was never meant to guarantee correctly rounded results.

In particular their work is more ambitious than mine in that they seem to account for the range reduction and output compensation while looking for the coefficients with LP, which enables them to guarantee correctly rounded results.

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

#34

Post by Sesse__ »

thebooktocome wrote: post #22
nsajko wrote: 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…

By itself, Remez is not usually helpful for these kinds of low-accuracy polynomial approximations, because getting the minmax error beneath the quantization threshold is too strong a constraint. Usually one ends up doing some brute force polishing at the end to try and reduce the polynomial degree and/or the bits necessary to represent coefficients.

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.

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

#35

Post by mrguyorama »

dietrichepp wrote: post #21
phire wrote: post #20

Earlier quoted context omitted.

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

The bank organization is relatively well-known, so maybe you put the framebuffer in one bank, you put the zbuffer in another bank, and you have two banks left over without touching expansion memory. I mentioned World Driver Championship specifically because it runs at 640x480, and runs well, without the expansion pack. Yes, memory access by the CPU will slow the RDP down. But the RDP is plenty slow even when the CPU…

Your example of World Driver Championship is important; It had a custom RDP microcode implementation to achieve that. The RDP microcode implementations Nintendo distributed were pretty mediocre, either being very slow but accurate, or fast and too inaccurate, even for 3D games. Some of the most impressive games on the console were only achieved by implementing custom microcode, which was excessively difficult because Nintendo refused to distribute resources to help do so, despite that being an intended use of the console's hardware.

Another huge problem in rasterization was that pretty much all graphics resources had to be in a 4kb texture cache to be rasterized, and unless you micromanaged that cache really effectively (and it was cut in half if you wanted certain RDP features!) that cache constantly had the wrong data, and this would slow everything down. If they had given it just a bit more cache for textures, it likely would have been much closer to it's claimed peak performance in normal usage.

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

#36

Post by nwallin »

dietrichepp wrote: post #4
accrual wrote: post #3

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)

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…

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

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

#37

Post by Sesse__ »

nsajko wrote: post #32
tyg13 wrote: post #19

Earlier quoted context omitted.

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.

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 (Rem…

Why does he even care about pi/2? Shouldn't the wrapping of the input (due to the use of fixed-point) make sure that sin(pi/2) == sin(0)?

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

#38

Post by nsajko »

sosodev wrote: post #18
nsajko wrote: 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.

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

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

#39

Post by nsajko »

Sesse__ wrote: post #37
nsajko wrote: post #32

Earlier quoted context omitted.

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 (Rem…

Why does he even care about pi/2? Shouldn't the wrapping of the input (due to the use of fixed-point) make sure that sin(pi/2) == sin(0)?

True, the author of the video should probably have done even more range reduction.

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

#40

Post by sosodev »

nsajko wrote: post #38
sosodev wrote: post #18

Earlier quoted context omitted.

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.

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

The burden of proof is on you though. If you think you can do it better then do it. It's ridiculous to post a dismissal without even watching the full video.
Post reply on HN