Exp Function

Thank you very much for the help.

What is your idea of “fastest”? Least cycles to execute once? Most throughput when executed in bulk? Also, does it have to be the e^x function or can it also simply be 2^x? What are your outside constraints? Sometimes, the fastest solution to a problem is to solve a different problem instead, and to make the rest of the program work around that alternative problem.

P.S.: I rolled my own sine and cosine using fixedpoint math, and it's way faster than the one listed in that file — around 20 cycles of latency for computing both sine and cosine of a shared x at once, vs. 95 cycles for the sine of 4 x's. And if I made a bulk version, the throughput would be at around 4-8 cycles per computation or something. Though I also changed it around so that it no longer depends on pi to represent 180°. Instead, “one” in the fixedpoint input is one rotation. The error is around 1/128Ki, which is sufficient for what I am using it for. I tuned it to exactly the precision I need, got rid of the unnecessary pi dependency, and made it extremely fast. All this is to exemplify that you can go way faster if you make informed choices and get rid of arbitrary conventions.

Aressera wrote:

If you can tolerate approximation, then you can take advantage of the logarithmic structure of floating point numbers to calculate an approximate 2^x, then scale that to be an approximate exp().

How would this work? Shifting exponent bits? What to do with mantissa bits?

I'll probably need to look into this soon. But for GPU, so SIMD optimizations are already there.

JoeJ wrote:

What to do with mantissa bits?

I think you can fit a polynomial or something like that to approximate the function for different mantissa values.

Yeah, I'd simply select the n most significant mantissa bits, and then have a 2^n sized lookup table, and then use the other m remaining mantissa bits as the interpolant in that table, either linear or quadratic or cubic, etc.. And then you simply do a correction step based on the exponent bits, and maybe a final refinement step.

Though I don't know whether float bit extraction is a thing on GPUs.

RmbRT wrote:

Though I don't know whether float bit extraction is a thing on GPUs.

Yes, it's the same, just the shitty shading languages make it a bit more cumbersome. There are keywords to cast float to int, but it's free under the hood. This way you can use atomics to find the maximum floating point number for example, or reuse LDS memory initially reserved and used as floats for integer data later.

Thanks for the suggestion. Could work fast by putting the LUT in constant ram.

But well, first i need to test if i can at all convert exp() results to integers for atomic addition. I had verified this only for pow() results before. And i need to see if GPUs have HW instructions for exp2 / log2. If so that's probably hard to beat with either lut or polynomal i guess.

JoeJ wrote:

if GPUs have HW instructions for exp2 / log2

AFAIK they do.

"exp2 is typically implemented with a native base-2 exponentional instruction."
https://developer.download.nvidia.com/cg/exp2.html

Aressera wrote:

"exp2 is typically implemented with a native base-2 exponentional instruction."

I saw the same holds for RDNA4 ISA. But for sure, since AMDs ISA is NOT top secret. :D

I also saw RDNA4 can do floating point atomics now, which is nice. Idk which arch has added this. GCN didn't have.

JoeJ said:
Thanks for the suggestion. Could work fast by putting the LUT in constant ram. But well, first i need to test if i can at all convert exp() results to integers for atomic addition. I had verified this only for pow() results before.

And i need to see if GPUs have HW instructions for exp2 / log2. If so that's probably hard to beat with either lut or polynomal i guess.

LUTs are really the most powerful when you have lots of bit extraction & analysis instructions such as leading zero count, etc.., and can pipeline an entire batch of requests, and the LUT is small enough to have good cache hit ratio.

Also, what is the expected latency/throughput for transferring the bit representation of a float from float registers to integer registers? For example on x86, there is no direct path for that unless you use the MMX instructions, but switching those registers from float to int state has some cost associated with it. Or you have to go through L1 cache/memory to transport the bits. The same is when you want to extract values from vector registers into general purpose registers. The transfer is quite limited in throughput and the latency is also bad. The only upside is that it doesn't interfere with the memory unit (I think). Though, I guess for GPU programming, all you really care about is small working set / cache footprint, and good throughput.

RmbRT wrote:

Also, what is the expected latency/throughput for transferring the bit representation of a float from float registers to integer registers?

I assume the same registers are used for both kinds. But might depend on HW.
On GCN there are two kinds of registers. Scalar and Vector registers.

Scalar means all the 64 threads can use the same register. The compiler figures out if a value is the same for all threads, and uses a scalar register if so. Though, only integers can be scalar, so things like loop counters or addresses.

Vector registers are unique to each thread, and can hold integers or float.
Notice this has nothing to do with vec3 or vec4. There is no CPU alike SIMD which could bundle those 3 or 4 numbers together, nor is there any HW support for matrix data types.
So the 3 numbers making a vec3 are not necessarily in order, and thus you can not index the dimensions by number.
For the same reason you can not index arrays efficiently in registers either, and because there is no RAM stackframe on GPU, you can only index arrays efficiently from LDS ram (compute shader only), constant ram (uniform buffers), or VRAM.
(This lack of array support felt pretty unusual to me)

We can say registers on GPU are much more general, and you have way more of them than on CPU.
But they have to be enough for all the things you would put on the CPU stack as well, so it's no luxury.

Ofc. my GCN (PS4 gen) knowledge is a bit outdated.
E.g. RDNA4 may have support for small arrays in registers - i got this impression when skimming ISA yesterday.
And maybe there are 'native' matrix data types now due to AI acceleration.

RmbRT wrote:

Though, I guess for GPU programming, all you really care about is small working set / cache footprint, and good throughput.

Um, tbh idk what 'footprint' or 'throughput' precisely means. Because i did not read those programming books. ; )

But in my words i would list those guides regarding shaders:

Minimize execution divergence across threads. (But it's bullshit to say 'branches are slow on GPU')

Minimize random memory access across threads. (Think of parallel execution first. The same thread reading [0], [1], [2] does not help as much as threads 1,2,3 reading those same values within the same parallel instruction)

Minimize register usage per shader (a long shader can still use only few registers if it's simple, a short shader may need many registers if it needs to keep lots of data around e.g. due to many nested loops)

Minimize LDS usage per compute shader.

(The latter two points allow to have more 'hyperthreading tasks' in flight so you can hide VRAM latencies, which are much longer on GPU.)

On API level the guide is:

Minimize stalls on synchronization. E.g. We have small work B depending on results from huge work A, and we also have independent huge work C.
Then we can dispatch A and C, barrier, then B. Which may allow better saturation than submitting A, barrier, B, then C.
If there are no barriers in the way, GPUs can overlap work from different dispatches. (Which is the only kind of 'async compute' you can do with OGL lacking multiple queues.)

As always, only profiling tells what's really a win or loss in practice.

JoeJ wrote:

As always, only profiling tells what's really a win or loss in practice.

Yup, and that's why in practice most games don't consider these operations a bottleneck anymore.

Hardware changes. Floating point processing has evolved a lot in games.

In the 1980s and early 1990s? Game consoles around the millennium? Any game that needed any of these functions would build approximation tables. Sin/cos lookup tables were standard and lots of libraries provided them. It was normal to compute them at program startup at a suitable precision for the game.

The PS1 had no FPU but PS2 did. The the N64 had no FPU, the Gamecube did. 486SX did not but 486DX did, Pentium and beyond did. During the transition era, many games used a mix of floating point and fixed point, and these math functions were still approximated because they were far too slow.

Once floating point coprocessors started to become widespread, some games started to incorporate it. Doom 1 & 2 didn't use floating point, Diablo was fixed point, Quake 3 used a mix of floating point and fixed point, Hexen, Fallout, and Descent and a few others were floating point. Games could do limited amounts of the math but they still used the floating point coprocessors for the operations, including the earliest true-3D games.

These days most of the operations aren't blips on the profiler. We'll not think twice about most transcendental math functions, sin and cos, tanh, e^x, and more are freely used because the cost on modern processors basically vanishes into the out-of-order core. It doesn't matter that the CPU can take a few cycles to churn on them because at any given moment the CPU can have 20+ instructions going through the pipeline simultaneously.

In fact, on modern processors a lookup table is often slower than computation because of the lookup to an effectively random lookup in the page that isn't easily prefetched. The work of rounding/truncating to get the value into a lookup table bin or two, loading the address into memory, and potentially interpolating between two values, that's not only slower, it's also less precise.

There are some "don't be stupid" elements like using optimized libraries for matrix manipulations versus manually running a matrix multiply, but even that is unlikely to show up on a profiler on a modern processor.

ALWAYS profile. Don't spend your valuable time imagining what might be slow and "fixing" based on guesswork. The actual performance issues are rarely the ones you'd guess, are almost always unexpected issues in the code. Measure before, and measure after to make sure you've fixed it.

There's nothing new here:

"Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code, but only after that code has been identified. It is often a mistake to make a priori judgements about what parts of a program are really critical, since the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail." -- Donald Knuth, 1974, discussing architectures from the 1960s.

frob wrote:

We'll not think twice about most transcendental math functions, sin and cos, tanh, e^x, and more are freely used because the cost on modern processors basically vanishes into the out-of-order core. It doesn't matter that the CPU can take a few cycles to churn on them because at any given moment the CPU can have 20+ instructions going through the pipeline simultaneously.

I strongly disagree with this statement. Maybe if you are not writing performance-sensitive code, or the number of function calls is small, but for anything where it matters, avoiding these functions absolutely makes a difference. They are orders of magnitude slower than basic arithmetic.

For example, I just benchmarked std::sin() versus the sin_ps() from the sse_mathfun.h I linked earlier in the thread, which is an SSE implementation that evaluates 4 sin() operations simultaneously. On GCC for 32-bit float:

• std::sin() - 0.13 billion operations per second.

• sin_ps() - 0.43 billion operations per second.

So, just by inlining and using SSE, we got a 3.3x speedup. That is just SSE. With AVX-512 we could get roughly 10x speedup over std::sin() (assuming perfect scaling, which is likely for these functions because we aren't memory bound). If you can lay out the data contiguously (SoA layout), then the speedup over standard library can be huge.

Now, even if we consider just the sin_ps() function, we can see that while it is quite fast, it's still not keeping up with basic arithmetic operations. On my CPU (i7 4770K), I can do at most about 14 GFLOPS per thread with SSE, 28 GFLOPS with AVX, and a bit more with fused multiply-add. So, we can see that sin_ps() is still 32 times slower than an optimized multiply loop, per float value. std::sin() is 105 times slower. That's a far cry from "the cost on modern processors basically vanishes into the out-of-order core".

So, I think I can safely say that you should absolutely avoid those types of functions if possible. For example, most operations in 3D math can be done with dot and cross products rather than with angles and trig functions. When these functions can't be avoided, try to lay out the data in SoA format and process it with SIMD instructions to get the best performance. Avoid standard library implementations because they are usually slow. In extreme cases, use function approximations to get another ~2-3x speedup.

frob wrote:

These days most of the operations aren't blips on the profiler. We'll not think twice about most transcendental math functions, sin and cos, tanh, e^x, and more are freely used because the cost on modern processors basically vanishes into the out-of-order core.

Sure, but there are still cases where transcendental ops become a major bottleneck. For example, i have it in a reduction of depth mips requiring to unwarp, mix and then rewarp the values for all pixels. Because there is not much else to do other than this at his point, no out of core or similar HW features can help. Reducing my resolution from 16^2 to 8^2 gives me a speedup of something like 20% for the entire GI calculation, although all the heavy traversal and rendering work remains the exact same otherwise. This feels crazy, because i would assume the constant mip reduction cost should be totally negligible. And it would be, if i would not need those transcendentals.

Sadly my CPU profiling skills are a bit lacking to be 100% sure, but actually this kind of surprise happens each time when i have some heavy use for transcendentals. They are performance killers still, and those desperate posts about eventually optimizing them won't go away i guess. ; )

A speedup that isn't on a critical path is pointless. That's the entire point of the Knuth quote.

Sure, absolutely go ahead and use a faster version if you know you have it available. Replace the versions in the standard library, a few linker commands and the built-in version is swapped out with whatever version you provide. No need to have a pessimization, if your performance metrics show something you know can be improved, by all means improve it.

Just because an operation takes time does not mean it is performance critical. Those changes can be identified, but that's the key, AFTER they are identified. People doing optimizations for the last 50+ years have known that you must first identify the actual issues, guessing at them without measurement is a fools errand. Knuth called it out in 1974, calling it "the root of all evil" in programming. It remains so.

Performance must be measured first, issues identified, changed, and then measured again to be sure you've actually improved the situation. I've seen hundreds of times where people attempted an optimization only to find they had made the situation worse. I've also seen hundreds of times where people identified a bit of slow code, changed it, and saw there was no effect; even though the code was slow it wasn't in the critical path, it wasn't an actual bottleneck. They had wasted the time optimizing non-critical code.

Without actual profiling results and looking at the exact set of code, and measuring after, it's all a crap shoot and you're statistically unlikely to get lucky.

JoeJ said:
Um, tbh idk what 'footprint' or 'throughput' precisely means. Because i did not read those programming books. ; )

Throughput is how many operations you can start per cycle, or how many cycles need to pass until you can start a new operation, regardless of how long an operation actually takes to execute. Thinking in terms of conveyor belts, it is the rate at which the belt feeds new inputs. By cache footprint I meant how large the working set is. For example, you can execute 2 load operations per cycle, but they take 3–5 cycles to complete (for L1), so you could issue 6–10 L1 load operations before completing the first load, at a throughput of 2 (or ½, depending on convention), and a latency of 3–5. Throughput is operations per cycle, or cycles per operation, when amortised across many independent operations. Latency is cycles between issuing a single operation and receiving its result.

P.S.: Actually, this is a great example. Stores have a throughput of 1 per cycle. Loads have 2 per cycle. A loop going over lots of inputs and writing one output per iteration can at most do one input per cycle, because that is the theoretical limit of how fast it can write the results, even with out of order execution and all that. But as soon as you spill a single register in that loop to the stack, you already do at least two stores per iteration, meaning the theoretical maximum performance is already halved by that. Having an algorithm that only performs one or two loads per execution, and does one store for the result, and does not spill registers, can be multiple times faster than one that spills registers. So register pressure is essential, and using simpler approximations that use fewer registers and spill less often can make a huge difference.

frob said:
premature optimization is the root of all evil

Why is everyone always going on the defensive when anyone tries to increase the performance of a piece of code? If I write all my code with performance in mind, I have a way easier time when actually optimising bottlenecks. The worst thing in optimisation is when you make your bottleneck code faster, but the other code is also so slow or otherwise inefficient that you can no longer measure speedups from your optimisation, because other factors now bottleneck the code. So you have to optimise the rest of the program (which was a “root of all evil” to do from the get-go) in order to even get any benefits from optimising your hotspot code any more.

frob said:
A speedup that isn't on a critical path is pointless.

This is false. For example, in multithreaded code, having threads that use unnecessary amounts of memory bandwidth constantly across a wide range of tasks (so, not contained to a single “hot spot”) can make your actual hot spot thread so slow by starving it of memory bandwidth, that you cannot optimise it without first optimising the rest of the program to use less memory bandwidth. Knuth's quote may be valid for single-threaded single-core systems, maybe, and only in cases where you spend the overwhelming majority of the runtime in one loop that does 99% of the required work of the program.

But we are no longer in the single-threaded, single-core world. We have multi-threaded applications or GPU code that gets bottlenecked by register pressure and similar things. Using the default implementation of a “cheap” transcendental operation may use more registers or FPU units or whatever than required for the specific use case, and therefore slow down the entire program by taking up too many shared resources (registers or arithmetic units).

In my compiler, a single std::vector copy in one thread reduced the performance of my bottleneck thread by 20%, even though it's an entirely different thread. If you write all “non-hotspot code” with less discipline than the “hotspot code”, then you are guaranteed to do sloppy things that indirectly slow down the bottleneck code. Like copying an std::vector when a more disciplined approach could get away without any memory copies. And that was just one line of “non-hotspot code” that reduced the bottleneck thread's performance by 20%. It was by accident that I even found that out, because I tried everything I could to make the hotspot thread faster, and nothing had any effect. It was not because the compiler had somehow already produced optimal code. It was because completely unrelated code slowed down the thread so much that my optimisations were useless because the thread got starved of resources and was stalling. And this is something where even the best profiler won't tell you why the code is not going faster even as you optimise it. Had I not commented out that single std::vector copy in another thread on a whim, I would not have noticed that this was causing my bottleneck thread to stall. And there was no direct dependency between the stalling code and the vector copy. These where wholly unrelated operations.

———————————————————————————————

In every instance where I saw people talk about optimisation, there was always a bunch of people trying to shut down the conversation with the knee-jerk reaction, shouting “premature optimisation”, and these people always try to do so by guilt-tripping whoever is trying to write better code into feeling bad about it. IMO this is a projection of their own feelings of guilt that arises whenever they see someone try hard to write performant code. Just like we saw with the badly optimised AAA games that came out over the last few years, with people like Randy Pitchford defending stuttery and smeary graphics and gaslighting his customers, even telling them to “buy a better PC”, when they already own a 5090.