Hi,

CPython has two private APIs for that: _PyUnicodeWriter (str) and _PyBytesWriter (bytes/bytearray).

--

_PyUnicodeWriter is an append-only API to build a string. The API is designed for the CPython implementation of Unicode strings. The first call requires to specified the maximum code point. There is a micro-optimization for "%s" % "abc" and "{}".format("abc"): it stores the string "abc" as "read-only" and only create a new buffer at the second append. Internally, it uses an overallocated Python str object.

For best performance, the overallocation can be disabled before the last append. Overallocation when it's not needed can has a significant impact on micro-benchmarks on short strings (1-100 characters): it can require an additional memory copy since the result must be resized to the exact size.

I wrote this class to reduce the slowdown introduced by the initial implementation of the PEP 393 (flexible strings: ASCII, UCS1, UCS2 or UCS4): be as fast or faster than Python 2.

The overallocation factor depends on the platform:

#ifdef MS_WINDOWS /* On Windows, overallocate by 50% is the best factor */ # define OVERALLOCATE_FACTOR 2 #else /* On Linux, overallocate by 25% is the best factor */ # define OVERALLOCATE_FACTOR 4 #endif

--

For bytes, there is _PyBytesWriter which provides a "char *" pointer. It's basically a thin wrapper to control overallocation. In CPython, it internally uses a Python bytes (or bytearray) object, resized on demand, to avoid memory copies when returning the result object (don't allocate a buffer with malloc, from a bytes object from it, and delete the temporary buffer).

It uses a short buffer of 512 bytes allocated on the stack, to avoid an realloc() for short strings.

Overallocation can also be disabled before the last append.

The buffer allocated on the stack requires to expose the buffer size and the structure as part of the ABI, not sure if it's possible in HPy which tries to abstract implementation details.

--

See also the article that I wrote on it: https://vstinner.github.io/pybyteswriter.html

I kept a few microbenchmarks on str%args and str.format(): https://github.com/vstinner/pymicrobench

• bench_bytes_format_int.py
• bench_str_format.py
• bench_str_format_keywords.py

I spent time micro-optimize most common Python operations on strings using these APIs ;-)

--

/* The _PyBytesWriter structure is big: it contains an embedded "stack buffer". A _PyBytesWriter variable must be declared at the end of variables in a function to optimize the memory allocation on the stack. */ typedef struct { /* bytes, bytearray or NULL (when the small buffer is used) */ PyObject *buffer;

/* Number of allocated size. */
Py_ssize_t allocated;

/* Minimum number of allocated bytes,
   incremented by _PyBytesWriter_Prepare() */
Py_ssize_t min_size;

/* If non-zero, use a bytearray instead of a bytes object for buffer. */
int use_bytearray;

/* If non-zero, overallocate the buffer (default: 0).
   This flag must be zero if use_bytearray is non-zero. */
int overallocate;

/* Stack buffer */
int use_small_buffer;
char small_buffer[512];

} _PyBytesWriter;

/* Initialize a bytes writer

By default, the overallocation is disabled. Set the overallocate attribute to control the allocation of the buffer. */ PyAPI_FUNC(void) _PyBytesWriter_Init(_PyBytesWriter *writer);

/* Get the buffer content and reset the writer. Return a bytes object, or a bytearray object if use_bytearray is non-zero. Raise an exception and return NULL on error. */ PyAPI_FUNC(PyObject *) _PyBytesWriter_Finish(_PyBytesWriter *writer, void *str);

/* Deallocate memory of a writer (clear its internal buffer). */ PyAPI_FUNC(void) _PyBytesWriter_Dealloc(_PyBytesWriter *writer);

/* Allocate the buffer to write size bytes. Return the pointer to the beginning of buffer data. Raise an exception and return NULL on error. */ PyAPI_FUNC(void*) _PyBytesWriter_Alloc(_PyBytesWriter *writer, Py_ssize_t size);

/* Ensure that the buffer is large enough to write *size* bytes. Add size to the writer minimum size (min_size attribute).

str is the current pointer inside the buffer. Return the updated current pointer inside the buffer. Raise an exception and return NULL on error. */ PyAPI_FUNC(void*) _PyBytesWriter_Prepare(_PyBytesWriter *writer, void *str, Py_ssize_t size);

/* Resize the buffer to make it larger. The new buffer may be larger than size bytes because of overallocation. Return the updated current pointer inside the buffer. Raise an exception and return NULL on error.

Note: size must be greater than the number of allocated bytes in the writer.

This function doesn't use the writer minimum size (min_size attribute).

See also _PyBytesWriter_Prepare(). */ PyAPI_FUNC(void*) _PyBytesWriter_Resize(_PyBytesWriter *writer, void *str, Py_ssize_t size);

/* Write bytes. Raise an exception and return NULL on error. */ PyAPI_FUNC(void*) _PyBytesWriter_WriteBytes(_PyBytesWriter *writer, void *str, const void *bytes, Py_ssize_t size);

/* --- _PyUnicodeWriter API ----------------------------------------------- */

typedef struct { PyObject *buffer; void *data; enum PyUnicode_Kind kind; Py_UCS4 maxchar; Py_ssize_t size; Py_ssize_t pos;

/* minimum number of allocated characters (default: 0) */
Py_ssize_t min_length;

/* minimum character (default: 127, ASCII) */
Py_UCS4 min_char;

/* If non-zero, overallocate the buffer (default: 0). */
unsigned char overallocate;

/* If readonly is 1, buffer is a shared string (cannot be modified)
   and size is set to 0. */
unsigned char readonly;

} _PyUnicodeWriter ;

/* Initialize a Unicode writer. *

• By default, the minimum buffer size is 0 character and overallocation is
• disabled. Set min_length, min_char and overallocate attributes to control
• the allocation of the buffer. */ PyAPI_FUNC(void) _PyUnicodeWriter_Init(_PyUnicodeWriter *writer);

/* Prepare the buffer to write 'length' characters with the specified maximum character.

Return 0 on success, raise an exception and return -1 on error. */ #define _PyUnicodeWriter_Prepare(WRITER, LENGTH, MAXCHAR)
(((MAXCHAR) <= (WRITER)->maxchar
&& (LENGTH) <= (WRITER)->size - (WRITER)->pos)
? 0
: (((LENGTH) == 0)
? 0
: _PyUnicodeWriter_PrepareInternal((WRITER), (LENGTH), (MAXCHAR))))

/* Don't call this function directly, use the _PyUnicodeWriter_Prepare() macro instead. */ PyAPI_FUNC(int) _PyUnicodeWriter_PrepareInternal(_PyUnicodeWriter *writer, Py_ssize_t length, Py_UCS4 maxchar);

/* Prepare the buffer to have at least the kind KIND. For example, kind=PyUnicode_2BYTE_KIND ensures that the writer will support characters in range U+000-U+FFFF.

Return 0 on success, raise an exception and return -1 on error. */ #define _PyUnicodeWriter_PrepareKind(WRITER, KIND)
(assert((KIND) != PyUnicode_WCHAR_KIND),
(KIND) <= (WRITER)->kind
? 0
: _PyUnicodeWriter_PrepareKindInternal((WRITER), (KIND)))

/* Don't call this function directly, use the _PyUnicodeWriter_PrepareKind() macro instead. */ PyAPI_FUNC(int) _PyUnicodeWriter_PrepareKindInternal(_PyUnicodeWriter *writer, enum PyUnicode_Kind kind);

/* Append a Unicode character. Return 0 on success, raise an exception and return -1 on error. */ PyAPI_FUNC(int) _PyUnicodeWriter_WriteChar(_PyUnicodeWriter *writer, Py_UCS4 ch );

/* Append a Unicode string. Return 0 on success, raise an exception and return -1 on error. */ PyAPI_FUNC(int) _PyUnicodeWriter_WriteStr(_PyUnicodeWriter *writer, PyObject *str /* Unicode string */ );

/* Append a substring of a Unicode string. Return 0 on success, raise an exception and return -1 on error. */ PyAPI_FUNC(int) _PyUnicodeWriter_WriteSubstring(_PyUnicodeWriter *writer, PyObject *str, /* Unicode string */ Py_ssize_t start, Py_ssize_t end );

/* Append an ASCII-encoded byte string. Return 0 on success, raise an exception and return -1 on error. */ PyAPI_FUNC(int) _PyUnicodeWriter_WriteASCIIString(_PyUnicodeWriter *writer, const char *str, /* ASCII-encoded byte string */ Py_ssize_t len /* number of bytes, or -1 if unknown */ );

/* Append a latin1-encoded byte string. Return 0 on success, raise an exception and return -1 on error. */ PyAPI_FUNC(int) _PyUnicodeWriter_WriteLatin1String(_PyUnicodeWriter *writer, const char *str, /* latin1-encoded byte string */ Py_ssize_t len /* length in bytes */ );

/* Get the value of the writer as a Unicode string. Clear the buffer of the writer. Raise an exception and return NULL on error. */ PyAPI_FUNC(PyObject *) _PyUnicodeWriter_Finish(_PyUnicodeWriter *writer);

/* Deallocate memory of a writer (clear its internal buffer). */ PyAPI_FUNC(void) _PyUnicodeWriter_Dealloc(_PyUnicodeWriter *writer);

/* Format the object based on the format_spec, as defined in PEP 3101 (Advanced String Formatting). */ PyAPI_FUNC(int) _PyUnicode_FormatAdvancedWriter( _PyUnicodeWriter *writer, PyObject *obj, PyObject *format_spec, Py_ssize_t start, Py_ssize_t end);

Victor

On Thu, Jun 10, 2021 at 5:05 PM Antoine Pitrou <antoine@python.org> wrote:

I'll answer with general concerns.

1. A dedicated builder API that allocates the unicode object at the end is really a good idea (PyUnicode_Join is really too slow for high-performance string building)

2. The builder itself should ideally be a stack variable (even if the allocated string payload is malloc'ed)

3. There could be separate builder types:

• UCS1, UCS2 and UCS4 builder types (for when you know the width upfront)
• a dynamic width builder type

4. builders should support presizing and/or reserving more data on the fly

5. builders should support variants of appending with or without implicit reallocation (the latter, for the case where the right size is fully preallocated)

I'm biased, but I suggest you look at Arrow's BufferBuilder API (C++, but should be relatively to do a C equivalent): https://github.com/apache/arrow/blob/master/cpp/src/arrow/buffer_builder.h#L...

It has been serving us well.

Separately from the builder API, there are cases where the data already exists somewhere as a full-blown UTF8 string (this is of course more and more common, since UTF8 is ubiquitous). There should be a fast conversion method from a UTF8 memory area to a unicode object.

Regards

Antoine.

Le 10/06/2021 à 16:48, Antonio Cuni a écrit :

...

Hi all, at the language summit many people told me that the HPy team should try to communicate more with the CPython developers, so let's try :).

In HPy we want to design an API to build bytes/str objects in two steps, to avoid the problem that currently in CPython they are not really immutable.

Before making any proposal, I spent quite a lot of time in researching how the current API are used to construct bytes/str objects, and I summarized my results here: https://docs.hpyproject.org/en/latest/misc/str-builder-api.html I think that my survey could be interesting for the people in this ML, independently of HPy.

That said, I also opened an issue where to discuss concrete proposals for the HPy API to do that: https://github.com/hpyproject/hpy/issues/214

I would be glad to receive comments and suggestions about that, and especially to know whether I missed some important use case in my analysis.

Also, if you think that these kind of mails are off-topic in this ML, please let me know and I'll stop.

Antonio

---

capi-sig mailing list -- capi-sig@python.org To unsubscribe send an email to capi-sig-leave@python.org https://mail.python.org/mailman3/lists/capi-sig.python.org/ Member address: antoine@python.org

---

capi-sig mailing list -- capi-sig@python.org To unsubscribe send an email to capi-sig-leave@python.org https://mail.python.org/mailman3/lists/capi-sig.python.org/ Member address: vstinner@python.org

-- Night gathers, and now my watch begins. It shall not end until my death.