<div dir="ltr"><div><div><div><div><div><br><div class="gmail_quote"><div dir="ltr">On Wed, Jul 5, 2017 at 12:05 PM Mark Dickinson <<a href="mailto:dickinsm@gmail.com">dickinsm@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Mon, Jul 3, 2017 at 5:52 AM, Siyuan Ren <<a href="mailto:netheril96@gmail.com" target="_blank">netheril96@gmail.com</a>> wrote:<br>
> The current PyLong implementation represents arbitrary precision integers in<br>
> units of 15 or 30 bits. I presume the purpose is to avoid overflow in<br>
> addition , subtraction and multiplication. But compilers these days offer<br>
> intrinsics that allow one to access the overflow flag, and to obtain the<br>
> result of 64 bit multiplication as a 128 bit number. Or at least on x86-64,<br>
> which is the dominant platform.  Any reason why it is not done?<br>
<br>
Portability matters, so any use of these intrinsics would likely also<br>
have to be accompanied by fallback code that doesn't depend on them,<br>
as well as some buildsystem complexity to figure out whether those<br>
intrinsics are supported or not. And then the Objects/longobject.c<br>
would suffer in terms of simplicity and readability, so there would<br>
have to be some clear gains to offset that. Note that the typical<br>
Python workload does not involve thousand-digit integers: what would<br>
matter would be performance of smaller integers, and it seems<br>
conceivable that 64-bit limbs would speed up those operations simply<br>
because so many more integers would become single-limb and so there<br>
would be more opportunities to take fast paths, but there would need<br>
to be benchmarks demonstrating that.<br>
<br>
Oh, and you'd have to rewrite the power algorithm, which currently<br>
depends on the size of a limb in bytes being a multiple of 5. :-)<br>
<br>
--<br>
Mark<br></blockquote><div><br></div>When I pushed to get us to adopt 30-bit digits instead of 15-bit digits, I hoped it could also happen on 32-bit x86 builds as the hardware has fast 32bit multiply -> 64 result support. But it made the configuration more difficult and IIRC would've increase the memory use of the PyLong type for single digit numbers on 32-bit platforms so we settled on moving to 30 bits only for 64-bit platforms (which were obviously going to become the norm).</div><div class="gmail_quote"><br></div><div class="gmail_quote">A reasonable digit size for hardware that supports 128bit results of 64bit multiplies would be 60 bits (to keep our multiple of 5 bits logic working).  But I doubt you will see any notable performance gains in practical applications by doing so.  Sure, numbers in the 1-4 billion range are slightly less efficient today, but those are not likely to appear in hot loops in a typical application.  Microbenchmarks alone should not be used to make this decision.<div><br></div><div>remember: We had native integer support in Python 1 & 2 via the old PyInt type. In Python 3 we ditched that in favor of PyLong everywhere. This was a performance hit for the sake of proper high level language simplicity.  We've already regained all of that since then in other areas of the interpreter. </div><div><br></div><div>-gps</div></div></div></div></div></div></div></div>