News for hackers. Stuff that matters.
Re:Fixed Point Arithmetic by benhoyt on Sunday October 17, 2021 @09:34PM (#28901406)
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?
Re:Fixed Point Arithmetic by stkdump on Monday October 18, 2021 @02:23AM (#28902767)
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.

Re:Fixed Point Arithmetic by snak on Monday October 18, 2021 @02:26PM (#28909297)
FP abbreviation is probably not a good idea here, while talking of Floating Point and Fixed Point, a little bit confusing.
Re:Fixed Point Arithmetic by dreamcompiler on Sunday October 17, 2021 @11:32PM (#28901992)
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...

Re:Fixed Point Arithmetic by chas on Sunday October 17, 2021 @10:34PM (#28901721)
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.
Re:Fixed Point Arithmetic by wtallis on Sunday October 17, 2021 @11:04PM (#28901856)
> 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.

Re:Fixed Point Arithmetic by chas on Monday October 18, 2021 @03:28AM (#28903086)
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.
Re:Fixed Point Arithmetic by corysama on Sunday October 17, 2021 @11:59PM (#28902105)
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.
Re:Fixed Point Arithmetic by chas on Monday October 18, 2021 @03:16AM (#28903013)
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

Re:Fixed Point Arithmetic by whateveracct on Sunday October 17, 2021 @10:20PM (#28901634)
The main appeal of fixed point nowadays is determinism across hardware - so networked games benefit, for instance.
Re:Fixed Point Arithmetic by benhoyt on Sunday October 17, 2021 @10:40PM (#28901751)
Interesting. Are IEEE-specified floating point operations not deterministic?
Re:Fixed Point Arithmetic by atq2119 on Monday October 18, 2021 @02:10AM (#28902723)
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.

Re:Fixed Point Arithmetic by cmroanirgo on Sunday October 17, 2021 @11:39PM (#28902019)
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

Re:Fixed Point Arithmetic by newpavlov on Monday October 18, 2021 @02:04AM (#28902696)
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.
Re:Fixed Point Arithmetic by lmm on Monday October 18, 2021 @02:32AM (#28902804)
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.
Re:Fixed Point Arithmetic by anonymoushn on Monday October 18, 2021 @02:03AM (#28902694)
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
Re:Fixed Point Arithmetic by emacs28 on Monday October 18, 2021 @12:40AM (#28902283)
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.
Re:Fixed Point Arithmetic by tsimionescu on Monday October 18, 2021 @02:12AM (#28902730)
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.
Re:Fixed Point Arithmetic by shultays on Sunday October 17, 2021 @10:26PM (#28901672)
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
Re:Fixed Point Arithmetic by dragonwriter on Sunday October 17, 2021 @10:28PM (#28901687)
“fp” is an unfortunate abbreviation for floating point when contrasted with fixed point.
Re:Fixed Point Arithmetic by shultays on Monday October 18, 2021 @04:25AM (#28903312)
Hah, thanks for pointing that out, I haven't noticed it
Re:Fixed Point Arithmetic by Asraelite on Monday October 18, 2021 @06:42AM (#28904066)
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.
Re:Fixed Point Arithmetic by shultays on Monday October 18, 2021 @09:00AM (#28904963)
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?

Re:Fixed Point Arithmetic by anonymoushn on Monday October 18, 2021 @02:00AM (#28902681)
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.
Re:Fixed Point Arithmetic by franga2000 on Monday October 18, 2021 @02:43AM (#28902853)
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.

Re:Fixed Point Arithmetic by anonymoushn on Tuesday October 19, 2021 @08:37AM (#28917403)
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.

Re:Fixed Point Arithmetic by shultays on Monday October 18, 2021 @04:55AM (#28903459)
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

Re:Fixed Point Arithmetic by Const-me on Monday October 18, 2021 @06:41AM (#28904057)
> 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.

Re:Fixed Point Arithmetic by justshowpost on Monday October 18, 2021 @01:22AM (#28902470)
> 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.

Re:Fixed Point Arithmetic by tuatoru on Monday October 18, 2021 @01:44AM (#28902591)
> 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.

Re:Fixed Point Arithmetic by SuchAnonMuchWow on Monday October 18, 2021 @02:12AM (#28902729)
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.

Re:Fixed Point Arithmetic by benhoyt on Monday October 18, 2021 @02:39AM (#28902834)
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.
Re:Fixed Point Arithmetic by tuatoru on Monday October 18, 2021 @03:32PM (#28910420)
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.
Re:Fixed Point Arithmetic by Jare on Monday October 18, 2021 @02:04AM (#28902698)
Swift recently switched its Date internal format to fixed I think:

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

Re:Fixed Point Arithmetic by codr7 on Monday October 18, 2021 @12:25AM (#28902219)
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.