3 ms·

Null-terminated strings have to be up there with null-pointers as design ideas that seemed great at the time, but turned out to be extremely costly because of t

Null-terminated strings have to be up there with null-pointers as design ideas that seemed great at the time, but turned out to be extremely costly because of the insane number of bugs they produce. I wonder what an alternative world would look like where C had decided to use pascal-strings instead (prefixing the string with its length). We would undoubtedly have argued about the length of the size prefix, but a mistake there is trivial to spot compared to wrong application of str[nls]*cpy(_s)?.

pjmlp 4y ago
Specially given the alternatives outside Bell Labs in systems programming, since at least 1958 starting with JOVIAL.
tyingq 4y ago
That also would have made for a nice performance benefit passing to zero-copy type calls. And reduced complexity for new languages written in C implementing their own string types. Tcl was irritating when it was first invented, as it directly used C strings, and couldn't process binary data at all.
theamk 4y ago
I used to program in Pascal a lot, and its counted strings were one of the worst features. First, you cannot really "argue" about length of the size prefix - it is a part of ABI/calling convention, and unless you have template-like mechanism and overloading/conventions, you will have to use whatever stdlib was compiled with. And Borland Pascal's stdlib was compiled with 1 byte prefix, making max string length of 255 bytes. This made sense when total RAM was measured in hundreds of kilobytes, but generated so many bugs when a normally short string had to be just a bit longer. I was somewhat envious of my C-using friends who could put entire help message into a single string. But not envious enough to switch to much slower C tooltchain :) There were other reasons, too, like using less registers in assembly-level loops (old machines had much fewer registers than modern ones). Or not having to worry about validating strings when reading binary data from disk.
- pjmlp 4y ago
  That is why we used arrays of chars for that case, and naked Assembly blocks.
- addaon 4y ago
  One can imagine that in a world that had taken a turn towards Pascal strings, we would have ended up in a world where string lengths were varint encoded -- 7 bits of string length in the first byte, plus a continuation bit. I'd imagine that the initial (pure software) implementation of this would have no specific length limit, but we'd be back in the < 1 MB system memory days; so, continuing the imagination, early 32-bit CISC processors would reasonably invest in a varint-to-int decoding probably limited to a 4-byte memory read (28 bit string length), which would be a significant accelerator and cover all sane use cases. In the mid 32 bit era the limit of 256 MB strings would become occasionally relevant, but assuming varint-to-int set an overflow flag if the continuation bit on the last byte was set, this could be mitigated sanely; and the late 32 bit era would give a 64-bit read variant (56 bit string length plus overflow flag), which would probably be cleaned up in the 64 bit era to drop the overflow flag due to lack of use once memory address sizes < 56 bit became standard. The above is, of course, speculation on an alternate timeline -- but it's certainly consistent and believable. What's interesting is what impact such a path would have elsewhere. I'd expect two other consequences: First, our existing uses of varints (e.g. protobufs) would become faster and more efficient, and would probably appear earlier in the timeline. Second, UTF8 would likely become varint-representation-compatible, giving up the (valuable) ability to tell which byte of a codepoint is being decoded in isolation, in exchange for hardware acceleration of encoded<->codepoint conversion; and likely giving us 2^28 codepoints based on a 4-byte maximum length, rather than arbitrarily choosing a maximum length of three bytes to give 2^21 codepoints. What else would be different? Hard to say… but I do think that size prefixes could have been an alternate route.
  - theamk 4y ago
    I cannot imagine varints working well for in-memory structures, especially in C. Iterating over string with x[i] is (was?) a very common operation, and with varint length there is an extra memory fetch, extra math and a possible jump. On later CPUs, there is also unaligned reads and possible pipeline-stalling data dependency. Smart optimizers can help, but when C was designed, the compilers were pretty simple. And there are other problems -- for example, a simple act of adding a character to string can cause shift-by-1 invalidating existing pointers. Varints can be useful on disk/network streram, but I've never seen them used for actively modified in-memory storage.
david2ndaccount 4y ago
pascal strings are terrible, the correct solution is to just always have pointer+length and even better to make that a built-in type for all types.

pjmlp 4y ago

Specially given the alternatives outside Bell Labs in systems programming, since at least 1958 starting with JOVIAL.

tyingq 4y ago

That also would have made for a nice performance benefit passing to zero-copy type calls. And reduced complexity for new languages written in C implementing their own string types. Tcl was irritating when it was first invented, as it directly used C strings, and couldn't process binary data at all.

theamk 4y ago

I used to program in Pascal a lot, and its counted strings were one of the worst features. First, you cannot really "argue" about length of the size prefix - it is a part of ABI/calling convention, and unless you have template-like mechanism and overloading/conventions, you will have to use whatever stdlib was compiled with. And Borland Pascal's stdlib was compiled with 1 byte prefix, making max string length of 255 bytes. This made sense when total RAM was measured in hundreds of kilobytes, but generated so many bugs when a normally short string had to be just a bit longer. I was somewhat envious of my C-using friends who could put entire help message into a single string. But not envious enough to switch to much slower C tooltchain :) There were other reasons, too, like using less registers in assembly-level loops (old machines had much fewer registers than modern ones). Or not having to worry about validating strings when reading binary data from disk.

pjmlp 4y ago
That is why we used arrays of chars for that case, and naked Assembly blocks.
addaon 4y ago
One can imagine that in a world that had taken a turn towards Pascal strings, we would have ended up in a world where string lengths were varint encoded -- 7 bits of string length in the first byte, plus a continuation bit. I'd imagine that the initial (pure software) implementation of this would have no specific length limit, but we'd be back in the < 1 MB system memory days; so, continuing the imagination, early 32-bit CISC processors would reasonably invest in a varint-to-int decoding probably limited to a 4-byte memory read (28 bit string length), which would be a significant accelerator and cover all sane use cases. In the mid 32 bit era the limit of 256 MB strings would become occasionally relevant, but assuming varint-to-int set an overflow flag if the continuation bit on the last byte was set, this could be mitigated sanely; and the late 32 bit era would give a 64-bit read variant (56 bit string length plus overflow flag), which would probably be cleaned up in the 64 bit era to drop the overflow flag due to lack of use once memory address sizes < 56 bit became standard. The above is, of course, speculation on an alternate timeline -- but it's certainly consistent and believable. What's interesting is what impact such a path would have elsewhere. I'd expect two other consequences: First, our existing uses of varints (e.g. protobufs) would become faster and more efficient, and would probably appear earlier in the timeline. Second, UTF8 would likely become varint-representation-compatible, giving up the (valuable) ability to tell which byte of a codepoint is being decoded in isolation, in exchange for hardware acceleration of encoded<->codepoint conversion; and likely giving us 2^28 codepoints based on a 4-byte maximum length, rather than arbitrarily choosing a maximum length of three bytes to give 2^21 codepoints. What else would be different? Hard to say… but I do think that size prefixes could have been an alternate route.
- theamk 4y ago
  I cannot imagine varints working well for in-memory structures, especially in C. Iterating over string with x[i] is (was?) a very common operation, and with varint length there is an extra memory fetch, extra math and a possible jump. On later CPUs, there is also unaligned reads and possible pipeline-stalling data dependency. Smart optimizers can help, but when C was designed, the compilers were pretty simple. And there are other problems -- for example, a simple act of adding a character to string can cause shift-by-1 invalidating existing pointers. Varints can be useful on disk/network streram, but I've never seen them used for actively modified in-memory storage.

david2ndaccount 4y ago

pascal strings are terrible, the correct solution is to just always have pointer+length and even better to make that a built-in type for all types.