Re: [boost] Fixed point integer proposal
Some years ago I wrote a fixed point template for transparent fixed point integer arithmetics and conversion.
To me, "fixed point" => !"integer".
Obviously fixed point is not an integer in mathematical sense. What I meant was that a fixed point represented by an integer shares some of the same computational properties: Arithmetic is faster than floats on most architectures. Adding (and accumulating) fixed points or multiplying by an integer is exact. Conversion to integer is fast.
particular, saturating or otherwise detecting overflows seemed to be required.
Saturation and overflow detection can be specified as a policy. For me there are two important design criteria: 1st priority is that computational performance matches integer performance. 2nd priority is that it is possible to make a seamless float type and the fixed point type exchange. Adding saturation handling and overflow checks, that are not natively supported by the underlying integer is of lower priority for me. In my fixed point class I implemented overflow check as an optional policy. That way you can add all the overhead checks you want in your debug configuration and strip it in your release build. As of saturation (I assume it's computer graphics people that want that feature) it should be straight forward to implement that as a policy too in the same way as the overflow check. In my option I see little practical use of a saturation policy. Saturation code would kill performance and people would be better off using MMS registers for native saturation.
recall that someone was actually working on that. It was also suggested that I ought to provide all of the features that <cmath> provides for floating point.
It makes sense to support rounding, abs and mod. I don't see a practical need to natively support trigonometry functions. A conversion to float and back has to be fine. Soren
Soren Holstebroe wrote:
It makes sense to support rounding, abs and mod. I don't see a practical need to natively support trigonometry functions. A conversion to float and back has to be fine.
My use-case for fixed-point arithmetic is game development on embedded devices that lack FPUs. Native support for trigonometric functions is something I would definitely want.
Hi Kenny,
My use-case for fixed-point arithmetic is game development on embedded devices that lack FPUs. Native support for trigonometric functions is something I would definitely want.
I can see there could be a need for it. However, in my opinion, it would be out of the scope for a fixed point template to accurately and effectively implement trigonometric functions. Especially for game programming you would probably be better of interpolating values from a sinus table rather than calculating the exact value. Soren
My use-case for fixed-point arithmetic is game development on embedded devices that lack FPUs. Native support for trigonometric functions is something I would definitely want.
On Thu, Jun 25, 2009 at 01:57:51PM -0500, Soren Holstebroe wrote:
I can see there could be a need for it. However, in my opinion, it would be out of the scope for a fixed point template to accurately and effectively implement trigonometric functions.
Regardless, it's easily something that can be added later, and whenever it's added, it makes sense to put it in a separate header from the class template anyway. I'm sure that at review time, the people who want a useful system now that can be built upon later with extra functions will outvote anyone who would rather hold their breath for something that does everything everyone might want. -- It's so hard to see the Sun with the truth in your eyes. http://surreal.istic.org/ Yellow: it's the new khaki.
Daniel Hulme wrote:
My use-case for fixed-point arithmetic is game development on embedded devices that lack FPUs. Native support for trigonometric functions is something I would definitely want.
On Thu, Jun 25, 2009 at 01:57:51PM -0500, Soren Holstebroe wrote:
I can see there could be a need for it. However, in my opinion, it would be out of the scope for a fixed point template to accurately and effectively implement trigonometric functions.
Regardless, it's easily something that can be added later, and whenever it's added, it makes sense to put it in a separate header from the class template anyway. I'm sure that at review time, the people who want a useful system now that can be built upon later with extra functions will outvote anyone who would rather hold their breath for something that does everything everyone might want.
Agreed. I was just saying that there are use-cases where simply converting to float and back isn't good enough.
Hello, In fact, fixed point is not faster on many architectures than floating point. One assumes that it is mainly PSP, DS and Gamecube guys that want fixed-point just for speed these days (I'm looking at you, Kenny ;). It was the case years ago that fixed-point was faster than floating-point, but it is less commonly true now than conversely. Modern systems typically have at least one if not many dedicated FPU's which can work in parallel with the main ALU(s). Similarly, it is often faster to use floating-point trig than fixed-point trig. FPU trig is heavily optimised in micro-code and, perhaps surprisingly, it is often faster to do trig on an FPU than break the cache with the table lookup that is often used in fixed-point. And lastly, converting to and from fixed- and floating-point is generally very slow. Of course, I am referring mainly to embedded hardware systems like game consoles, but I think in general the idea that fixed-point is faster is not as true as it once was. The reason for this preamble is to make the case that the main reason for fixed-point these days is accuracy and not speed. As has been noted in this thread, fixed point is accurate and does not drift. This is not entirely accurate (no pun intended), as there is drift in both fixed- and floating-point, but fixed-point is generally more stable for things like physics simulators. Given that, I would vote for a fixed-point system that favored accuracy and resolution over speed. Indeed, there is a case to be made for a so-called "floating-fixed-point" system; I wrote one of these some time ago and it helped a great deal with accuracy. The basic idea is to use an N.M fixed-point format for numbers, and the result of operations changed to a minimal N2.M2 format in order to preserve accuracy. Has anyone put forward a generalised arithmetic system that used arbitrarily-sized "floating-fixed-point" values to allow for an arbitrarily large (or arbitrarily small) number system? This would seem to me to be of more value than a "fixed-fixed-point" system designed primarily for speed, which has a dubious premise and has all the associated issues of accuracy and operation result types. Regards, Christian. On Fri, Jun 26, 2009 at 4:38 AM, Soren Holstebroe <holstebroe@gmail.com>wrote:
Some years ago I wrote a fixed point template for transparent fixed point integer arithmetics and conversion.
To me, "fixed point" => !"integer".
Obviously fixed point is not an integer in mathematical sense. What I meant was that a fixed point represented by an integer shares some of the same computational properties: Arithmetic is faster than floats on most architectures. Adding (and accumulating) fixed points or multiplying by an integer is exact. Conversion to integer is fast.
particular, saturating or otherwise detecting overflows seemed to be required.
Saturation and overflow detection can be specified as a policy. For me there are two important design criteria: 1st priority is that computational performance matches integer performance. 2nd priority is that it is possible to make a seamless float type and the fixed point type exchange.
Adding saturation handling and overflow checks, that are not natively supported by the underlying integer is of lower priority for me. In my fixed point class I implemented overflow check as an optional policy. That way you can add all the overhead checks you want in your debug configuration and strip it in your release build. As of saturation (I assume it's computer graphics people that want that feature) it should be straight forward to implement that as a policy too in the same way as the overflow check. In my option I see little practical use of a saturation policy. Saturation code would kill performance and people would be better off using MMS registers for native saturation.
recall that someone was actually working on that. It was also suggested that I ought to provide all of the features that <cmath> provides for floating point.
It makes sense to support rounding, abs and mod. I don't see a practical need to natively support trigonometry functions. A conversion to float and back has to be fine.
Soren _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
2009/6/25 Christian Schladetsch <christian.schladetsch@gmail.com>:
Hello,
In fact, fixed point is not faster on many architectures than floating point. One assumes that it is mainly PSP, DS and Gamecube guys that want fixed-point just for speed these days (I'm looking at you, Kenny ;).
On my quad core desktop there is a difference between ints and floats. I just wrote a quick test with the following loop for some random initialization values: for (int i = 0; i < iterations; ++i) { sum += a * b; a += b; } I used MSVC++ to compile. I set iterations to a billion. When I used ints I got around 800 ticks. When I used floats I got around 3700 ticks. That is almost a factor five. For my purposes, that's an optimization I am willing to sacrifice a lot for. Soren
I just wrote a quick test with the following loop for some random initialization values:
for (int i = 0; i < iterations; ++i) { sum += a * b; a += b; }
I used MSVC++ to compile.
I set iterations to a billion. When I used ints I got around 800 ticks. When I used floats I got around 3700 ticks.
That is almost a factor five. For my purposes, that's an optimization I am willing to sacrifice a lot for.
I just did the same test, with SSE2 enabled. int: 0.916 seconds, 1321730048 float: 1.398 seconds, 4.5036e+015 In this case, floats were 70% the speed of ints, but also gave a modicum of the correct result. The ints were faster but gave the incorrect result. Furthermore, this was ints not fixed-point. Would doing it using an actual fixed-point number make up the %30 difference? Perhaps, but it would still give the wrong result. I didn't mean to claim that fixed-point was "always slower than floating point" - especially for toy cases like this ints will be faster (if wrong) because there is nothing else for the CPU todo while the FPU is working. Add in some fetches or stores and I think you will get a far different result. In any case, I merely intended to make the point that one good reason for using fixed-point over floating point is accuracy and not necessarily speed. Regards, Christian.
Just to make the case for fixed-point accuracy over flixed-point speed: template <class Number> Number work(size_t iterations, std::vector<Number> const &data) { Number sum = 0; size_t size = data.size(); for (size_t i = 0; i < iterations; ++i) { Number a = data[i % size]; Number b = data[(i + 500)%size]; sum += a * b; } return sum; } BOOST_AUTO_TEST_CASE(test_floats) { size_t iterations = 1000*1000*100; size_t outter = 1;//00;//0*1000*10; double int_t = 0; double float_t = 0; size_t size = 100000; std::vector<int> ints(size); srand(42); generate_n(ints.begin(), size, rand); std::vector<float> floats(size); srand(42); generate_n(floats.begin(), size, rand); boost::timer int_timer; int int_sum = 0; for (size_t n = 0; n < outter; ++n) { int_sum += work(iterations, ints); } int_t = int_timer.elapsed(); boost::timer float_timer; float float_sum = 0; for (size_t n = 0; n < outter; ++n) { float_sum += work(iterations, floats); } float_t = float_timer.elapsed(); cout << int_t << ", " << float_t << "; " << int_sum << ", " << float_sum << endl; }
1.103, 0.949; 129244096, 1.80144e+016 In this (slightly-less non-toy case), floats were a little bit faster. If you actually used fixed-point here, rather than floats, then the difference would be much larger again. Regards, Christian On Fri, Jun 26, 2009 at 12:23 PM, Christian Schladetsch < christian.schladetsch@gmail.com> wrote:
I just wrote a quick test with the following loop for some random initialization values:
for (int i = 0; i < iterations; ++i) { sum += a * b; a += b; }
I used MSVC++ to compile.
I set iterations to a billion. When I used ints I got around 800 ticks. When I used floats I got around 3700 ticks.
That is almost a factor five. For my purposes, that's an optimization I am willing to sacrifice a lot for.
I just did the same test, with SSE2 enabled.
int: 0.916 seconds, 1321730048 float: 1.398 seconds, 4.5036e+015
In this case, floats were 70% the speed of ints, but also gave a modicum of the correct result.
The ints were faster but gave the incorrect result. Furthermore, this was ints not fixed-point. Would doing it using an actual fixed-point number make up the %30 difference? Perhaps, but it would still give the wrong result.
I didn't mean to claim that fixed-point was "always slower than floating point" - especially for toy cases like this ints will be faster (if wrong) because there is nothing else for the CPU todo while the FPU is working.
Add in some fetches or stores and I think you will get a far different result.
In any case, I merely intended to make the point that one good reason for using fixed-point over floating point is accuracy and not necessarily speed.
Regards, Christian.
In this (slightly-less non-toy case), floats were a little bit faster. If you actually used fixed-point here, rather than floats, then the difference would be much larger again.
You are indeed right, that enabling SSE2 gives float speed close to integer speed. I tested your code example and depending on which operations that were used in the calculation I got different winner types (i changed the mod operator in your array access, since that was very expensive and biased the results). I also tested my fixed point template and interestingly it performed best of the three for some calculations. I was surprised about that one and have no good explanation to that yet. I might have to look into the generated assembly code to check out what is going on. Anyway, as you point out, speed isn't the only justification for a fixed point class, if at all, though you might get considerable speed gains on some architectures. I have enjoyed the seamless syntax of converting third party fixed point audio stream (libmad) to floats for audio filtering and then to the sound system output. Since I defined my float audio to be in normal range between -1 and 1 I just had to define a 16 bit signed fixed point for the audio output type. Driftless accumulation is another obvious benefit of fixed point in many applications. All in all I still believe a fixed point class would fit in the boost library, since it has many general applications. Regards Soren
On Thursday 25 June 2009 18:41:43 Christian Schladetsch wrote:
In fact, fixed point is not faster on many architectures than floating point. One assumes that it is mainly PSP, DS and Gamecube guys that want fixed-point just for speed these days (I'm looking at you, Kenny ;).
My work requires fixed-point types for modeling cheap embedded microprocessors and other digital signal processing circuits. After using home-made code, code based on Williams' DDJ article and SystemC fixed-point types, I have finally settled on the AlgorithmicC datatypes from Mentor Graphics. A boost implementation would be extremely useful for DSP modeling. For DSP modeling, N-bit x N-bit = N-bit will not suffice. Typically, hardware implementation in critical paths of DSP chips have code equivalent to the following: s[3:-3] x u[3:-4] = s[4:-3] where s[4:-3] indicates an 9-bit signed fixed-point number with bits representing: sign, 2^4, 2^2, ..., 2^--3. In this case, the general-purpose fixed-point library does the following: 8-bit signed * 8-bit unsigned = 16-bit signed -> 9-bit signed where the 7 bits to be removed are found from the specification above. Regards, Ravi
participants (5)
-
Christian Schladetsch -
Daniel Hulme -
Kenny Riddile -
Ravi -
Soren Holstebroe