[boostcon][proto] Suggestion for LIAW session: fixed-point numbers
Hi, Are there any proto-based ideas for the library-in-a-week sessions? If not, would building a fixed-point data type be of interest? The domain is narrow enough that something useful can be accomplished in 4 sessions, but of large enough scope to present opportunities for exploring proto in depth. A fairly simple design follows representing a number: fixed_number<int width, int ulp, // 2^{ulp} is the smallest increment possible bool signed, template assigner<first, last, signed> > 'assigner' handles rounding/truncation/wrapping/etc when assigning another number (floating-point or fixed-point) to the current one. Internally, each fixed-point number would be represented by a boost::uint64_t or a boost::int64_t (limiting the maximum precision allowed). As an example, fixed_number<5, -3, false> would represent a data type that would go from 0 to 3.875 in steps of 0.125. Proto would be used for creating all arithmetic operations since the return type of a+b could be different from the type of either a or b. A bonus would involve getting the fixed-point data type to play well with std::complex (and, yes, I am aware that std::complex is not designed to work with anything other than double and float, and will require specialization in the std namespace). If there is sufficient interest, I could even provide a starting point with +,-,* implemented; / would take more time. The design above is intended as a starting point for discussion and I am most definitely not wedded to it. I am a tyro when it comes to proto, and hence would need someone with more proto expertise to guide the discussion. Regards, Ravi
On 13/03/11 22:24, Ravi wrote:
Are there any proto-based ideas for the library-in-a-week sessions? If not, would building a fixed-point data type be of interest? The domain is narrow enough that something useful can be accomplished in 4 sessions, but of large enough scope to present opportunities for exploring proto in depth. A fairly simple design follows representing a number:
I like the idea :) What was the plan for LIAW this year ? IIRC some stuff were pointed otu last eyar as potential contenders.
Proto would be used for creating all arithmetic operations since the return type of a+b could be different from the type of either a or b. A bonus would involve getting the fixed-point data type to play well with std::complex (and, yes, I am aware that std::complex is not designed to work with anything other than double and float, and will require specialization in the std namespace).
Well, isnt having a boost::complex data type be of interest too ?
If there is sufficient interest, I could even provide a starting point with +,-,* implemented; / would take more time. The design above is intended as a starting point for discussion and I am most definitely not wedded to it. I am a tyro when it comes to proto, and hence would need someone with more proto expertise to guide the discussion.
I can help on this point
On Sunday 13 March 2011 14:27:38 Joel Falcou wrote:
What was the plan for LIAW this year ? IIRC some stuff were pointed otu last eyar as potential contenders.
Is the list of potential contenders available somewhere?
Proto would be used for creating all arithmetic operations since the return type of a+b could be different from the type of either a or b. A bonus would involve getting the fixed-point data type to play well with std::complex (and, yes, I am aware that std::complex is not designed to work with anything other than double and float, and will require specialization in the std namespace).
Well, isnt having a boost::complex data type be of interest too ?
It would be of interest to me but I am afraid that too much bike-shedding might ensue. Complex numbers are extremely straightforward with multiple sets of equivalent perfectly internally consistent minimal interfaces; in such cases, personal preferences decide the interface, more or less. See N1589 for examples.
If there is sufficient interest, I could even provide a starting point with +,-,* implemented; / would take more time. The design above is intended as a starting point for discussion and I am most definitely not wedded to it. I am a tyro when it comes to proto, and hence would need someone with more proto expertise to guide the discussion.
I can help on this point
Are you volunteering/proposing to run the LIAW session? What is the standard procedure for running the LIAW session? Regards, Ravi
On 3/15/2011 12:31 PM, Ravi wrote:
On Sunday 13 March 2011 14:27:38 Joel Falcou wrote:
What was the plan for LIAW this year ? IIRC some stuff were pointed otu last eyar as potential contenders.
Is the list of potential contenders available somewhere?
I don't know. Hartmut? Jeff?
Proto would be used for creating all arithmetic operations since the return type of a+b could be different from the type of either a or b. A bonus would involve getting the fixed-point data type to play well with std::complex (and, yes, I am aware that std::complex is not designed to work with anything other than double and float, and will require specialization in the std namespace).
Well, isnt having a boost::complex data type be of interest too ?
It would be of interest to me but I am afraid that too much bike-shedding might ensue. Complex numbers are extremely straightforward with multiple sets of equivalent perfectly internally consistent minimal interfaces; in such cases, personal preferences decide the interface, more or less. See N1589 for examples.
If there is sufficient interest, I could even provide a starting point with +,-,* implemented; / would take more time. The design above is intended as a starting point for discussion and I am most definitely not wedded to it. I am a tyro when it comes to proto, and hence would need someone with more proto expertise to guide the discussion.
I can help on this point
Are you volunteering/proposing to run the LIAW session? What is the standard procedure for running the LIAW session?
I know that in past years, Jeff has run the LIAW session. I expect this year would be no exception, but it would certainly be good to have a proto expert on hand. Joel would be perfect for that. I just want to say I think a proto-based fixed-point number library is a really fun idea for a LIAW project. Meaty and doable. I'm just sorry I won't be attending this year to help! -- Eric Niebler BoostPro Computing http://www.boostpro.com
On 15/03/11 08:45, Eric Niebler wrote:
On 3/15/2011 12:31 PM, Ravi wrote:
On Sunday 13 March 2011 14:27:38 Joel Falcou wrote:
What was the plan for LIAW this year ? IIRC some stuff were pointed otu last eyar as potential contenders.
Is the list of potential contenders available somewhere?
I don't know. Hartmut? Jeff?
Usually we have some discussion the first day to choose what we want to do :p
I know that in past years, Jeff has run the LIAW session. I expect this year would be no exception, but it would certainly be good to have a proto expert on hand. Joel would be perfect for that.
wow thanks ^^
I just want to say I think a proto-based fixed-point number library is a really fun idea for a LIAW project. Meaty and doable. I'm just sorry I won't be attending this year to help!
Additional fact is that my proto tutorial is the day before the start of LIAW so it may make people more familliar with proto itself.
I wrote a similar class, years ago. The signature was simply: template< SignProperty is_signed, int int_bits, //!< Number of integer bits. int frac_bits //!< Number of fractional bits. > class CFixed; The way I structured it was to discard information only on assignment (unless the maximum internal storage had overflowed, of course). While I agree that it's tempting to just use int64 for storage, the size and speed implications of creating large arrays of them provides a strong argument against this approach. Since the most common use of fixed-point arithmetic is for speed, the priority is speed over safety. For example, never assume that overflow checking is performed. Furthermore, operatorns supported by the class are primarily designed to avoid unnecessary arithmetic, while minimizing surprises. The general policies were: * No virtual functions! Fixed-point types must be as fast and small as hand-coded fixed-point arthmetic, using built-in types. * Converting constructor is implicit, since conversions (such as reductions in precision) are so common, in fixed-point arithmetic. * add/subtract return the greater of the int_bits and frac_bits (independently) of the operands. * add/subtract returns signedness of the type with the greater range (choosing unsigned, in the event of a tie). * multiply returns a type in which the int and frac bits are the sum of the corresponding values of the operands. The result is signed, unless both operands are unsigned. * The return type of divide is equivalent to multiplying the numerator by the inverse of the denominator. * inverse returns a type with one fewer frac bits than the operand had int bits and one more int bits than the operand had frac bits. This sacrifice of precision is necessary to avoid overflow. I like the idea of abstracting the assigner, but I guess I don't really see what you'd want to vary besides perhaps rounding behavior. One area in which I spent a fair amount of time was fast conversion to/from IEEE floating-point. In trying to use the rounding-by-adding trick, I got slightly burned by differences in FPU configuration of Linux vs. Windows. With x87 arithmetic, the default FPU configuration keeps different amounts of intermediate precision. Optimized formatted string conversion was another time sink. Matt ________________________________ From: boost-bounces@lists.boost.org on behalf of Ravi Sent: Sun 3/13/2011 5:24 PM To: boost@lists.boost.org Subject: [boost] [boostcon][proto] Suggestion for LIAW session: fixed-pointnumbers Hi, Are there any proto-based ideas for the library-in-a-week sessions? If not, would building a fixed-point data type be of interest? The domain is narrow enough that something useful can be accomplished in 4 sessions, but of large enough scope to present opportunities for exploring proto in depth. A fairly simple design follows representing a number: fixed_number<int width, int ulp, // 2^{ulp} is the smallest increment possible bool signed, template assigner<first, last, signed> > 'assigner' handles rounding/truncation/wrapping/etc when assigning another number (floating-point or fixed-point) to the current one. Internally, each fixed-point number would be represented by a boost::uint64_t or a boost::int64_t (limiting the maximum precision allowed). As an example, fixed_number<5, -3, false> would represent a data type that would go from 0 to 3.875 in steps of 0.125. Proto would be used for creating all arithmetic operations since the return type of a+b could be different from the type of either a or b. A bonus would involve getting the fixed-point data type to play well with std::complex (and, yes, I am aware that std::complex is not designed to work with anything other than double and float, and will require specialization in the std namespace). If there is sufficient interest, I could even provide a starting point with +,-,* implemented; / would take more time. The design above is intended as a starting point for discussion and I am most definitely not wedded to it. I am a tyro when it comes to proto, and hence would need someone with more proto expertise to guide the discussion. Regards, Ravi _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Tuesday 15 March 2011 18:45:49 Gruenke, Matt wrote:
template< SignProperty is_signed, int int_bits, //!< Number of integer bits. int frac_bits //!< Number of fractional bits. > class CFixed;
I, too, used a class like this in the past, but experience makes me wish for more flexibility. When modeling hardware operations implemented on signal/image processing algorithms, the following schemes have all seen wide use: 1. signed, int_bits, frac_bits <- your design 2. signed, msb_power_of_2, lsb_power_of_2 3. signed, width, int_bits 4. signed, width, frac_bits Of these, the only one I found to be completely intuitive was the second one. All of the others required non-obvious rules to represent the cases when the MSB is to the right of the binary point or the LSB is much to the left of the binary point. Subsequently, my colleagues and I found that most of the reasoning in choosing appropriate bit-widths is in figuring out the ULP. Our experience led me to propose my design.
The way I structured it was to discard information only on assignment (unless the maximum internal storage had overflowed, of course). While I agree that it's tempting to just use int64 for storage, the size and speed implications of creating large arrays of them provides a strong argument against this approach.
Good idea, but this is a refinement that can wait until later.
Since the most common use of fixed-point arithmetic is for speed, the priority is speed over safety.
In order of decreasing priority: correctness, speed, safety. Safety can be enforced in debug builds.
For example, never assume that overflow checking is performed. Furthermore, operatorns supported by the class are primarily designed to avoid unnecessary arithmetic, while minimizing surprises.
Agreed.
The general policies were:
* No virtual functions! Fixed-point types must be as fast and small as hand-coded fixed-point arthmetic, using built-in types.
* Converting constructor is implicit, since conversions (such as reductions in precision) are so common, in fixed-point arithmetic.
Agreed, but this is not an issue with the 'assigner' template argument.
* add/subtract return the greater of the int_bits and frac_bits (independently) of the operands.
* add/subtract returns signedness of the type with the greater range (choosing unsigned, in the event of a tie).
Disagreed. Follow the integers - operating on a signed always returns signed.
* multiply returns a type in which the int and frac bits are the sum of the corresponding values of the operands. The result is signed, unless both operands are unsigned.
* The return type of divide is equivalent to multiplying the numerator by the inverse of the denominator.
* inverse returns a type with one fewer frac bits than the operand had int bits and one more int bits than the operand had frac bits. This sacrifice of precision is necessary to avoid overflow.
This one is tricky; the behavior you propose is completely unacceptable for signal processing.
I like the idea of abstracting the assigner, but I guess I don't really see what you'd want to vary besides perhaps rounding behavior.
Examples (not exhaustive): Truncation vs rounding (direction - 4 possible ways) Wrapping vs saturation vs symmetric saturation Allowing only values of 2^{k} (used a lot in ASIC loop filters) Regards, Ravi
________________________________ From: Ravi [mailto:lists_ravi@lavabit.com] Sent: Tue 3/15/2011 11:20 PM To: boost@lists.boost.org Cc: Gruenke, Matt Subject: Re: [boost] [boostcon][proto] Suggestion for LIAW session: fixed-pointnumbers
All of the others required non-obvious rules to represent the cases when the MSB is to the right of the binary point or the LSB is much to the left of the binary point.
I'm not sure we're talking about the same thing, here. The template parameters of the results returned by my operators were determined by those of the operands. For instance, 8.16 + 8.8 would return a 9.16. If the result is then stored into a 16.8, then a right-shift of 8 bits is performed as part of the assignment. In the case of 0.16 * 8.8, the result is 8.24. So, the only thing you have to think about is whether you need to force a conversion in the middle of an complex expression to avoid running out of range. But that can easily be managed by breaking up complex expressions into smaller, simpler ones.
* add/subtract return the greater of the int_bits and frac_bits (independently) of the operands.
* add/subtract returns signedness of the type with the greater range (choosing unsigned, in the event of a tie).
Disagreed. Follow the integers - operating on a signed always returns signed.
I don't feel strongly about this point. I thought it would be sensible to try to follow what C does.
* multiply returns a type in which the int and frac bits are the sum of the corresponding values of the operands. The result is signed, unless both operands are unsigned.
* The return type of divide is equivalent to multiplying the numerator by the inverse of the denominator.
* inverse returns a type with one fewer frac bits than the operand had int bits and one more int bits than the operand had frac bits. This sacrifice of precision is necessary to avoid overflow.
This one is tricky; the behavior you propose is completely unacceptable for signal processing.
Which one? Inverse? If you need more headroom, you can always add it before the operation (hint: it's free). I think I included inversion more for completeness. Is it something you use often? Since integer division is usually so slow, I expect that most people will just opt for floating point when they get into that territory. Regards, Matthew A. Gruenke
On 16/03/11 05:10, Gruenke, Matt wrote:
I'm not sure we're talking about the same thing, here. The template parameters of the results returned by my operators were determined by those of the operands. For instance, 8.16 + 8.8 would return a 9.16. If the result is then stored into a 16.8, then a right-shift of 8 bits is performed as part of the assignment. In the case of 0.16 * 8.8, the result is 8.24.
So, the only thing you have to think about is whether you need to force a conversion in the middle of an complex expression to avoid running out of range. But that can easily be managed by breaking up complex expressions into smaller, simpler ones.
I think the idea was to use proto to actually look at the whoel expression as a whole and figure out the needed bit storage directly then work within it
-----Original Message----- From: boost-bounces@lists.boost.org on behalf of Joel Falcou Sent: Wed 3/16/2011 2:17 AM To: boost@lists.boost.org Subject: Re: [boost] [boostcon][proto] Suggestion for LIAWsession: fixed-pointnumbers On 16/03/11 05:10, Gruenke, Matt wrote:
I'm not sure we're talking about the same thing, here. The template parameters of the results returned by my operators were determined by those of the operands. For instance, 8.16 + 8.8 would return a 9.16. If the result is then stored into a 16.8, then a right-shift of 8 bits is performed as part of the assignment. In the case of 0.16 * 8.8, the result is 8.24.
So, the only thing you have to think about is whether you need to force a conversion in the middle of an complex expression to avoid running out of range. But that can easily be managed by breaking up complex expressions into smaller, simpler ones.
I think the idea was to use proto to actually look at the whoel expression as a whole and figure out the needed bit storage directly then work within it
In my implementation, the size of the storage used was determined by the template parameters, such that an array of 9.7 fixed-point numbers would only take 2 bytes per element (we actually had such arrays and could not afford for them to be any larger than necessary). Since each operator was a template where the result was defined in terms of the operands, different unnamed temporaries, within an expression, could use different amounts of storage. The largest supported storage size was 64-bits, since we were interested in efficiency and required nothing larger. I have no experience with Boost.Proto. If the primary purpose of the proposed exercise is as a case study to demonstrate use of Proto, then perhaps my comments are of little or no relevance. However, if the primary goal is to produce the most useful and efficient fixed-point library possible, then I offer my insights and experience in hopes that a better product might result. Regards, Matthew A. Gruenke
On Wednesday 16 March 2011 00:12:49 Gruenke, Matt wrote:
I'm not sure we're talking about the same thing, here. The template parameters of the results returned by my operators were determined by those of the operands. For instance, 8.16 + 8.8 would return a 9.16. If the result is then stored into a 16.8, then a right-shift of 8 bits is performed as part of the assignment. In the case of 0.16 * 8.8, the result is 8.24.
So, the only thing you have to think about is whether you need to force a conversion in the middle of an complex expression to avoid running out of range. But that can easily be managed by breaking up complex expressions into smaller, simpler ones.
I think the idea was to use proto to actually look at the whoel expression as a whole and figure out the needed bit storage directly then work within it
In my implementation, the size of the storage used was determined by the template parameters, such that an array of 9.7 fixed-point numbers would only take 2 bytes per element (we actually had such arrays and could not afford for them to be any larger than necessary). Since each operator was a template where the result was defined in terms of the operands, different unnamed temporaries, within an expression, could use different amounts of storage. The largest supported storage size was 64-bits, since we were interested in efficiency and required nothing larger.
This is what I have in mind as well. However, Joel's suggestion is also interesting, though I would personally consider it an optimization that can be performed once the interface is complete.
I have no experience with Boost.Proto. If the primary purpose of the proposed exercise is as a case study to demonstrate use of Proto, then perhaps my comments are of little or no relevance. However, if the primary goal is to produce the most useful and efficient fixed-point library possible, then I offer my insights and experience in hopes that a better product might result.
Your comments are very much appreciated. Your experience matches mine quite a lot; our (minor) disagreements stem, I think, mostly from my considering a larger set of use cases than just speed. Regards, Ravi
-----Original Message----- From: Ravi [mailto:lists_ravi@lavabit.com] Sent: Wed 3/16/2011 12:09 PM To: boost@lists.boost.org Cc: Gruenke, Matt Subject: Re: [boost] [boostcon][proto] Suggestion for LIAWsession: fixed-pointnumbers On Wednesday 16 March 2011 00:12:49 Gruenke, Matt wrote:
I think the idea was to use proto to actually look at the whoel expression as a whole and figure out the needed bit storage directly then work within it
In my implementation, the size of the storage used was determined by the template parameters, such that an array of 9.7 fixed-point numbers would only take 2 bytes per element (we actually had such arrays and could not afford for them to be any larger than necessary). Since each operator was a template where the result was defined in terms of the operands, different unnamed temporaries, within an expression, could use different amounts of storage. The largest supported storage size was 64-bits, since we were interested in efficiency and required nothing larger.
This is what I have in mind as well. However, Joel's suggestion is also interesting, though I would personally consider it an optimization that can be performed once the interface is complete.
I'm not sure I follow. If he's saying that a single storage size can be determined for evaluating all parts of a compound expression, then I'd expect it to be only the same or larger than what my implementation uses. The downside of using types that are larger than necessary is that on some architectures divide and sometimes multiply are more expensive for larger operands. Matt
On Tuesday 15 March 2011 21:10:52 Gruenke, Matt wrote:
All of the others required non-obvious rules to represent the cases when the MSB is to the right of the binary point or the LSB is much to the left of the binary point.
I'm not sure we're talking about the same thing, here. The template parameters of the results returned by my operators were determined by those of the operands.
In the system you proposed, what are the template parameters for the fixed- point number with the following range? { 0, 1, ..., 15 } x 2^{-11} Or, the fixed-point number holding values in the following range? { 0, 1, ..., 15 } x 2^{11}
* inverse returns a type with one fewer frac bits than the
operand had int bits and one more int bits than the operand had frac bits. This sacrifice of precision is necessary to avoid overflow.
This one is tricky; the behavior you propose is completely unacceptable for signal processing.
Which one? Inverse? If you need more headroom, you can always add it before the operation (hint: it's free). I think I included inversion more for completeness. Is it something you use often? Since integer division is usually so slow, I expect that most people will just opt for floating point when they get into that territory.
Fixed-point numbers are used in plenty of places where speed is not an issue -- modeling signal processing circuits in software is one example, and firmware in embedded control systems with no floating point unit is another. In such cases, falling back to floating-point is not an option. Implementing dividers in hardware is a tricky task, especially since most dividers are serial, but with some parallelization or statistical rounding. Getting division and CORDIC working correctly are pretty much the only non-trivial challenges in low-to-medium speed fixed-point circuit design. At high speeds, carry propagation latency can be tricky as well. Regards, Ravi
-----Original Message----- From: Ravi [mailto:lists_ravi@lavabit.com] Sent: Wed 3/16/2011 2:21 AM To: boost@lists.boost.org Cc: Gruenke, Matt Subject: Re: [boost] [boostcon][proto] Suggestion for LIAW session: fixed-pointnumbers On Tuesday 15 March 2011 21:10:52 Gruenke, Matt wrote:
All of the others required non-obvious rules to represent the cases when the MSB is to the right of the binary point or the LSB is much to the left of the binary point.
I'm not sure we're talking about the same thing, here. The template parameters of the results returned by my operators were determined by those of the operands.
In the system you proposed, what are the template parameters for the fixed- point number with the following range? { 0, 1, ..., 15 } x 2^{-11}
11 fractional bits.
Or, the fixed-point number holding values in the following range? { 0, 1, ..., 15 } x 2^{11}
15 integer bits.
Fixed-point numbers are used in plenty of places where speed is not an issue
I've used them to represent timestamps, for instance. The combination of range, precision, ease of computation, and associative addition were all desirable properties.
firmware in embedded control systems with no floating point unit is another. In such cases, falling back to floating-point is not an option.
Software floating-point libraries are sometimes an option. Especially when IEEE-754 compliance isn't required. Anyway, getting back to inversion, I just figured that overflowing is a nasty scenario to allow. I guess the better thing to do is keep all the precision and just expand the integral portion of the result by 1 bit. If the total number of bits is too large, then perhaps the user can tweak the operand, use an alternate function, or go the manual route. Matt
On Wednesday 16 March 2011 19:24:31 Gruenke, Matt wrote:
In the system you proposed, what are the template parameters for the fixed- point number with the following range?
{ 0, 1, ..., 15 } x 2^{-11}
11 fractional bits.
Or, the fixed-point number holding values in the following range?
{ 0, 1, ..., 15 } x 2^{11}
15 integer bits.
Suboptimal at best, and usually unacceptable because it leads to overflow of the underlying type (int64, for example) much sooner than necessary in complex expressions. The way it is usually avoided is to specify (in your notation) the examples above as -7.11 and 15.-11, which, while consistent, is completely unintuitive and unobvious. Regards, Ravi
Eh? So what you want is essentially (denormal) floating-point, except that the exponent is specified at compile time? That's interesting. I haven't had a need for higher range than precision, so it was never a problem for me to include bits all the way down to 2^0. Matt ________________________________ From: boost-bounces@lists.boost.org on behalf of Ravi Sent: Thu 3/17/2011 1:28 AM To: boost@lists.boost.org Subject: Re: [boost] [boostcon][proto] Suggestion for LIAW session:fixed-pointnumbers On Wednesday 16 March 2011 19:24:31 Gruenke, Matt wrote:
In the system you proposed, what are the template parameters for the fixed- point number with the following range?
{ 0, 1, ..., 15 } x 2^{-11}
11 fractional bits.
Or, the fixed-point number holding values in the following range?
{ 0, 1, ..., 15 } x 2^{11}
15 integer bits.
Suboptimal at best, and usually unacceptable because it leads to overflow of the underlying type (int64, for example) much sooner than necessary in complex expressions. The way it is usually avoided is to specify (in your notation) the examples above as -7.11 and 15.-11, which, while consistent, is completely unintuitive and unobvious. Regards, Ravi _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Message du 16/03/11 04:18 De : "Ravi"
A : boost@lists.boost.org Copie à : Objet : Re: [boost] [boostcon][proto] Suggestion for LIAW session: fixed-pointnumbers
On Tuesday 15 March 2011 18:45:49 Gruenke, Matt wrote:
template< SignProperty is_signed, int int_bits, //!< Number of integer bits. int frac_bits //!< Number of fractional bits.
class CFixed;
I, too, used a class like this in the past, but experience makes me wish for more flexibility. When modeling hardware operations implemented on signal/image processing algorithms, the following schemes have all seen wide use: 1. signed, int_bits, frac_bits <- your design 2. signed, msb_power_of_2, lsb_power_of_2 3. signed, width, int_bits 4. signed, width, frac_bits
Of these, the only one I found to be completely intuitive was the second one. All of the others required non-obvious rules to represent the cases when the MSB is to the right of the binary point or the LSB is much to the left of the binary point. Subsequently, my colleagues and I found that most of the reasoning in choosing appropriate bit-widths is in figuring out the ULP. Our experience led me to propose my design.
I think that this is the format documented on wikipedia http://en.wikipedia.org/wiki/Fixed-point_arithmetic
The way I structured it was to discard information only on assignment (unless the maximum internal storage had overflowed, of course). While I agree that it's tempting to just use int64 for storage, the size and speed implications of creating large arrays of them provides a strong argument against this approach.
Good idea, but this is a refinement that can wait until later.
I don't know if doing as some integer traits could make happy every body. * fast will choose the faster representation * least will choose the minimal representation
Since the most common use of fixed-point arithmetic is for speed, the priority is speed over safety.
In order of decreasing priority: correctness, speed, safety. Safety can be enforced in debug builds.
I agree.
* Converting constructor is implicit, since conversions (such as reductions in precision) are so common, in fixed-point arithmetic.
Agreed, but this is not an issue with the 'assigner' template argument.
I expect however the class will not provide implicit conversions to built-in types. Good luck for those that will participate in the LIAW, Vicente
On Thu 4/21/2011 6:02 PM, Vicente BOTET wrote:
Message du 16/03/11 04:18 De : "Ravi"
A : boost@lists.boost.org Copie à : Objet : Re: [boost] [boostcon][proto] Suggestion for LIAW session: fixed-pointnumbers
On Tuesday 15 March 2011 18:45:49 Gruenke, Matt wrote:
I think that this is the format documented on wikipedia http://en.wikipedia.org/wiki/Fixed-point_arithmetic
The point of confusion was that his implementation was general enough to handle numbers where the value of the lsb > 1. I agree that this generalization has sufficient value to warrant use of a different template parameter scheme. I think something like <sign, log2(msb), log2(lsb)> is pretty sensible and implementation-friendly.
The way I structured it was to discard information only on assignment (unless the maximum internal storage had overflowed, of course). While I agree that it's tempting to just use int64 for storage, the size and speed implications of creating large arrays of them provides a strong argument against this approach.
Good idea, but this is a refinement that can wait until later.
I don't know if doing as some integer traits could make happy every body. * fast will choose the faster representation * least will choose the minimal representation
In most cases, smaller WILL be the faster implementation. Where this is not the case, the compiler can hopefully help out and provide most of the benefits of hand-tuning for a particular architecture. I think the difference between Ravi's proposal and mine is really down to something I don't consider an implementation detail. When I implemented fixed-point templates, I parameterized the return type of operators, in order to avoid discarding any information. The only place where I discarded information was on assignment/conversion. It's not just about loss of information, but actually the semantics of the operators. Matt
Message du 22/04/11 02:55 De : "Gruenke, Matt" A : boost@lists.boost.org Copie à : Objet : Re: [boost] [boostcon][proto] Suggestion for LIAWsession: fixed-pointnumbers
On Thu 4/21/2011 6:02 PM, Vicente BOTET wrote:
Message du 16/03/11 04:18 De : "Ravi"
A : boost@lists.boost.org Copie à : Objet : Re: [boost] [boostcon][proto] Suggestion for LIAW session: fixed-pointnumbers
On Tuesday 15 March 2011 18:45:49 Gruenke, Matt wrote:
I think that this is the format documented on wikipedia http://en.wikipedia.org/wiki/Fixed-point_arithmetic
The point of confusion was that his implementation was general enough to handle numbers where the value of the lsb > 1. I agree that this generalization has sufficient value to warrant use of a different template parameter scheme. I think something like is pretty sensible and implementation-friendly.
The way I structured it was to discard information only on assignment (unless the maximum internal storage had overflowed, of course). While I agree that it's tempting to just use int64 for storage, the size and speed implications of creating large arrays of them provides a strong argument against this approach.
Good idea, but this is a refinement that can wait until later.
I don't know if doing as some integer traits could make happy every body. * fast will choose the faster representation * least will choose the minimal representation
In most cases, smaller WILL be the faster implementation. Where this is not the case, the compiler can hopefully help out and provide most of the benefits of hand-tuning for a particular architecture.
Maybe sometimes, but not always. So I will prefer to been able to state explicitly if I need the smallest builtin representation or the faster one. Up to the implementation to ensure that.
I think the difference between Ravi's proposal and mine is really down to something I don't consider an implementation detail. When I implemented fixed-point templates, I parameterized the return type of operators, in order to avoid discarding any information. The only place where I discarded information was on assignment/conversion. It's not just about loss of information, but actually the semantics of the operators.
I think the result type should be deduced from the parameters type and the operation of course. We need of course to consider when the resulting type can not be represented using the available builtin types. Best, Vicente
On Fri 4/22/2011 2:32 AM, Vicente BOTET wrote:
In most cases, smaller WILL be the faster implementation. Where this is not the case, the compiler can hopefully help out and provide most of the benefits of hand-tuning for a particular architecture.
Maybe sometimes, but not always. So I will prefer to been able to state explicitly if I need the smallest builtin representation or the faster one. Up to the implementation to ensure that.
For how many architectures and generations do you expect this to be optimized? Don't forget that what might be faster to compute in registers could result in a much more significant performance drop, once arrays of these numbers are written/read to/from memory. Using smaller types also tells the compiler whether there's useful information in the MSBs, enabling the compiler to do more optimizations. IMO, smaller is the safer bet, performance-wise. If a user knows that a given CPU is going to do 64-bit arithmetic faster than 32-bit or 16-bit, then the user typically has the option to coerce this behavior by padding out the MSBs. And as a last resort, there's always the option to hand-code select parts. That said, if there's a way to influence the type used for internal representation without a lot of interface clutter/baggage (e.g. some kind of traits interface), I'd be all for it. But my expectation would be for knowledgable users to use it for their own tuning, rather than any promises made by the library.
I think the result type should be deduced from the parameters type and the operation of course. We need of course to consider when the resulting type can not be represented using the available builtin types.
Agreed. A static assert is one option. As a user, I want to be notified when I might inadvertently lose range or precision. When this happens, I would then perform an explicit conversion to a type with fewer significant bits *before* the operation. Either that, or perhaps invoke a named, "unchecked" function, in place of the operator. Matt
On Friday 22 April 2011 00:04:31 Gruenke, Matt wrote:
In most cases, smaller WILL be the faster implementation. Where this is not the case, the compiler can hopefully help out and provide most of the benefits of hand-tuning for a particular architecture.
Maybe sometimes, but not always. So I will prefer to been able to state explicitly if I need the smallest builtin representation or the faster one. Up to the implementation to ensure that.
For how many architectures and generations do you expect this to be optimized?
Don't forget that what might be faster to compute in registers could result in a much more significant performance drop, once arrays of these numbers are written/read to/from memory. Using smaller types also tells the compiler whether there's useful information in the MSBs, enabling the compiler to do more optimizations.
IMO, smaller is the safer bet, performance-wise. If a user knows that a given CPU is going to do 64-bit arithmetic faster than 32-bit or 16-bit, then the user typically has the option to coerce this behavior by padding out the MSBs. And as a last resort, there's always the option to hand-code select parts.
That said, if there's a way to influence the type used for internal representation without a lot of interface clutter/baggage (e.g. some kind of traits interface), I'd be all for it. But my expectation would be for knowledgable users to use it for their own tuning, rather than any promises made by the library.
I could not figure out a way to change the underlying type based on some traits. As far as a suggestion for LIAW goes, this detail is immaterial. As Matt stated earlier, his view is that the underlying type is part of the contract, while mine is that the underlying type is an implementation detail. My experience with modern CPUs (limited to some x86_64 chips, MIPS, some ARM variants and one proprietary embedded processor) in conjunction with maximal optimization by modern compilers has led me to discover no general patterns; smaller types have been slower as often as they have been faster, even with arrays of numbers. In fact, for some problems with very little branching, floating point arithmetic was much faster. If the underlying type truly needs to be specified, we could use a preprocessor definition. However, all of this is irrelevant to the idea of fixed-point numbers for a LIAW session. We have heard from neither Jeff Garland nor Hartmut Kaiser. Until we hear from them, I am doubtful that a proto-based LIAW session would be considered feasible by the Boostcon organizers. Regards, Ravi
On 16/03/2011 02:45, Gruenke, Matt wrote:
One area in which I spent a fair amount of time was fast conversion to/from IEEE floating-point. In trying to use the rounding-by-adding trick, I got slightly burned by differences in FPU configuration of Linux vs. Windows. With x87 arithmetic, the default FPU configuration keeps different amounts of intermediate precision.
What do you mean? MSVC doesn't specify whether floating point instructions use x87 or SSE (it is free to use either). GCC allows to choose whether you use exclusively x87 (32-bit default), SSE (64-bit default) or any (experimental).
I'm talking about x87 instructions, and I do mean Linux vs. Windows - not GCC vs. MSVC. The default configuration is platform-dependent and many libraries are written and tested against the respective configuration, only. Certain x87 instructions can retain higher intermediate precision than that of the datatype you're using. Therefore, if you use the "magic number" addition trick to get the FPU to perform a shift and round, you're in for a surprise. While one can always change the FPU configuration, it's an impractical work-around since you need to be careful about always changing it back before calling any library functions that might be affected. http://www.vinc17.org/research/extended.en.html These days, SSE support is so prevalent that explictly using it is an easy and viable alternative, in most cases. Regards, Matthew A. Gruenke ________________________________ From: boost-bounces@lists.boost.org on behalf of Mathias Gaunard Sent: Wed 3/16/2011 9:27 AM To: boost@lists.boost.org Subject: Re: [boost] [boostcon][proto] Suggestion for LIAW session:fixed-pointnumbers On 16/03/2011 02:45, Gruenke, Matt wrote:
One area in which I spent a fair amount of time was fast conversion to/from IEEE floating-point. In trying to use the rounding-by-adding trick, I got slightly burned by differences in FPU configuration of Linux vs. Windows. With x87 arithmetic, the default FPU configuration keeps different amounts of intermediate precision.
What do you mean? MSVC doesn't specify whether floating point instructions use x87 or SSE (it is free to use either). GCC allows to choose whether you use exclusively x87 (32-bit default), SSE (64-bit default) or any (experimental). _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Ravi-41 wrote:
Hi, Are there any proto-based ideas for the library-in-a-week sessions? If not, would building a fixed-point data type be of interest? The domain is narrow enough that something useful can be accomplished in 4 sessions, but of large enough scope to present opportunities for exploring proto in depth.
Hi, i would be interested in knowing if tis idea has been retained for the LIAW session of BoostCon. Thanks, Vicente -- View this message in context: http://boost.2283326.n4.nabble.com/boostcon-proto-Suggestion-for-LIAW-sessio... Sent from the Boost - Dev mailing list archive at Nabble.com.
On May 18, 2011, at 8:21 PM, Vicente Botet wrote:
Ravi-41 wrote:
Hi, Are there any proto-based ideas for the library-in-a-week sessions? If not, would building a fixed-point data type be of interest? The domain is narrow enough that something useful can be accomplished in 4 sessions, but of large enough scope to present opportunities for exploring proto in depth.
Hi,
i would be interested in knowing if tis idea has been retained for the LIAW session of BoostCon.
Jeff is having us work on pre-reviews of libraries, also important and with immediate impact. I do miss the wild ideas though!!
participants (8)
-
Eric Niebler -
Gordon Woodhull -
Gruenke, Matt -
Joel Falcou -
Mathias Gaunard -
Ravi -
Vicente Botet -
Vicente BOTET