What are the advantages/disadvantages of null-terminated strings vs length-prefixed strings?

Question

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?

Answer 1

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.

Answer 2

Null-terminated strings can't include the null byte, whereas length-prefixed ones can include all 256 possible binary values.

Answer 3

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.

In the diagram above (from the official Rust book), 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.

Answer 4

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

Answer 5

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.

Answer 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.

Answer 7

Zero-terminated strings have two main advantages:

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

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

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

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

3. 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.

4. 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.

Answer 8

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 9

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.

Answer 10

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 11

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 (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, 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.