Pre-PEP: UTF-8 String Representation

Ideas
1

I am considering using UTF-8 as Unicode’s internal representation. The potential benefits are:

  • PEP 393’s Flexible String Representation (FSR) is an implementation detail and is not part of the Stable ABI. Some extension modules use the fastest available APIs for performance reasons, which makes moving to the Stable ABI harder. Eliminating the overhead of creating a UTF-8 cache could help encourage Stable ABI adoption.
  • Python is a glue language. C, C++, and Rust have many libraries that process UTF-8 efficiently, but supporting FSR requires hand-written code.
  • UTF-8 can use less memory for large strings when only some characters require the 4-byte kind.

Reference implementation

Specification

  • Ordinary non-ASCII strings retain a UTF-8 representation. The PEP 393 fixed-width representation (FSR) is created and retained only when needed.
  • Lone surrogates are preserved internally using surrogatepass, without changing Python-level semantics such as string length and indexing.
  • Strings under construction with PyUnicode_New() continue to use a writable FSR.
  • Many paths, including string operations, UnicodeWriter, codecs, and JSON, have been changed to process UTF-8 directly or read characters sequentially.
  • PyUnicode_KIND() returns the width of the fixed-width representation. PyUnicode_DATA() and the various *_DATA() functions create the FSR lazily, so they may return NULL if memory is exhausted.
  • PyUnicode_READ_CHAR() and PyUnicode_ReadChar() normally create an FSR cache and read from it. If memory is exhausted, they fall back to scanning the UTF-8 representation. PyUnicode_READ(), which takes a pointer, has no such fallback.
  • Writes are limited to construction buffers created by PyUnicode_New(). Calling PyUnicode_WriteChar(), PyUnicode_Fill(), or PyUnicode_CopyCharacters() on a string whose primary representation is UTF-8 calls abort(). A UTF-8 representation is generated for construction-buffer strings when they are read.
  • PyUnicode_New() and the write APIs will be deprecated. When these APIs are removed in the future, we plan to maintain O(1) random access using a more efficient position table, similar to PyPy’s.

Open questions

  • PyUnicode_DATA() currently cannot fail. In this implementation, it can return NULL. Extension modules that do not check for NULL would likely crash immediately, for example with a segmentation fault. Is there a better migration path?
  • The current implementation hashes the UTF-8 representation directly, so hash(s) == hash(s.encode()). Should we adjust the string hash to distinguish it from the bytes hash, given that a dictionary may contain both str and bytes keys?
2 Likes
2

Ok, I have multiple questions :sweat_smile:

This change is scary for C extensions. C extensions are not designed to support PyUnicode_DATA() failure. They will start crashing if PyUnicode_DATA() returns NULL on a memory allocation failure.

str[int] access. Since CPython was created, str[int] always have a complexity of O(1). If I recall correctly, PyPy uses UTF-8 internally and creates a cache on the first str[int] (O(n) complexity), so following str[int] are O(1). So you plan to create such cache lazily at the first str[int] access?

Read C API. Since 2012 (Python 3.3 with PEP 393), the most efficient way to iterate on Python str characters is:

int kind = PyUnicode_KIND(strobj);
const void *data = PyUnicode_DATA(strobj);
Py_ssize_t len = PyUnicode_GET_LENGTH(strobj);
for (Py_ssize_t pos = 0; pos < len; pos++ {
    Py_UCS4 ch = PyUnicode_READ(kind, data, pos);
    ...
}

What is the most efficient way to iterate on characters with your change? Also, is there a way to have an efficient implementation which works on FSR (Flexible String Representation) and UTF-8? Or someone needs to have two different code paths?

I suppose that using the FSR API on the UTF-8 storage will be inefficient, since it has to duplicate the string in the FSR format.

In 2024, I proposed PEP 756 “Add PyUnicode_Export() and PyUnicode_Import() C functions” which is supposed to abstract the internal string storage and let the caller uses the most efficient implementation depending on the storage: Py_UCS1, Py_UCS2, Py_UCS4 or UTF-8. Sadly, this PEP got rejected.

Note: I’m aware of the generic PyUnicode_ReadChar() and PyUnicode_READ_CHAR() but they are less efficient than PyUnicode_READ().

I don’t see the need to create a FSR cache. Why not iterating on UTF-8 characters instead?

I just proposed to soft deprecate them: Soft deprecate PyUnicode C API modifying “immutable” str objects. I’m fine with a hard deprecation if Python switches to UTF-8 storage.

I suppose that the replacement is to use PyUnicodeWriter API.

Write C API.

I designed PyUnicodeWriter with the idea in mind that Python may change its internal storage one day. That’s why PyUnicodeWriter_Create() only takes a length in characters, and not the “maximum character” as PEP 393 PyUnicode_New() does.

I just proposed adding PyUnicodeWriter to the limited C API. The pythoncapi-compat project provides PyUnicodeWriter on Python 3.6-3.13 by using the old private implementation (_PyUnicodeWriter). So it’s possible to use PyUnicodeWriter on old Python versions by using pythoncapi-compat.

But PyUnicodeWriter doesn’t fit all use cases. Some functions really want to work on an array of characters (ex: Py_UCS4 array), or create a UTF-8 string. For these functions, PyUnicode_FromKindAndData() and PyUnicode_FromString() can be used.

3 Likes
3

Yes. It would be ideal if there were a way to require callers to check the return value for NULL, but I don’t know of a good way to enforce that.

If there is a better approach than deprecating PyUnicode_DATA() and adding something like PyUnicode_DATA_MUST_CHECK_RETURN_VALUE_IS_NOT_NULL(), I’d like to know.

I think this is the most important issue to resolve before writing the PEP.

I plan to use FSR for that instead at first. Operations such as str[i] and str[i:j] would create an FSR cache and construct the result from that.

When we eventually remove the FSR cache, I would like to implement a cache using the same approach as PyPy.

In many languages, including Rust, I think that if you can obtain a pointer to the UTF-8 data with PyUnicode_AsUTF8AndSize(), you can iterate over code points more efficiently than with an API that requires an actual function call for every code point.
I also plan to add an API that returns UTF-8 even when the string contains surrogates, rather than raising an error. Codex named it _PyUnicode_GetPrimaryUTF8(), but it should probably be given a more appropriate name and made public by the time I write the PEP.

For languages that do not provide such functionality, Python should also provide a UTF-8 iteration API.

/* Allocation-free iteration over immutable Unicode objects. Start at zero;
   position is an opaque cursor (UTF-8 bytes or FSR code points). Only reuse
   positions produced for the same object. Next returns 1 on success, or 0
   at end without changing position or ch. The caller keeps str alive. */
PyAPI_FUNC(int) _PyUnicode_Next(PyObject *str, Py_ssize_t *position, Py_UCS4 *ch);

This function still starts with an underscore because I haven’t yet decided whether this exact signature should become a public API. By the time I write the PEP, I plan to settle on the name and signature and make it a public API.

Unless you use the deprecated PyUnicode_New(), UTF-8 data is always available, so I think it should be sufficient to provide an efficient option specifically for UTF-8.

With that approach, the time complexity of code like the following would become significantly worse. I think this would be a much bigger backward-compatibility issue than a crash caused by a memory allocation failure, which should be extremely rare.

for (Py_ssize_t i=0; i<PyUnicode_GET_LENGTH(o); i++) {
    Py_UCS4 ch = PyUnicode_READ_CHAR(o, i);
    ...
}

Yes. For use cases such as converting numbers to strings, the output is ASCII, so this is straightforward. In other cases, however, a temporary UCS4 array would probably be necessary.

There will be use cases that become faster with a UTF-8 internal representation and others that become slower, so I cannot claim that it will always improve performance. However, PyPy has already implemented this approach, so I don’t expect any catastrophic performance regressions.

I also believe it would significantly improve interoperability with other languages, especially Rust.

4

Have you considered adding UTF-8 as an alternative representation? Strings created by PyUnicode_FromKindAndData and other current APIs would have FSR; ones created by PyUnicode_FromString would have UTF-8, and the other representation would be generated on demand?

One issue I see that some extensions use the PyUnicodeObject struct. Should that be deprecated/removed before it’s changed?

An option is to make PyUnicode_DATA/PyUnicode_KIND/etc. themselves fail with Py_FatalError on allocation failure, rather than return NULL and let user code crash.
Then add new fallible versions for these functions, and deprecate the existing ones.

It’s probably not worth it to optimize dicts that contain both str and bytes with the same contents.
Note hash(s) == hash(s.encode()) is currently true for CPython’s ASCII strings, and I don’t think anyone’s complaining.

1 Like
5

Yes. We need to decide whether hash() is computed from UTF-8 or FSR, but it is still possible to defer generating UTF-8 for Unicode objects created from FSR. For example, in workloads that repeatedly slice small pieces from the beginning of a large string, avoiding UTF-8 generation could provide a significant performance improvement.

I updated the proof-of-concept implementation to generate the UTF-8 representation lazily.

That is also something we need to consider in the long term, but I don’t think it is essential as long as projects like PyObjC are willing to keep up with CPython’s evolution.

Implemented.

You are right.

6

I had Codex investigate how the top 4,000 packages on PyPI use the PEP 393 APIs.

For example, libraries like regex have algorithms that assume a fixed-width representation and repeatedly access the FSR, so even if we provide a Release() API, we probably should not free the FSR immediately.

I don’t think PyUnicode_Import is necessary. Extension modules have no way to know which representation is the most efficient for a particular Python implementation. UnicodeWriter would be a better fit.

PyUnicode_Export may be a good fit for extension modules that need the best possible performance. On the other hand, some extension modules, such as regex, require UCS.
So rather than guaranteeing that “No memory is copied and no conversion is done,” I think that if UTF-8 is not among the requested formats, the UCS representation should be generated lazily.

7

I will adjust PyObjC for changes to the PyUnicodeObject layout as needed.

Longer term I’d like to find a solution that doesn’t require me to poke at the internals of strings,

8

Compilers (and newer C/C++ standards) have the [[nodiscard]] attribute for this.

This could be added to PyUnicode_DATA (so C extensions using modern compilers & newest python will start generating warnings, so that consumers can be fixed), and 1 (or N) python versions later, you actually begin returning NULL in some cases.

9

Which kind of API (abstraction) do you need for that?

10

Skimming through the list of users, a good chunk are indirectly via Cython, which means a good chunk can be fixed fairly easily just by Cython adapting.

I think whatever you do indexing an arbitrary element is likely to be a little worse than it is now (even if you keep it O(1)). In general I guess it’s not a hugely common thing to do to strings. I think Cython currently transforms iteration over a string into for i in range(len(s)): ch = s[i]. That’d probably have to change but obviously it isn’t too hard to get the next element of a utf-8 string.

So nothing about this is seeming like a disaster from a Cython maintainer point of view. Although “not a disaster” isn’t a hugely compelling argument either for or against.

1 Like
11

I don’t think nodiscard quite does what you want. In that it doesn’t force you to check against NULL but it just forces you to use the result in some way.

If you call PyUnicode_DATA and don’t use the result then it’s pretty pointless but likely to be “safe”

12

I think we need an API to create an instances of Unicode subclass from UTF-8, UTF-16, and UTF-32. For PyObjC, it would be UTF-16.

PyObject *
_PyUnicode_FromUTF16WithType(
    PyTypeObject *type, /* Unicode subclass */
    const uint16_t *data,
    Py_ssize_t units);
13

The short answer: An API to create an instance of a string object using a subclass of str. That way I can pass in a subclass with an additional C field in the value struct.

The long answer needs a separate thread as it’s off topic for this discussion. PyObjC uses a subclass of str because there was (and likely is) no way to have a class that behaves like a string, but isn’t a subclass of str. Having something like __index__ for string-like types could help, but I haven’t thought through the implications of that and if I’d be the only user of such an API.