Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

queue.acm.org

Post reply on HN
Print view View original

11–20 of 58 posts

Re: Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

#11

Post by IshKebab »

PopsiclePete wrote: post #2

>Using an address + length format would cost one more byte of overhead than an address + magic_marker format, and their PDP computer had limited core memory. I find this interesting - why only one more byte of overhead? That would've limited string lengths to 256. So 2 bytes would seem the minimum, and even then, how do you go to 4 bytes once memory becomes cheap without breaking everything? Using NUL-termination, th…

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

Re: Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

#12

Post by pjmlp »

aknoob wrote: post #8

A null-terminated representation is as close to a fundamental datatype for a string as possible. It is same in spirit as other fundamental data types in C like array. People have built abstractions over these fundamental datatypes over the years.

If it isn't in libc, it doesn't get used by anyone wanting to write portable APIs.

Re: Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

#13

Post by saint_fiasco »

IshKebab wrote: post #10
aknoob wrote: post #8

A null-terminated representation is as close to a fundamental datatype for a string as possible. It is same in spirit as other fundamental data types in C like array. People have built abstractions over these fundamental datatypes over the years.

It's not fundamental at all. You can't even represent null bytes in a null-terminated string. A length prefix is pretty clearly superior.

Why would you want to represent a null byte in a string? Is there a character encoding where the null value has a meaning?

Re: Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

#14

Post by rzzzt »

IshKebab wrote: post #11
PopsiclePete wrote: post #2

>Using an address + length format would cost one more byte of overhead than an address + magic_marker format, and their PDP computer had limited core memory. I find this interesting - why only one more byte of overhead? That would've limited string lengths to 256. So 2 bytes would seem the minimum, and even then, how do you go to 4 bytes once memory becomes cheap without breaking everything? Using NUL-termination, th…

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.

Re: Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

#15

Post by pjmlp »

JustSomeNobody wrote: post #6

Did they choose "wrong"? No. Did they make a choice and move on? Yes.

Yes, because there were already safer systems programming languages being used by the time C got invented.

OS safety was already a concern in 1961.

Re: Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

#16

Post by function_seven »

IshKebab wrote: post #10
aknoob wrote: post #8

A null-terminated representation is as close to a fundamental datatype for a string as possible. It is same in spirit as other fundamental data types in C like array. People have built abstractions over these fundamental datatypes over the years.

It's not fundamental at all. You can't even represent null bytes in a null-terminated string. A length prefix is pretty clearly superior.

A string contains characters. NUL is not a character; it's nothing.

"Fundamental" in this case means "matches reality". Having a number at the beginning doesn't match reality as closely as having the string of characters in sequential memory addresses with something to terminate them.

The quick fox made the jump\N

or

27The quick fox made the jump

The second one requires more work to store (a character-counting routine), and needs even more work to handle variable length strings that may exceed 255-ish bytes/characters.

I'm not discounting the benefits of prefixing the length, just saying it's not more fundamental than null-terminating an arbitrary sequence of characters.

Re: Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

#18

Post by jerf »

function_seven wrote: post #16
IshKebab wrote: post #10

Earlier quoted context omitted.

It's not fundamental at all. You can't even represent null bytes in a null-terminated string. A length prefix is pretty clearly superior.

A string contains characters. NUL is not a character; it's nothing. "Fundamental" in this case means "matches reality". Having a number at the beginning doesn't match reality as closely as having the string of characters in sequential memory addresses with something to terminate them. The quick fox made the jump\N or 27The quick fox made the jump The second one requires more work to store (a character-counting routin…

"A string contains characters. NUL is not a character; it's nothing."

You already couldn't make this argument stick in the ASCII era, where a string can't contain NUL but can contain SOH (Start of Heading), STX (Start of Text), ETX (End of Text), EOT (End of Transmission), ENQ (Enquiry), ACK (Acknowledge), BEL, BS, HT (horizontal tab), LF, VT (vertical tab), FF (form feed), CR, SO (shift out), SI (shift in), DLE (data link escape), DC1, DC2, DC3, DC4 (device control 1-4), NAK (negative ACK), SYN (synchronous idle), ETB (end of transmission block), CAN (cancel), EM (end of medium), SUB (substitute), ESC (escape), FS (file separator), GS (group separator), RS (record separator), US (unit separator), and DEL, but Unicode makes that argument even sillier. Strings have always contained things that aren't "characters".

The real problem is no matter what in-band character you take as the magical termination character, you will have strings that want that in it, because in the general case strings can contain anything, because C is always asking you to pass them around to things as the general-purpose storage data structure. You can fix that with an escaping scheme, but now you have an escaped string, not just "a string". Since strings do indeed need to be able to carry NUL in the general case, you either must have some sort of scheme for representing them, or expect a ton of errors when things jam the distinguished character into your string when you didn't expect it. (Note that for precisely the same reasons that NUL-termination isn't a good idea, there isn't any way to "filter" wrong NULs. You can't tell.)

You might just barely be able to argue the problem is that C's library mistook NUL-terminated strings for arbitrary-sized arrays that can contain anything, but in C if you want arbitrarily-sized arrays you would then have no choice but to pass the array size around to every call that expected such a thing. The next immediately obvious thing to do is to pack the number together with the array in a struct, and lo, we're back to length-delimited strings.

No matter how you slice it, C's got a major foundational screw-up in this area somewhere. If NUL-terminated strings are the bee's knees, C's APIs still took them in way too many places where they are not appropriate, and it caused decades of serious and often exploitable bugs.

Re: Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

#19

Post by jerf »

tbirdz wrote: post #5
PopsiclePete wrote: post #2

>Using an address + length format would cost one more byte of overhead than an address + magic_marker format, and their PDP computer had limited core memory. I find this interesting - why only one more byte of overhead? That would've limited string lengths to 256. So 2 bytes would seem the minimum, and even then, how do you go to 4 bytes once memory becomes cheap without breaking everything? Using NUL-termination, th…

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.

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.

Re: Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

#20

Post by andrewstuart2 »

function_seven wrote: post #16
IshKebab wrote: post #10

Earlier quoted context omitted.

It's not fundamental at all. You can't even represent null bytes in a null-terminated string. A length prefix is pretty clearly superior.

A string contains characters. NUL is not a character; it's nothing. "Fundamental" in this case means "matches reality". Having a number at the beginning doesn't match reality as closely as having the string of characters in sequential memory addresses with something to terminate them. The quick fox made the jump\N or 27The quick fox made the jump The second one requires more work to store (a character-counting routin…

None of it really "matches reality." It's all binary numbers, and on a deeper level, voltages or magnetized particles.

0 is not a letter of the alphabet, but nor is 01000001 (ascii 'a').

So either the first number is special, or you look for a special number to indicate the end. Neither represents reality, because the "end" of a single group of characters is visually identical to a million white-space characters that happen to fit into the emptiness that follows.

My point being, it's probably not helpful to argue which "matches reality" when they're both just abstract representations of concepts.

Post reply on HN