Mailing List Archive: Python: Dev

Re: [Python-checkins] cpython: Issue #14716: Change integer overflow check in unicode_writer_prepare()

Index | Next | Previous | View Threaded

dickinsm at gmail

May 7, 2012, 4:35 AM

Post #1 of 7 (185 views)
Permalink

Re: [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 [at] python> wrote:
> http://hg.python.org/cpython/rev/ab500b297900
> changeset: 76821:ab500b297900
> user: Victor Stinner <victor.stinner [at] gmail>
> 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
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

dickinsm at gmail

May 7, 2012, 5:04 AM

Post #2 of 7 (182 views)
Permalink

Re: [Python-checkins] cpython: Issue #14716: Change integer overflow check in unicode_writer_prepare() [In reply to]

On Mon, May 7, 2012 at 12:35 PM, Mark Dickinson <dickinsm [at] gmail> 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".
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

storchaka at gmail

May 7, 2012, 8:48 AM

Post #3 of 7 (179 views)
Permalink

Re: [Python-checkins] cpython: Issue #14716: Change integer overflow check in unicode_writer_prepare() [In reply to]

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).

_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

storchaka at gmail

May 7, 2012, 9:33 AM

Post #4 of 7 (177 views)
Permalink

Re: [Python-checkins] cpython: Issue #14716: Change integer overflow check in unicode_writer_prepare() [In reply to]

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.

_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

solipsis at pitrou

May 7, 2012, 9:38 AM

Post #5 of 7 (175 views)
Permalink

Re: [Python-checkins] cpython: Issue #14716: Change integer overflow check in unicode_writer_prepare() [In reply to]

On Mon, 7 May 2012 12:35:27 +0100
Mark Dickinson <dickinsm [at] gmail> 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.

_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

victor.stinner at gmail

May 7, 2012, 2:51 PM

Post #6 of 7 (171 views)
Permalink

Re: [Python-checkins] cpython: Issue #14716: Change integer overflow check in unicode_writer_prepare() [In reply to]

> 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
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

greg.ewing at canterbury

May 7, 2012, 4:12 PM

Post #7 of 7 (170 views)
Permalink

Re: [Python-checkins] cpython: Issue #14716: Change integer overflow check in unicode_writer_prepare() [In reply to]

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
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

Index | Next | Previous | View Threaded

Interested in having your list archived? Contact Gossamer Threads