_PyAccu API

Issue #12778: In 2011, Antoine Pitrou found a performance issue in the JSON serializer when serializing many small objects: it used way too much memory for temporary objects compared to the final output string.

The JSON serializer used a list of strings and joined all strings at the end of create a final output string. Pseudocode:

def serialize():
    pieces = [serialize(item) for item in self]
    return ''.join(pieces)

Antoine introduced an accumulator compacting the temporary list of "small" strings and put the result in a second list of "large" strings. At the end, the list of "large" strings was also compacted to build the final output string. Pseudo-code:

def serialize():
    small = []
    large = []
    for item in self:
        small.append(serialize(item))
        if len(small) > 10000:
            large.append(''.join(small))
            small.clear()
    if small
        large.append(''.join(small))
    return ''.join(large)

The threshold of 10,000 strings is justified by this comment:

/* Each item in a list of unicode objects has an overhead (in 64-bit
 * builds) of:
 *   - 8 bytes for the list slot
 *   - 56 bytes for the header of the unicode object
 * that is, 64 bytes.  100000 such objects waste more than 6MB
 * compared to a single concatenated string.
 */

Issue #12911: Antoine Pitrou found a similar performance issue in repr(list), and so proposed to convert its accumular code into a new private _PyAccu API. He added the _PyAccu API to Python 2.7.5 and 3.2.3. Title of te repr(list) change: "Fix memory consumption when calculating the repr() of huge tuples or lists".

The _PyUnicodeWriter API

_PyBytesWriter API: first try, big fail

Since Python was much faster with _PyUnicodeWriter, I expected to get good speedup with a similar API for bytes. The graal would be to share code for bytes and Unicode (Spoiler alert! I reached this goal, but only for a single function: format an integer to decimal).

My first attempt of a _PyBytesWriter API was in 2013: Issue #17742: Add _PyBytesWriter API. But quickly, I noticed with microbenchmarks that my change made Python slower! I spent hours to understand why GCC produced less efficient machine code. When I started to dig the "strict aliasing" optimization issue, I realized that I reached a deadend.

Extract of the _PyBytesWriter structure:

typedef struct {
    /* Current position in the buffer */
    char *str;

    /* Start of the buffer */
    char *start;

    /* End of the buffer */
    char *end;

    ...
} _PyBytesWriter;

The problem is that GCC emited less efficient machine code for the C code (see my msg187595):

while (collstart++<collend)
    *writer.str++ = '?';

For the writer.str++ instruction, the new pointer value is written immediatly in the structure. The pointer value is read again at each iteration. So we have 1 LOAD and 1 STORE per iteration.

GCC emits better code for the original C code:

while (collstart++<collend)
    *str++ = '?';

The str variable is stored in a register and the new value of str is only written once, at the end of loop (instead of writing it at each iteration). The pointer value is only read once before the loop. So we have 0 LOAD and 0 STORE (related to the pointer value) in the loop body.

It looks like an aliasing issue, but I didn't find how to say to GCC that the new value of writer.str can be written only once at the end of the loop. I tried the __restrict__ keyword: the LOAD (get the pointer value) was moved out of the loop. But the STORE was still in the loop body.

I wrote to gcc-help: Missed optimization when using a structure, but I didn't get any reply. I just gave up.

_PyBytesWriter API: new try, the good one

In 2015, I created the Issue #25318: Add _PyBytesWriter API to optimize Unicode encoders. I redesigned the API to avoid the aliasing issue.

The new _PyBytesWriter doesn't contain the char* pointers anymore: they are now local variables in functions. Instead, functions of API requires two parameters: the bytes writer and a char* parameter. Example:

PyObject * _PyBytesWriter_Finish(_PyBytesWriter *writer, char *str)

The idea is to keep char* pointers in functions to keep the most efficient machine code in loops. The compiler doesn't have to compute complex aliasing rules to decide if a CPU register can be used or not.

_PyBytesWriter features:

• Optional overallocation: overallocate the buffer by 25% on Windows and 50% on Linux. Same idea than _PyUnicodeWriter.
• Support bytes and bytearray type as output format to avoid an expensive memory copy from bytes to bytearray.
• Small buffer of 512 bytes allocated on the stack to avoid the need of a buffer allocated on the heap, before creating the final bytes/bytearray object.

A _PyBytesWriter structure must always be allocated on the stack (to get fast memory allocation of the smaller buffer).

While _PyUnicodeWriter has a 5 functions and 1 macro to write a single character, write strings, write a substring, etc. _PyBytesWriter has a single _PyBytesWriter_WriteBytes() function to write a string, since all other writes are done directly with regular C code on char* pointers.

The API itself doesn't make the code faster. Disabling overallocation on the last write and the usage of the small buffer allocated on the stack may be faster.

In Python 3.6, I optimized error handlers on various codecs: ASCII, Latin1 and UTF-8. For example, the UTF-8 encoder is now up to 75 times as fast for error handlers: ignore, replace, surrogateescape, surrogatepass. The bytes % int instruction became between 30% and 50% faster on a microbenchmark.

Later, I replaced char* type with void* to avoid compiler warnings in functions using Py_UCS1* or unsigned char*, unsigned types.