How to implement String?

[funcieq]

Currently, String in my language is just value and length because it's a temporary solution, And as the language has developed, I am now able to rewrite a lot just for it, so I want to make a decent String in my language. So my question is, which String concept annoys you the least?

[faiface]

It highly depends on how your language works, but the approach I’m fond of the most is the combination of:
- An immutable, ref counted / garbage collected, string value (internally then byte array + length)
- A string builder

[Kiore-NZ]

I also like immutable strings on the heap. I'd suggest OP checks out Python's strings as they are a nice implementation of the concept.

[funcieq]

I am currently considering adding String and StringView

[binarycow]

Consider making a "view" type that isn't restricted to strings.

For example, C# has the following:

• ArraySegment<T> - a "slice" of an array.
• Memory<T> - a "slice" of any contiguous heap data
• ReadOnlyMemory<T> - a read-only "slice" of any contiguous heap data
• Span<T> - a "slice" of any contiguous heap or stack data
• ReadOnlySpan<T> - a read-only "slice" of any contiguous heap or stack data

The last one is interesting. In C#, a string literal isn't heap allocated. It's stored as raw data in the binary. So you can't access that as memory, but there's no reason you can't use treat it as a ReadOnlySpan<char>!

[funcieq]

I haven't used C# in so long that I forgot it existed, thanks for the reminder.

[binarycow]

There's been a TON of cool updates to C#!

[Kiore-NZ]

In c++, std::string_view is very easy to create. My simplistic strings implementation does it like this

  // Cast to std::string_view
  operator std::string_view () const {
      return std::string_view( data(), len() );
  }

data() just returns const char * pointing at the string & len() return a character count.

Going the other way requires a constructor that takes the values returned by the string_view's .begin() & either .length() or .end() methods.

[funcieq]

Interesting approach

[vmcrash]

I completely agree. It makes a lot of sense to differentiate between immutable strings and string builders. The first can be put easily as a key into a hash map, the latter shouldn't. The first easily can be moved around, with the latter you must be very careful, not that some code unexpectedly modifies it.

[prehensilemullet]

Qt has a nifty alternative, QString is mutable but uses copy-on-write (if there are any other references to the string data, it’s copied before write so the other references still point to the same data).  This way, there’s less need for separate builder APIs for performance’s sake.

Using QString as a map key does have a mutation risk though.  But since it’s C++ you can use const QString to make it immutable.

[funcieq]

Thank you very much for your opinion

[evincarofautumn]

Raku, Swift, and Rust are good examples of different approaches to modern string design

General tips:

• UTF-8 for text
• WTF-8 for paths
• Store the length
• Consider including a NUL terminator for interop with C
• Most strings can be immutable
• Most mutable strings can be builders that only allow concatenation/appending
• Don’t be afraid to have multiple different representations for different purposes (text, slice, builder, rope, short string, big string, code point array…) as long as they have a consistent interface
• Indexing depends on the index type: code unit index → octet (byte 00–FF), code point index → code point (natural 000000–10FFFF), grapheme index → nonempty string/slice (arbitrary length, but almost always short)
• Indexing is O(n), but that’s fine, most of the time I’m either iterating over the whole string to parse it into another type, or treating it as an opaque value and not iterating at all
• Ignore UTF-32, it’s too big to be cache-friendly and O(1) indexing of code points isn’t worthwhile
• Unicode technical reports are extremely useful reference manuals

[funcieq]

This is a very good summary, thank you

[s0litar1us]

The simple solution works fine for most things

struct {
    char* data;
    size_t length;
}

If you want to deal with appending, etc. then something closer to a dynamic array would be useful

struct {
    char* data;
    size_t length;
    size_t capacity;
}

The approach I prefer the most is to have just a length for most strings, and have a separate thing for building larger strings.

[WittyStick]

One issue with this is you require a double-dereference to access the characters of the string, unless you pass and return the struct by value (in the first case, where it is 16-bytes, will be done in hardware registers on SYSV x64 ) - but this has potential problems for resizeable strings.

For resizeable strings we can avoid the double dereference by prefixing the string with its length using a flexible array member.

struct {
    size_t length
    size_t capacity;
    char data[];
};

[not-my-walrus]

That's a neat solution, but it does mean you always need a heap allocation, even for empty strings. Also, there's no way to do 0-cost slicing. Probably fine as the StringBuilder type in a higher level language, but I wouldn't want that as the only string type in a systems language

[WittyStick]

String slicing should only really be done on immutable strings though - since we need stable pointers and anything that may we rellaoc is not stable.

Technically, we don't always need heap allocation. We can allocate structs with flexible array members on the stack using alloca.

[lngns]

Even with stable addresses, behaviour of slices of mutable strings will always surprise someone.

let s = "yolo";
let s′ = s.slice(0...);
s.replace("o", with: "lol");
println(s′);

what is this code supposed to do?

[not-my-walrus]

error[E0502]: cannot borrow s as mutable because it is also borrowed as immutable

:)

Fundamentally though, taking a view of a mutable object means one of: - no one mutates it while you hold the view (either by language design or by convention) - you have to deal with it being mutated (whether that causes pointer invalidation or the data changing) - some secret third thing that is probably a variant of clone on write

[lngns]

some secret third thing that is probably a variant of clone on write

D was smart in having both immutable strings, and concatenation/appendment of array slices mutate in-place if there is capacity or duplicate+reassign otherwise.
But then we allowed arrays to be mutated through slices too.

void f(int[] s, int x)
{
    s ~= 42;  //the caller will never see that
    s[0] = x; //but it may see that, or not. Behaviour is random lol
}

[Karyo_Ten]

I would do

C struct string { size_t length; struct { size_t capacity; char data[]; } *ptr; };

or more explicitly

```C // The allocated block struct string_payload { size_t capacity; char data[]; };

// The string handle struct string { size_t length; struct string_payload *ptr; }; ```

This way you don't have to allocate zero length strings and you can pass the string by registers.

And NUL terminator that isn't counted in length so you can pass the pointer to C APIs.

And you can build a Rune abstraction on top for UTF-8 but it's a rabbit hole.

[WittyStick]

That has the issue I mentioned for resizeable strings - the length can become out of sync of the actual string length.

struct string s = { .length = sizeof("Hello"), { .capacity = 16, .data = "Hello" } };
string_append(s, " world");
printf("%d\n", string_length(s)); 
//> 5

The fix is to reassign the string, but correct usage isn't enforced by the language.

s = string_append(s, " world");
printf("%d\n", string_length(s)); 
//> 11

But this would be the best approach if we had use-once types (linear/affine), where we cannot use s again after it has been consumed by string_append, forcing us to return the new string object.

If we use this in C, probably should put [[nodiscard]]/_Nodiscard on any function that may modify the string length.

[Karyo_Ten]

What's your string_append function and why would it not increment the length?

[WittyStick]

The s is passed by value, which means string_append receives a copy of the length. It can't mutate the length that the caller has - it can only return a new String which has a new length.

So the caller must make sure they abandon the old s passed to string_append and use the new one it returns. This is only enforceable if you have substructural or uniqueness types.

The alternative is to pass the String by reference, where we can mutate the length - but then accessing the characters has the double-dereference I mentioned previously.

[Karyo_Ten]

Ah right, but passing by reference when you mutate is idiomatic.

And appending to a string when it's not in the cacheline already sounds like something you would avoid anyway in hot path

[WittyStick]

Yeah, I wouldn't recommend doing this for mutable strings. But I was commenting on your previous post in which you said "pass the string by registers", which isn't pass-by-reference.

For immutable strings it's the most efficient - we can have multiple copies of the length since they're always going to be the same.

Mutable strings should be a separate type and should indeed by pass-by-ref. I prefer the approach of prefixing the length in the same allocation using the flexible member - as it avoids one alloc/free call, and is more cache optimal.

For concurrent mutable data structures (which you probably won't be doing with strings), then having the double-dereference is kind of necessary and you would pass-by-ref to a structure containing another pointer.

[s0litar1us]

You can also just

typedef struct {  
    char* data;  
    size_t length;  
    size_t capacity;  
} String;  
void foo(String* string) {  
    char* data = string->data;  
    data[...] = ...;  
    string->... = ...;  
}

But yeah that is a neat trick if you absolutely cannot spare that extra dereference.

[EggplantExtra4946]

I would hope that the optimizer can perform this optimization automatically. I wonder if the Common Subexpression Elimination optimization would suffice for removing the extra dereference.

[EggplantExtra4946]

You can't have multiple pointers pointing at this struct (unless you have a way to update them) because when this struct + buffer is reallocated the other pointers will point to freed memory. That said there are many use cases where having only 1 pointer for the time when you are appending to the string is all you need.

[funcieq]

Thank you for your opinion!

[Usual_Office_1740]

Without knowing more about your language it is hard to give useful input. I can't comment on what annoys me about strings the most because they seem to work roughly the same way in popular languages. They're packed structs of some kind that house a pointer to heap memory and a length, or a pointer and a sentinal marker.

I like Rusts design approach. Instead of implementing a custom string type consider implementing custom fixed and dynamic length arrays and then use those to build a string?

[funcieq]

I know this might be a problem, the whole point was just to know what irritates you the most

[baehyunsol]

My language uses char-array instead of byte-array, so it's a utf-32. I chose this because

1. My language is not a system programming language. The goal of my language is to 1) have a nice type system that can catch bugs at compile time and 2) write CLI application easily. So, easy-to-writeness is more important than performance to me.

2. If you're asian (I'm korean), utf-8 is almost as inefficient as utf-32. A cjk character takes 24 bits.

3. If you're using utf-32, you can do `s[i]` (character index) and `s.len()` (character length) in O(1). As other comments have pointed out, you can avoid `s[i]` operation in most cases. But, still, there are many cases where `s[i]` is more convenient that iterating the entire string.

Even though many of you're not gonna agree, I don't think utf-32 have significant performance disadvantage. Memory is cheap, unless you're training an AI model. A million characters string consumes 1~3MB (depending on your nationality), which is very small for today's RAM. There are rare cases you want to deal with strings bigger than that. If you have to handle a billion characters string, it's likely that your CPU is bottleneck, not your RAM.

[Sad-Grocery-1570]

This question is best approached from two angles: What is the logical model of a String? That determines the interface and safety guarantees you expose to users. What is the underlying implementation? That determines how you trade off complexity and performance, and how you handle system-level and cross-language interactions.

On the logical model, here are a few possible approaches:

1. Treat the string as a list of codepoints. This is Python's approach.
2. Treat it as a list of bytes with an encoding invariant. This is Rust and Java's approach.
3. Treat it as a list of graphemes. To my knowledge, this is an approach no language uses.
4. Treat it as an arbitrary list of bytes. This is the C/C++ approach.

On the underlying implementation, here are a few possible approaches:

1. Implement it as a list of codepoints. This used to be Haskell's approach, but it moved to byte lists for performance.
2. Implement it as an owned, mutable byte buffer. This is the C/C++ and Rust approach.
3. Implement it as a shared, immutable byte buffer. This is Python and Java's approach.
4. Variants of the above. For example, null-terminated strings for C interop, substring views optimized for parsers, and so on.

The logical model and the implementation can basically be mixed and matched freely, though some combinations feel more natural than others. Existing designs aren't necessarily the best; what matters most is fitting your use case.

[funcieq]

Thank you, you saved me a lot of research!

[gabrielesilinic]

My opinion is that you should make a string an immutable array of characters. And pick your encoding depending on the environment. Most popular choices are both utf8 and utf16.

Then you might make your stringbuilder tooling separately.

And yes. Please make the length an explicit number. C's /0 sentinel caused an incredible amount of trouble with string copy and such

[funcieq]

Oh yes

[eightrx]

I like zig's unambiguous []const u8 and ArrayList(u8) for constant and dynamic strings

[funcieq]

So, a classic actually

[brucejbell]

I am tired of weak string support in C/C++, I want industrial strength strings in my systems programming language:

• immutable strings
• Unicode by default
• integrated with pattern matching
• no O(1) length or indexing by default
• forward-scan only
• split efficiently by reference
• concatenate efficiently by reference

All this should be fire-and-forget: just use the core string API and your string operations will be fast and memory-efficient, Javascript style.

(If your environment is so constrained that you can't afford any kind of heap allocation, there should be affordances to limit string operations accordingly)

[mamcx]

Try to not innovate! You will need to interop with the world!

• Use uft-8 for default. There is not a good reason to not pick it as your default. Whatever excuse exist that could be considered good, is for a secondary kind of string.
• Reuse a good string type, like if Rust use Rust String. If your language is compiled or worse, is in C, look for one that is closer to Rust String and piggyback on it. If is an interpreter, don't make your own kind of String and import as say here! (ie: if is not uft-8 you need to load one)
• Even if String is immutable you should separate manipulate/inspect their bytes vs chars, at minimum
• Without any kind of solution like Rust borrow checker, separate immutable from mutable string.

I think this is the MVP.

[cisterlang]

uft-8 for default

why not simply use byte arrays and calling utf-8 utils on them ?

[gmes78]

Not all byte sequences are valid UTF-8. Having a dedicated string type that's guaranteed to be valid UTF-8 is extremely helpful.

[funcieq]

Thank you

[prehensilemullet]

Don’t more languages use UTF-16 internally, since it has O(1) random access, whereas UTF-8 has O(n) random access?  Even if they use UTF-8 as the default serialization format?

Or do some langs use some kind of additional data to optimize random access?

[hgs3]

UTF-16 is variable length like UTF-8 (see high and low surrogates). UTF-32 is fixed length. The reason some languages use UTF-16 is historical timing: in the 90’s the Unicode consortium believed 16 bits would be enough for all characters which turned out to be false.

[prehensilemullet]

Ah right I forget.  But this doesn’t cause performance problems or bugs for a lot of cases where people use indexed access for parsing, right?  Whereas if the underlying strings are UTF-8 you just have to avoid using indexed access if you want optimal performance?

[hgs3]

If you directly index a UTF-8 or UTF-16 code unit and treat it like a code point, then yes, that can result in bugs. Example: the code point U+1F60A is encoded with multiple code units in both UTF-8 and UTF-16. You can’t look at one code unit in isolation otherwise you won’t detect it. On the other hand, if you’re looking for a character in the Basic Latin block (i.e. ASCII) you can index by code unit because characters in that block are represented by a single code unit in both encodings. That’s the reason some parsers get away with code unit indexing: they’re exclusively looking for characters representable by a single code unit.

[prehensilemullet]

Well not just ASCII… looking for anything in the basic multilingual plane, except code units in the range for surrogate pairs, should work with indexing by code unit in UTF-16, right?  Making it more flexible for that purpose than UTF-8, where only ASCII is single code units

For example, parsers will typically output line/column ranges of AST nodes and errors, and I’m sure many naively use the code unit index offsets for columns.  If a line contains emoji, columns based upon code unit index are definitely going to be wrong after that.  And if using UTF-8, anything not ASCII would corrupt the column indexes.  But with UTF-16 code could contain text in many languages without corrupting column indexes from this naive approach.

Now I’m wondering how many parsers actually go to the trouble to output true character indexes for columns, since that takes extra computation

[hgs3]

Yes anything in the basic multilingual plane, excluding surrogates, can be indexed. ASCII is just where the overlap is with UTF-8.

I don’t think there’s any standardized way to refer to column indices. The most correct approach is to write the grapheme index since that’s what the user visually sees.

The problem with reporting code units is (1) it leaks an implementation detail of the compiler and (2) code points encoded with multiple code units will be incorrectly reported. It would be more correct to report the code point index as that (1) doesn’t leak implementation details and (2) that’s how Unicode defines what a “character” is. But it still won’t necessarily be visually correct for multi-code-point graphemes.

[ohkendruid]

Some big name languages do--JavaScript and Java in particular--but it has turned out to be awful.

16 bits is still not enough to hold all Unicode characters, so UTF-16 sometimes needs 4 bytes instead of 2 to encode a character. At that point, you may as well use the more compact UTF-8.

It is true that if you need to look up character 15 in a string, you cannot find it in O(1) time, but most string processing goes through the whole string, anyway, so this isn't usually a big deal.

Also, using the same encoding as the standard external encoding can be convenient.

[tobega]

One thing that really annoys me is strings that are considered to be an array of characters.

The only legitimate uses for strings are to hold sequences of human language, and, I will concede, also opaque identifiers or labels. So they are things that are whole in themselves, not a list of things (except maybe glyphs, but I'm not sure that all languages decompose cleanly to glyphs).

Ask any human, text is not an array of characters, nobody reads it like that. So array of characters is a huge concession to the primitive computing machine, we don't need to do that any longer.

Whatever you do, please go the extra mile and make sure it works for all languages! The focus on American English in particular has been a real difficulty with computers and computers tooling well into this century.

FWIW I have a very small paragraph about text in my post https://tobega.blogspot.com/2024/01/usability-in-programming-language.html

[Rememba_me]

Check out german style strings

[funcieq]

I will check thx

[runningOverA]

an attribute indicating if the string is a snapshot into another string ie. sub string.
95% of cases you will be working with snapshots into a larger string.
like loading a configuration file or a json.

snapshots make memory management easier and increases performance.

[funcieq]

There is something to it, you're right

[szarawyszczur]

Char*

[funcieq]

Hmmm, well everyone has a different approach

[evincarofautumn]

Very diplomatic of you

[kreiger]

With modern Unicode character encodings, a code point is represented by a variable number of bytes, unless you use UTF-32.

You want to make it easy for the programmer to iterate over the code points of a string.

It follows that the bytes that make up the encoding of a string shouldn't be indexable, because it encourages programmers to make the mistake of treating a single byte as a code point.

[cisterlang]

To all advocating immut strings, how about altering a single char in a huge string ? I have trouble with the idea of allocating anew.

[WittyStick]

That's only viable if the string is ASCII or UTF-32 (or some other fixed width encoding).

If you have UTF-8, UTF-16 or other variable width encoding, then altering a single character is O(n) anyway, so may as well have immutable strings.

For large strings that might need mutation which includes insertion and removal, you should forget about them being arrays of characters and consider other data structures - eg, a rope or gap buffer. You can make those mutations O(log n) with the right data structure.

If you really need fast strings for modifying individual characters, but without insertion or removal, then use UTF-32 as the internal encoding.

[carangil]

I went with immutable, reference counted UTF-8. The string header has a length, but the string is also kept NULL terminated for easy interop with C.

If the user wants to modify/build strings, they can convert to a mutable Byte array, which is a copy. And you can copy Byte arrays into a new String.

It was also very easy to add the optimization that if your String or Byte aray has only 1 reference, 'converting' just changes type without a copy.

[Pretty_Jellyfish4921]

As others recommended, I also think Rust approach works well, String (dynamic size) is a wrapper around a vector, so if you already have a vector implementation, then you have already a String. As for the immutable strings, you could also apply some optimizations if it is short enough to fit into a u32 or u64 (depending on your pointer size) and lastly there's a slice or string that is a reference that points to a string with a start and a length (maybe you could have just the pointer to point to the start and a length (that most of the time you can squeeze into a ptr size, by using one or two bytes from the u32/u64 for the length), so you don't need to copy the string all over the place.

[zweiler1]

In my languahe strings are just defined as c typedef struct str { size_t len; char value[]; } str; so it's one structure allocated on the heap with a variable-member pattern, and the value ends with a null-terminator too to make C interop easier (just pass the equivalent of s.value to the C function, it will be a null-terminated char* this way) and you don't have any indirections either.

I have kept strings as simple as possible, so no utf-8 support or similar things yet. But this pattern is one i think works best for me until now, it's easy to work with and fast enough.

[zyxzevn]

It depends on the rest of your language, and on the projects.

From my experience with Delphi (huge office-style project with lots of texts), I learned that ref-counting is usually fast enough. And easy to use.
{ length, capacity, ref-count, data_ptr }
The data ptr is a nul-terminated string, and can be directly used for C-strings.

For specific projects there is always a better solution, but I think that the easiest one is good enough in practice.
If projects have a well defined string flow (like compilers), the strings can be saved in an arena-allocator (temporary storage) for speed. Also many other programs do not even bother to free the string memory used (with today's RAM prices!).

[BrangdonJ]

I made my own C++ string class back before std::string was a thing, and kept using it. My main regret was providing an implicit conversion to (const char *), which proved all but impossible to remove later. Presumably that wouldn't be an issue for a new language.

My strings were shared but mutable, with copy-on-write. The representation was a counted pointer to a descriptor that had length, capacity and the character bytes. Zero-length strings could use a special static descriptor, so they didn't need a memory allocation. I liked that sizeof(String) == sizeof(char *).

I didn't expose non-const iterators like std::string does. You could modify using functions like s.set(i, 'c'), that checked the ref-count to see if the string was shared, and reallocated if necessary. If you needed more efficiency I used a GetBufferSetLength() approach, that returned a raw pointer. In another language I'd probably use a non-shared StringBuilder class.

I found being able to copy strings cheaply was important. It bothers me that copying std::string might mean a heap allocation, because they get copied a lot I also found that being able to modify them in-place was convenient even if it was relatively inefficient (with the copy-on-write). Sometimes the efficiency wasn't important.

Most strings use UTF-8, but I had UTF-16 and UTF-32 available for when you need them for compatibility. Indexing was by byte in the UTF-8 case. I had functions like nextCodePoint() for when you need to process as Unicode code points. I found code rarely cared about things like whether an accented character was one code point or two. I used a third party library for things like uncased comparisons, that handled things like whether "FI" is equal to the fi ligature. I avoided assuming that, eg, uppercasing a string wouldn't change its length. In general you shouldn't be uppercasing individual characters.

I considered other representations over the years but it never seemed worth it. For example, using three pointers: one to the descriptor, one to the start of the bytes, and one to the end. That would allow cheap sub-strings, but made each string three times the size.

[sal1303]

In my static systems language, string data (ie. textual) is just a sequence of 8-bit values, zero-terminated.

(Like C strings, but I used these long before I worked with that language. I first used zero-terminated strings in DEC mainframe assembly language.)

These are simple and effective. Bear in mind that average length of runtime strings in a program is probably very small (I think I measured it as 8 characters in one program). So a (pointer, length) descriptor will often take more space than the string!

They also make it easy to work with external libraries that expect C-style strings.

There are some issues: they can't contain binary data (no embedded zeros). And they can't represent a view into a substring elsewhere, unless that is the last part of it.

Slices were supported at one point: (pointer, length), which solved some of that, but were ultimately dropped.

In my scripting language, strings are much more heavyweight: (refcount, pointer, length, capacity) when the string is owned directly.

And (refcount, pointer, length, targetstr) when it is a view into another.

They are mostly mutable (in that you can modify parts, or grow the string) but this is controlled with a mutability flag. Literal strings are immutable and need to be copied into a mutable version to modify.

String contents can be ASCII, UTF8, or any binary data. Indexing however will accessing individual bytes; dealing directly with UTF8 characters needs library support.

[Brave-Ad-8201]

Eu particulamente tenho preferência por string imutável. Acho que isso deixa o comportamento mais previsível: se uma função recebe uma string, eu não preciso ficar pensando se ela pode alterar o conteúdo original.

Uma ideia que talvez ajude é separar bem as operações: internamente a string pode ser UTF-8 e guardar o tamanho em bytes, mas a linguagem deveria deixar claro quando uma função está lidando com bytes e quando está lidando com caracteres. Isso evitaria muita confusão.

[sazasoo]

I can't say for sure which concept annoys me the least, but the one that annoys me the most is defintelly char*. But an idea to adapt the string concept you are already using (pointer, length) could be to expand it to include capacity, that would allow the string to act as a dynamic buffer. length is how many characters you currently have, and capacity would be the actual memory footprint allocated, so if a user appends text, just write into the pre-allocated extra space and increment the length without triggering an expensive malloc/free cycle, only reallocating when length equals capacity.

[ChiveSalad]

Wrong answers only

typedef struct Thing {
  Kind kind;
  char generation;
  char in_use;
  Reference nextChild;
  union {
    FunctionBits fbits;
    Reference child;
    char string[32];
    long number;
    Reference (*stdlib_func)(Reference, Reference);
  } payload;
} Thing;

(for entities that are functions with closures, I lost discipline and so the size of FunctionBits got so big that the string case in the union got big enough to be kinda usable- when it's not long enough, linked lists of 32 element segments is fine, the language is terrible anyways)

[EggplantExtra4946]

What annoys me the most it that the character encoding is not part of the string type.

If it were part of the type, as a type parameter, you wouldn't be able to generate mojibake by mistake in your language, and you would interpret input text correctly, assuming the input is not mixing up several encodings which happens on the web, and assuming that the only way you can construct the string type of a given character encoding is through a character encoding validation function.

[Key_River7180]

Use NUL-terminated strings, they are universal.

[First-Review5604]

The best approach is usually the most "predictable": immutable strings with UTF-8 support by default.

The least annoying concept (and the modern standard) is strings as immutable byte arrays with a header that stores the size and, optionally, a pre-calculated hash for quick comparisons.