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 256-bit outperforms multiprecision fixed_int 256-bit 2.5 times. Actually this number is even bigger as it doesn't substract time used by the other parts of the algorithm.
Well that's disappointing then ! :-( Certainly looks like lazy evaluation of higher-order limbs is a big win in this case - I'm guessing that most operations use only one or two limbs, and just every now and then you get a true big number? Thanks, John.