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

Tue Jul 21 12:11:33 EDT 2009

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.itk.org/mailman/private/insight-developers/attachments/20090721/c227be19/attachment.htm>