[Insight-developers] vnl updates : Rounding Test : Performance and Correctness
Luis Ibanez
luis.ibanez at kitware.com
Tue Dec 30 17:35:20 EST 2008
Just for completeness,
Here is the test output
when run on Debian Linux with gcc 4.2 (no Debug, no Release)
cd Insight/Testing/Code/Common
ctest -R itkVNLRound -V
101/184 Testing itkVNLRoundProfileTest1
Test command: /home/ibanez/bin/Insight/bin/itkCommonTests2
itkVNLRoundProfileTest1
Initial Value = -10
Value Increment = 2e-05
Probe Tag Starts Stops Time (s)
if-round 1 1 0.0325642
std::vector 1 1 0.0169749
vnl_math_rnd 1 1 0.026947
Error in : -8.5 : -9 : -8
Error in : -6.5 : -7 : -6
Tested 1000000 entries
-- Process completed
***Failed
0% tests passed, 1 tests failed out of 1
The following tests FAILED:
-------------------------------
(All number below are in "seconds"):
The net time of running vnl_math_rnd (one million times) is
0.026947 - 0.0169749 = 0.0099721
The net time of running the if-based rounding (one million times) is
0.0325642 - 0.0169749 = 0.0155893
The difference between vnl_math_rnd() and the
if-based implementation is
-0.0056172
which is
36 % of the time of running the if-based version
or
56 % of the time of running the vnl_math_rnd() version
Note that in the great scheme of things we are talking about
a difference of
5 nanoseconds
per execution.
NOTE: The implementation of the if-based version is made in a
C function call. Converting it to a template or a macro
should already bring them closer.
Luis
---
Machine Characteristics:
processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 23
model name : Intel(R) Core(TM)2 Duo CPU T9600 @ 2.80GHz
stepping : 6
cpu MHz : 800.000
cache size : 6144 KB
physical id : 0
siblings : 2
core id : 0
cpu cores : 2
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 10
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge
mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pb
x smx est tm2 ssse3 cx16 xtpr sse4_1 lahf_lm
bogomips : 5590.52
clflush size : 64
processor : 1
vendor_id : GenuineIntel
cpu family : 6
model : 23
model name : Intel(R) Core(TM)2 Duo CPU T9600 @ 2.80GHz
stepping : 6
cpu MHz : 800.000
cache size : 6144 KB
physical id : 0
siblings : 2
core id : 1
cpu cores : 2
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 10
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge
mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pb
x smx est tm2 ssse3 cx16 xtpr sse4_1 lahf_lm
bogomips : 5585.97
clflush size : 64
-----------------------
Luis Ibanez wrote:
>
> To get some hard data on timing and correctness
> I just added a test:
>
> itkVNLRoundProfileTest1.cxx
>
> to Insight/Testing/Code/Common
>
>
> It does the following:
>
>
> A) Compares the "if" implementation
> of rounding to the vnl_math_rnd()
>
> B) Measures the computation time needed
> for executing vnl_math_rnd()
>
>
> After running the test on Linux, gcc 4.2 we observe that
> it fails due to the policy of rounding to Even...
>
>
> Here are my early impressions:
>
> 1) Rounding is too much of a basic operation.
>
> 2) Implementing it is a very minimal amount of code
>
> 3) We use it everywhere
>
> 4) We need it to be cross-platform
>
> 5) We need it to be reasonably fast,
> but it is not the most demanding part of our
> algorithms.
>
>
>
> That leads me to suggest:
>
>
> a) Let's stop using vnl_math_rnd()
>
> b) Write our own (let's discuss the details in a separate email)
>
> We are talking about 10 ~ 20 lines of code,
> we should be able to do that :-)
>
>
> c) Have a biased and non-biased implementation
>
> * double itkRound( double )
> * double itkNonBiasRound( double )
> * ... and maybe other flavors too...
>
>
> and use one or the other depending on the application.
>
>
>
> The overall impression is that: ITK being a library with
> more than 130,000 lines of code, it would be shameful to
> depend on a third party library for implementing correctly
> an operation as basic as rounding, particularly when we
> can implement it in 10 lines of code.
>
>
>
> Luis
>
>
>
> --------------------
> Bill Lorensen wrote:
>
>> I wonder what the radiology community says about this?
>>
>> On Tue, Dec 30, 2008 at 4:32 PM, Steve M. Robbins <steve at sumost.ca>
>> wrote:
>>
>>> On Tue, Dec 30, 2008 at 01:58:28PM -0500, Luis Ibanez wrote:
>>>
>>>
>>>> Choosing the rounding standard based on the performance of the platform
>>>> doesn't seem to be a good solution for ITK.
>>>>
>>>> We would want a round() function that produces the *same* output on
>>>> *every* platform.
>>>
>>>
>>> That makes sense to me.
>>>
>>>
>>>
>>>> If we pick a rounding policy, it should be the same for all
>>>> platforms, and it should also include a specification on how
>>>> it will apply to negative numbers.
>>>
>>>
>>> I've always been under the impression that round-to-even is to be
>>> preferred, since the other methods (round-up, round-down, or
>>> round-to-zero) will bias the calculations.
>>>
>>> Quoting Wikipedia:
>>>
>>> Despite the custom of rounding the number 4.5 up to 5, in fact 4.5
>>> is no nearer to 5 than it is to 4 (it is 0.5 away from both). When
>>> dealing with large sets of scientific or statistical data, where
>>> trends are important, traditional rounding on average biases the
>>> data upwards slightly. Over a large set of data, or when many
>>> subsequent rounding operations are performed as in digital signal
>>> processing, the round-to-even rule tends to reduce the total
>>> rounding error, with (on average) an equal portion of numbers
>>> rounding up as rounding down. This generally reduces upwards
>>> skewing of the result.
>>>
>>> http://en.wikipedia.org/wiki/Rounding
>>>
>>> Also, according to Goldberg's classic paper [1] Knuth also prefers
>>> round-to-even, which is a strong recommendation in my books ;-)
>>>
>>> [1] http://docs.sun.com/source/806-3568/ncg_goldberg.html
>>>
>>> Cheers,
>>> -Steve
>>>
>>> -----BEGIN PGP SIGNATURE-----
>>> Version: GnuPG v1.4.9 (GNU/Linux)
>>>
>>> iD8DBQFJWpNp0i2bPSHbMcURAkkEAKCeGnxwyjeQYc+NiJ7tcPiw/3birgCfZ9zv
>>> F5W5uGojrYesCPeonZloUpw=
>>> =E/CS
>>> -----END PGP SIGNATURE-----
>>>
>>> _______________________________________________
>>> Insight-developers mailing list
>>> Insight-developers at itk.org
>>> http://www.itk.org/mailman/listinfo/insight-developers
>>>
>>>
>>
>>
>
More information about the Insight-developers
mailing list