<p>I'm designing a language that I intend to be implemented on the .NET platform. To my understanding, the native string representation uses UTF-16, by storing an array of <code>char</code> (an unsigned 16-bit type) and offering an API that treats each 16-bit code unit as an element.</p>
<p>This isn't the indexing behaviour I want for strings in my language. At the very least, I want to index character-by-character, returning the nth code <em>point</em> from the data - which is different from the nth code <em>unit</em>, because of surrogate pairs.</p>
<p>Given an unknown amount and position of surrogate pairs in the underlying data, it seems that a naive algorithm to index by character would be forced into O(N) performance (i.e., iterating over the code units until there are enough to make N code points). <strong>Is it possible to do better than this</strong>, perhaps by recording auxiliary data or using a more complex data structure? Or is resorting to UCS-32 or another such &quot;flat&quot; encoding the only viable option?</p>
<p>Is it possible to support better-than-O(N) indexing for <em>grapheme clusters</em> (notwithstanding the work required to identify the clusters)?</p>
<p>What approaches are taken by real-world languages to store and use such string data?</p>
<p>This is not a duplicate of <a href="https://langdev.stackexchange.com/questions/1493">How have modern language designs dealt with Unicode strings?</a> or <a href="https://langdev.stackexchange.com/questions/2729">Prior art on modeling characters of variable lengths</a> in that I am specifically interested in the implementation of indexing operators, the performance characteristics afforded by various designs, and any relevant optimization techniques.</p>

<implementation><unicode>
Supporting reasonably efficient high-level indexing for strings
CC BY-SA 4.0
2023-11-27T11:40:09.953Z
Generally, indexing by code-point is not useful as there are many combining code points (mulitple code points that combine into a single character), besides just the surrogate pairs.  So UCS-32 doesn't really help.
Chris Dodd
CC BY-SA 4.0
2023-11-27T11:41:56.260Z
@ChrisDodd hence the part about grapheme clusters. But in principle, I imagine that the general form of a solution would apply more or less the same way to both, because either way it's about indexing an abstract sequence of variable-length clusters within a lower-level sequence... yes?
Karl Knechtel
CC BY-SA 4.0
2023-11-29T07:03:44.787Z
It's not your question, but you should rethink your plan to treat strings as arrays of code points. Treating strings as arrays of anything just encourages people to write buggy ad-hoc lexers. It's better that string indices be opaque like `fgetpos`/`fsetpos` cookies in C, and be manipulated by higher-level functions than integer arithmetic. This is something that most languages handle poorly and I wish newer languages would break the cycle.
benrg
CC BY-SA 4.0
2023-11-29T07:11:24.337Z
Your question about efficient indexable representations of strings seems like it might be more appropriate on CS.SE, since the fact that the elements are code points or grapheme clusters is unlikely to matter. Look at the [\[succinct-data-structures\]](https://cs.stackexchange.com/questions/tagged/succinct-data-structures) tag.
benrg
<blockquote>
<p>Is it possible to support better-than-O(N) indexing for <em>grapheme clusters</em> (notwithstanding the work required to identify the clusters)?</p>
</blockquote>
<p>You can of course do it by indirecting.  That would be quite inefficient.  MoarVM does it with what it calls 'synthetic codepoints', which take advantage of the fact that most grapheme clusters have just one code point: a string is represented by a sequence of 32-bit entities; if the high bit of one is clear, then the low bits are a code point; if the high bit is set, then the low bits represent a pointer to an indirect grapheme cluster object.</p>
<p>In MoarVM, the implementation knows about synthetic codepoints; atop something like .net, you would be at a bit of a disadvantage, but it would still be possible to implement the strategy with some performance penalty.  Represent a string with a pair of two arrays: an array of 32-bit integers, as above, and an array of indirect grapheme cluster objects; for an element of the first array whose high bit is set, the low 31 bits are an index into the second array.  (You could also make the second array contain the contents of the grapheme clusters directly, skipping an indirection in some cases, but then you would not be able to share structure between strings, so there are tradeoffs.)</p>
<p>One common strategy orthogonal to this that you can use is to notice when a string is all Latin-1, or all UCS-2 with no grapheme clusters of more than one codepoint, and when it is, represent it compactly with just one or two bytes per codepoint.</p>
<p>Also note that this strategy does not allow you to represent a string with more than <span class="math-container">$2^{31}$</span> distinct grapheme clusters of more than one codepoint.  So it might be desirable to have an additional representation that's fully indirect, as a simple array of words—one per grapheme cluster.</p>
<blockquote>
<p>recording auxiliary data</p>
</blockquote>
<p>This is how swift works, using what it calls <a href="https://www.swift.org/blog/utf8-string/#breadcrumbs" rel="nofollow noreferrer">breadcrumbs</a>.  But this seems inferior to just using a string representation that's fit for purpose to begin with.</p>

CC BY-SA 4.0
2023-11-27T16:59:34.443Z
2023-11-27T16:59:34.443Z
Moonchild
<p><strong>Depends on what you mean by &quot;possible.&quot;</strong></p>
<p>If you mean &quot;never have to iterate over the string,&quot; no, it's not possible because even if you <em>do</em> use a custom data structure, you need to iterate at least <em>once</em> to build that data structure.</p>
<p>But if you mean, &quot;don't have to iterate to index a character or grapheme cluster,&quot; then what you could do is build a second list containing the location (start and end) of the characters, in order.</p>
<p>You index into the location list, then index into the string.</p>
<p>You could do the same for grapheme clusters.</p>

CC BY-SA 4.0
2023-11-27T15:39:01.337Z
2023-11-27T15:39:01.337Z
Gavin D. Howard
CC BY-SA 4.0
2023-11-27T16:45:25.947Z
-1, this does not answer the question. The question specifically asks “What approaches are taken by real-world languages to store and use such string data?” which this does not answer.
Alexis King
CC BY-SA 4.0
2023-11-27T18:12:19.503Z
That's unfair because this does answer the highlighted question. There are three questions in OP. I answered two.
Gavin D. Howard
# Supporting reasonably efficient high-level indexing for strings
Posted by: username_0 on 2023-11-27
I'm designing a language that I intend to be implemented on the .NET platform. To my understanding, the native string representation uses UTF-16, by storing an array of `char` (an unsigned 16-bit type) and offering an API that treats each 16-bit code unit as an element.

This isn't the indexing behaviour I want for strings in my language. At the very least, I want to index character-by-character, returning the nth code *point* from the data - which is different from the nth code *unit*, because of surrogate pairs.

Given an unknown amount and position of surrogate pairs in the underlying data, it seems that a naive algorithm to index by character would be forced into O(N) performance (i.e., iterating over the code units until there are enough to make N code points). **Is it possible to do better than this**, perhaps by recording auxiliary data or using a more complex data structure? Or is resorting to UCS-32 or another such "flat" encoding the only viable option?

Is it possible to support better-than-O(N) indexing for *grapheme clusters* (notwithstanding the work required to identify the clusters)?

What approaches are taken by real-world languages to store and use such string data?

This is not a duplicate of [How have modern language designs dealt with Unicode strings?](https://langdev.stackexchange.com/questions/1493) or [Prior art on modeling characters of variable lengths](https://langdev.stackexchange.com/questions/2729) in that I am specifically interested in the implementation of indexing operators, the performance characteristics afforded by various designs, and any relevant optimization techniques.
**Tags:** implementation unicode
> **Comments:**
> **username_1**: Generally, indexing by code-point is not useful as there are many combining code points (mulitple code points that combine into a single character), besides just the surrogate pairs.  So UCS-32 doesn't really help.  
> **username_0**: @ChrisDodd hence the part about grapheme clusters. But in principle, I imagine that the general form of a solution would apply more or less the same way to both, because either way it's about indexing an abstract sequence of variable-length clusters within a lower-level sequence... yes?  
> **username_2**: It's not your question, but you should rethink your plan to treat strings as arrays of code points. Treating strings as arrays of anything just encourages people to write buggy ad-hoc lexers. It's better that string indices be opaque like `fgetpos`/`fsetpos` cookies in C, and be manipulated by higher-level functions than integer arithmetic. This is something that most languages handle poorly and I wish newer languages would break the cycle.  
> **username_2**: Your question about efficient indexable representations of strings seems like it might be more appropriate on CS.SE, since the fact that the elements are code points or grapheme clusters is unlikely to matter. Look at the [\[succinct-data-structures\]](https://cs.stackexchange.com/questions/tagged/succinct-data-structures) tag.  
---
## 2 answers
### Answer by username_3 on 2023-11-27. Score: 2
> Is it possible to support better-than-O(N) indexing for *grapheme clusters* (notwithstanding the work required to identify the clusters)?

You can of course do it by indirecting. That would be quite inefficient. MoarVM does it with what it calls 'synthetic codepoints', which take advantage of the fact that most grapheme clusters have just one code point: a string is represented by a sequence of 32-bit entities; if the high bit of one is clear, then the low bits are a code point; if the high bit is set, then the low bits represent a pointer to an indirect grapheme cluster object.

In MoarVM, the implementation knows about synthetic codepoints; atop something like .net, you would be at a bit of a disadvantage, but it would still be possible to implement the strategy with some performance penalty. Represent a string with a pair of two arrays: an array of 32-bit integers, as above, and an array of indirect grapheme cluster objects; for an element of the first array whose high bit is set, the low 31 bits are an index into the second array. (You could also make the second array contain the contents of the grapheme clusters directly, skipping an indirection in some cases, but then you would not be able to share structure between strings, so there are tradeoffs.)

One common strategy orthogonal to this that you can use is to notice when a string is all Latin-1, or all UCS-2 with no grapheme clusters of more than one codepoint, and when it is, represent it compactly with just one or two bytes per codepoint.

Also note that this strategy does not allow you to represent a string with more than $2^{31}$ distinct grapheme clusters of more than one codepoint. So it might be desirable to have an additional representation that's fully indirect, as a simple array of words—one per grapheme cluster.

> recording auxiliary data

This is how swift works, using what it calls [breadcrumbs](https://www.swift.org/blog/utf8-string/#breadcrumbs). But this seems inferior to just using a string representation that's fit for purpose to begin with.
---
### Answer by username_4 on 2023-11-27. Score: -1
**Depends on what you mean by "possible."**

If you mean "never have to iterate over the string," no, it's not possible because even if you *do* use a custom data structure, you need to iterate at least *once* to build that data structure.

But if you mean, "don't have to iterate to index a character or grapheme cluster," then what you could do is build a second list containing the location (start and end) of the characters, in order.

You index into the location list, then index into the string.

You could do the same for grapheme clusters.
> **Comments:**
> **username_5** (2023-11-27): -1, this does not answer the question. The question specifically asks “What approaches are taken by real-world languages to store and use such string data?” which this does not answer.  
> **username_4** (2023-11-27): That's unfair because this does answer the highlighted question. There are three questions in OP. I answered two.  
---
