Re: [boost] [fixed_point] First presentation from GSoC 2015 and more
Date: Thu, 13 Oct 2016 20:41:27 +0000 (UTC) From: Christopher Kormanyos
I discuss P0106R0 (a revision to N3352) in my paper, the latest draft of which is always available here: https://github.com/ johnmcfarlane/fixed_point/blob/master/doc/p0037.md#p0106 I'm honestly not sure which approach is preferable overall. The set of features and qualities requested during SG14 and SG6 meetings is large and conflicting. It includes minimal build times, minimal run-time overhead, every rounding and overflow strategy listed in P0105, decimal radix and support for specialized fixed-point instructions on embedded architectures. Hi John. Thanks for visiting this thread.
My recommendation would be to limit the scope of the proposal
to a realistic level in the SGs so that we can end up with anything
at all within a reasonable time scale. We could consider back porting
some (but probably not all) of SG14's specified interface to Boost
if that helps move anything along.
A second pair of implementor eyes would be a huge help. I should point out that although it hasn't seen much attention lately, P0106 may still be active. (Frankly, the evolution of my design has been largely a process of slowly copying or facilitating all the most popular from Lawrence's proposal!) One problem P0037 faces - even if it were to be standardized - would be that alone, it only provides fixed-point arithmetic. It's designed to work with types that also solve arbitrary width, rounding and overflow but those types are not part of any proposal. In particular, without an arbitrary-width integer type, it's very difficult to use fixed_point<> safely.
I was also wondering about decimal radix, but I don't know if it
might simply be better to identify those 80% of the most popular use cases and simply specify these. At least it would get the library
moving forward and people could use fixed-point in C++. This is basically what we tried to do with the GSoC project.
That makes sense. I at least want to have a solution which doesn't close the door on decimal in future additions. Here's my current plan: https://github.com/johnmcfarlane/fixed_point/blob/master/doc/p0037.md#non-bi...
In your work I've been experiencing some trouble with>> the division routine. Can you elaborate? Was this recently? I've been trying out numerous strategies for arithmetic operators. My current preferred approach is to pad the left-hand operand before performing the division but that's only been checked in for a few months.
I'm not sure about the design, and error on my side is
a likely possibility. But division operator in the master branch seems like it does not pad before divide. This might give the wrong result.
I hope that's not the case but it's a tough operator to get right - especially with 32-bit operands. If you ever find a good example of this happening I'd be very interested in it. At least when using the elastic alias, precision loss should be avoidable (beyond inevitable approximation of rational numbers and x/0). tl;dr: The details of padding in the division operator follow... The padding is done on this line: https://github.com/johnmcfarlane/fixed_point/blob/91c3f2e272f9fd5e33ffb4dc2d... It's on display in this test: https://github.com/johnmcfarlane/fixed_point/blob/1cc7ceaaff5422667ae962995a... In the above test, the two operands have a single fractional digits. If operator/ did not pad the LHS, then the integer operation would be 126/8 which would lose precision. Instead, the LHS is promoted and shifted left by 8 bits. Then, integer division occurs and the value is stored with (hopefully!) no further shifts.
For division, I have used the following approach.
* handle sign * extend n bits to 2n bits
* shift left by radix split plus one round bit
* divide 2n / n -> n bits
* handle round and sign So you're right this requires 64-bit extension for a 32-bit fixed-point
unless you tackle the problem of two-component division, which I have done using a simplified version of Knuth long division. At the moment, this is only in develop branch. The compiler switch is BOOST_FIXED_POINT_DISABLE_WIDE_INTEGER_MATH.
This is core to the difference in approach between P0037 and P0106. I guarantee to use built-in integer math for any type specialized on built-in integers. I believe that types with arbitrary width can then be built upon this foundation using novel integer types. Here is an example using Boost.Multiprecision to express a Googol: http://johnmcfarlane.github.io/fixed_point/#boost fixed_point<> uses the same algorithm regardless of whether the `Rep` integer is an uint8_t or a 400-bit custom type.
I also had some problems compiling
on VC12 (but you don't target that
compiler anyway). So that's no big deal.
You will need a C++11-compliant compiler as sg14::fixed_point<> creates literal types. Lack of support for features like constexpr constructors is the main obstacle to compiling under VC++ 2013 and earlier. I actually agree with that approach. Either it uses C++11 or
it does not. I don't see the need to cater to a specific older compiler for new library work.
It's a pragmatic choice. Three reasons are: * C++11 has everything I need to implement (with difficulty) a literal type. In particular, I can write most of my unit tests using `static_assert` which is the best thing ever! * Once you start returning novel specializations from your arithmetic operators, `auto` type deduction is essential to usability. * Many of my target users in SG14 are stuck with compilers which are behind the curve.
In your work you are using wrapped versions of elementary transcendental functions designed for built-in float. You might appreciate our hand-crafted functions designed to be highly efficient in several digit ranges.
Yes! I would be very interested in seeing if I could adapt those function. We worked hard on these. And there are many good
algorithms available in boost/fixed_point/fixed_point_negatable_cmath.hpp
Having spent a non-trivial amount of time writing the simplest sqrt I
could find, I appreciate the effort this must have involved.
Mine are placeholders and I've deliberately postponed the non-trivial task
of adding cmath equivalents. It's come up - maybe a couple of times - whether these functions are desired and the response has been to just keep the proposal narrow so they are not included.
There are interesting questions regarding how to implement some functions. For example, you surely don't always want the same inputs and outputs from functions involving angles. And hopefully these functions can be constexpr - unlike existing functions. I agree. Also, how have you approached the trade-off between speed and accuracy? I went for a very simple sqrt function which is adequate if the value is calculated at compile time but is likely not desirable at run-time. This isn't a problem that floating-point variants face.
The elementary transcendental functions use many techniques
including polynomial approximation, Pade approximation, Taylor series,
Newton iteration. For low digit counts, mostly polynomial approximation. We express the coefficients directly as integral values of the fixed_point representation and avoid as much as possible full division and multiply, favoring integer div and mul. These functions are quite efficient. We have not constexpr-ed them. But it looks like there is potential for that.
Writing constexpr functions in C++11 can be a big challenge.
I have also benched our fixed_point on bare-metal embedded systems both 8-bit and 32-bit with very satisfying efficiency results. This is a key feature for our embedded users that might also be interesting for SG14.
My current aim is to match integer performance for common arithmetic operations when using built-ins. This leads to some situations where overflow is a big problem - but no worse than dealing with raw integers. I'm curious how you deal with multiplying two int-sized values together without resorting to wider, slower types.I was under the impression that P0106 types always widen to fit their values. We have resorted to wider integer for internal mul and div or used higher level algorithms when the compiler switch BOOST_FIXED_POINT_DISABLE_WIDE_INTEGER_MATH is activated as mentioned above (develop branch only). In our approach, full multiplication requires:
* sign conversion
* left shift for round bit
* multiply n*n --> 2n bits
* right shift and round * sign conversion
On a 32-bit system, a full 32*32 -> 64 mul is required. This full multiplication approach can not achieve your desired efficiency goal on 8-bit and 32-bitCPUs. Division uses similar approach.
Multiplication and division with plain int or unsigned can achieve the efficiency goal --- if it were not for handling rounding and overflow.
In my current branch, I'm actually trying to get even closer to integer-level efficiency. No longer does 32-bit multiplication result in 64-bit results on systems with 32-bit integer. This means that overflow on 32-bit arithmetic operations is even more common. The solution is explicit casting to 64-bit or use of an integer type which auto-widens: http://johnmcfarlane.github.io/fixed_point/#elastic
This is the toughest design issue I face - especially when combined with division.
Thank you and best regards, Chris And thank you. Keep up the good work! John Thanks again and best regards, Chris
Cheers,
John
On 10/14/2016 12:11 PM, John McFarlane wrote:
I discuss P0106R0 (a revision to N3352) in my paper, the latest draft of which is always available here: https://github.com/ johnmcfarlane/fixed_point/blob/master/doc/p0037.md#p0106
I once wrote and shipped a fixed-point software renderer. Granted that was about 9 years ago. There has been a great deal of discussion of fixed-point libraries over the years on the the boost devel list going back to at least 2007. I hope you've taken the time to explore the archives. For example: http://lists.boost.org/Archives/boost/2013/02/200690.php I read through P0106R0 but I came away feeling I knew almost nothing about what the actual implementation would be. I looked around the code and documentation on github as well. After about 30 minutes it started to make some sense and looks pretty nice. I couldn't figure out answers to some basic questions. How does division work? Does it promote 32 -> 64 before division? Does mixed fixed arithmetic work? i.e. s16.16 * s24.8? Is the result of an operation necessarily the same as the operands? - For example its sometimes useful to do s16.16 * s16.16 -> s24.8. How does one convert between different fixed-point representations? How does one convert raw fixed-point integers <-> fixed-point class? Note: the doxygen documentation for convert to float operator does not say it's explicit, that worried me greatly but I saw it is marked as explicit in the code. I can't find the numeric_limits specialization. I can't find the cmath functions. At least a subset was crucial for my past work: * abs * fmod * floor * ceil * sqrt * cos * sin * atan2 I never did get a generic trig functions implementation. IIRC our implementation used lookup tables and CORDIC algorithm for just a handful of formats.
Hello Boost developers,
A partial implementation of fixed-point in a Boost-like>> style based on proposal N3352 is now available. There has been a great deal of discussion of fixed-point libraries over the years on the the boost devel list going back to at least 2007. I hope you've taken the time to explore the archives. For example: http://lists.boost.org/Archives/boost/2013/02/200690.php
Thank you for pointing that out. Yes, I remember that threadand we were involved in it. It partly helped motivate theGSoC15 project.
Best regards, Chris.
On Saturday, October 15, 2016 6:13 PM, Michael Marcin
I discuss P0106R0 (a revision to N3352) in my paper, the latest draft of which is always available here: https://github.com/ johnmcfarlane/fixed_point/blob/master/doc/p0037.md#p0106
I once wrote and shipped a fixed-point software renderer. Granted that was about 9 years ago. There has been a great deal of discussion of fixed-point libraries over the years on the the boost devel list going back to at least 2007. I hope you've taken the time to explore the archives. For example: http://lists.boost.org/Archives/boost/2013/02/200690.php I read through P0106R0 but I came away feeling I knew almost nothing about what the actual implementation would be. I looked around the code and documentation on github as well. After about 30 minutes it started to make some sense and looks pretty nice. I couldn't figure out answers to some basic questions. How does division work? Does it promote 32 -> 64 before division? Does mixed fixed arithmetic work? i.e. s16.16 * s24.8? Is the result of an operation necessarily the same as the operands? - For example its sometimes useful to do s16.16 * s16.16 -> s24.8. How does one convert between different fixed-point representations? How does one convert raw fixed-point integers <-> fixed-point class? Note: the doxygen documentation for convert to float operator does not say it's explicit, that worried me greatly but I saw it is marked as explicit in the code. I can't find the numeric_limits specialization. I can't find the cmath functions. At least a subset was crucial for my past work: * abs * fmod * floor * ceil * sqrt * cos * sin * atan2 I never did get a generic trig functions implementation. IIRC our implementation used lookup tables and CORDIC algorithm for just a handful of formats. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-----Original Message----- From: Boost [mailto:boost-bounces@lists.boost.org] On Behalf Of Michael Marcin Sent: 15 October 2016 17:13 To: boost@lists.boost.org Subject: Re: [boost] [fixed_point] First presentation from GSoC 2015 and more
On 10/14/2016 12:11 PM, John McFarlane wrote:
I discuss P0106R0 (a revision to N3352) in my paper, the latest draft of which is always available here: https://github.com/ johnmcfarlane/fixed_point/blob/master/doc/p0037.md#p0106
<snip>
I can't find the cmath functions. At least a subset was crucial for my past work: * abs * fmod * floor * ceil * sqrt * cos * sin * atan2
Then you will note with approval that Christopher Kormanyos has implemented all the application C Math functions, which also allows the much of the Boost.Math library to be used without further ado. This is a tremendous advantage if you start with existing floating-point code and want to use it with fixed-point. A few examples are shown in the /examples folder, most spectacularly (though not specially usefully?) the Bernoulli numbers, calculated at an extravagant precision. (Using Boost.Math may mean that floating-point is used en route, but you can't make omelette without breaking eggs ? ;-) Similarly, input/output uses floating point, but only if used, controlled by a macro, so suitable for bare-metal applications.). A downside of using C math functions, internally and externally, is that these cannot portably be constexpr - yet. This means that, despite marking constexpr, fixed-point cannot yet be made constexpr. This seems an important attribute but must await changes to Standard and implementation of C++. Paul --- Paul A. Bristow Prizet Farmhouse Kendal UK LA8 8AB +44 (0) 1539 561830
On 10/17/2016 4:10 AM, Paul A. Bristow wrote:
Then you will note with approval that Christopher Kormanyos has implemented all the application C Math functions, which also allows the much of the Boost.Math library to be used without further ado. This is a tremendous advantage if you start with existing floating-point code and want to use it with fixed-point.
Which is awesome! I hope they also make it into the SG14 proposal.
I can only speak for P0037 although P0106 has also been reviewed by SG14.
Adding <cmath>-like functions was discussed at our meeting in March. It's
also briefly discussed in P0037: https://github.com/johnmcfarla
ne/fixed_point/blob/master/doc/p0037r3.md#library-support
The proposal is quite tightly scoped. However, that doesn't stop me
prototyping surrounding features in the reference implementation [
https://github.com/johnmcfarlane/fixed_point/] - especially if I think they
might warrant standardization at a later date. These functions are quite a
lot to bite off which is why I only supplied a few wrappers so far. I'm
sure it's not easy to get better performance that FPU-supported
floating-point variants. However, I am interested in seeing if I can make
use of the algorithms in Boost.fixed_point.
On Mon, Oct 17, 2016 at 9:31 PM, Michael Marcin
On 10/17/2016 4:10 AM, Paul A. Bristow wrote:
Then you will note with approval that Christopher Kormanyos has implemented all the application C Math functions, which also allows the much of the Boost.Math library to be used without further ado. This is a tremendous advantage if you start with existing floating-point code and want to use it with fixed-point.
Which is awesome!
I hope they also make it into the SG14 proposal.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman /listinfo.cgi/boost
On 10/18/2016 6:51 PM, John McFarlane wrote:
I can only speak for P0037 although P0106 has also been reviewed by SG14. Adding <cmath>-like functions was discussed at our meeting in March. It's also briefly discussed in P0037: https://github.com/johnmcfarla ne/fixed_point/blob/master/doc/p0037r3.md#library-support
The proposal is quite tightly scoped. However, that doesn't stop me prototyping surrounding features in the reference implementation [ https://github.com/johnmcfarlane/fixed_point/] - especially if I think they might warrant standardization at a later date. These functions are quite a lot to bite off which is why I only supplied a few wrappers so far. I'm sure it's not easy to get better performance that FPU-supported floating-point variants. However, I am interested in seeing if I can make use of the algorithms in Boost.fixed_point.
I'm not sure what the target is. My game dev fixed-point usage falls into 4 broad categories: 1. deterministic reproducible game state representation/logic (eg stable replay format across multiple platforms/compilers/releases) 2. network/serialization formats 3. converting assets for use with GLES 1.x GPUs 4. embedded/mobile systems with no FPU, no GPU and sometimes no or limited software floating-point emulation Performance was not a major issue for fixed-point outside of the last case in which the std floating-point cmath routines were horribly slow and/or broken.
I can only speak for P0037 although P0106 has also been reviewed by SG14. Adding <cmath>-like functions was discussed at our meeting in March. It's also briefly discussed in P0037: https://github.com/johnmcfarla ne/fixed_point/blob/master/doc/p0037r3.md#library-support
The proposal is quite tightly scoped. However, that doesn't stop me prototyping surrounding features in the reference implementation [ https://github.com/johnmcfarlane/fixed_point/] - especially if I think they might warrant standardization at a later date. These functions are quite a lot to bite off which is why I only supplied a few wrappers so far. I'm sure it's not easy to get better performance that FPU-supported floating-point variants. However, I am interested in seeing if I can make use of the algorithms in Boost.fixed_point.
I'm not sure what the target is. My game dev fixed-point usage falls into 4 broad categories:
1. deterministic reproducible game state representation/logic (eg stable replay format across multiple platforms/compilers/releases) 2. network/serialization formats 3. converting assets for use with GLES 1.x GPUs 4. embedded/mobile systems with no FPU, no GPU and sometimes no or limited software floating-point emulation
Performance was not a major issue for fixed-point outside of the last case in which the std floating-point cmath routines were horribly slow and/or broken. Much of my work is in the area of 4. This is also a good test of the limits of the C++ language via <cmath>-likefunctions with very few digits and very many digits.It's a true exercise in generic mathematical programming. In the area of 4., fixed_point tends to be slower thanhardware-supported FPU-based calculations, but reallycan outperform software-emulated floating-point libs.So we're really targeting other areas mentioned aboveand also cost-sensitive embedded systems with no FPU.Our docs describe these issues.
It is good that we are converging on <cmath>-like functions.
The only significant potential conflict that I can detectbetween SG14 fixed_point design and Bioost GSoCfixed_point design is the issue of bounded/unboundedmath that Vicente raised earlier in the thread.
As far as I can tell, SG14 design automatically widensor shrinkens the width of the fixed_point type formul/div via standard operator* and operator/.SG14 design offers bounded math through C-like namedfunctions. Whereas the Boost GSoC code uses exclusivelybounded math via operator+, operator-, operator*, operator/with no widening or shrinkening.
This difference in design strategy is becoming troubling to mebecause it would not be a good idea to have divergingdesign strategies in Boost and SG14. At the same time,I am somewhat hesitant to try and change our design becauseit is based on a hybrid of both the preliminary specificationsand popular use cases.
Best regards, Chris
On Wednesday, October 19, 2016 4:42 AM, Michael Marcin
I can only speak for P0037 although P0106 has also been reviewed by SG14. Adding <cmath>-like functions was discussed at our meeting in March. It's also briefly discussed in P0037: https://github.com/johnmcfarla ne/fixed_point/blob/master/doc/p0037r3.md#library-support
The proposal is quite tightly scoped. However, that doesn't stop me prototyping surrounding features in the reference implementation [ https://github.com/johnmcfarlane/fixed_point/] - especially if I think they might warrant standardization at a later date. These functions are quite a lot to bite off which is why I only supplied a few wrappers so far. I'm sure it's not easy to get better performance that FPU-supported floating-point variants. However, I am interested in seeing if I can make use of the algorithms in Boost.fixed_point.
I'm not sure what the target is. My game dev fixed-point usage falls into 4 broad categories: 1. deterministic reproducible game state representation/logic (eg stable replay format across multiple platforms/compilers/releases) 2. network/serialization formats 3. converting assets for use with GLES 1.x GPUs 4. embedded/mobile systems with no FPU, no GPU and sometimes no or limited software floating-point emulation Performance was not a major issue for fixed-point outside of the last case in which the std floating-point cmath routines were horribly slow and/or broken. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (4)
-
Christopher Kormanyos -
John McFarlane -
Michael Marcin -
Paul A. Bristow