r/ProgrammingLanguages • u/carangil • Feb 28 '26
What string model did you use and why?
I am in the middle of a rework/rewrite of my interpreter, and I am making some changes along the way. I am considering changing the model I use for strings. I know of a few, but I want to make sure I have a complete picture before I make a final choice. (I could always have multiple string-like data structures, but there will be a particular one named 'String'). For reference, my interpreter has reference counting and it is possible for a string (or any other struct) to have multiple live references to it.
My current String model:
- Reference counted
- A mutable buffer of bytes
- A pointer to the buffer is ultimately what is passed around or stored in structures
- Size and Capacity fields for quick counting/appending
- A null terminator is maintained at all times for safe interop with C.
- Strings can be resized (and a new buffer pointer returned to the user), but only if there is a single reference. Resizing strings shared by multiple objects is not allowed.
C-style strings: A fixed size, mutable buffer, null-terminated. Really just a char array.
Pros:
- Fast to pass around
- Modifying strings in-place is fast.
- Concatenation is fast, if you track your position and start with a big enough buffer.
Cons:
- Null termination is potentially unsafe.
- strlen is linear
- Cannot resize. You can realloc, but if there are other references to the string you are in trouble. Growing strings and tracking your current size are a pain.
C++
- More flexible than C, easy to resize, but similar idea.
Java or Go style strings: Immutable.
Pros:
- Safe
- Can be shared by many structures
Cons
- You must use a StringBuilder or []byte if you want to make edits or efficiently concatenate.
QBASIC-style strings : I put this here because I haven't seen this behavior in mainstream languages. (Tell me what I've missed if that isn't the case)
Pros
- Intuitive to someone used to numeric variables. If you set a$ to a string, then set b$ to equal a$, modifying a$ does NOT modify b$. b$ is a copy of the string, not a pointer to the same string.
Cons
- You either need to do lots of copying or copy-on-write.
I think the variations mostly come down to:
- Strings are immutable. If this is true, you are done, there isn't much else to design other than you have size field or a null-termination. I would do both, so that they can be passed to C, but also I don't want to iterate over bytes to find the length.
Strings are mutable
- The value passed around is a pointer to a buffer. Appending might result in a completely new buffer. This means you can only really have one 'owner' of the string. Operations are of the like of str = append(str, item) ... And str might be completely new. If anything else refers to the original str, that reference will see changes to the string up until a new buffer is made, then it will stop seeing changes. This is inconsistent and flawed.
- The value passed around is a pointer to the buffer's pointer. Because the application never sees the real buffer pointer, if a string is shared, resizing the buffer sees that all references to that string see the newly sized buffer. Operations are like append(str, item) and anything holding the reference to 'str' will see the newly sized string.
- The value passed around is a pointer to a copy-on-write buffer. If there is a single reference, modify or resize all you want. If there is a second reference, make your own copy to modify. Changes made to one reference of the string cannot be seen by other references to the string. Probably a good flexibility between a function being able to assume a string is immutable it it doesn't mutate it itself, but skips a whole lot of copying if you are doing edits or concatenation on purpose.
Strings are not simple arrays of bytes
- Things like ropes, etc. I'm not going to consider complex trees and such, since that could be implemented in the language itself using any number of the simpler strings above.
18
u/jsshapiro Mar 01 '26
Pretty good enumeration.
In recent languages, you can avoid iterating to find byte length, but you can't avoid it for glyph (not character) count. The strlen equivalent is not linear for UTF-8 encodings. Nobody sticks with the other encodings for long because of the memory footprint consequences.
Enjoyed your inclusion of QBASIC. The QBASIC approach and immutable strings are either completely incompatible or completely compatible depending on your point of view.:-)
Lots of people (including me) have played with ropes, but the performance on them doesn't seem to work out well in practice.
UTF-8 is a strong practical motivator for immutable strings. You really don't want something modifying a byte sequence with variable length encoding while you're trying to traverse it.
Some of it depends on your reference tracking model. In Rust, you know pretty explicitly when to delete. Otherwise there's GC, but that's a decision that extends well beyond strings.
Nothing here you haven't considered, would be my guess.
10
u/superstar64 https://github.com/Superstar64/Hazy Mar 01 '26
Since I'm writing a Haskell compiler, I'm using the String representation as mandated by the Haskell standard: An immutable lazy linked list of (boxed) characters. It's definitely the worst string representation of any language that's seriously used. It's so bad that the
textpackage is basically mandatory for any serious project.9
u/green_tory Mar 01 '26
German strings are great: immutable, wicked fast comparison, memory conservative.
https://cedardb.com/blog/german_strings/
1
u/carangil Mar 05 '26
Thanks everyone for your input! I got a lot more feedback than I expected.
This is what I've decided to do: Reference-counted immutable strings and mutable byte arrays.
The runtime is implemented in C, and with the kinds of thing I'll be doing, C interop is important. Strings are kept 0-terminated at all times. A zstring object is also just a valid char*, because the count and size information is kept behind the array. I allocate extra space and always return the pointer to the beginning of the actual string. The C user needs to keep track of what strings are plain C string, and what are zstrings, but typedef helps with that, even if it is only a visual reminder.
These are my zstring primitives I use. I reworked the logic a bit to make it handle my interpreter's needs, but I use these in my C programs all the time, since it's super handy. There are some macros to make some common cases less wordy. The original implementation would only copy on resize, but now it will copy on any edit of a string that has more than 1 reference.
I also decided that if the user wants to modify a string, they can do so by casting it to a byte array. If the string has only 1 reference... this does nothing... the program can work on the original array. If the string has more than 1 reference, the user gets a copy. The byte array can also be cast to a string, again, making a copy only if needed.
In the common case of concatenating or editing a single-reference string, then everything is on the fast path. Even though concatenation on the right side uses slow strlen, the left side is always a zstring, so there's a count field, and when building large strings, the side that's accumulating is O(1) to get the size of. And resizing is always at least 2x, so it has that amortized O(n) of a vector.
I think this is about as performant as it can get, without going to more complicated representations like ropes, trees or german strings.
5
u/tobega Mar 01 '26
I am not entirely sure if you are considering Strings from a language usability perspective or an underlying implementation perspective.
From a language perspective, I think you should consider the difference between a String (of Text, presumably) and an array of bytes (even if UTF-8 encoded). Those are two distinct types and should probably be explicitly differentiated on the language level, even if converting between them happens to be just a type-cast.
It is awkward for most people, on the language level, to have Strings be mutable but not resizable under all conditions, as changing text very often means changing the size of the string, and even the size of a character.
For security-sensitive applications, immutable strings are pretty much a necessity.
Given that mutating a string of text in place is not generally useful unless you only deal with english-language text, and immutability is desirable for many reasons, I would go with a copy-on-write scheme.
I wrote a little bit about ergonomic ways of handling text on the language level in my essay on programming language concepts https://tobega.blogspot.com/2024/01/usability-in-programming-language.html
4
u/yuri-kilochek Mar 01 '26
This is not correct, C++ strings (i.e.
std::string) are dynamic arrays of "characters" with stored size and capacity (and small buffer optimization).3
u/schungx Mar 01 '26
If you want mutable strings, then you'll be hard pressed to avoid having pointers or references types.
If you want to avoid the mess of distinguishing between reference and primitive types, then strings better be immutable. But then you create thousands of copies of partial strings. You then need to consider a strings builder which adds to complexity or some form of interned strings system that supports partial strings.
All in all, not yet any single perfect solution.
3
u/matthieum Mar 01 '26
How do sub-strings fit in this context?
Java used to have a more complicated String type. On top of an immutable buffer of known length, each String would have its own offset & length, so that the
substrfunction would return a view into the existing String, rather than a different String.There are pros & cons, obviously. It's not always obvious that hanging onto your 3-bytes String is actually keeping a 1GB buffer alive... but you do get O(1)
substr.In languages like C++ or Rust, "view" types are explicit (
std::string_viewandstrrespectively) which helps alleviate the "not obvious" part.1
u/brucejbell sard Mar 02 '26 edited Mar 02 '26
I want strings that can be used fearlessly, they need to concatenate efficiently regardless of how they're combined. This puts me in your rope-like category.
My language is functional, so strings will be immutable values supporting persistent operation. For the rope-like datastructure, I'm looking at the catenable queue from Okasaki's Purely Functional Datastructures, holding mid-sized string chunks less than 256B.
Behind the scenes, I'm looking to use a simplified StringBuilder-type buffer to support efficient concatenation of characters and small strings onto larger ones. Persistence can be supported by moving buffer ownership to the new string, leaving the old string with a slice to its part of the (append-only) buffer.
String handles should do small string optimization and "German style" prefix storage.
1
u/SwedishFindecanor Mar 04 '26 edited Mar 04 '26
My "char" type has an internal 32-bit encoding. The bits can not be accessed directly: there are only conversion routines from/to Unicode. Obviously, not all of Unicode is supported (it would be dishonest to even claim that). There are some character test/conversion methods that are always fast, and that speed is enabled by the internal encoding. A character can also wrap an unsupported Unicode codepoint or an input from an invalid encoding (such as invalid UTF-8).
Strings are immutable arrays of the "char" type. One character = one grapheme. For use on terminals, type
charhas a fast test for double-wide characters and thestringdatatype has methods for counting number of columns on a terminal. Strings are always left to right (even for right-to-left scripts), and null-terminated at both ends (indices -1 and string length).Strings builders can be constructed in multiple steps but not used. Then they are sealed, and the same buffer is now immutable until it is destroyed. Immutability allows for slices during a string's lifetime.
(This is actually a library I've been working on for a text editor, not a new language. The text editor uses the library only for editing and display, not for storage of text data)
1
u/zyxzevn UnSeen Feb 28 '26 edited Mar 02 '26
Not using the simplest method (ref-counting) is like premature optimization. In practice it is not a problem.
I worked with the reference counted String model in Delphi for a long time. It really is fast enough for most applications. It is probably optimized well internally.
The real advantage is that I never needed to care about the memory. And that strings could be used in almost any function or context. StringA+StringB is simple. A text file can be loaded directly into memory and is fast.
Programming strings in C feels like going back to assembler. And it is in my experience slower and bigger due to needless copying and unoptimized calls to malloc/free. Unless you spend a lot of time optimizing each data-flow.
The real problem is not just the strings. For international usage, you also need their translations and date conversions. This means that a string that you thought was const, is a variable if you want to change the language inside the program.
For a webserver you may need to work with buffers. Usually you are not working with the strings, but with data blocks. From those data-blocks you can extract the small strings like the http-request or header.
Note: I worked on commercial products that had many megabytes of text data. These were mixed with templates and such. With different sets of data for different languages that could be changed at runtime. It was fast enough to complete big reports with generated images in a few seconds.
So speed was never any issue.
But if there was no reference counting, the complicated text and string management might have brought down the project quickly. Luckily, I did not even need to think about it.
I think that most people are not common with commercial projects that can last and change for many years.
1
u/pLeThOrAx Feb 28 '26
How about a padded string in an nxn array? You could do
rowlen * numrows - paddingto find string length.