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:
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.)