[HN Gopher] Neo Geo Dev: Fixed Point Numbers
___________________________________________________________________
Neo Geo Dev: Fixed Point Numbers
Author : thunderbong
Score : 74 points
Date : 2024-08-20 02:39 UTC (20 hours ago)
(HTM) web link (mattgreer.dev)
(TXT) w3m dump (mattgreer.dev)
| vardump wrote:
| On the PC side, most developers stopped predominantly using fixed
| point for high performance code somewhere in the Pentium 1-3 era.
| For 486 class systems it was still pretty useful.
|
| Other than on retro systems, fixed point is still useful in
| smaller microcontrollers.
| pjmlp wrote:
| Michael Abrash books contain information on these kinds of
| optimizations, which were exactly on this transition point, as
| timeframe.
| VyseofArcadia wrote:
| A buddy of mine and I are working on a weekend project
| together. We recently realized that we don't need all that much
| precision, just a little, and switching from doubles or floats
| to 16-bit fixed point in our main data structure actually makes
| it small enough to fit an instance in a typical cache line (<
| 64 bytes).
|
| Completely unnecessary for our target platform but deeply
| satisfying.
| vardump wrote:
| For performance sensitive code memory bandwidth is very often
| the limiting factor, thus compressing values tends to make a
| lot of sense. The number of CPU cores is increasing much
| faster than memory bandwidth.
|
| So not necessarily completely unnecessary.
| VyseofArcadia wrote:
| I expect it will have some effect given that we anticipate
| having ~1000 instances of that data structure alive at
| worst case, at least dozens at any given time.
| twoodfin wrote:
| A few years before that era, I was having a lot of fun with
|
| https://en.wikipedia.org/wiki/Fractint
| mmaniac wrote:
| This sort of thing is ordinary for consoles without floating
| point numbers. It's easy to do in software with integers, but
| sometimes hardware acceleration will use it too.
|
| The SNES and GBA both supported affine transformations, where the
| elements of the multiplication matrix are fixed point numbers.
| The Playstation's geometry coprocessor (GTE) used fixed point
| matrices with quite low 16 bit precision. An emulator feature
| called PGXP is able to perform these calculations at higher
| precision.
| 01HNNWZ0MV43FF wrote:
| And just to head off the discussion that happens every single
| thread:
|
| - Yes, the PS1 had "jittery" vertices because 16 bits is not
| enough precision
|
| - No, it was not because of using integers, you can use
| integers (AKA fixed-point) to do 3D just fine. If it had been
| 16.16 (32 bits total) it would probably look fine.
|
| - No, this isn't the cause of the texture warping, that's
| because unlike the N64 it only supported affine texture
| mapping, not perspective-correct texture mapping. The PS1 saw
| every 3D triangle as just a 2D triangle, and texture mapping in
| 2D differs from texture mapping in 3D
|
| - Yes, the texture warping is why many of the best-looking PS1
| games were basically built on a grid or found other ways to use
| a large amount of small triangles instead of a small amount of
| large triangles.
| fidotron wrote:
| It's worth saying the original Playstation was entirely fixed
| point. You can go surprisingly far with it.
|
| https://en.wikipedia.org/wiki/Fixed-point_arithmetic#Softwar...
|
| I spent so much of the early stage of my career doing early
| mobile stuff I practically still think in fixed point, and always
| have to adjust to floats, for example, fixed point results can be
| compared exactly while with floats that is not a great idea. TeX
| uses fixed point entirely because it was reproducible across
| machines in an era where floating point was not.
| __s wrote:
| I think fixed point would be used a lot more with proper
| support in programming languages
| fidotron wrote:
| What you would need is the language to track the expected
| range of the numbers. You often end up with multiple
| different multiply/divide implementations (shifting amounts
| before/after) based on if you can safely guarantee you are
| within an expected range or not.
| SideQuark wrote:
| I doubt it. It fails for far too many useful programming
| situations that it would cause more problems than floating
| point.
|
| Cannot use it efficiently for nearly anything: finance
| software, science software, engineering software, high
| quality graphics software... 3d software, pretty much
| anything that has any range needed or ability to lower errors
| while doing accumulation of information.
|
| This is exactly why floating point was invented and
| standardized - fixed point is a failure for most any program,
| and only can work with much effort only for certain
| situations.
|
| (I've written tons of fixed point code, numerical libraries
| across the spectrum from high performance, high quality,
| tunable quality, arbitrary precision libs, posits and unums,
| IEEE half-float software implementations, and more, so I do
| know what I'm talking about).
| jerf wrote:
| Is there even any performance benefit on modern CPUs? I
| tried to consult some real tables but I'm not experienced
| enough to be sure I'm reading them correctly. If I'm
| reading something like [1] properly, it looks like it is
| not a clear win on modern hardware to use fixed point &
| integer operations. It would depend on the ratio of
| addition/subtraction/multiplication to division.
|
| (Obviously one must factor out a lot of local
| considerations, which modern CPUs are full unto overflowing
| with; I'm kind of looking at a very, very broad average
| performance question across code bases doing enough
| different math operations to average out, not whether one
| particular loop can run theoretically run faster or slower
| with one or the other.)
|
| [1]: https://stackoverflow.com/questions/2550281/floating-
| point-v...
| ooterness wrote:
| It depends a lot on CPU architecture. Floating point
| units may be tied to each core, or they may be shared, so
| it may further depend on other concurrent workloads.
|
| There's also SIMD instructions. Modern CPUs have built-in
| instructions for handling multiple ints or floats as a
| vector. If you can get your fixed-point varies to for
| into 8-bit or 16-bit fields instead of 32, then the same
| sized vector units can handle more values per
| instruction.
| taeric wrote:
| My gut would be that you also get some benefit by some
| auxiliary choices. With a lot of precomputed constants,
| you can probably avoid a lot of known multiplications.
| That said, yeah, if you have to start doing a lot of
| fixed point multiplications, you could eat any savings
| you had.
| ack_complete wrote:
| Address calculations are a place where fixed point can
| still have an advantage -- it's often less latency and
| fewer ops to step a fixed-point accumulator and shift it
| into an address offset on the integer units than to step
| a floating point accumulator, convert it to integer, then
| move that over from the FP/vector units to the integer
| units.
| thequux wrote:
| You might be surprised at where fixed point is already
| used: * Finance software: if you're using floats, you're
| doing something horribly wrong. All balances are measured
| in integer multiples of some quantum; depending on the
| system, that may be cents, it may be 0.1 cents, or it may
| be 0.01 cents. Gradations finer than that simply do not
| exist, and integer overflow is both more likely to be
| noticed and more easily explained to be a bug than
| precision loss (and this matters when you have a regulator
| asking uncomfortable questions) * CAD software: floating
| point may make sense for simulations, but at least for PCB
| design, layout is done in fixed point. You need consistent
| precision across the board, and avoiding edge cases in your
| geometry kernel from precision issues makes everything much
| easier. Besides, with a 1um quantum, 32-bit numbers are
| sufficient for a board 4km on a side. If you need larger, I
| would _love_ to see your fab. * Robotics: maybe this one 's
| just me, but expressing motion control algorithms in fixed
| point has saved me EUR1/part on more than a few occasions
| as a result of being able to use an MCU without hardware
| floating point. Compared to the EUR0.20/part saved by
| muntzing the rest of the circuit, the small amount of
| additional work was totally worth it.
|
| Indeed, the tools for working with fixed point aren't
| great. C is a lost cause; the best you can do is name your
| variables things like velocity_12_4 and manually check that
| the precision lines up. Rust wasn't great when I tried,
| though const generics may have resulted in an improvement.
| C++ was, astonishingly enough, quite good; I made a header-
| only fixedpoint.h with a templated struct
| `fixed<type,size,precision>` and all inline operations. I
| get the impression that Ada would be even better, but I've
| yet to use it in anger.
| edflsafoiewq wrote:
| The most common place is probably image/audio processing.
| Sample values are usually always quantized, even in
| intermediate stages. Decoding a JPEG for example is a
| bunch of fixed point math.
| hansvm wrote:
| > fixed point results can be compared exactly
|
| You gain the ability to get stable results across machines, but
| there still necessarily exists a loss of precision, and
| different implementations of the same algorithm will get
| different results.
|
| When would you want to compare fixed-point results bitwise
| though?
| adancalderon wrote:
| "If you wan't"
| capitainenemo wrote:
| Hedgewars uses fixed point due to inconsistencies in floating
| point implementations breaking deterministic lockstep. 0AD and
| Spring: RTS has similar issues although I think both use streflop
| now.
| nritchie wrote:
| When I was a freshman (or so) in high-school, our computer lab
| had just graduated from a time-share terminal to the next-door
| university to the Apple II. A kid (Ray Tobey) in the next grade
| up started to code a project to submit to a Byte Magazine game
| contest. The due date came and went, but he carried on in every
| moment of his free time. Long story short, this game became
| SkyFox of which Woz said "consider this flight simulator as the
| finest Apple game ever done." From Ray, I learned the value of
| using continued fraction approximations to trig functions using
| only integer math. Later, this became useful when I had to
| implement image rotation in a scan generator for a scanning
| electron microscope.
| 01HNNWZ0MV43FF wrote:
| Oh cool! I think I played that on my family's Apple II. I think
| it was mislabeled as "Star Fox" and probably pirated. Sorry
| Ray...
| tralarpa wrote:
| On the Amiga and Atari, based on the Motorial 68000 like the
| NeoGeo, all 3D games used fixed point arithmetic.
|
| At that time, such games were written in assembler, and you had
| to be very careful to place the instructions for scaling and
| descaling in the right places, not only to get the final result
| in the right units (i.e., screen coordinates), but also in
| intermediate calculations to preserve precision.
| wk_end wrote:
| I always felt when learning about this stuff that people -
| pedagogically - make fixed point seem more complicated than it
| is.
|
| Since this article is talking about more precisely positioning
| sprites in a 2D world, it could practically be a one-liner:
| "instead of tracking positions/velocities in pixels, track them
| in half pixels". Everything falls out of that intuition.
| city41 wrote:
| I'm the author of the blog post. I just used sprite positioning
| as a simple example. Things like collision detection and
| physics can't be done with half pixels.
| 01HNNWZ0MV43FF wrote:
| They can't?
| wk_end wrote:
| Not sure what you mean - sure you can.
|
| Trying to read between the lines here, if your objection is
| to _half_ -pixels because they're not precise enough for
| (good) physics, then I apologize for being unclear - I mean
| half-pixels, or quarter-pixels, or eighth-pixels, or
| whatever.
|
| Another way of wording my comment is that I think it's easier
| - especially for beginners - to think in terms of smaller
| units (represented as integers) than in terms of a new number
| format for representing fixed-size fractional parts of larger
| units. But the two concepts are ultimately the same.
| city41 wrote:
| But that's basically what fixed point is, no? Half pixels
| is fixed point with a single bit for decimals. Quarter
| pixels is two bits, and so on. I think the disadvantage is
| you now have to think in a strange unit that isn't
| intuitive. For my game I tend to think in screen sizes for
| things. Thinking in screen size*factor would be harder I
| think. Fixed point is basically just doing that for me and
| hiding the details really.
|
| To be fair, rereading the post I realize I did make it
| sound like you would only need this for positioning
| sprites. I'll see about rewording it.
|
| Or maybe we're both talking about the same thing and you're
| taking a different approach. That is fair too.
| wk_end wrote:
| Yeah, we're technically talking about the same thing -
| just a different way of thinking about it.
|
| When I was learning retro game dev (mostly Game Boy), I
| found fixed point very intimidating. Reading stuff like
| "the player will move at 1.5 pixels per frame, and to
| store the decimal point we'll use this special format
| where certain bits represent the fractional part and
| certain bits represent the integer part" scared the heck
| out of me when I was still, like, coming to grips with
| binary representations at all.
|
| Whereas "the player will move at 3 half-pixels per frame"
| is just a really straightforward conceptualization. The
| data representation is the same, the code to convert from
| half-pixels to pixels is the same, but one way of
| understanding it feels very technical and abstract.
|
| Especially when working in assembly language (like I
| was), where you don't really have any kind of typing
| mechanism, it never really made sense to build a fixed-
| point data type abstraction.
|
| And, to be clear, I'm not trying to give you,
| specifically, any guff for this; it's as fine an article
| on fixed-point that there is.
| pistoleer wrote:
| I wonder how many people have reinvented the concept of fixed
| point when they calculated using "cents" instead of "dollars".
| fizzynut wrote:
| Is it possible to get rid of all the macros TO_FIXED, FROM_FIXED,
| mult, etc and replace them with a class with the correct
| constructors / operator overloads?
|
| Then your code doesn't ever need to be aware of the special fixed
| point math and horrible syntax everywhere and everything just
| works?
| msk-lywenn wrote:
| Yes it can. I've seen it done properly only once though. You
| still have to pay attention to avoid overflows
| BearOso wrote:
| Multiplying without having a larger intermediate is much more
| complex than the article states. You have to use the commutative
| property of multiplication and split the whole and decimal parts
| of each number out, otherwise you're stuck with single digit
| whole numbers or only multiplying fractions.
|
| So you'd take A.a * B.b and split it into A*B +
| A*b + a*B + a*b
|
| Or out = ((A >> fixedbits) * (B >> fixedbits)
| << fixedbits) + ((A >> fixedbits) * b) +
| ((B >> fixedbits) * a) + ((a * b) >> fixedbits);
|
| If you can get away with a little less precision and smaller
| whole numbers, you can avoid some of the multiplications by just
| doing this, which is quite common: (A.a >>
| (fixedbits / 2)) * (B.b >> (fixedbits / 2))
| Joker_vD wrote:
| It's such a shame that multiplication in C (or most other
| languages, really) doesn't have its natural type (intM, intN)
| -> int{M+N}. Instead, you have to recover the higher half of
| the result either by doing additional narrow multiplication
| yourself, or by using some compiler intrinsic.
| jnwatson wrote:
| Gcc can frequently tell what you're trying to accomplish and
| emit the correct instructions. Still I agree it would be
| ideal if this were explicit.
| jnwatson wrote:
| FYI, the multiply assert isn't guaranteed to work and can be
| compiled out by a sufficiently smart compiler. Overflow of signed
| values is UB, the compiler can assume that UB is impossible,
| therefore the expression in the if resolves to false.
| throwawayk7h wrote:
| Fixed point should really be used way more often than it is. It's
| much safer, for one thing, and less mysterious. But because C
| lacks first-class support for fixed point, the whole world has
| become flopsy.
| djmips wrote:
| Nit to the author. Decimal point. Decimal digits. Actually binary
| point and binary digits.
___________________________________________________________________
(page generated 2024-08-20 23:01 UTC)