6 ms·

>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

>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, the upper bound for a string is effectively the amount of memory the OS is willing to give you, and code can keep working without modification for decades. Am I missing something here?

mnarayan01 9y ago
Two bytes extra for the length, but one byte saved from the marker character.
tbirdz 9y ago
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.
- jerf 9y ago
  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.
  - PopsiclePete 9y ago
    So then....they chose correctly?
    - jerf 9y ago
      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.
  - pjmlp 9y ago
    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.
- jandrese 9y ago
  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.
deleted 9y ago
[deleted]
IshKebab 9y ago
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).
- rzzzt 9y ago
  Length itself could also be stored with variable length encoding.
- PopsiclePete 9y ago
  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?
  - jandrese 9y ago
    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.
  - IshKebab 9y ago
    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).
kbenson 9y ago
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.

mnarayan01 9y ago

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

tbirdz 9y ago

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.

jerf 9y ago
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.
- PopsiclePete 9y ago
  So then....they chose correctly?
  - jerf 9y ago
    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.
- pjmlp 9y ago
  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.
jandrese 9y ago
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.

deleted 9y ago

[deleted]

IshKebab 9y ago

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

rzzzt 9y ago
Length itself could also be stored with variable length encoding.
PopsiclePete 9y ago
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?
- jandrese 9y ago
  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.
- IshKebab 9y ago
  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).

kbenson 9y ago

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.