Re: [Python-Dev] [Python-checkins] cpython: Issue #14716: Change integer overflow check in unicode_writer_prepare()
On Mon, May 7, 2012 at 12:08 PM, victor.stinner <python-checkins@python.org> wrote:
http://hg.python.org/cpython/rev/ab500b297900 changeset: 76821:ab500b297900 user: Victor Stinner <victor.stinner@gmail.com> date: Mon May 07 13:02:44 2012 +0200 summary: Issue #14716: Change integer overflow check in unicode_writer_prepare() to compute the limit at compile time instead of runtime. Patch writen by Serhiy Storchaka.
if (newlen > PyUnicode_GET_LENGTH(writer->buffer)) { - /* overallocate 25% to limit the number of resize */ - if (newlen <= (PY_SSIZE_T_MAX - newlen / 4)) + /* Overallocate 25% to limit the number of resize. + Check for integer overflow: + (newlen + newlen / 4) <= PY_SSIZE_T_MAX */ + if (newlen <= (PY_SSIZE_T_MAX - PY_SSIZE_T_MAX / 5)) newlen += newlen / 4;
Hmm. Very clever, but it's not obvious that that overflow check is mathematically sound. As it turns out, the maths works provided that PY_SSIZE_T_MAX isn't congruent to 4 modulo 5; since PY_SSIZE_T_MAX will almost always be one less than a power of 2 and powers of 2 are always congruent to 1, 2 or 4 modulo 5, we're safe. Is the gain from this kind of micro-optimization really worth the cost of replacing obviously correct code with code whose correctness needs several minutes of thought? Mark
On Mon, May 7, 2012 at 12:35 PM, Mark Dickinson <dickinsm@gmail.com> wrote:
will almost always be one less than a power of 2 and powers of 2 are always congruent to 1, 2 or 4 modulo 5, we're safe.
Bah. That should have read "1, 2, 3 or 4 modulo 5".
07.05.12 14:35, Mark Dickinson написав(ла):
Hmm. Very clever, but it's not obvious that that overflow check is mathematically sound.
My fault. Overflow will be at PY_SSIZE_T_MAX congruent to 4 modulo 5 (which is impossible if PY_SSIZE_T_MAX is one less than a power of 2). Mathematically strict limit must be (PY_SSIZE_T_MAX - 1 - (PY_SSIZE_T_MAX - 4) / 5).
07.05.12 18:48, Serhiy Storchaka написав(ла):
My fault.
However, it's not my fault. I suggested `newlen < (PY_SSIZE_T_MAX - PY_SSIZE_T_MAX / 5)` and not `newlen <= (PY_SSIZE_T_MAX - PY_SSIZE_T_MAX / 5)`. In this case, there is no overflow.
However, it's not my fault. I suggested `newlen < (PY_SSIZE_T_MAX - PY_SSIZE_T_MAX / 5)` and not `newlen <= (PY_SSIZE_T_MAX - PY_SSIZE_T_MAX / 5)`. In this case, there is no overflow.
Oh. I didn't understand why you replaced <= by <, and so I used <=. Anyway, I reverted the change for all reasons listed in this thread. Victor
On Mon, 7 May 2012 12:35:27 +0100 Mark Dickinson <dickinsm@gmail.com> wrote:
Hmm. Very clever, but it's not obvious that that overflow check is mathematically sound. As it turns out, the maths works provided that PY_SSIZE_T_MAX isn't congruent to 4 modulo 5; since PY_SSIZE_T_MAX will almost always be one less than a power of 2 and powers of 2 are always congruent to 1, 2 or 4 modulo 5, we're safe.
Is the gain from this kind of micro-optimization really worth the cost of replacing obviously correct code with code whose correctness needs several minutes of thought?
Agreed that the original code is good enough. Dividing by 4 is fast, and this particular line of code is followed by a memory reallocation. In general, "clever" micro-optimizations that don't produce significant performance improvements should be avoided, IMHO :-) Regards Antoine.
Mark Dickinson wrote:
Is the gain from this kind of micro-optimization really worth the cost of replacing obviously correct code with code whose correctness needs several minutes of thought?
The original code isn't all that obviously correct to me either. I would need convincing that the arithmetic being used to check for overflow can't itself suffer from overflow. At least that much is obvious from the new version. -- Greg
participants (5)
-
Antoine Pitrou -
Greg Ewing -
Mark Dickinson -
Serhiy Storchaka -
Victor Stinner