
Boost : 
Subject: Re: [boost] Looking for some "real world" extended precision integer arithmetic tests
From: Andrii Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 20120126 16:16:28
John,
Benchmark description follows (test code and results in the attachments):
History:
Voronoi diagram predicates use 256bit signed int type in case of voronoi of
points and 4096bit signed int in case of voronoi of segments. This
benchmark was run only for the point inputs.
Input coordinates for the voronoi algorithm are from int32 domain.
Fixed_int type was used only to compute center's of the inscribed circles
and was not used to store any algorithm intermediate values.
Voronoi fixed_int is not a complete integer type (it doesn't provide all
the integer operations, just those required by the voronoi algorithm).
Preconditions:
Before running benchmark I made sure that output generated with your
fixed_int and with mine implementation is completely the same over a set of
30000 random input data sets.
Bencmark results (time in seconds per test):
*Using voronoi extended_int256 type*:
 Number of points  Number of tests  Time per one test 
 10  10000  0.000038 
 100  1000  0.000621 
 1000  100  0.006990 
 10000  10  0.073000 
 100000  1  0.783000 
*Using voronoi extended_int4096 type*:
 Number of points  Number of tests  Time per one test 
 10  10000  0.000038 
 100  1000  0.000621 
 1000  100  0.007130 
 10000  10  0.074500 
 100000  1  0.795000 
*Using multiprecision type mp_int256_t:*
 Number of points  Number of tests  Time per one test 
 10  10000  0.000098 
 100  1000  0.001720 
 1000  100  0.019230 
 10000  10  0.199800 
 100000  1  2.045000 
*Using multiprecision type mp_int512_t:*
 Number of points  Number of tests  Time per one test 
 10  10000  0.000238 
 100  1000  0.004299 
 1000  100  0.047770 
 10000  10  0.491500 
 100000  1  5.023000 
*Using multiprecision type mp_int1024_t:*
 Number of points  Number of tests  Time per one test 
 10  10000  0.000686 
 100  1000  0.012558 
 1000  100  0.139440 
 10000  10  1.428000 
 100000  1  14.373000 
Conclusions:
0) The main reason vornoi fixed_int outperforms multiprecision fixed_int is
that it doesn't operate with leading bytes if those are not set (correct me
if I'm wrong).
1) Performance of the voronoi fixed_int type is almost independent on the
memory allocated for it.
2) Performance of the multiprecision fixed_int type strongly correlates
with the memory allocated for it.
3) Voronoi fixed_int 256bit outperforms multiprecision fixed_int
256bit 2.5 times. Actually this number is even bigger as it doesn't
substract time used by the other parts of the algorithm.
Regards,
Andrii
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk