1

Python is one of the few languages to support a string data type of code points (Unicode Scalar Values). I'm also wanting to creating a language that has this same characteristic, but I need to understand how Python optimizes such representation.

There is a PEP about this: https://peps.python.org/pep-0393/ But I don't understand the C code entirely. How do they save space, when like, characters of mixed range appear together in a string? For example, say a string with millions of characters are all limited to Latin-1, except one; will they end up storing every character in the RAM with 4 bytes or will they split the string somehow? Any ideas on how they optimize strings?

2
  • You could find out at least part of the answer by creating such a mixed string in Python and checking its byte size. My hunch is that it behaves as you fear; the million-character string will use 4 bytes per character. It's hard to do it differently in your language if you want to treat strings as arrays of code points; you may be able to use a UTF-8 internal representation if you don't promise random access to arbitrary code point indices. Dec 22, 2022 at 16:18
  • @Hans-MartinMosner Well, I'm not that familiar with RAM inspection.
    – Hydroper
    Dec 22, 2022 at 16:43

2 Answers 2

3

The Python implementation chooses simplicity over aggressive optimisation. We can examine that using sys.getsizeof:

>>> import sys
>>> a = 'a' * 999_999
>>> sys.getsizeof(a)  # 1 byte per character, plus some overhead
1000048
>>> cry_laugh = '\U0001f602'  # cry-laughing emoji
>>> sys.getsizeof(cry_laugh)  # mostly overhead
80
>>> sys.getsizeof(a + cry_laugh)  # 4 bytes per character, plus some overhead
4000076

Exact details may be different based on platform or Python version.

If you want more space-efficiency for your language, you can consider using UTF-8 natively, like some other languages have chosen.

The advantage of that is that the optimisation you are looking for comes for free.

The disadvantage, and the main reason CPython uses their own method, is that indexing is no longer cheap.

my_string[some_index] is O(1) in Python, because it can basically index strings the same way C indexes arrays: In pseudocode, it can read the memory at my_string.data_start + some_index * my_string.bytes_per_character. This stems from back when Python strings were bytestrings, and there's been a lot of code written that depends on that performance.

UTF-8, however, can't guarantee that, because not every code point has the same length. To get the nth code point in a UTF-encoded string, you need to iterate over n code points to find the correct offset.

This does not have to be a deal breaker, if your users expect that behaviour. It just means that instead of writing code like:

for i in range(len(my_string)):  # un-Pythonic but still fast in CPython
    do_something_with(my_string[i])

you'll want to encourage users to write code like:

for code_point in my_string:  # fast both in CPython and runtimes using UTF-8
    do_something_with(code_point)

I recommend not providing an index operator to strings, for example, if it's going to be slower than O(log(n))

2
  • Thanks for the answer and memory analysis (can't upvote). It seems like it's worthier to stick to UTF-8 as it'll be much easier to optimize it. I really don't mind the overhead from mapping code-point indexes into UTF-8 indexes. I'll change some of the docs in my language about the string data type.
    – Hydroper
    Dec 22, 2022 at 17:08
  • GraalPy uses Truffle Strings, which support string compaction, lazy repetition, and lazy concatenation. So, 'a' should only use one octet for the actual backing store (plus overhead), but interestingly, 'a' * 999_999 should also be tiny, not use 999999 octets. The emoji will use 4 octets (plus overhead), and the concatenation of the two strings should again only use a small amount of memory. I haven't checked this, but this is my understanding of how Truffle Strings work. So, that's an example of a Python implementation where the string in your example should have much lower memory usage. Dec 22, 2022 at 21:06
3

You used the plural in your title:

String representation in Python runtimes

But both in your question as well as in Jasmijn's answer, the only runtime that is considered is CPython.

Since you are specifically asking about optimizations, I feel that CPython might not be the best choice. CPython has many goals, portability, clarity, simplicity, fast startup times, etc. but I wouldn't call it a high-performance implementation. Therefore, I believe it would make sense to look at some implementations that do have high performance as one of their goals.

I remember that PyPy, at least at some point in the past, experimented with Ropes. Ropes give you "almost O(1)" indexing. Technically, Ropes are tree-structured, but they are very shallow. With Ropes, different sub-Ropes can have different representations, so you could split your string into parts that contain only ASCII characters and encode them as, well, ASCII (or alternatively, parts that contain only characters from a single 8-bit character set and use the native character encoding for that character set), parts that contain only characters in the BMP and encode them as UTF-16, and parts that contain characters outside the BMP and encode them as UTF-32.

Ropes would also allow some operations to be very fast that are traditionally slow in Python.

GraalPy is currently in the process of being converted to Truffle Strings, which are a Highly Optimized Cross-Language String Implementation:

https://youtu.be/wI-qcZUA2vA

If you are not familiar with the Truffle Language Implementation Framework, it does have some similar goals to RPython, namely being high-performance, easy to use, cross-language (i.e. you can use Truffle to implement many languages), allow you to use a high-level language (RPython in the case of RPython, Java or any other JVM language in the case of Truffle), allowing you to only write an interpreter and get a JIT compiler "for free", and be a true "framework", providing you with many ready-made pieces such as garbage collectors, FFI, debugger, profiler, data types, operations, etc.

Unlike RPython, Truffle not only allows you to easily implement many programming languages, but also to run a single application written in many different languages in a single process with cross-language optimizations such as inlining, and high-performance high-fidelity interoperability between the languages.

One way of achieving this is providing common data types such as arrays, lists, maps, dictionaries, sets, and objects, method resolution, inheritance, lambdas, closures, etc. that can be used by all languages. And, yes, also strings.

Which poses a couple of challenges – if you want a single string datatype to be able to be used by many languages, and to be passed back and forth between the languages and always behave like a native string from that language, you have to consider that

  • In Ruby, strings are mutable, in many other languages, they are immutable.
  • In Python and ECMAScript, strings have a fixed encoding, in Ruby and R, they can have many encodings.
  • Even though Python and ECMAScript agree that strings should have fixed encoding, they don't agree on what that encoding should be: in Python, it is UTF-32, in ECMAScript, it is UTF-16.
  • Even though strings in both Ruby and R can have many encodings, they work very differently: R simply uses the system encoding, so even though strings can have many different encodings, all strings within the same runtime always have only one and the same encoding, and R itself does not actually care about the encoding, whereas in Ruby, different strings in the same runtime can have different encodings, and each string is aware of its own encoding, and is able to convert itself to other encodings and to figure out the most efficient compatible encoding for operations that involve multiple strings. Also, IO streams and Regexps are encoding-aware as well.

Truffle Strings manage to support all of these different use cases (well, almost all, Mutable Truffle Strings are not interoperable with languages that only support immutable Truffle Strings, but it is very cheap to convert between them), at very high performance and high degrees of interoperability.

Truffle Strings are automatically compacted, i.e. if a UTF-16 string consists only of code points in ASCII or Latin-1, it will actually only take up one octet per character (it will essentially be stored in-memory as ISO 8859-1 but will logically still present itself as UTF-16), and UTF-32 strings support two levels of compaction (Latin-1 and UCS-2). Truffle Strings support lazy views (i.e. zero-copy substring operations), lazy views into native memory (i.e. zero-copy string interop with C extensions), lazy concatenation, and lazy repetition.

It is important to remember that strings don't exist in a vacuum. E.g. Ruby's encoding-aware strings would be useless without Ruby's encoding-aware I/O and encoding-aware text processing, especially regexp. Likewise, Truffle Strings work well with TRegex, Truffle's regex implementation. (BTW, TRegex is very cool in itself, since it is implemented as just another Truffle language. This means it benefits from automatically being JIT-compiled, cross-language optimizations, and all that other stuff. For example, regex can be inlined into subroutines and vice-versa.)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.