1 additional byte of overhead would give you 2 bytes for the length, since you wouldn't have to have the NUL byte at the end of the string.

You could do some kind of variable int encoding scheme, where longer strings would require more bytes for length, with some overhead to indicate how many length bytes are required for each string.

You don't even need that length prefix if you use something like SDNV. Ironically this would have introduced a case where you have something like a null terminator that can overflow.

It would have also been a fair bit of overhead on those old single-Mhz machines. Still, almost everything you do with strings is slow so it probably would have been manageable. As an added bonus, it is zero space overhead for short strings (up to 127 characters) which are the majority of strings.

In the PDP era, they would have noticed the overhead of having a variable-length int at the beginning they would have to decode.

In the modern era, it's probably cheap to the point of being free, because in the vast majority of cases I would expect branch prediction to largely eliminate the checks as being very predictable.

Even in the PDP era I am not so sure, given the architectures and OSes being developed outside AT&T, some of them in production.

So then....they chose correctly?

Despite being vigorously opposed to NUL-termination in the modern era, yes, I would not criticize the people who actually made the decision for the PDP. They had no real reason to believe we'd still be discussing that decision 60 years later.

Two bytes extra for the length, but one byte saved from the marker character.

There are various schemes to address this. A simple one is to make the legtth prefix variable, nad use the high order bit use the highorder bit of each byte to indicate there is another length byte following the current one. This gives you 128 possible values for each length byte. The max string size for a single byte prefix would be 127 (2^(8-1), the max size for two bytes would be 16384 (2^16-2), etc.

It's not necessarily a good solution, there are likely ones that are much more performant, but many solutions exist, and a few have even been implemented in widely used languages.

I presume the machine at the time was 16-bit, and thus you could never have a string longer than 65536 bytes in memory.

On a modern machine you'd need at least 4 bytes. `std::string` uses `size_t` (64-bits on 64-bit machines).

Length itself could also be stored with variable length encoding.

That's what I mean though - if you standardize, as part of the language, that you can have 2 bytes for the string length because at the time no machine could handle anything larger, how do you move forward once 4 or 8 bytes is not a big deal without breaking everything?

Best solution would be something like SDNV. Short strings (up to 127 characters) have no length penalty and you can handle strings of any length.

I don't think these were invented back when K&R were designing C, but it feels like something any smart computer language designer could invent if the need arose.

N-bit machines can use N-bit lengths for strings in memory. If you're storing strings your storage format has to specify a way to decide the prefix length (or you can use some other system).

For example `std::string` uses `std::size_t` as a length which is 32-bit on 32-bit machines and 64-bit on 64-bit machines. When you serialise a string to protobuf (for example) it uses a variable-length prefix. Other formats could have fixed 4-byte prefixes or whatever they want (even null-terminated).