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

Wed Jul 22 05:32:32 EDT 2009

Hi,

Now I realized that I forgot that "long long" is not portable... One
potential option would be to use long as you suggested. Maybe
something along the lines of

long Round(double x) {
# if SIZEOF_LONG == 8
  // fast 64 bits implementation when possible
  [...]
# elif  SIZEOF_LONG == 4
  // fast 32 bits implementation when possible
  [...]
#else
  // vanilla implementation
  [...]
#endif
}

This is going to be a ifdef hell but should be doable.

Also, because of the backward-compatibility policy I don't think it is
possible to modify the current signature of itk::Math::Round. And
because of the covariant return types issue on msvc 6, we cannot add
"long Round(double x)", so we might need to choose another name for
the long variants. Maybe itk::Math::lRound or  itk::Math::LRound?

Tom

On Wed, Jul 22, 2009 at 10:49, Tom Vercauteren<tom.vercauteren at m4x.org> wrote:
> 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
>>
>>
>