Fixed Point Arithmetic | Hacker News Reader

Fixed Point Arithmetic

vha3.github.io

79 pointsvha360 comments

> If you #include <stdfix.h>, you gain access to compiler-understood fixed-point data types. For example, you get access to type _Accum, which is a 16.15 fixed point exactly like the one that we've been considering above.

You can actually use _Accum without including stdfix.h, at least for compilers that conform the embedded extension to C (ISO/IEC TR 18037 [1]). Stdfix.h just gives you a macro named `accum` among others; this approach has been used for any new C keyword since C99 (e.g. _Bool vs. stdbool.h, _Alignas vs. stdalign.h). The size of _Accum type is also not exactly defined (it can well be 4.27).

[1] http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1169.pdf

I know fixed point was very important back in the days when CPUs didn't have dedicated floating point instructions. How important is it now, when most common CPUs have fast floating point operations? Is there still a performance win? Do games and similar software use them today?

The main appeal of fixed point nowadays is determinism across hardware - so networked games benefit, for instance.

Interesting. Are IEEE-specified floating point operations not deterministic?

That's my question too.

I wrote a multiplayer strategy game back in mid 90's issuing floating point and it was deterministic. No problems. Maybe chip optimizations have affected this?

We looked at fixed point, but with careful scheduling we'd get zero fpu (x87) stalls for float operations, so it wasn't a real win to go fixed. And it gave us the benefit of having more registers to use without needing to use the main stack as much, which also made the asm easier to read.

Edit: typos

Your compiler or runtime might reorder operations, different machines might have DAZ and FTZ set differently, some CPUs might helpfully offer you a bunch of extra bits of precision while others do not

Achieving reliable reproducibility for floating point calculations is... difficult, to say the least. There are minor differences between hardware (x87 vs SSE is the most famous one, but there are others). Changing compiler, its version or options may produce subtly different results (the most obvious example is the -ffast-math flag). And even the bigger problem is implementation of non-primitive (e.g. trigonometric) functions. Usually your program will use implementation from a system or vendor library, which probably have different underlying implementations.

Deterministic in what sense? A given build is generally deterministic if it contains only one code path, but compiler optimizations mean different builds of the same code might produce different results for the same inputs, and certainly the same code in two different functions could behave differently. And if you wanted to take advantage of SSE2 on systems that had it then that would generally mean having two codepaths that gave different results.

Floating point is deterministic, but it has limited precision, which introduces arithmetic errors depending on the specific values of the data. For example with full precision fp do: a = 2^25; b = 1; c = a+b; and you will just get c = 2^25. This is because there are 24 bits of precision but the +1 is 25 bits away from the most significant bit when representing 2^25+1 in binary, so the 1 gets lost in the fp representation.

It is this limited precision that makes it more or less non-deterministic in practice: sequencing operations differently may give results that are bit-wise different, but are close enough given the precision guarantees of floating point numbers. So, on different computers your computations may diverge due to different optimizations applied by the compiler/processor. This was especially true with the x87's 80 bits of precision internally, it may be less likely to happen with SSE floating-point.

They're deterministic but partially implementation defined.

Some instructions don't guarantee the maximum possible precision, and implementations can differ in the least significant bits of their result. Addition and multiplication give you the correctly rounded result. However, there is typically some leeway in fma fusion. That is, if you multiply then add, it is in some cases implementation defined whether you get a result that was rounded after the multiplication and before the addition, or you get the correctly rounded result of doing the multiply and add as one operation without intermediate rounding.

All this is with the most conservative compiler settings. Be very, very careful about your optimization settings.

And let's not get into nans.

All this adds up to a situation where writing floating point code that is guaranteed to produce the same bit exact result on all implementations is basically a superhuman task. Better to just use fixed point and be done with it.

They are still popular for multiplayer games that has a synced game state. In all clients you want to get exact same results when they run same code which is not possible with fp

“fp” is an unfortunate abbreviation for floating point when contrasted with fixed point.

Hah, thanks for pointing that out, I haven't noticed it

Is it really not possible to guarantee the same floating point behavior across different CPUs? I was under the impression that compilers had flags for that kind of thing.

I am not the expert but looks like there are some answers (atq2119 and newpavlov) under this thread: https://news.ycombinator.com/item?id=28901751

tldr: it is hard. I was wrong by saying it is "not possible". But I wonder if it is possible if your target platform includes various consoles?

Integer arithmetic is still simpler to implement in hardware and therefore faster than floating point arithmetic, so it is still heavily used for resource-constrained numerical programs. This shows up in signal processing code for e.g. very low-level network software, radios, and image processing. It is also popular for running efficient neural net inference. In neural nets, it is usually paired with reduced precision e.g. int8 because in addition to getting more operations per second, you can transfer more weights per byte of L1 cache and per byte-per-second of memory bus. Since navigating those memory limitations is a major part of performance optimization, reduced-precision fixed-point can help a lot. I should also mention that resource constraints happen with high-end hardware where you are trying to get maximum performance/throughput and in low-end hardware where you are trying to make things possible at all, so fixed-point arithmetic may be more widespread than you would expect.

> Integer arithmetic is still simpler to implement in hardware and therefore faster than floating point arithmetic

This is true in the abstract, but not necessarily true of a specific commodity chip. Processor vendors spend a lot of silicon on offering low latency and high throughput floating point support. It's a fairly recent trend of processor vendors adding fast int8 or bfloat16 vectors after the ML craze demonstrated that there was demand for vector support for more bandwidth-friendly datatypes.

It is absolutely very dependent on your specific hardware. I would expect dedicated digital signal processor chips to almost always support a high-performance fixed-point multiply-add instruction. In contrast, I would expect chips targeted and HPC or scientific computing to be much more focused on double throughput than anything else.

At least as far as int32 vs float32 goes, surprisingly float is easier to make fast in the hardware. This is because floats are composed of multiple sections that can be processed in parallel whereas all of the bits of and integer addition, for example, have a serial dependency.

The relative performance of float32 vs int32 is heavily dependent on the specific operations you care about and what hardware resources (i.e. area, power, std cells) you have available.

While floating point numbers can be cleanly split into a mantissa and exponent, adding floats requires shifting the exponent, which can be an expensive operation. Each portion of a floating point arithmetic operation is also implemented with integer arithmetic, which limits the performance spread. Many floating point operations require significantly fewer bits though, which can lead to major speedups.

On the integer side, the serial carry dependence mean ripple-carry adders are usually a bummer, but there a ton of carry-lookahead variants that can lessen the performance impact of that dependency. If you have several integer additions at once, you can use a carry-save variant to only pay that serial cost once all of the additions are done. Finally, if you are willing to significantly change your integer encoding, there are tools like redundant number systems[0] that allow you to move around the traditional trade-offs for arithmetic circuits including completely removing the serial dependency on carries. That said, if you require rescaling your fixed-point numbers during the computation, the fixed-point implementation will require more integer operations than floating-point operations.

All of this is also quite dependent on the overall architecture of the chip too, since the number of integer units vs float units and how data is moved around can have a way bigger impact on performance than how each arithmetic operation is implemented.

[0] http://lux.dmcs.pl/csII/ca2_RedundantNS.pdf

Several years ago I wrote a signal-processing kernel module for realtime interrupt handling in Linux. Surprise! You cannot do floating point in the kernel. So I wrote it all in fixed point.

ISTR the reason you couldn't use floats in the kernel had more to do with context switching and the kernel not spilling the FP registers than speed per se, but I might be misremembering.

Edit: Looks like I remembered it basically right:

https://stackoverflow.com/questions/13886338/use-of-floating...

It's not all about performance; fixpoints are consistent and predictable, which is very much not true of floats.

We should all be grateful that most banks still run Cobol, which has native fixpoint support for good reasons.

> fixed point was very important back in the days when CPUs didn't have dedicated floating point instructions

That's a misconception, before widespread dedicated hardware (eg on-chip 80x87) there was software-emulated floating point arithmetic (eg Microsoft Binary Format) for general use. In contrast, fixed point solutions are very narrow purposed, that is, you choose a specific binary representation format so your specific range of values would fit with acceptable precision.

> I know fixed point was very important back in the day

So you don't care if your bank account is out by a percent or two?

Well, others do.

You will have the exact same issue with the fixed-point presented in the article than with floating-point: they shouldn't be used for financial transactions because they are in base 2 so they can not accurately represent decimal fractions.

There are cases where fixed-point is preferred over floating-point, such as implementing an iDFT (or in general in algorithms when the dynamic of the numbers you manipulate is fixed and you need very precise control over the rounding errors).

But the article state: "Problem: I want to do arithmetic with fractional resolution but I can't afford the CPU cycles to use floating point." which isn't true for modern hardware. The rest of the article is still very interesting, but this is just a bad start.

Sarcasm does not become you. :-) I'm well aware of decimal types, which is what I'd use for currency values. That or "fixed point" integer cents.

Thank you for taking the time to comment, rather than simply down-voting. You are right. I should not comment at the end of a day.

Games that need to do dead reckoning and arrive at the same result on multiple computers either use fixed point or contain bugs. For example, almost every fighting game works this way. Early in the development of one fighting game I advised the lead developer to use integers for all parts of the game state, and he did not. Later, when testing the Switch port of the game, he was forced to switch to integers everywhere.

I've only done a small amount of game programming, but I can't for the life of me imagine why a dead reckoning approach would be necessary or preferable in the first place.

Dead reckoning uses a series of time delta and velocity vector pairs to continuously determine the latest position, right? So in a multiplayer setting, the vector is received over the network and due to unpredictable latency, the time value has to be as well. At that point, why not just send the new position in absolute coordinates? This would avoid any FP arithmetic inaccuracies between devices, especially the kind that accumulate over time as they would by continuously adding vectors on top of each other.

Fighting games derive the game state from a sequence of input states from each player sent over the network. Input states are typically 2 bytes or less (e.g. 4 bits for 9 possible directions on the joystick, 1 bit per button for each of 8 or fewer buttons). Once all input states up to some recent-ish ones for both players are present, the displayed game state is a successor to a guaranteed-correct recent-ish gamestate. Fighting games rely on the notion of sequences of inputs leading to a single correct gamestate because this is apparently necessary to preserve properties like "frame traps." That is, if I use a move and you block it, and I recover faster than you by 3 frames, and then I use a move that comes out in 5 frames, and you also use a move that comes out in 3 frames, I must always hit you and no other outcome must be possible. Some other genres are concerned with preserving other properties, like "if you click on someone's head with a rifle then they get hit," so they quite reasonably take different approaches.

If you can run the same simulation on two different machines using the same sequence of input states from all players and get different results, that's a bug. One way to get this kind of bug is for some parts of the internal state of the game to rely on floating point computations.

Swift recently switched its Date internal format to fixed I think:

https://forums.swift.org/t/pitch-clock-instant-date-and-dura...

You are correct. This article, written in 2021, does not apply with the motivation stated in the article anymore, outside of niche applications. FP is actually faster in many situations nowadays (for example divisions). If you account for the extra shifts you need for fixed point operations, then FP is certainly faster.

Ignoring the reduced range, you can perfectly store integers in FP variables. Even banks could store everything in FP instead of integer variables in the lowest unit they support (for example cents). Integers at overflow fail catastrophically, so that also has to be controlled for. It is not the case that the loss of precision for large FP values is fundamentally worse, though it does happen earlier for the same total size of variable.

Integers and fixed point save space if you need a large range. The exponent of a fixed point is stored in the code, instead of in the variable. Integer instructions are encoded into shorter binary form, because they were part of the introduced set from the beginning (if you disregard the extra shifts required for fixed point). These are the advantages as far as I can tell.

FP abbreviation is probably not a good idea here, while talking of Floating Point and Fixed Point, a little bit confusing.

And one additional advantage: in a game I worked on our fixed point class had a fractional part that is in base 10 and it was in thousands (0b1 == 1/1000). This was making fractional numbers add up in the way you expect them in base 10

For example if you have 10 buildings that gives 0.1 crystal everyday, you would gain exactly 1 crystal per day. In the user interface you wouldn't see something like "0.999 crystal per day". And it is not just for pretty tooltips, if there is a game logic that checks ">= 1.0 crystal per day" then that condition is guaranteed to be satisfied after 10 crystal buildings

> Is there still a performance win?

Sometimes. Rarely. Specifically, it's a performance win when you don't need 32 bit of precision, when 8 or 16 bits is enough in these integers. When it happens, you can pack twice as many lanes in the SIMD vectors, and use instructions which view 16-byte vectors as 8 int16_t lanes, or 16 uint8_t lanes.

FP32 is much faster to multiply and especially to divide, compared to Int32.

> Do games and similar software use them today?

Image and video processing code which for some weird reason runs on CPU definitely does.

Prepared as a lecture supplement for ECE 4760 (Digital System Design Using Microcontrollers) at Cornell.

Nice explanation! May I suggest a tiny addition to the text? Fixed point (in decimal) is also useful to make sure 1 trillion dimes are 100 billion dollars instead of $99,999,997,952.

Don't use stdfix.h if you are doing this though. As soon as you need to change your headroom (even temporarily within an algorithm), it will be a pain. Just use the boring C90 types (possibly typedeffed to something else) and write the operators you need.

Fixed point was still normal instruction in mandatory classes when I was in school. It is a pity, but I feel like we stopped teaching it at some point.

Another advantage: the results of additions no longer depend on the operation order. Converting floats to such ints helped me remove nondeteminism from a large pipeline that did additions over large sets of numbers. It was annoying to trace diffs in the pipeline when we were making changes and wanted to see what the end results are.

I used fixed point for my game's physics, because I wanted things to be deterministic across platforms and compilers (the game has a hidden "solver" which is used to tweak things a little bit to make the game more fun, but this involves rerunning simulations multiple times).

I did need a sqrt, but I cared more about predictability than accuracy, so I just did an iterative algorithm (actually two - one for the integer part, and then a second one to get better precision)

Did you use stdfix, another library, or just hand-roll it?

Handrolled. It looks like this: https://ideationapps.com/2020/12/09/making-two-birds-fixed-p...

I used fixed-point for all the 3d code in The Virtual Reality Playhouse (1992). That was the last time I wrote any significant assembler code. Good times.

By the way ... that was the first VR program one could run at home. I drove liquid crystal classes with the modem control lines. Switching left/right was synchronized to the monitor's vertical retrace.

Even better times. :)

Fixed point is critical reading for a lot of FPGA work.

For those of us unfamiliar with FPGA work, can you elaborate?

FPGAs let you define the structure of the hardware, and implementing fixed point is a lot simpler in terms of logic gages used and usually higher performance. You absolutely could use floating point, but the HW cost would be high, so most folks convert to fixed and use that. Then the question becomes how many bits, as you can have arbitrary width fixed point, so must choose at the design time depending on the application requirements.

That would be easier with Forth :).

Whenever I hear "fixed point arithmetic", it reminds me of the jittery graphics on PSX.

Can't find a more official source than Reddit, but here goes:

> It's because the position of each polygon's vertex (corner) is only calculated at a very low precision. Once the polygon moves (or the camera) the vertexes will stay at the same point, until they're closer to the next and suddenly "jump" to the new position without transition. Newer graphics hardware could interpolate smoothly here with more in-between states (that's where all the talk about "floating point precision" came from in graphics).

0. https://www.reddit.com/r/gaming/comments/bkedc/heres_a_quest...

The “jitter” of PSX graphics is caused by a number of factors: https://retrocomputing.stackexchange.com/a/5021

Incidentally, the Nintendo 64 also used fixed point numbers in RDP graphics instructions, but did not exhibit the same visual artifacts as the PlayStation.

I'm using fixed point for real-time DSP on cortex-M. Faster than floating.

Using the CMSIS-DSP Q31 functions, in particular. On Rust `i32`s.

On the PIC32, fixed add is ~2 cycles and floating point is is ~60. And about a 2x increase for multiplies. On architectures with floating point hardware some of the advantage is lost, but it's fantastic for DSP on microcontrollers.

Do you have numbers for x86? A web search didn't give me a clear answer, especially for non-vectorized code.

I don't unfortunately. I came up with those numbers by using the timers on the PIC32 to measure execution time, in case that's helpful.

Or alternatively (and often more simply) by setting and clearing a GPIO pin before/after the operation being timed, and then using the oscilloscope to measure execution time

There are half a million x86 microarchitectures. You can look up a particular microarchitecture in Agner Fog’s instruction tables (link below). There will be both throughput and latency values for different instructions (or something else, depending on microarchitecture). Keep in mind that x86 has both x87 and SSE floating-point, it sounds like what you want is the single precision, non-vectorized SSE instructions (like ADDSS). Also note that most microarchitectures are superscalar and may have multiple units capable of executing the instruction you are looking at.

https://www.agner.org/optimize/instruction_tables.pdf

In general, recent consumer x86 CPUs will be faster at floating point code than fixed point code. Floating point multiply is already faster than integer multiply; fixed point has the additional cost of the bitshift. (which is very small, but non-zero) Addition/subtraction are similar.

Mid-range smartphones will generally have acceptable floating point units, and you should stick to floating point math. If you're targeting low end smartphones, you never know what you're going to get.

Fixed point is generally only still useful on embedded. If you're building software for fixed point, it's generally because you know exactly what CPU your software is going to run on, and you know it doesn't have a FPU.

> Fixed point is generally only still useful on embedded.

Also multimedia. Modern CPUs compute FP32 floats equally fast as integers. However, when you only need 8 or 16 bits of precision, RAM bandwidth often dominates computations. Most image and video codecs are still using 8 bits per channel.

Profit from fixed point can be quite large for these use cases. That’s assuming the implementation is good, with SSE2, AVX2 or NEON SIMD.

Reply on news.ycombinator.com