[issue5512] Streamline integer division

[Mark Dickinson]

Mark Dickinson <dickinsm at gmail.com> added the comment:

Updated patch.  Lots of cleanup, but only one significant change:  the 
inner loop now uses signed arithmetic instead of unsigned arithmetic.  This saves a negation and fixes a subtle bug: the previous inner loop code 
was incorrect when using 15-bit digits on machines with sizeof(short) == 
sizeof(long).  Not that I know of any such machines:  the Cray T3E 
famously has no 16-bit integer type, but there sizeof(short) is 4 and 
sizeof(long) is 8.

A few more timings, this time from doing a single huge integer division:  
10**1000000//10**500000 (so this effectively times just the inner loop, 
since all else will be insignificant).  All timings are best-of-5, from 
non-debug builds of py3k, on the same system: OS X 10.5.6/2.4 GHz Core 2 
Duo.  Times in brackets are the approximate per-inner-loop times 
(remembering that there are 4 times as many iterations of the inner loop 
for 15-bit digits).

32-bit build, 15-bit digits, unpatched:  92382.2 ms   (~7.5 ns)
32-bit build, 15-bit digits, patched:    36473.3 ms   (~3.0 ns)
64-bit build, 30-bit digits, unpatched:  14581.4 ms   (~4.8 ns)
64-bit build, 30-bit digits, patched:     7385.1 ms   (~2.4 ns)

... and just for fun, the other combinations:

64-bit build, 15-bit digits, unpatched:  61927.5 ms   (~5.1 ns)
64-bit build, 15-bit digits, patched:    43632.9 ms   (~3.6 ns)
32-bit build, 30-bit digits, unpatched:  62374.1 ms  (~20.3 ns)
32-bit build, 30-bit digits, patched:    26928.3 ms   (~8.8 ns)


Thanks for the updated pidigits script, Victor!  Maybe this is too small 
right now to be worth including in the Tools directory, but I hope we can 
fatten it up with some other benchmarks.  What do you think?

----------
Added file: http://bugs.python.org/file13391/faster_integer_division2.patch

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue5512>
_______________________________________