Various notes: * PyUnicode_READ() is slower than reading a Py_UNICODE array. * Some decoders unroll the main loop to process 4 or 8 bytes (32 or 64 bits CPU) at each step.

I am interested if you know other tricks to optimize Unicode strings in Python, or if you are interested to work on this topic.

Beyond creation, the most frequent approach is to specialize loops for all three possible width, allowing the compiler to hard-code the element size. This brings it back in performance to the speed of accessing a Py_UNICODE array (or faster for 1-byte strings). A possible micro-optimization might be to use pointer arithmetic instead of indexing. However, I would expect that compilers will already convert a counting loop into pointer arithmetic if the index is only ever used for array access. A source of slow-down appears to be widening copy operations. I wonder whether microprocessors are able to do this faster than what the compiler generates out of a naive copying loop. Another potential area for further optimization is to better pass-through PyObject*. Some APIs still use char* or Py_UNICODE*, when the caller actually holds a PyObject*, and the callee ultimate recreates an object out of the pointers being passed. Some people (hi Larry) still think that using a rope representation for string concatenation might improve things, see #1569040. Regards, Martin

Hi,

 * Use a Py_UCS4 buffer and then convert to the canonical form (ASCII, UCS1 or UCS2). Approach taken by io.StringIO. io.StringIO is not only used to write, but also to read and so a Py_UCS4 buffer is a good compromise.  * PyAccu API: optimized version of chunks=[]; for ...: ... chunks.append(text); return ''.join(chunks).  * Two steps: compute the length and maximum character of the output string, allocate the output string and then write characters. str%args was using it.  * Optimistic approach. Start with a ASCII buffer, enlarge and widen (to UCS2 and then UCS4) the buffer when new characters are written. Approach used by the UTF-8 decoder and by str%args since today.

I ran extensive benchmarks on these 4 methods for str%args and str.format(args). The "two steps" method is not promising: parsing the format string twice is slower than other methods. The PyAccu API is faster than a Py_UCS4 buffer to concatenate a lot of strings, but it is slower in many other cases. I implemented the last method as the new internal "_PyUnicodeWriter" API: resize / widen the string buffer when writing new characters. I implemented more optimizations: * overallocate the buffer to limit the cost of realloc() * write characters directly in the buffer, avoid temporary buffers when possible (it is possible in most cases) * disable overallocation when formating the last argument * don't copy by value but copy by reference if the result is just a string (optimization already implemented indirectly in the PyAccu API) The _PyUnicodeWriter is the fastest method: it gives a speed up of 30% over the Py_UCS4 / PyAccu in general, and from 60% to 100% in some specific cases! I also compared str%args and str.format() with Python 2.7 (byte strings), 3.2 (UTF-16 or UCS-4) and 3.3 (PEP 393): Python 3.3 is as fast as Python 2.7 and sometimes faster! (Whereras Python 3.2 is 10 to 30% slower than Python 2 in general) -- I wrote a tool to run benchmarks and to compare results: https://bitbucket.org/haypo/misc/src/tip/python/benchmark.py https://bitbucket.org/haypo/misc/src/tip/python/bench_str.py Run the benchmark: ./python benchmark.py --file=FILE script bench_str.py Compare results: ./python benchmark.py compare_to FILE1 FILE2 FILE3 ... -- Python 2.7 vs 3.2 vs 3.3: http://bugs.python.org/file25685/REPORT_32BIT_2.7_3.2_writer http://bugs.python.org/file25687/REPORT_64BIT_2.7_3.2_writer http://bugs.python.org/file25757/report_windows7 Warning: For the Windows benchmark, Python 3.3 is compiled in 32 bits, whereas 2.7 and 3.2 are compiled in 64 bits (formatting integers is slower in 32 bits). -- UCS4 vs PyAccu vs _PyUnicodeWriter: http://bugs.python.org/file25686/REPORT_32BIT_3.3 http://bugs.python.org/file25688/REPORT_64BIT_3.3 Victor

On 5/29/2012 3:51 PM, Nick Coghlan wrote:

On Wed, May 30, 2012 at 8:44 AM, Victor Stinner wrote:

...

I also compared str%args and str.format() with Python 2.7 (byte strings), 3.2 (UTF-16 or UCS-4) and 3.3 (PEP 393): Python 3.3 is as fast as Python 2.7 and sometimes faster! (Whereras Python 3.2 is 10 to 30% slower than Python 2 in general) Very cool news!

Cheers, Nick.

Very cool indeed! Thanks, Victor. I have programs that are just full of formatting operations, that will benefit from this work.

...

The "two steps" method is not promising: parsing the format string twice is slower than other methods.

The "1.5 steps" method is more promising -- first parse the format string in an efficient internal representation, and then allocate the output string and then write characters (or enlarge and widen the buffer, but with more information in any case). The internal representation can be cached (as for struct module) that for a repeated formatting will reduce the cost of parsing to zero.

I implemented something like that, and it was not efficient and very complex. See for example the (incomplete) patch for str%args attached to the issue #14687: http://bugs.python.org/file25413/pyunicode_format-2.patch IMO this approach is less efficient than the "Unicode writer" approach because: - you have to create many substrings or temporary strings in the first step, or (worse) compute each argument twice: the writer approach is more efficient here because it avoids computing substrings and temporary strings - you have to parse the format string twice, or you have to write two versions of the code: first create a list of items, then concatenate items. The PyAccu method concatenates substrings at the end, it is less efficient than the writer method (e.g. it has to create a string of N fill characters to pad to WIDTH characters). - the code is more complex than the writer method (which is very similar to what is used in Python 2.7 and 3.2) I wrote a much more complex patch for str%args to remember variables of the first step to avoid most of the parsing work in the second step. The patch was very complex and hard to maintain. I chose to not publish it and try another approach (the Unicode writer). Note: I'm talking about str%args and str.format(args), the Unicode writer is not the most efficient method for *any* function creating strings! Victor