[Insight-developers] vnl updates : Rounding Test : Performance and Correctness
Luis Ibanez
luis.ibanez at kitware.com
Tue Dec 30 18:25:29 EST 2008
And when adding a template and Macro based implementations
to the test, and compiling for Release (in the same platform)
we get the following numbers:
Initial Value = -10
Value Increment = 2e-05
Probe Tag Starts Stops Time (s)
Functor 100 100 0.0109601
Macro 100 100 0.00650821
if-round 100 100 0.00651316
std::vector 100 100 0.00443856
vnl_math_rnd 100 100 0.00450361
Error in : -8.5 : -9 : -8
Error in : -6.5 : -7 : -6
These results don't quite make sense to me...
I would have blamed memory-coherence, but after adding
a global for-loop that repeats the computation 100 times,
the values remain about the same.
----
Any guesses are welcome...
BTW,
If somebody can also explain why the rounding
errors appear only in:
-8.5 and -6.5
and not in all even numbers in the range -10:10
-8.5, -6.5, -4.5, -2.5, 0.5, 2.5, 4.5, 6.5, 8.5
that will be very kind as well... :-)
Luis
------------------
Luis Ibanez wrote:
>
>
> 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