[Insight-developers] itk::Math:: limitations (was: Using Math::Floor in interpolation code?)

[Tom Vercauteren]

Hi Brad,

I agree that it would be more pleasing to have a consistent
  long Round(double x)

However, I wouldn't know how to implement that in an efficient manner.
That's why I would rather have a nice
  long long Round64(double x)
and use this version for image indexes. This basically amount to having
  long Round(double x) { return static_cast<long>(Round64(x)); }

Thoughts?
Tom

*Side note*
I also like fixed-width types, they are much easier to deal with.
Boost has a nice wrapper to use them in a portable manner in c++:
http://www.boost.org/doc/libs/1_39_0/boost/cstdint.hpp
It might be a nice thing to consider for ITK 4.0

On Tue, Jul 21, 2009 at 18:11, Bradley Lowekamp<blowekamp at mail.nih.gov> wrote:
> Hi Tom,
> Thank you for running that experiment. That is quite a nice performance
> boost.
> I personally don't have a need for more the 32-bit index of images. (Heck,
> if you were indexing frames of video at 30 fps you'd have over 4 years
> worth.) But  the index's value type is "long" and we should try our best not
> to truncate that unnecessarily. Unless, the community decides that index
> types really only need to be a int type. Yes, as you pointed out the size of
> integers types is not very straight forward and are inconsistent across
> platforms. But to formally state my point: there exists systems where the
> sizeof(int) != sizeof(long), yet your code is only the same as what exists
> when the previous expression is true. However, given that we just found the
> limitation of long only being 32-bit on windows, I don't know if any one
> really dependent are larger indexing.
> Specifically and ideally for a rounding function to be compatible with the
> index's type a signature similar to the following would be best:
> long Round(double x);
> long Round(float x);
>
> *Side note*
> I am starting to like the idea of C99's exact-width, minimum-width, and
> fastest-width integer types. The type "uin32_t" just makes since and I would
> think make things easier for portability in many cases, but I don't have the
> experience to really say.
> Brad
>
>
> On Jul 21, 2009, at 9:38 AM, Tom Vercauteren wrote:
>
> Hi Brad,
>
> If the INT_MAX/2 limitations seems to restrictive for your needs, we
> could also write some 64-bit variants of the itk::Math:: rounding
> routines.
>
> I made a small experiments (see attached file for linux) in that
> direction. The optimized floating point to integral type conversions
> functions can be ported to 64 bits. the good news is that the
> performance improvement is still there (roughly a times 4 on both 32
> and 64 bit linux and a time 2.5 on 32 bits mac). Note that we still
> have similar limitations, i.e. it wont be meaningful for arguments
> which absolute value is greater than 2^(64-2) (note the -2 instead of
> -1) and we expect the FPU to be in the default rounding mode.
>
> Would this seems better to you? We could then either modify the
> existing itk::Math:: routines or add some 64bits variants, e.g.
>
>  int Round(float   x);
>  int Round(double  x);
>  long long int Round64(double  x);
>
> Unfortunately we cannot add "long long int Round(double  x);" because
> MSVC 6 does not support covariant return types. Also a few points to
> keep in mind are that:
> - int may not be 32 bits
> - long long int  may not be 64 bits
> - On a standard machine, float can represent integers exactly only up
> to 2^24 and double can do it up to 2^53. This means that strictly
> speaking switching between continuous indexes (doubles) and indexes
> (long long?) is somewhat inconsistent.
>
> Thoughts?
> Tom
>
> P.s. : Below are the reported times for the attached experiment
>
> on a linux 64 bits machine:
> time_ref:   794.103
> time_llround:1735.42
> time_llrint: 357.661
> time_asm:   283.258
> time_sse2:   188.613
> time_sse2_32bitsimplementation:   188.609
>
> on a 32 bits mac
> time_ref:   1272.14
> time_llround:1491.39
> time_llrint: 669.917
> time_asm:   505.983
> time_sse2_32bitsimplementation:   257.107
>
> On Mon, Jul 20, 2009 at 20:12, Bradley Lowekamp<blowekamp at mail.nih.gov>
> wrote:
>
> Hello Tom,
>
> What do I mean? That is a good question. Looking at the code you posted, it
>
> performed the floor operation to "long" precisions. (Which can be 32 or 64
>
> bits of precision. )  The itk::Image's
>
> Index' ValueType (the precisions of indexs) is type long also. So I think
>
> ideally we need an tik::Floor methods to support long type....
>
> But as the discussion from a couple of weeks ago reveled the size of long is
>
> not consistent. Specifically on windows 64-bit it's only 32 bits. This can
>
> cause some problems and limitation, which still need to be sorted out.
>
> In summary, I think that the code should be replaces with a version of floor
>
> which supports the same type as we are using for index types. (Which
>
> currently is long, but may be changed to a portable 64-bit type in the
>
> future.
>
> Brad
>
> On Jul 20, 2009, at 12:29 PM, Tom Vercauteren wrote:
>
> Hi Brad,
>
>
> On Mon, Jul 20, 2009 at 17:40, Bradley Lowekamp<blowekamp at mail.nih.gov>
>
> wrote:
>
> On Jul 20, 2009, at 10:13 AM, Tom Vercauteren wrote:
>
> P.S.: As for the other itk::Math:: routines, the limitations are that
>
> itk::Math::Floor is only guaranteed to work for arguments less than
>
> INT_MAX/2. Also it expects the FPU rounding mode to be the default
>
> one.
>
> <itk-InterpolateFloor-2009-07-20.patch><ATT00001.txt>
>
> Is it limited to INT_MAX/2 for 64-bit integers too?
>
> I am not sure what you mean by "for 64-bit integers" since the
>
> itk::Math:: routines take a float or double as input and produce an
>
> int as output and, as far as I know, int is usually 32 bits even on 64
>
> bit platforms.
>
> That being said, it is true that the INT_MAX/2 limitation also holds
>
> on 64 bits systems. Actually, for almost all itk::Math:: routines, one
>
> should currently assume that they only work for arguments that have an
>
> absolute value less than INT_MAX/2-1 *. The main exception being
>
> RoundHalfIntegerToEven that works up to INT_MAX.
>
> When I initially started working on those rounding functions for ITK,
>
> the discussions on the list led to a consensus that these limitations
>
> were not a problem. Do you think otherwise? Would you be in favor for
>
> adding an assert in these rounding functions for this INT_MAX/2
>
> limitation so that errors might be caught in a debug mode?
>
> Tom
>
>
> * The actual implementation of the itk::Math:: routines depend on the
>
> architecture and compiler so in some cases, it might work but I
>
> definitely wouldn't rely on that.
>
> ========================================================
>
> Bradley Lowekamp
>
> Lockheed Martin Contractor for
>
> Office of High Performance Computing and Communications
>
> National Library of Medicine
>
> blowekamp at mail.nih.gov
>
>
> <rounding64_time_tests.cxx>
>
> ========================================================
>
> Bradley Lowekamp
>
> Lockheed Martin Contractor for
>
> Office of High Performance Computing and Communications
>
> National Library of Medicine
>
> blowekamp at mail.nih.gov
>
>