homepage

This patch slightly optimize conversion int to string with base 2, 8 or 16 by calculating exactly number of digits and avoiding unnecessary memory allocation. The code is similar to used for decimal conversion.
Without patch:
$ ./python -m timeit -s 'x=1' 'bin(x)'
1000000 loops, best of 3: 0.295 usec per loop
$ ./python -m timeit -s 'x=1' 'oct(x)'
1000000 loops, best of 3: 0.327 usec per loop
$ ./python -m timeit -s 'x=1' 'hex(x)'
1000000 loops, best of 3: 0.298 usec per loop
$ ./python -m timeit -s 'x=9**999' 'bin(x)'
100000 loops, best of 3: 11.9 usec per loop
$ ./python -m timeit -s 'x=9**999' 'oct(x)'
100000 loops, best of 3: 4.55 usec per loop
$ ./python -m timeit -s 'x=9**999' 'hex(x)'
100000 loops, best of 3: 3.99 usec per loop
With patch:
$ ./python -m timeit -s 'x=1' 'bin(x)'
1000000 loops, best of 3: 0.213 usec per loop
$ ./python -m timeit -s 'x=1' 'oct(x)'
1000000 loops, best of 3: 0.228 usec per loop
$ ./python -m timeit -s 'x=1' 'hex(x)'
1000000 loops, best of 3: 0.215 usec per loop
$ ./python -m timeit -s 'x=9**999' 'bin(x)'
100000 loops, best of 3: 9.76 usec per loop
$ ./python -m timeit -s 'x=9**999' 'oct(x)'
100000 loops, best of 3: 3.58 usec per loop
$ ./python -m timeit -s 'x=9**999' 'hex(x)'
100000 loops, best of 3: 3.3 usec per loop

While optimizing stuff is nice, I'm not sure there's a use case here. Does it significantly speed up a real-world workload you're having?

No, I do not think that any application will significantly speeded up.
In fact, it is not optimization, and getting rid of the apparent pessimization. In addition to increasing the speed, memory fragmentation is reduced.
The patch has a minimum size, the new code is not larger and not more complex than the old one, it is similar to code already used in this file, there are small nonconditional advantages. I see no reason not to accept the changes.

A few comments:
(1) The patch appears to assume that a Unicode string created with PyUnicode_New(size, 127) will have 'kind' PyUnicode_1BYTE_KIND. While this might be true in the current implementation, I don't know whether this is guaranteed in general. Martin, any comments on this?
(2) The patch doesn't compile with '--with-pydebug': there's a reference to the (now) undefined variable 'buffer' in one of the asserts.
(3) The overflow check looks as though it needs to be reworked.

> (1) The patch appears to assume that a Unicode string created with PyUnicode_New(size, 127) will have 'kind' PyUnicode_1BYTE_KIND. While this might be true in the current implementation, I don't know whether this is guaranteed in general. Martin, any comments on this?
The same assumption is used above in long_to_decimal_string(). I added
the same assert and changed maxchar to 'f'.
> (2) The patch doesn't compile with '--with-pydebug': there's a reference to the (now) undefined variable 'buffer' in one of the asserts.
Fixed.
> (3) The overflow check looks as though it needs to be reworked.
I was left an old constraint (it is enough), but it really can be
weakened (in fact, it can be so weakened in the current code).
Thank you for the comments and the found error.

Thanks for the updates.
> The same assumption is used above in long_to_decimal_string(). I added
> the same assert and changed maxchar to 'f'.
I think 'x' would be more appropriate. :-)

> I think 'x' would be more appropriate. :-)
Oops. You are right, of cause.

> (1) The patch appears to assume that a Unicode string created with
> PyUnicode_New(size, 127) will have 'kind' PyUnicode_1BYTE_KIND.
> While this might be true in the current implementation, I don't know
> whether this is guaranteed in general. Martin, any comments on
> this?
There is a guarantee that the shortest form must always be used.
So as long as the Unicode representation doesn't fundamentally change
again, this property is indeed guaranteed.

> There is a guarantee that the shortest form must always be used.
Okay, sounds good. Thanks.

New changeset dcd3344b6d5b by Mark Dickinson in branch 'default':
Issue #14339: Improve speed of bin, oct and hex builtins. Patch by Serhiy Storchaka (with minor modifications).
http://hg.python.org/cpython/rev/dcd3344b6d5b 

Thanks for the patch. I made some minor changes, notably moving the overflow check closer to where it's needed, moving some comments around, and removing a (possibly inappropriate) PyErr_NoMemory call.

This should have waited until Serhiy submits a contributor form. Serhiy, can you please do this soon? Else I'll have to revert the change.

Aargh. Sorry, yes. Serhiy, can you do this? The form can be found at:
http://www.python.org/psf/contrib/contrib-form-python/ 

Whoops; that looks like a slightly older version of the form. I think the correct one is:
http://www.python.org/psf/contrib/contrib-form/ 

I can only do this tomorrow.

2.100 - v = PyUnicode_DecodeASCII(p, &buffer[sz] - p, NULL);
...
 2.104 + assert(p == PyUnicode_1BYTE_DATA(v));
 2.105 return v;
 2.106 }
You may call assert(_PyUnicode_CheckConsistency(v, 1)) to ensure that the newly created string is "consistent" (see the function for the details).

Serhiy: what's the status of your contributor form? Note that you can also fax it, or scan it and send it by email.

> You may call assert(_PyUnicode_CheckConsistency(v, 1)) to ensure
> that the newly created string is "consistent" (see the function
> for the details).
Done in the following changeset:
changeset: 76560:3bdcf0cab164
parent: 76558:5fea362b92fc
user: Victor Stinner <victor.stinner@gmail.com>
date: Thu Apr 26 00:37:21 2012 +0200
files: Objects/longobject.c
description:
long_to_decimal_string() and _PyLong_Format() check the consistency of newly
created strings using _PyUnicode_CheckConsistency() in debug mode

I sent the signed form. Martin, sorry for the delay. Mark, sorry, that
involuntarily let you down.

Serhiy: thanks for submitting the form! No need to apologise: it was my bad for making the commit prematurely.
And now that I see that all-important asterisk next to your name, I'll reclose the issue. :-)