Re: [boost] ANN: Optimized numeric_cast<> implementation

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2001-10-26 11:25:46

Fernando,

I am very glad that you are addressing these issues! I'll try to take a look
at your proposal; at first glance it looks very complete and I am optimistic
that we can accept it.

**** I would very much like to hear commentary from others as well. ****

Regards,
Dave

===================================================
  David Abrahams, C++ library designer for hire
 resume: http://users.rcn.com/abrahams/resume.html

        C++ Booster (http://www.boost.org)
          email: david.abrahams_at_[hidden]
===================================================

----- Original Message -----
From: "Fernando Cacciola" <fcacciola_at_[hidden]>
To: "boost" <boost_at_[hidden]>
Sent: Thursday, October 25, 2001 4:50 PM
Subject: [boost] ANN: Optimized numeric_cast<> implementation

>
> Hi boosters,
>
> Those of you who have followed the development of the boost template based
> math library (thread with "Math functions" in the subject) will know that
it
> was pointed out that there are optimization issues with numeric_cast<>
that
> prevent it from being used as broadly as we need.
>
> Based on my prior work on numerical conversion functions, I submit here a
> new optimized implementation of numeric_cast<>.
>
> Motivation:
> ~~~~~~~~
>
> The current numeric_cast<> implementation presents the following drawbacks
> (or at least this is what I could infer from the code):
> * It doesn't has a return type optimization for the trivial case
> Target==Source.
> * It performs the same runtime range-checking logic, even in cases when
> range checking is unnecessary: for example, when Target=double and
> Source=float.
> * It can not be used -or it is not clear how would it behave- with mixed
> integral/float combinations.
>
> The new implementation and the new additional interface.
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
> The interface to numeric_cast<> itself remains the same (except for the
> optimizations introduced).
> But in this new implementation, numeric_cast is a wrapper around some new
> tools which I describe below:
>
> (A) boost::numeric_range<N>
>
> This new class formalizes a solution to the "problem" with
> std::numeric_limits::min().
> It exposes the following interface which is consistent across integer and
> floating point types:
>
> boost::numeric_range<N>::lowest() // closer to -INF
> boost::numeric_range<N>::highest() // closer to +INF
> boost::numeric_range<N>::smallest() // closer to 0
>
> (B) boost::numeric_cast_traits<T,S>
>
> This new class is the core of the submission.
> It is a traits class that provides information and optimized methods for
the
> conversion from values of type S to values of type T.
>
> The following is a transcription of the documentation included in its
header
> file:
>
> //
> // numeric_cast_traits<T,S> traits.
> //
> // This traits class provides facilities for the conversion
> //   from a value 's' of type 'S'
> //   to   a value 't' of type 'T'.
> //
> // The facilities are:
> //
> //   static const int  numeric_cast_traits<T,S>::mixture
> //   static const int  numeric_cast_traits<T,S>::sign_mixture
> //   static const bool numeric_cast_traits<T,S>::subranged
> //   static const bool numeric_cast_traits<T,S>::trivial
> //   type              numeric_cast_traits<T,S>::super_type
> //   type              numeric_cast_traits<T,S>::sub_type
> //   type              numeric_cast_traits<T,S>::arg_type
> //   type              numeric_cast_traits<T,S>::ret_type
> //   struct            numeric_cast_traits<T,S>::range_checker
> //   struct            numeric_cast_traits<T,S>::converter
> //
> // mixture
> //
> //   This integral constant expression of type int determines
> //   one of the four integral/float possible combinations.
> //   It takes one of the following values:
> //
> //     numeric_cast_mixture::integral_to_integral
> //     numeric_cast_mixture::integral_to_float
> //     numeric_cast_mixture::float_to_integral
> //     numeric_cast_mixture::float_to_float
> //
> // sign_mixture
> //
> //   This integral constant expression of type int,
> //   determines one of the four signed/unsigned
> //   possible combinations.
> //   It takes one of the following values:
> //
> //     numeric_cast_sign_mixture::unsigned_to_unsigned
> //     numeric_cast_sign_mixture::signed_to_signed
> //     numeric_cast_sign_mixture::signed_to_unsigned
> //     numeric_cast_sign_mixture::unsigned_to_signed
> //
> // subranged
> //
> //   This integral constant expression of type bool
> //   conceptually determines if the target T is "subranged"
> //   with respect to the source type S.
> //   A value of true implies that the converted value might be
> //   truncated or rounded off, because the target type T cannot
> //   represent every value of the source type S.
> //   A value of false implies that the conversion
> //   will always be exact regardless the actual source value 's',
> //   because the type T can represent every value of type S.
> //   Notice that this is a compile-time predicate,
> //   independent of any actual value of type S to be converted.
> //
> // trivial
> //
> //   This integral constant expression of type bool
> //   is 'true' if both source and target types are the same, that is
> //   if T==S.
> //   It is false otherwise.
> //
> // super_type
> //
> //   This is the type to which two operands of types S and T
> //   must be promoted in order to participate in a common arithmetic
> //   or relational operation.
> //   It is either T or S, depending on the value of subranged.
> //
> // sub_type
> //
> //   This is the type T or S which is not the super_type.
> //
> // arg_type
> //
> //   This type is either 'S' or 'S const&'.
> //   It represents the 'optimal' argument type for the functions
> //   in range_checker and converter.
> //
> //   If S is a built-in type, arg_type is 'S', otherwise, it is
> //   'S const&'.
> //
> // ret_type
> //
> //   This type is either 'T' or 'T const&'
> //   It represents the return type of the member function
> //
> //     converter::cvt
> //
> //    If T==S, ret_type is 'T const&' otherwise, it is 'T'.
> //
> // range_checker
> //
> //   This object is used to perform range checking for the conversion
> //   from a particular value 's' to the type T.
> //   A range_checker object exposes the following interface:
> //
> //     static int out_of_range ( arg_type s ) ;
> //
> //       This static member function determines if the value 's'
> //       can be represented by the type T without truncation.
> //       It does not determine if the conversion is exact; that is,
> //       a rounding (inexact) conversion is considered to be in range.
> //       For instance, a conversion producing a floating point
> //       underflow is considered in range.
> //
> //       The test is conceptually the same as
> //
> //             s >= numeric_range<T>::lowest ()
> //          && s <= numeric_range<T>::highest()
> //
> //       The return value is one the the following constants:
> //
> //         range_check_result::cInRange
> //         range_check_result::cNegOverflow
> //         range_check_result::cPosOverflow
> //
> //     static void assert_in_range ( arg_type s ) ;
> //
> //         this static member function calls result=out_of_range(s),
> //         and if result!=cInRange, throws a corresponding exception:
> //
> //           result==cNegOverflow -> throw boost::negative_overflow();
> //           result==cPosOverflow -> throw boost::positive_overflow();
> //
> // converter
> //
> //   This object is used to perform a conversion
> //   from s of type S to t of type T.
> //
> //   A converter object exposes the following interface:
> //
> //     static ret_type cvt ( arg_type s ) ;
> //
> //  This object uses internally range_checker::assert_in_range(), thus,
> //  it might throw any of the exceptions thrown by the check.
> //
> // NOTE: both range_checker and converter are optimized according to
> //       combined properties of T and S.
>
>
> the core of the optimizations resides in the different range_checker and
> converters statically selected
> according to S and T.
>
> As you can see in the header "numeric_cast_traits_detail.hpp", there are 4
> range checkers and
> 3 converters.
>
> NOTE: the classes below are implementation details, I shown them here so
you
> can get an idea of how the optimizations work.
>
> full_range_checker::assert_in_range(s)
>     asserts that ( s >= lowest(T) && s <= highest(T))
>
> void_range_checker::assert_in_range(s)
>     does effectively nothing.
>     it is selected when the conversion is trivial or not subranged.
>
> non_negative_range_checker::assert_in_range(s)
>     asserts that ( s>= 0 )
>     it is used when there is a signed to unsigned conversion and the
target
> type has bigger positive range.
>
> positive_range_checker::assert_in_range(s)
>     asserts that ( s < highest(T))
>     it is used when there is an unsigned to signed conversion. (the
negative
> range is implicitly OK)
>
> non_rounding_converter::cvt
>     converts from a floating point or integer type to another floating
point
> type.
>
> rounding_converter::cvt
>     converts from a floating point type to an integer type.
>
> void_converter::cvt
>     effectively does nothing: returns a const reference to its const
> reference argument.
>     it is used when T==S.
>
>
> If you look closely you will discover some "gaps".
> In order to fill those gaps I need further definitions and choices that I
> can't make myself.
>
> a) The rounding from floating point to integer is fixed.
>     I couldn't figured out how to let the user plug in a rounding scheme
> without too much interface clutter.
>     I think it will end up using *one* of the new C99 rounding functions
> when they become available
>
> b) There isn't control for inexact conversions, such as underflow.
> c) out_of_range conditions throw exceptions. On some applications it might
> be better to return the truncated value instead.
>
> The overall design contemplates the above gaps, so it would be relatively
> easy to change the code to accommodate things.
>
> the code:
> ~~~~~~
>
> I uploaded the code in a new folder on the Files Section:
>
>   http://groups.yahoo.com/group/boost/files/improved_numeric_cast/
>
>
> The code is split in several files. They are intended to be in different
> directories of a boost installation:
>
> boost\
>     numeric_cast.hpp
>
http://groups.yahoo.com/group/boost/files/improved_numeric_cast/numeric_cast
> .hpp
>     numeric_cast_traits.hpp
>
http://groups.yahoo.com/group/boost/files/improved_numeric_cast/numeric_cast
> _traits.hpp
>     numeric_range.hpp
>
http://groups.yahoo.com/group/boost/files/improved_numeric_cast/numeric_rang
> e.hpp
>     detail\
>         numeric_cast_traits_detail.hpp
>
http://groups.yahoo.com/group/boost/files/improved_numeric_cast/numeric_cast
> _traits_detail.hpp
>         numeric_cast_range_detail.hpp
>
http://groups.yahoo.com/group/boost/files/improved_numeric_cast/numeric_cast
> _range_detail.hpp
>         meta_programing_tools.hpp
>
http://groups.yahoo.com/group/boost/files/improved_numeric_cast/meta_program
> ing_tools.hpp
>     libs\
>         numeric_cast_test.cpp
>
http://groups.yahoo.com/group/boost/files/improved_numeric_cast/numeric_cast
> _test.cpp
>         numeric_cast_test_output.txt
>
http://groups.yahoo.com/group/boost/files/improved_numeric_cast/numeric_cast
> _test_output.txt
>
> There is a ZIP file with everything too:
>
http://groups.yahoo.com/group/boost/files/improved_numeric_cast/numeric_cast
> .zip
>
>
>
> The implementation:
> ~~~~~~~~~~~~~~~
>
> All the files contain extensive documentation; however, the "detail"
headers
> are rather complex.
> I tried my best at making the implementation as readable as possible, but
> also as portable as possible, so most of the code looks uglier that you
> would have expected, because I needed to accommodate the poor non-type
> template parameter support of Borland C++ and the poor
> partial-specialization support of Visual C++.
>
> The file 'meta_programing_tools.hpp' is an update of the file
> 'meta_tools.hpp' that I've uploaded for my optional<> class before. It
> borrowed some stuff from 'ice.hpp' and 'select_type.hpp', but for type
> parameters instead of non-type parameters.
>
> I used some of the type_traits headers.
>
> Opinions?
>
> Best regards,
>
> Fernando Cacciola
> Sierra s.r.l.
> fcacciola_at_[hidden]
> www.gosierra.com
>
>
> Info: http://www.boost.org  Unsubscribe:
<mailto:boost-unsubscribe_at_[hidden]>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
>