<p>There are two main ways to implement strings in a language: null-terminated and length-prefixed strings.</p>
<p>From Wikipedia:</p>
<blockquote>
<p>A <a href="https://en.wikipedia.org/wiki/Null-terminated_string" rel="noreferrer"><strong>null-terminated string</strong></a> is a character string stored as an array
containing the characters and terminated with a null character, often this is the null character (NUL), which has all bits zero.</p>
</blockquote>
<p>and:</p>
<blockquote>
<p><a href="https://en.wikipedia.org/wiki/String_(computer_science)#Length-prefixed" rel="noreferrer"><strong>Length-prefixed</strong></a></p>
<p>The length of a string can also be stored explicitly,   for example
by prefixing the string with the length as a byte value.</p>
</blockquote>
<p>For example, the string <code>&quot;Hello, World!&quot;</code>, when using null-terminated strings (using ASCII), is stored as:</p>
<pre><code>48 65 6C 6C 6F 2C 20 57 6F 72 6C 64 21 00
                                       ^^
                                       the NUL character
</code></pre>
<p>and using length-prefixed string:</p>
<pre><code>0D 48 65 6C 6C 6F 2C 20 57 6F 72 6C 64 21
^^
the length byte
</code></pre>
<p>These approach is vastly different, so what are the advantages of advantages/disadvantages of using one instead of another?</p>

<implementation><strings>
What are the advantages/disadvantages of null-terminated strings vs length-prefixed strings?
CC BY-SA 4.0
2023-10-28T09:38:16.260Z
A common trick for ASCII strings (pre-unicode) was to use the 8th bit in the byte to mark the end of the string -- the last character would have it set (or clear) and all the others would have it clear (or set).
Chris Dodd
CC BY-SA 4.0
2024-07-17T18:06:31.327Z
You might be entertained by my very first blog post from 2003 which was on this subject. https://ericlippert.com/2003/09/12/erics-complete-guide-to-bstr-semantics/
Eric Lippert
CC BY-SA 4.0
2023-08-15T21:36:37.173Z
See also: https://stackoverflow.com/questions/25068903/what-are-pascal-strings
oɔɯǝɹ
CC BY-SA 4.0
2023-05-21T22:06:11.873Z
how is this really a _language_-related question as opposed to a computer science question? Because you mention "implementation" in the question but not "design", so I'm not sure as someone considering answering this question if you care about language design questions like usability- aside from which I'm not really sure if there's more to say than is just about the computer-science face of the question.
starball
<h1>Manipulation</h1>
<p>Manipulating length-prefixed strings is a lot easier than manipulating null-terminated ones. For example, when you concatenate strings, you just have to add the lengths, while for the null-terminated case you have the extra null to remove. When splitting strings, you have to not forget to include the null. For length-prefixed strings, you just take the length of the array and halve it.</p>

CC BY-SA 4.0
2023-05-17T00:52:55.763Z
2023-11-06T20:11:36.240Z
2023-11-06T20:11:36.240Z
Seggan
CC BY-SA 4.0
2023-11-06T20:11:25.050Z
@starball i never said you can do it without moving data.
Seggan
CC BY-SA 4.0
2024-07-22T16:12:34.453Z
@starball: If code which expects to work with a string first calls a function to convert a string pointer into text address and length, and if special prefix values are reserved for data records that, instead of holding a string directly, hold the address and length of the actual string content, then one could pass arbitrary substrings to code which expects to receive a single "string pointer", without having to copy any string data (construct a record containing a header, the address of the start of the desired substring, and the length of the desired substrign).
supercat
CC BY-SA 4.0
2024-07-22T16:25:28.427Z
@supercat sure. that's my understanding of what `std::stringview` is. but in the context o this question, I think it's debatable whether that counts as being the string itself. `std::stringview`, for example, is a non-reference-counted, non-owning view type.
starball
CC BY-SA 4.0
2024-07-22T16:40:18.220Z
@starball: Can code easily accept pointers to `std::string` and `std::stringview` interchangeably?  What I'd advocate would essentially be having a constructors for "readable string descriptor" and "mutable string descriptor" structures which could accept pointers to descriptors or minimal-storage-overhead in-place strings interchangeably.
supercat
CC BY-SA 4.0
2023-05-21T21:49:15.557Z
okay, but when splitting strings, who says you can do it without moving data? If you give more space to fit the length prefix than for each character, then don't you have to move data? Then it's not just a usability cost- it's a performance cost...
starball
<p>Null-terminated strings seem to have many disadvantages, but the biggest problem is you usually have to also store a size somewhere else, to avoid vulnerabilities, making it seemingly redundant.</p>
<p>But there is an unexpected advantage to also have the null terminator, that is in simple routines such as scanning a string starting from a given point for a complete grapheme cluster, you'll only need to pass one pointer, without the start of the string or the size.</p>
<p>Similar situations are common in any case you use characters like &quot;commands&quot;, say escapes in quotes and regexes, and printf and datetime formats. If you have a unified format for all the escapes, it won't have any problems. But if something has to be escaped in multiple layers, or the same thing has different meaning in different layers, the code quickly becomes ugly, and someone will want to choose a raw format in all but one layer instead. Strings and regexes usually doesn't have escapes with conflicting meaning, but the designer may not think making exceptions for regexes a good idea, and may not come up with a general interface for adding escapes or making escaped quotes and the escape characters optionally kept in the escaped format. But they could be improved if the designer does.</p>
<p>Null-terminated strings are a bit worse than escapes, but if we are not considering the buffer size part, they mix with other levels of escapes just like escapes. Sometimes a system message is already a text message in a format that is known to not contain nulls, so using nulls this way won't have a problem. And sometimes you know the string is a valid Unicode string, and you could escape the nulls like the Java way of using an overly long presentation. The former is an indication of something is stringly typed, which is frown upon by some people. The later implies fixing the character encoding, and either trust or presanitization of user data, which are not always desirable. They may seem strange for these reasons, but if your language is designed to work in the specific situation, you really didn't break anything.</p>
<p>Programmers would want a raw format only because it isn't sure what the other layers would be. But if another layer is already specified in the language, and already had some rules of what is valid and what is not, having a shared way of manipulating all &quot;commands&quot; may even improve something, for example the grapheme cluster case. In such cases, the null terminators could not be dismissed just because they are redundant when a clearly defined buffer size is a must. And buffer sizes could be dedicated for the maximum size instead of the current string length.</p>

CC BY-SA 4.0
2023-08-15T21:15:58.587Z
2023-08-15T21:15:58.587Z
user23013
<p>Length-based strings have two non-obvious performance advantages:</p>
<p>Concatenating lots of them into a big chunk is faster as you can preallocate the correct buffer size by just looking at the lengths.</p>
<p>Furthermore, comparing lots of strings with different lengths but common prefixes is faster. An example of this is a set of fully qualified names like <code>java.util.Set</code>, <code>java.util.HashSet</code>, <code>java.util.Collection</code>, etc.</p>
<p>The non-obvious advantage of zero-terminated strings is that one doesn't have to think up front about the length of an index type, i.e. setting the length to e.g. 32bit won't create a compatibility issue someday.</p>

CC BY-SA 4.0
2023-07-17T18:17:45.810Z
2024-07-16T21:30:17.210Z
2024-07-16T21:30:17.210Z
feldentm
CC BY-SA 4.0
2023-08-17T17:26:06.550Z
On the flip side, zero-terminated strings will have a performance cost which will increase sharply as their length becomes significant relative to the CPU cache size--something that would happen long before a 32-bit length becomes a problem.
supercat
<p>If you use just one byte for the length you can not have strings longer than 256 characters. The disadvantage of storing the length of a string is, that you have to make a decision about the length of the integer used to store the length of the string. If you terminate your string with a reserved byte, you do not have to make this decision. It will work equally no matter how large your storage will be.</p>
<p>X11 for example made such a decision. They decided that the integer used for the size of the window has 16 bit (CARD16). Even today you can not create bigger windows.</p>

CC BY-SA 4.0
2023-11-08T17:51:51.033Z
2023-11-08T17:51:51.033Z
ceving
CC BY-SA 4.0
2023-11-08T17:53:18.810Z
Welcome to PLDI!
rydwolf
<p>I commonly hear null-terminated strings referred to as <strong>C strings</strong>, and length-prefixed strings referred to as <strong>Pascal strings</strong>.</p>
<p>The advantages of null-terminated strings are that they save several bytes over length-prefixed strings. Instead of needing to store a length (generally at least two bytes), they can store a null character of just one byte.</p>
<p>The disadvantages of null-terminated strings are many. Indexing is O(n) instead of O(1) (though with Unicode and packed representations, the codepoint indexing of length-prefixed strings is also O(n)). Any time the length is needed for ex. reallocation, it must be recomputed, which remains an O(n) operation. They cannot contain the null byte, as it is reserved. They are <strong>extremely unsafe</strong>. Length checking is expensive, so it is tempting for programs to not do it, which can easily cause buffer overflows - the standard <code>gets</code> function in C is the classic example of this.</p>

CC BY-SA 4.0
2023-10-26T23:41:00.467Z
2024-07-23T22:24:38.927Z
2024-07-23T22:24:38.927Z
apropos
CC BY-SA 4.0
2023-11-02T20:59:15.673Z
From my experience, the term "Pascal strings" usually refers to strings that are prefixed by a single length byte, and whose length is thus limited to 255 bytes.  As such, the overhead is the same as for a zero *terminated* string, but a byte greater than for a zero *padded* string.  While zero-terminated strings don't have a hard length limit, efficiency goes downhill with length, so in many cases where code would use strings that would get longer than 255 bytes, neither approach to holding strings will be as good as tracking the length separately.
supercat
CC BY-SA 4.0
2023-11-03T19:54:32.507Z
[It appears to be ambiguous.](https://stackoverflow.com/a/25069152)
apropos
CC BY-SA 4.0
2024-07-19T19:50:38.943Z
A length doesn't have to be at least 2 bytes. There could be a specialized short string with a 1 byte length as described above.
qwr
CC BY-SA 4.0
2024-07-21T07:50:30.210Z
"Instead of needing to store a length (at least two bytes)" This would benefit from clarification. It seems trivial to have one-byte length prefixes, or even variable-size length prefixes.
MisterMiyagi
CC BY-SA 4.0
2024-07-21T07:52:23.193Z
"though with Unicode, the codepoint indexing of length-prefixed strings is also O(n)" This would also benefit from clarification. For example, Python has full unicode string support but O(1) indexing.
MisterMiyagi
CC BY-SA 4.0
2024-07-25T14:11:33.813Z
Funnily enough, UTF-32 has constant time indexing, at the cost of being incredibly wasteful of space.
qwr
<h1>Short String Optimization</h1>
<p>One way one could save having to allocate a separate buffer at a separate location is <strong>short string optimization</strong>. The idea is if the string is shorter than the size of a pointer, the data can be stored in the space of the pointer. However, this requires knowing the size of the string <strong>beforehand</strong>. An example of how this could be implemented in C would be:</p>
<pre><code>typedef struct String {
    size_t len;
    union {
        char *ptr, data[sizeof(char *)];
    };
} String;
</code></pre>
<p>And if <code>len &lt; sizeof(char *)</code>, access <code>data</code> directly, otherwise, access <code>ptr</code>.</p>
<p>A language could have string optimizations like this built-in, but of course, this is only possible if the length is known before-hand, which is not possible with null-terminated strings.</p>

CC BY-SA 4.0
2023-11-08T18:03:17.517Z
2023-11-08T18:03:17.517Z
CPlus
<p>Zero-terminated strings have two main advantages:</p>
<ol>
<li><p>It's easy to design code that can process zero-terminated strings and zero-padded strings in known-length buffers interchangeably.</p>
</li>
<li><p>Approaches involving prefixed strings involve engineering trade-offs; although in many cases, zero-terminated strings will be worse than even less-than-ideal prefixed forms, data interchange between prefixed string implementations which make different trade-offs will be awkward.</p>
</li>
</ol>
<p>For many purposes, it would be useful to have a format where the byte pointed to by a &quot;string pointer&quot; will be one of the following, using different ranges of values to represent them:</p>
<ol>
<li><p>Part of the length of a length-prefixed string which fills the allocated space.</p>
</li>
<li><p>Part of the length of a length-prefixed string buffer which is presently empty.</p>
</li>
<li><p>Part of the length of a length-prefixed string buffer which is partially full, and whose last byte value X either indicates--if less than 128--that it is (X+1) bytes away from being full, or indicates that the preceding 256-X bytes hold the number of empty bytes at the end of the buffer.</p>
</li>
<li><p>A pointer to a &quot;type marker&quot; byte for a structure resembling one of the following:</p>
<pre><code> struct readableStringRef {
   unsigned char typeMarker,dummy;
   unsigned length;
   char *content;
 };
</code></pre>
<p>or</p>
<pre><code> struct writableStringRef {
   unsigned char typeMarker,dummy;
   unsigned length;
   char *content;
   unsigned buffer_size;
   unsigned (*adjust_func)(void* string, unsigned op, 
                           unsigned param, void *param2);
 };
</code></pre>
</li>
</ol>
<p>Code which receives a pointer to a string in any of the above numbered formats could call one of two functions to convert it into one of the two structures in (4), based upon whether the code would need to modify the string's length.  Code which needs to e.g. append something to a string could then be agnostic to whether it was stored in a buffer, in <code>malloc</code> storage, storage managed by some other means, etc. and code which needs to pass a substring to a function that will only read it could construct a <code>readableStringRef</code> identifying that substring, whether or not it was the tail, without having to copy or modify the original string.</p>

CC BY-SA 4.0
2023-07-17T16:19:08.030Z
2023-07-18T11:41:16.040Z
2023-07-18T11:41:16.040Z
supercat
CC BY-SA 4.0
2024-07-25T14:17:42.533Z
https://github.com/antirez/sds does something funny in that it has a pointer to the start of the array and is null terminated, but also has the string struct before the pointer.
qwr
CC BY-SA 4.0
2024-07-25T22:58:56.053Z
@qwr: A difference between what I would advocate and that approach is that while fixed-sized string buffers would encode the length before the text, dynamic strings would not.  A function given a pointter to a string would need to use a 'standard' function to either construct or return the address of a descriptor (the function would accept a pointer to storage that could be used to hold a descriptor if given a pointer to a length-prefixed string, and either build a descriptor there and return its address, or return the string pointer if it already *was* a descriptor.
supercat
<h1>Real-world usage of null-terminated strings</h1>
<p>The only reason we still care about <a href="https://en.wikipedia.org/wiki/Null-terminated_string" rel="nofollow noreferrer">null-terminated strings</a> is because of the widespread usage of C strings and all the APIs built for them. It's simple to write some basic C or assembly functions that process a string byte by byte and stop at a null byte:</p>
<pre class="lang-c prettyprint-override"><code>while (*s) {
    putchar(*s);
    ++s;
}
</code></pre>
<p>Example compiled assembly from GCC <code>-Os</code>:</p>
<pre class="lang-x86asm prettyprint-override"><code>                                   # s starts in rbx 
L:  movsx   edi, BYTE PTR [rbx]    # while (*s)
    test    dil, dil               # 
    je      done                   # { 
    call    putchar                #   putchar(*s)
    inc     rbx                    #   ++s
    jmp     L                      # }
</code></pre>
<p>...but not <em>that</em> much simpler than comparing <code>s</code> to an end address <code>s+len</code> (GCC outsmarted me and saved an instruction in the loop, because I just counted down <code>len</code>):</p>
<pre class="lang-c prettyprint-override"><code>char* end = s + len;
while (s != end) {
    putchar(*s);
    ++s;
}
</code></pre>
<pre class="lang-x86asm prettyprint-override"><code>                                # s starts in rbx, len starts in rax
    lea     rbp, [rbx+rax]      # end = s + len
L:  cmp     rbx, rbp            # while (s != end) 
    je      done                # {
    movsx   edi, BYTE PTR [rbx] #    
    call    putchar             #   putchar(*s)  
    inc     rbx                 #   ++s  (gcc actually reorders inc before call?)
    jmp     L                   # }
</code></pre>
<h1>Vulnerabilities</h1>
<p>The massive downside is that a null-terminated string requires the string to have a null byte at the end AND not earlier. The vulnerabilities are numerous and very costly. Can you spot the problem in each example?</p>
<ul>
<li><a href="https://cwe.mitre.org/data/definitions/170.html" rel="nofollow noreferrer">CWE-170: Improper Null Termination</a></li>
</ul>
<pre class="lang-c prettyprint-override"><code>#define MAXLEN 1024
...
char *pathbuf[MAXLEN];
...
read(cfgfile,inputbuf,MAXLEN); 
strcpy(pathbuf,inputbuf);
...
</code></pre>
<ul>
<li><a href="https://cwe.mitre.org/data/definitions/463.html" rel="nofollow noreferrer">CWE-463: Deletion of Data Structure Sentinel</a> (sentinel being the null-terminator)</li>
</ul>
<pre class="lang-c prettyprint-override"><code>char *foo;
int counter;
foo=calloc(sizeof(char)*10);

for (counter=0;counter!=10;counter++) {
foo[counter]='a';

printf(&quot;%s\n&quot;,foo);
}
</code></pre>
<ul>
<li><a href="https://cwe.mitre.org/data/definitions/464.html" rel="nofollow noreferrer">CWE-464: Addition of Data Structure Sentinel</a> (Null byte injection)</li>
</ul>
<pre class="lang-c prettyprint-override"><code>char *foo;
foo=malloc(sizeof(char)*5);
foo[0]='a';
foo[1]='a';
foo[2]=0;  // example doesn't compile here so I simplified it
foo[3]='c';
foo[4]='\0';  // example has missing ; here
printf(&quot;%c %c %c %c %c \n&quot;,foo[0],foo[1],foo[2],foo[3],foo[4]);
printf(&quot;%s\n&quot;,foo);
</code></pre>
<ul>
<li><a href="https://cwe.mitre.org/data/definitions/193.html" rel="nofollow noreferrer">CWE-193: Off-by-one Error</a> especially common in string length calculations. This kind of thing is really easy to overlook:</li>
</ul>
<pre class="lang-c prettyprint-override"><code>char firstname[20];
char lastname[20];
char fullname[40];

fullname[0] = '\0';

strncat(fullname, firstname, 20);
strncat(fullname, lastname, 20);
</code></pre>
<p>The <code>strn*</code> functions aren't always safe. <a href="https://en.cppreference.com/w/c/string/byte/strncat" rel="nofollow noreferrer"><code>strncat(dest, src, count)</code></a> always puts a null character at the end, so can write up to <code>count+1</code> bytes! But <a href="https://en.cppreference.com/w/c/string/byte/strncpy" rel="nofollow noreferrer"><code>strncpy(dest, src, count)</code></a> <em>won't</em> null-terminate the result if <code>count</code> is reached before the entire <code>src</code> is copied.</p>
<h1>Length-based strings</h1>
<p>All mainstream languages since C that have a string object have used length-based strings because C strings are so painful and error-prone. A length-based string is easy to implement too (except in assembly that doesn't have structs). The most basic example is a struct holding 1. the length and 2. a pointer to or <a href="https://stackoverflow.com/questions/68769314/what-is-a-flexible-array-member-in-a-struct">flexible array member</a> (<a href="https://developers.redhat.com/articles/2022/09/29/benefits-limitations-flexible-array-members#" rel="nofollow noreferrer">saves you one dereference</a>) of the data.</p>
<pre class="lang-c prettyprint-override"><code>struct string {
  size_t len;
  char data[];  // flexible array member must come at end
}; 
</code></pre>
<p>(Since the flexible array member has data &quot;inline&quot;, it requires allocating <code>sizeof(struct string) + len</code> bytes.)</p>
<p>A <code>size_t len</code> might take 4 or 8 bytes instead of 1 null-terminating byte, but
many non-trivial string tasks require keeping track of the length of the string or buffer separately anyway, if you don't want to waste time re-computing it with <code>strlen</code> every time. Plus if those extra bytes really matter, you could do an initial length byte limited to 255 and support &quot;short strings&quot; with the same space overhead of a single byte, or a 2 byte length that can support a very reasonable 65535 characters at the cost of only 1 extra byte. From the Wikipedia article:</p>
<blockquote>
<p>FreeBSD developer Poul-Henning Kamp, writing in ACM Queue, referred to the victory of null-terminated strings over a 2-byte (not one-byte) length as &quot;the most expensive one-byte mistake&quot; ever.</p>
</blockquote>
<p>A dynamically-sized string or array could also track a <code>size_t capacity</code> for re-allocating when growing or shrinking.
<a href="https://github.com/antirez/sds" rel="nofollow noreferrer">SDS strings</a> are one implementation that combine a C-string with a prefix before the &quot;data pointer&quot; and a null terminator at the end.</p>

CC BY-SA 4.0
2024-07-19T20:57:56.040Z
2024-07-25T23:26:48.897Z
2024-07-25T23:26:48.897Z
qwr
<p>Null-terminated strings can't include the null byte, whereas length-prefixed ones can include all 256 possible binary values.</p>

CC BY-SA 4.0
2023-05-17T01:30:28.530Z
2023-05-17T01:30:28.530Z
pppery
CC BY-SA 4.0
2023-05-21T23:01:49.300Z
We're talking character strings here, not binary strings, so there's more than 256 possible values. Java, when exporting strings to C, will translate the null byte to C0 80 which is technically invalid in UTF-8 but which would decode to the null byte.
prosfilaes
CC BY-SA 4.0
2023-07-17T21:23:41.743Z
There's always [modified UTF-8](https://docs.oracle.com/javase/specs/jvms/se16/html/jvms-4.html#jvms-4.4.7) but that way lies madness.
Mike Samuel
CC BY-SA 4.0
2023-07-18T21:46:55.463Z
@prosfilaes: Many programs exist for the purpose of processing text *which will be primarily processed by other programs, rather than humans*.  As such, there's no need to worry about variable-length code points and other gratuitous complications.
supercat
CC BY-SA 4.0
2023-07-19T16:33:57.593Z
@supercat If you're processing an XML file, you need to recognize U+00A0 as a space. If you're processing a C file, you need to parse variable-length codes points to find if something is a valid identifier. Text files have Unicode and variable-length code points; if you want binary, you know where to find it. This idea that variable-length code points are gratuitous when they're necessary for text for humans is bizarre.
prosfilaes
CC BY-SA 4.0
2023-07-19T16:44:51.973Z
@prosfilaes: If one is processing XML files, one would need to write code to work with specific byte sequences which appear in that file; processing of such byte sequences should be an application issue, rather than a language issue.  Likewise if one wants to support C dialects that use gratuitously complicated rules to allow visually-indistinguishable idenifiers, rather than sticking with the standard C source code character set, such processing should be the responsibility of the compiler application code, rather than the language the compiler is written in.
supercat
CC BY-SA 4.0
2023-07-19T16:50:15.717Z
@prosfilaes: Having a facility to allow string literals to be encoded using something other than their source-file byte representation may be useful language feature, but there's no reason it should be limited to Unicode rather than allowing a program to generate literals using specified translation tables.
supercat
CC BY-SA 4.0
2023-07-19T17:00:19.200Z
@prosfilaes: More generally, a language that can work with arbitrary binary blobs will be able to, with proper application code, work with all present and future methods of encoding information as a sequence of octets  By contrast, a language which tries to add special semantics to certain byte sequences will be unable to work with information encoded in ways for which such treatment would be inappropriate.
supercat
CC BY-SA 4.0
2023-07-19T17:12:30.680Z
@supercat The standard C source code character set is Unicode. Welcome to the 21st century and ISO/IEC 9899:2018. Unicode is older now than ASCII was when Unicode was created, and actually supports the world. If you want to deal with binary blobs, deal with binary blobs; note that the null byte is a valid character in binary blobs. But if you want to deal with strings and text, accept that text is now Unicode, not ASCII. (Note that "tries to add special semantics to certain byte sequences" has been a permanent problem for EBCDIC users, and a lot of Unix code had to be fixed for 8-bit codes.)
prosfilaes
CC BY-SA 4.0
2023-07-19T17:31:10.577Z
@prosfilaes: C code targets that don't use Unicode vastly outnumber those that do.  Most of those targets don't do anything resembling text manipulation, but I'm pretty sure that even among targets that include text displays, the notion of "Unicode" would be far from universal.
supercat
CC BY-SA 4.0
2023-07-19T17:31:58.453Z
@supercat Then null-terminated strings, from all versions of C, are broken, as they can't work with arbitrary binary blobs. All real world languages provide a way to handle text, even in those early cases of FORTRAN and Algol-60 where it was just enough to print fixed strings. A programming language can provide ways to handle binary blobs as well as text.
prosfilaes
CC BY-SA 4.0
2023-07-19T17:32:34.920Z
If the C Standard wants to represent a subset of hosted applications that support Unicode and 32-bit `int`, that might be reasonable, but platforms that can't support 32-bit `int` aren't going to be able to usefully support Unicode either.
supercat
CC BY-SA 4.0
2023-07-19T17:33:56.637Z
@prosfilaes: The answer above these comments noted that an advantage of length-prefixed strings is that they're useful for arbitrary binary blobs, rather than only for those that don't contain null bytes or--*even worse*--the subset of such blobs that represent Unicode strings.
supercat
CC BY-SA 4.0
2023-07-19T17:37:19.550Z
@supercat Most C code is written for PC or phone, on AMD-64 or ARM 32 or 64. Platforms that can't support 32-bit int can't usefully support text; that's fine. There's not much reason for them to. Data types are more useful when they don't hold garbage; a data type that holds some but not all random binary data is less useful than a data type that holds text.
prosfilaes
CC BY-SA 4.0
2023-07-19T17:47:02.293Z
@prosfilaes: Embedded devices vastly outnumber PCs and phones.  With the exception of code whose purpose is to perform Unicode operations as a sequence of byte manipulations, most tasks that would involve Unicode text handling and all the corner cases associated therewith could be better accomplished in languages other than C.
supercat
CC BY-SA 4.0
2023-07-19T18:54:07.093Z
@supercat If you want to say most tasks that involve text handling are better accomplished in languages other than C, then fine. But general text handling is Unicode, not EBCDIC, ISO-2022 or ASCII; the days of English only output or non-user configurable language output are over.
prosfilaes
CC BY-SA 4.0
2023-07-19T19:35:40.153Z
@prosfilaes: Most of the tasks for which C is suitable would not particularly benefit from built-in language features that treat Unicode strings as anything other than binary blobs.  C may be better than some other languages for tasks that perform limited forms of string handling that can accomplished using fixed-length buffers, but most tasks that would benefit from language-level recognition of Unicode would involve dynamically-managed variable length strings, which really don't exist as a language-level concept in C.
supercat
<h1>Length-prefixed can include capacity</h1>
<p>This lets you &quot;over-allocate&quot; storage and remember how much you did so:</p>
<pre><code>0D 10 48 65 6C 6C 6F 2C 20 57 6F 72 6C 64 21 00 00 00
^  ^  ^                                      ^
|  |  data...                                over-allocation
|  capacity
length
</code></pre>
<p>This is particularly useful for languages with mutable strings, as it allows append operations to be amortized O(1).</p>

CC BY-SA 4.0
2023-05-17T00:51:16.747Z
2023-05-17T00:51:16.747Z
Bbrk24
CC BY-SA 4.0
2023-05-21T21:50:58.247Z
If you're just going to say "add a prefixing capacity" field, doesn't that apply equally well for null-terminated strings? who says you can't have a capacity prefix for a null-terminated string?
starball
CC BY-SA 4.0
2023-05-21T21:53:32.153Z
I suppose it's possible, but I don't know of any widespread implementations that prefix capacity but not length.
Bbrk24
CC BY-SA 4.0
2023-07-18T05:20:37.857Z
@starball You cannot do append operations in amortized O(1) on null-teminated strings with a capacity prefix because you still need to do find the end of the string, which is O(n).
wastl
CC BY-SA 4.0
2023-07-18T21:49:25.307Z
@wastl: One could do so if one specified that the last byte of the allocation must either be a zero if the string length is the allocation length minus one, a value 1-127 to indicate that there are 1-127 unused bytes following the null terminator, or a value 256-N to indicate that the preceding N bytes of storage hold the length of the unused portion of the storage, in little-endian format.
supercat
<p>An option missing from the question is <strong>fat pointers</strong> ─ the type <code>&amp;str</code> in Rust is an example of this. The length is not stored on the heap as a prefix to the string data, instead it is stored alongside the pointer, so that a reference to a string takes two words (length and pointer) instead of just one for a pointer.</p>
<p>This means that if there are multiple references to the same string, then the length data is duplicated compared to a length-prefixed string, which would only store the length once, where the string data is. But the upside is that a fat pointer can reference a substring without duplicating the string data on the heap.</p>
<p><a href="https://i.sstatic.net/4qWCs.png" rel="noreferrer"><img src="https://i.sstatic.net/4qWCs.png" alt="Rust String vs. &amp;str memory diagram" /></a></p>
<p>In the diagram above (<a href="https://doc.rust-lang.org/book/ch04-03-slices.html#string-slices" rel="noreferrer">from the official Rust book</a>), <code>s</code> is a <code>String</code> so it has a fat pointer to the whole string allocation (plus a <code>capacity</code> field, since it's a growable string), while <code>world</code> is a shared reference (i.e. a fat pointer) to a substring. This sharing would not be possible with length-prefixing, and would be possible with null-termination for substrings at the end of the string but not otherwise.</p>

CC BY-SA 4.0
2023-05-17T01:45:35.503Z
2023-05-17T01:45:35.503Z
kaya3
CC BY-SA 4.0
2023-07-17T18:12:59.273Z
Fat pointers are orthogonal to the question and are just a way to implement the length-based variant.
feldentm
CC BY-SA 4.0
2023-07-18T08:27:55.950Z
C++ strings (and string_views) follow this model, too (in most implementations).
Toby Speight
CC BY-SA 4.0
2024-07-20T01:32:16.357Z
This schema has a drawback when you want to modify the contents of the string, since you cannot change (nor free) those bytes. So you would have to use immutable strings and implement some kind of garbage collection...
Ángel
CC BY-SA 4.0
2024-07-21T23:24:56.743Z
Immutable strings can have Copy on Write
qwr
CC BY-SA 4.0
2024-07-22T16:08:32.227Z
@qwr: In the absence of a tracing collector, code which wants to replace a reference to a possible-shared immutable string with a reference to a different string would need to do an synchronized decrement of the reference count and ensure that eliminating the last reference to a string would either free the original string or (if it had the desired length) recycle it into a non-sharable mutable string instead of creating a new object.
supercat
CC BY-SA 4.0
2024-07-24T22:34:36.677Z
@Ángel @supercat or some way of proving that no other references live long enough to conflict with your mutation. Like rusts Borrow checker. Rust doesn't need cow, gc, or a reference count for this. It uses the `&mut` borrowing rules to safely allow modifying the buffer if there are no references.
user1937198
CC BY-SA 4.0
2024-12-15T00:31:35.017Z
@user1937198: If one has e.g. a hashmap which associates each key with a structure containing a few string references, how would Rust handle code which needs to change one of the string references at a time when it may or may not be the last existing reference to a string, without requiring synchronization with everything else that might be left holding the last reference?
supercat
CC BY-SA 4.0
2024-12-15T00:49:38.573Z
@supercat Require you to be holding mutable ownership of the hashmap whilst accessing the key, and not give that up until you give up mutable ownership of the referenced string value. Giving up the referenced string value is standard value borrowing. Getting hold of the hashmap ownership is standard borrowing, and the transitive relation is specified in the hashmap API lifetime parameters.
Because you have mut ownership to the hashmap you know there are no preexisting references. And because you give it up at the end, you know there are no extant references to the string leaking.
user1937198
CC BY-SA 4.0
2024-12-15T06:59:33.070Z
@user1937198: If the hashmap holds one of two extent references to a shared immutable string object, and another completely inependent hashmap holds the other reference to that shared string object, and both hashmaps are asked to replace that string reference with a reference to a different string, how would they synchronize their actions to ensure the string got deleted exactly once once the last reference was deleted?
supercat
CC BY-SA 4.0
2024-12-15T13:30:39.507Z
@supercat that would not compile.
user1937198
CC BY-SA 4.0
2024-12-15T13:46:40.680Z
Simply put, Ángel's claim that this option requires either a GC or immutable strings is not true, because this is how Rust does strings, Rust is not GC'd, and Rust has mutable strings. If you aren't sure how Rust is able to do that safely, read up on ownership and borrow checking, and if you are still unsure then [ask a question](https://langdev.stackexchange.com/questions/ask) - this comment section isn't a suitable or possible place to explain Rust's entire memory model.
kaya3
CC BY-SA 4.0
2024-12-15T13:49:49.670Z
The short answer is that if a hashmap contains two shared references to a string, then neither reference has any responsibility for freeing the string when the reference is cleared. Either the string has a static lifetime (i.e. it never needs to be freed, either it's part of the program's static data or it was intentionally leaked), or some other place besides the hashmap has ownership (i.e. they will free the string later, and the compiler will check that it happens after the hashmap is cleared and not before).
kaya3
CC BY-SA 4.0
2024-12-15T13:55:11.280Z
That said, you could make this work without a borrow checker by just making the pointer fatter: store the address of the start of the string (where a reference counter exists), an offset, and a length. Since that data is stored in the pointer, it still does not require the string itself to be length-prefixed or null-terminated.
kaya3
CC BY-SA 4.0
2024-12-15T19:26:16.130Z
@kaya3: In other words, if there is no other outside entity which would have responsibility for ownership, one either needs to synchronize all actions involving refreences to a string, or else to have a garbage collector that can forcibly globally synchronize its actions with those of everything that could manipulate references to strings.
supercat
<p>Length-prefixed strings have the advantage of being able to find their length in O(1) time rather than O(n) time. This means you can find the end of the string more easily with the length prefix. They are also less error prone to use since you don't have to deal with forgetting to null terminate a string.</p>
<p>One disadvantage to length prefixed strings is that they require more space. In addition, you are limited in what the max size of the string can be based on how many bytes are used to store the length.</p>

CC BY-SA 4.0
2023-05-17T00:49:27.650Z
2023-05-17T00:59:34.637Z
2023-05-17T00:59:34.637Z
Isaiah
CC BY-SA 4.0
2023-07-19T17:40:33.757Z
Strings which are prefixed by a variable-length prefix would require the same amount of space as zero-terminated strings when they're short enough to encode the length in a single byte.  One could encapsulate *both* buffer size and current length with a single byte of overhead [same as zero-termination] for strings or buffers up to 63 bytes, two bytes for strings up to 4095 bytes, and five bytes for strings up to 2GiB, while leaving a few prefix byte values available for other purposes.
supercat
CC BY-SA 4.0
2023-11-12T05:54:39.013Z
@supercat another way to do it is the ASN.1/DER scheme.
Karl Knechtel
CC BY-SA 4.0
2023-11-13T15:53:09.347Z
@KarlKnechtel: The scheme I was describing would allow the length of a string to be dynamically changed to any value less than the length of the buffer.  Effectively, one *bit* in the prefix says whether the buffer is full or not, and if the buffer isn't full then either there will a byte at the end to record that it's one byte short of full, two bytes to report that it's 1-255 bytes short of being full, or lots of bytes to report any amount of space short of being full.
supercat
CC BY-SA 4.0
2023-11-13T20:57:43.733Z
Yes, I understood that. I'm only saying that there are pre-existing schemes that do the same thing and might be considered more standardized.
Karl Knechtel
CC BY-SA 4.0
2024-07-22T15:51:23.623Z
@KarlKnechtel: I am unaware of any standard for any method that encapsulates both the size of the a buffer and its present length using only one more bit (or limiting the length range by a factor of two) compared with storing the size alone.
supercat
# What are the advantages/disadvantages of null-terminated strings vs length-prefixed strings?
Posted by: username_0 on 2023-05-17
There are two main ways to implement strings in a language: null-terminated and length-prefixed strings.
From Wikipedia:

A null-terminated string is a character string stored as an array
containing the characters and terminated with a null character, often this is the null character (NUL), which has all bits zero.

and:

Length-prefixed
The length of a string can also be stored explicitly,   for example
by prefixing the string with the length as a byte value.

For example, the string "Hello, World!", when using null-terminated strings (using ASCII), is stored as:
48 65 6C 6C 6F 2C 20 57 6F 72 6C 64 21 00
                                       ^^
                                       the NUL character

and using length-prefixed string:
0D 48 65 6C 6C 6F 2C 20 57 6F 72 6C 64 21
^^
the length byte

These approach is vastly different, so what are the advantages of advantages/disadvantages of using one instead of another?
**Tags:** implementation strings
> **Comments:**
> **username_4**: how is this really a _language_-related question as opposed to a computer science question? Because you mention "implementation" in the question but not "design", so I'm not sure as someone considering answering this question if you care about language design questions like usability- aside from which I'm not really sure if there's more to say than is just about the computer-science face of the question.  
> **username_3**: See also: https://stackoverflow.com/questions/25068903/what-are-pascal-strings  
> **username_1**: A common trick for ASCII strings (pre-unicode) was to use the 8th bit in the byte to mark the end of the string -- the last character would have it set (or clear) and all the others would have it clear (or set).  
> **username_2**: You might be entertained by my very first blog post from 2003 which was on this subject. https://ericlippert.com/2003/09/12/erics-complete-guide-to-bstr-semantics/  
---
## 12 answers
### Answer by username_20 on 2023-05-17. Score: 15
An option missing from the question is **fat pointers** ─ the type `&str` in Rust is an example of this. The length is not stored on the heap as a prefix to the string data, instead it is stored alongside the pointer, so that a reference to a string takes two words (length and pointer) instead of just one for a pointer.

This means that if there are multiple references to the same string, then the length data is duplicated compared to a length-prefixed string, which would only store the length once, where the string data is. But the upside is that a fat pointer can reference a substring without duplicating the string data on the heap.

[![Rust String vs. &str memory diagram](https://i.sstatic.net/4qWCs.png)](https://i.sstatic.net/4qWCs.png)

In the diagram above ([from the official Rust book](https://doc.rust-lang.org/book/ch04-03-slices.html#string-slices)), `s` is a `String` so it has a fat pointer to the whole string allocation (plus a `capacity` field, since it's a growable string), while `world` is a shared reference (i.e. a fat pointer) to a substring. This sharing would not be possible with length-prefixing, and would be possible with null-termination for substrings at the end of the string but not otherwise.
> **Comments:**
> **username_8** (2023-07-17): Fat pointers are orthogonal to the question and are just a way to implement the length-based variant.  
> **username_21** (2023-07-18): C++ strings (and string_views) follow this model, too (in most implementations).  
> **username_22** (2024-07-20): This schema has a drawback when you want to modify the contents of the string, since you cannot change (nor free) those bytes. So you would have to use immutable strings and implement some kind of garbage collection...  
> **username_12** (2024-07-21): Immutable strings can have Copy on Write  
> **username_6** (2024-07-22): @qwr: In the absence of a tracing collector, code which wants to replace a reference to a possible-shared immutable string with a reference to a different string would need to do an synchronized decrement of the reference count and ensure that eliminating the last reference to a string would either free the original string or (if it had the desired length) recycle it into a non-sharable mutable string instead of creating a new object.  
> **username_23** (2024-07-24): @Ángel @supercat or some way of proving that no other references live long enough to conflict with your mutation. Like rusts Borrow checker. Rust doesn't need cow, gc, or a reference count for this. It uses the `&mut` borrowing rules to safely allow modifying the buffer if there are no references.  
> **username_6** (2024-12-15): @user1937198: If one has e.g. a hashmap which associates each key with a structure containing a few string references, how would Rust handle code which needs to change one of the string references at a time when it may or may not be the last existing reference to a string, without requiring synchronization with everything else that might be left holding the last reference?  
> **username_23** (2024-12-15): @supercat Require you to be holding mutable ownership of the hashmap whilst accessing the key, and not give that up until you give up mutable ownership of the referenced string value. Giving up the referenced string value is standard value borrowing. Getting hold of the hashmap ownership is standard borrowing, and the transitive relation is specified in the hashmap API lifetime parameters.
Because you have mut ownership to the hashmap you know there are no preexisting references. And because you give it up at the end, you know there are no extant references to the string leaking.  
> **username_6** (2024-12-15): @user1937198: If the hashmap holds one of two extent references to a shared immutable string object, and another completely inependent hashmap holds the other reference to that shared string object, and both hashmaps are asked to replace that string reference with a reference to a different string, how would they synchronize their actions to ensure the string got deleted exactly once once the last reference was deleted?  
> **username_23** (2024-12-15): @supercat that would not compile.  
> **username_20** (2024-12-15): Simply put, Ángel's claim that this option requires either a GC or immutable strings is not true, because this is how Rust does strings, Rust is not GC'd, and Rust has mutable strings. If you aren't sure how Rust is able to do that safely, read up on ownership and borrow checking, and if you are still unsure then [ask a question](https://langdev.stackexchange.com/questions/ask) - this comment section isn't a suitable or possible place to explain Rust's entire memory model.  
> **username_20** (2024-12-15): The short answer is that if a hashmap contains two shared references to a string, then neither reference has any responsibility for freeing the string when the reference is cleared. Either the string has a static lifetime (i.e. it never needs to be freed, either it's part of the program's static data or it was intentionally leaked), or some other place besides the hashmap has ownership (i.e. they will free the string later, and the compiler will check that it happens after the hashmap is cleared and not before).  
> **username_20** (2024-12-15): That said, you could make this work without a borrow checker by just making the pointer fatter: store the address of the start of the string (where a reference counter exists), an offset, and a length. Since that data is stored in the pointer, it still does not require the string itself to be length-prefixed or null-terminated.  
> **username_6** (2024-12-15): @kaya3: In other words, if there is no other outside entity which would have responsibility for ownership, one either needs to synchronize all actions involving refreences to a string, or else to have a garbage collector that can forcibly globally synchronize its actions with those of everything that could manipulate references to strings.  
---
### Answer by username_24 on 2023-05-17. Score: 14
Length-prefixed strings have the advantage of being able to find their length in O(1) time rather than O(n) time. This means you can find the end of the string more easily with the length prefix. They are also less error prone to use since you don't have to deal with forgetting to null terminate a string.

One disadvantage to length prefixed strings is that they require more space. In addition, you are limited in what the max size of the string can be based on how many bytes are used to store the length.
> **Comments:**
> **username_6** (2023-07-19): Strings which are prefixed by a variable-length prefix would require the same amount of space as zero-terminated strings when they're short enough to encode the length in a single byte.  One could encapsulate *both* buffer size and current length with a single byte of overhead [same as zero-termination] for strings or buffers up to 63 bytes, two bytes for strings up to 4095 bytes, and five bytes for strings up to 2GiB, while leaving a few prefix byte values available for other purposes.  
> **username_25** (2023-11-12): @supercat another way to do it is the ASN.1/DER scheme.  
> **username_6** (2023-11-13): @KarlKnechtel: The scheme I was describing would allow the length of a string to be dynamically changed to any value less than the length of the buffer.  Effectively, one *bit* in the prefix says whether the buffer is full or not, and if the buffer isn't full then either there will a byte at the end to record that it's one byte short of full, two bytes to report that it's 1-255 bytes short of being full, or lots of bytes to report any amount of space short of being full.  
> **username_25** (2023-11-13): Yes, I understood that. I'm only saying that there are pre-existing schemes that do the same thing and might be considered more standardized.  
> **username_6** (2024-07-22): @KarlKnechtel: I am unaware of any standard for any method that encapsulates both the size of the a buffer and its present length using only one more bit (or limiting the length range by a factor of two) compared with storing the size alone.  
---
### Answer by username_15 on 2023-05-17. Score: 13
Null-terminated strings can't include the null byte, whereas length-prefixed ones can include all 256 possible binary values.
> **Comments:**
> **username_16** (2023-05-21): We're talking character strings here, not binary strings, so there's more than 256 possible values. Java, when exporting strings to C, will translate the null byte to C0 80 which is technically invalid in UTF-8 but which would decode to the null byte.  
> **username_17** (2023-07-17): There's always [modified UTF-8](https://docs.oracle.com/javase/specs/jvms/se16/html/jvms-4.html#jvms-4.4.7) but that way lies madness.  
> **username_6** (2023-07-18): @prosfilaes: Many programs exist for the purpose of processing text *which will be primarily processed by other programs, rather than humans*.  As such, there's no need to worry about variable-length code points and other gratuitous complications.  
> **username_16** (2023-07-19): @supercat If you're processing an XML file, you need to recognize U+00A0 as a space. If you're processing a C file, you need to parse variable-length codes points to find if something is a valid identifier. Text files have Unicode and variable-length code points; if you want binary, you know where to find it. This idea that variable-length code points are gratuitous when they're necessary for text for humans is bizarre.  
> **username_6** (2023-07-19): @prosfilaes: If one is processing XML files, one would need to write code to work with specific byte sequences which appear in that file; processing of such byte sequences should be an application issue, rather than a language issue.  Likewise if one wants to support C dialects that use gratuitously complicated rules to allow visually-indistinguishable idenifiers, rather than sticking with the standard C source code character set, such processing should be the responsibility of the compiler application code, rather than the language the compiler is written in.  
> **username_6** (2023-07-19): @prosfilaes: Having a facility to allow string literals to be encoded using something other than their source-file byte representation may be useful language feature, but there's no reason it should be limited to Unicode rather than allowing a program to generate literals using specified translation tables.  
> **username_6** (2023-07-19): @prosfilaes: More generally, a language that can work with arbitrary binary blobs will be able to, with proper application code, work with all present and future methods of encoding information as a sequence of octets  By contrast, a language which tries to add special semantics to certain byte sequences will be unable to work with information encoded in ways for which such treatment would be inappropriate.  
> **username_16** (2023-07-19): @supercat The standard C source code character set is Unicode. Welcome to the 21st century and ISO/IEC 9899:2018. Unicode is older now than ASCII was when Unicode was created, and actually supports the world. If you want to deal with binary blobs, deal with binary blobs; note that the null byte is a valid character in binary blobs. But if you want to deal with strings and text, accept that text is now Unicode, not ASCII. (Note that "tries to add special semantics to certain byte sequences" has been a permanent problem for EBCDIC users, and a lot of Unix code had to be fixed for 8-bit codes.)  
> **username_6** (2023-07-19): @prosfilaes: C code targets that don't use Unicode vastly outnumber those that do.  Most of those targets don't do anything resembling text manipulation, but I'm pretty sure that even among targets that include text displays, the notion of "Unicode" would be far from universal.  
> **username_16** (2023-07-19): @supercat Then null-terminated strings, from all versions of C, are broken, as they can't work with arbitrary binary blobs. All real world languages provide a way to handle text, even in those early cases of FORTRAN and Algol-60 where it was just enough to print fixed strings. A programming language can provide ways to handle binary blobs as well as text.  
> **username_6** (2023-07-19): If the C Standard wants to represent a subset of hosted applications that support Unicode and 32-bit `int`, that might be reasonable, but platforms that can't support 32-bit `int` aren't going to be able to usefully support Unicode either.  
> **username_6** (2023-07-19): @prosfilaes: The answer above these comments noted that an advantage of length-prefixed strings is that they're useful for arbitrary binary blobs, rather than only for those that don't contain null bytes or--*even worse*--the subset of such blobs that represent Unicode strings.  
> **username_16** (2023-07-19): @supercat Most C code is written for PC or phone, on AMD-64 or ARM 32 or 64. Platforms that can't support 32-bit int can't usefully support text; that's fine. There's not much reason for them to. Data types are more useful when they don't hold garbage; a data type that holds some but not all random binary data is less useful than a data type that holds text.  
> **username_6** (2023-07-19): @prosfilaes: Embedded devices vastly outnumber PCs and phones.  With the exception of code whose purpose is to perform Unicode operations as a sequence of byte manipulations, most tasks that would involve Unicode text handling and all the corner cases associated therewith could be better accomplished in languages other than C.  
> **username_16** (2023-07-19): @supercat If you want to say most tasks that involve text handling are better accomplished in languages other than C, then fine. But general text handling is Unicode, not EBCDIC, ISO-2022 or ASCII; the days of English only output or non-user configurable language output are over.  
> **username_6** (2023-07-19): @prosfilaes: Most of the tasks for which C is suitable would not particularly benefit from built-in language features that treat Unicode strings as anything other than binary blobs.  C may be better than some other languages for tasks that perform limited forms of string handling that can accomplished using fixed-length buffers, but most tasks that would benefit from language-level recognition of Unicode would involve dynamically-managed variable length strings, which really don't exist as a language-level concept in C.  
---
### Answer by username_18 on 2023-05-17. Score: 11
Length-prefixed can include capacity
This lets you "over-allocate" storage and remember how much you did so:
0D 10 48 65 6C 6C 6F 2C 20 57 6F 72 6C 64 21 00 00 00
^  ^  ^                                      ^
|  |  data...                                over-allocation
|  capacity
length

This is particularly useful for languages with mutable strings, as it allows append operations to be amortized O(1).
> **Comments:**
> **username_4** (2023-05-21): If you're just going to say "add a prefixing capacity" field, doesn't that apply equally well for null-terminated strings? who says you can't have a capacity prefix for a null-terminated string?  
> **username_18** (2023-05-21): I suppose it's possible, but I don't know of any widespread implementations that prefix capacity but not length.  
> **username_19** (2023-07-18): @starball You cannot do append operations in amortized O(1) on null-teminated strings with a capacity prefix because you still need to do find the end of the string, which is O(n).  
> **username_6** (2023-07-18): @wastl: One could do so if one specified that the last byte of the allocation must either be a zero if the string length is the allocation length minus one, a value 1-127 to indicate that there are 1-127 unused bytes following the null terminator, or a value 256-N to indicate that the preceding N bytes of storage hold the length of the unused portion of the storage, in little-endian format.  
---
### Answer by username_8 on 2023-07-17. Score: 8
Length-based strings have two non-obvious performance advantages:

Concatenating lots of them into a big chunk is faster as you can preallocate the correct buffer size by just looking at the lengths.

Furthermore, comparing lots of strings with different lengths but common prefixes is faster. An example of this is a set of fully qualified names like `java.util.Set`, `java.util.HashSet`, `java.util.Collection`, etc.

The non-obvious advantage of zero-terminated strings is that one doesn't have to think up front about the length of an index type, i.e. setting the length to e.g. 32bit won't create a compatibility issue someday.
> **Comments:**
> **username_6** (2023-08-17): On the flip side, zero-terminated strings will have a performance cost which will increase sharply as their length becomes significant relative to the CPU cache size--something that would happen long before a 32-bit length becomes a problem.  
---
### Answer by username_5 on 2023-05-17. Score: 6
# Manipulation

Manipulating length-prefixed strings is a lot easier than manipulating null-terminated ones. For example, when you concatenate strings, you just have to add the lengths, while for the null-terminated case you have the extra null to remove. When splitting strings, you have to not forget to include the null. For length-prefixed strings, you just take the length of the array and halve it.
> **Comments:**
> **username_4** (2023-05-21): okay, but when splitting strings, who says you can do it without moving data? If you give more space to fit the length prefix than for each character, then don't you have to move data? Then it's not just a usability cost- it's a performance cost...  
> **username_5** (2023-11-06): @starball i never said you can do it without moving data.  
> **username_6** (2024-07-22): @starball: If code which expects to work with a string first calls a function to convert a string pointer into text address and length, and if special prefix values are reserved for data records that, instead of holding a string directly, hold the address and length of the actual string content, then one could pass arbitrary substrings to code which expects to receive a single "string pointer", without having to copy any string data (construct a record containing a header, the address of the start of the desired substring, and the length of the desired substrign).  
> **username_4** (2024-07-22): @supercat sure. that's my understanding of what `std::stringview` is. but in the context o this question, I think it's debatable whether that counts as being the string itself. `std::stringview`, for example, is a non-reference-counted, non-owning view type.  
> **username_6** (2024-07-22): @starball: Can code easily accept pointers to `std::string` and `std::stringview` interchangeably?  What I'd advocate would essentially be having a constructors for "readable string descriptor" and "mutable string descriptor" structures which could accept pointers to descriptors or minimal-storage-overhead in-place strings interchangeably.  
---
### Answer by username_7 on 2023-08-15. Score: 4
Null-terminated strings seem to have many disadvantages, but the biggest problem is you usually have to also store a size somewhere else, to avoid vulnerabilities, making it seemingly redundant.

But there is an unexpected advantage to also have the null terminator, that is in simple routines such as scanning a string starting from a given point for a complete grapheme cluster, you'll only need to pass one pointer, without the start of the string or the size.

Similar situations are common in any case you use characters like "commands", say escapes in quotes and regexes, and printf and datetime formats. If you have a unified format for all the escapes, it won't have any problems. But if something has to be escaped in multiple layers, or the same thing has different meaning in different layers, the code quickly becomes ugly, and someone will want to choose a raw format in all but one layer instead. Strings and regexes usually doesn't have escapes with conflicting meaning, but the designer may not think making exceptions for regexes a good idea, and may not come up with a general interface for adding escapes or making escaped quotes and the escape characters optionally kept in the escaped format. But they could be improved if the designer does.

Null-terminated strings are a bit worse than escapes, but if we are not considering the buffer size part, they mix with other levels of escapes just like escapes. Sometimes a system message is already a text message in a format that is known to not contain nulls, so using nulls this way won't have a problem. And sometimes you know the string is a valid Unicode string, and you could escape the nulls like the Java way of using an overly long presentation. The former is an indication of something is stringly typed, which is frown upon by some people. The later implies fixing the character encoding, and either trust or presanitization of user data, which are not always desirable. They may seem strange for these reasons, but if your language is designed to work in the specific situation, you really didn't break anything.

Programmers would want a raw format only because it isn't sure what the other layers would be. But if another layer is already specified in the language, and already had some rules of what is valid and what is not, having a shared way of manipulating all "commands" may even improve something, for example the grapheme cluster case. In such cases, the null terminators could not be dismissed just because they are redundant when a clearly defined buffer size is a must. And buffer sizes could be dedicated for the maximum size instead of the current string length.
---
### Answer by username_12 on 2024-07-19. Score: 3
Real-world usage of null-terminated strings
The only reason we still care about null-terminated strings is because of the widespread usage of C strings and all the APIs built for them. It's simple to write some basic C or assembly functions that process a string byte by byte and stop at a null byte:
while (*s) {
    putchar(*s);
    ++s;
}

Example compiled assembly from GCC -Os:
                                   # s starts in rbx 
L:  movsx   edi, BYTE PTR [rbx]    # while (*s)
    test    dil, dil               # 
    je      done                   # { 
    call    putchar                #   putchar(*s)
    inc     rbx                    #   ++s
    jmp     L                      # }

...but not that much simpler than comparing s to an end address s+len (GCC outsmarted me and saved an instruction in the loop, because I just counted down len):
char* end = s + len;
while (s != end) {
    putchar(*s);
    ++s;
}

                                # s starts in rbx, len starts in rax
    lea     rbp, [rbx+rax]      # end = s + len
L:  cmp     rbx, rbp            # while (s != end) 
    je      done                # {
    movsx   edi, BYTE PTR [rbx] #    
    call    putchar             #   putchar(*s)  
    inc     rbx                 #   ++s  (gcc actually reorders inc before call?)
    jmp     L                   # }

Vulnerabilities
The massive downside is that a null-terminated string requires the string to have a null byte at the end AND not earlier. The vulnerabilities are numerous and very costly. Can you spot the problem in each example?

CWE-170: Improper Null Termination

#define MAXLEN 1024
...
char *pathbuf[MAXLEN];
...
read(cfgfile,inputbuf,MAXLEN); 
strcpy(pathbuf,inputbuf);
...


CWE-463: Deletion of Data Structure Sentinel (sentinel being the null-terminator)

char *foo;
int counter;
foo=calloc(sizeof(char)*10);

for (counter=0;counter!=10;counter++) {
foo[counter]='a';

printf("%s\n",foo);
}


CWE-464: Addition of Data Structure Sentinel (Null byte injection)

char *foo;
foo=malloc(sizeof(char)*5);
foo[0]='a';
foo[1]='a';
foo[2]=0;  // example doesn't compile here so I simplified it
foo[3]='c';
foo[4]='\0';  // example has missing ; here
printf("%c %c %c %c %c \n",foo[0],foo[1],foo[2],foo[3],foo[4]);
printf("%s\n",foo);


CWE-193: Off-by-one Error especially common in string length calculations. This kind of thing is really easy to overlook:

char firstname[20];
char lastname[20];
char fullname[40];

fullname[0] = '\0';

strncat(fullname, firstname, 20);
strncat(fullname, lastname, 20);

The strn* functions aren't always safe. strncat(dest, src, count) always puts a null character at the end, so can write up to count+1 bytes! But strncpy(dest, src, count) won't null-terminate the result if count is reached before the entire src is copied.
Length-based strings
All mainstream languages since C that have a string object have used length-based strings because C strings are so painful and error-prone. A length-based string is easy to implement too (except in assembly that doesn't have structs). The most basic example is a struct holding 1. the length and 2. a pointer to or flexible array member (saves you one dereference) of the data.
struct string {
  size_t len;
  char data[];  // flexible array member must come at end
}; 

(Since the flexible array member has data "inline", it requires allocating sizeof(struct string) + len bytes.)
A size_t len might take 4 or 8 bytes instead of 1 null-terminating byte, but
many non-trivial string tasks require keeping track of the length of the string or buffer separately anyway, if you don't want to waste time re-computing it with strlen every time. Plus if those extra bytes really matter, you could do an initial length byte limited to 255 and support "short strings" with the same space overhead of a single byte, or a 2 byte length that can support a very reasonable 65535 characters at the cost of only 1 extra byte. From the Wikipedia article:

FreeBSD developer Poul-Henning Kamp, writing in ACM Queue, referred to the victory of null-terminated strings over a 2-byte (not one-byte) length as "the most expensive one-byte mistake" ever.

A dynamically-sized string or array could also track a size_t capacity for re-allocating when growing or shrinking.
SDS strings are one implementation that combine a C-string with a prefix before the "data pointer" and a null terminator at the end.
---
### Answer by username_9 on 2023-11-08. Score: 2
If you use just one byte for the length you can not have strings longer than 256 characters. The disadvantage of storing the length of a string is, that you have to make a decision about the length of the integer used to store the length of the string. If you terminate your string with a reserved byte, you do not have to make this decision. It will work equally no matter how large your storage will be.

X11 for example made such a decision. They decided that the integer used for the size of the window has 16 bit (CARD16). Even today you can not create bigger windows.
> **Comments:**
> **username_10** (2023-11-08): Welcome to PLDI!  
---
### Answer by username_11 on 2023-10-26. Score: 2
I commonly hear null-terminated strings referred to as **C strings**, and length-prefixed strings referred to as **Pascal strings**.

The advantages of null-terminated strings are that they save several bytes over length-prefixed strings. Instead of needing to store a length (generally at least two bytes), they can store a null character of just one byte.

The disadvantages of null-terminated strings are many. Indexing is O(n) instead of O(1) (though with Unicode and packed representations, the codepoint indexing of length-prefixed strings is also O(n)). Any time the length is needed for ex. reallocation, it must be recomputed, which remains an O(n) operation. They cannot contain the null byte, as it is reserved. They are **extremely unsafe**. Length checking is expensive, so it is tempting for programs to not do it, which can easily cause buffer overflows - the standard `gets` function in C is the classic example of this.
> **Comments:**
> **username_6** (2023-11-02): From my experience, the term "Pascal strings" usually refers to strings that are prefixed by a single length byte, and whose length is thus limited to 255 bytes.  As such, the overhead is the same as for a zero *terminated* string, but a byte greater than for a zero *padded* string.  While zero-terminated strings don't have a hard length limit, efficiency goes downhill with length, so in many cases where code would use strings that would get longer than 255 bytes, neither approach to holding strings will be as good as tracking the length separately.  
> **username_11** (2023-11-03): [It appears to be ambiguous.](https://stackoverflow.com/a/25069152)  
> **username_12** (2024-07-19): A length doesn't have to be at least 2 bytes. There could be a specialized short string with a 1 byte length as described above.  
> **username_13** (2024-07-21): "Instead of needing to store a length (at least two bytes)" This would benefit from clarification. It seems trivial to have one-byte length prefixes, or even variable-size length prefixes.  
> **username_13** (2024-07-21): "though with Unicode, the codepoint indexing of length-prefixed strings is also O(n)" This would also benefit from clarification. For example, Python has full unicode string support but O(1) indexing.  
> **username_12** (2024-07-25): Funnily enough, UTF-32 has constant time indexing, at the cost of being incredibly wasteful of space.  
---
### Answer by username_14 on 2023-11-08. Score: 2
Short String Optimization
One way one could save having to allocate a separate buffer at a separate location is short string optimization. The idea is if the string is shorter than the size of a pointer, the data can be stored in the space of the pointer. However, this requires knowing the size of the string beforehand. An example of how this could be implemented in C would be:
typedef struct String {
    size_t len;
    union {
        char *ptr, data[sizeof(char *)];
    };
} String;

And if len < sizeof(char *), access data directly, otherwise, access ptr.
A language could have string optimizations like this built-in, but of course, this is only possible if the length is known before-hand, which is not possible with null-terminated strings.
---
### Answer by username_6 on 2023-07-17. Score: 1
Zero-terminated strings have two main advantages:

It's easy to design code that can process zero-terminated strings and zero-padded strings in known-length buffers interchangeably.

Approaches involving prefixed strings involve engineering trade-offs; although in many cases, zero-terminated strings will be worse than even less-than-ideal prefixed forms, data interchange between prefixed string implementations which make different trade-offs will be awkward.


For many purposes, it would be useful to have a format where the byte pointed to by a "string pointer" will be one of the following, using different ranges of values to represent them:

Part of the length of a length-prefixed string which fills the allocated space.

Part of the length of a length-prefixed string buffer which is presently empty.

Part of the length of a length-prefixed string buffer which is partially full, and whose last byte value X either indicates--if less than 128--that it is (X+1) bytes away from being full, or indicates that the preceding 256-X bytes hold the number of empty bytes at the end of the buffer.

A pointer to a "type marker" byte for a structure resembling one of the following:
 struct readableStringRef {
   unsigned char typeMarker,dummy;
   unsigned length;
   char *content;
 };

or
 struct writableStringRef {
   unsigned char typeMarker,dummy;
   unsigned length;
   char *content;
   unsigned buffer_size;
   unsigned (*adjust_func)(void* string, unsigned op, 
                           unsigned param, void *param2);
 };



Code which receives a pointer to a string in any of the above numbered formats could call one of two functions to convert it into one of the two structures in (4), based upon whether the code would need to modify the string's length.  Code which needs to e.g. append something to a string could then be agnostic to whether it was stored in a buffer, in malloc storage, storage managed by some other means, etc. and code which needs to pass a substring to a function that will only read it could construct a readableStringRef identifying that substring, whether or not it was the tail, without having to copy or modify the original string.
> **Comments:**
> **username_12** (2024-07-25): https://github.com/antirez/sds does something funny in that it has a pointer to the start of the array and is null terminated, but also has the string struct before the pointer.  
> **username_6** (2024-07-25): @qwr: A difference between what I would advocate and that approach is that while fixed-sized string buffers would encode the length before the text, dynamic strings would not.  A function given a pointter to a string would need to use a 'standard' function to either construct or return the address of a descriptor (the function would accept a pointer to storage that could be used to hold a descriptor if given a pointer to a length-prefixed string, and either build a descriptor there and return its address, or return the string pointer if it already *was* a descriptor.  
---
