6 ms·

> The trick is the size is hidden before the adress of the buffer. That is how strings use to be stored before C made the choice of using null-terminator. Pasc

by _448 4y ago

> The trick is the size is hidden before the adress of the buffer. That is how strings use to be stored before C made the choice of using null-terminator. Pascal stored the string size before the string data. The advantage of relying on a terminator symbol is that the string size can be any length where as storing the size at the start forces the string to not exceed certain size.

anonymoushn 4y ago
In execution environments with 64-bit pointers you may have trouble loading a string of more than 16 exabytes into RAM anyway
mh7 4y ago
strlen() returns a size_t so you're already constrained to a maximum length of SIZE_MAX.
- jcelerier 4y ago
  If you use a different data structure you would maybe use a different API for accessing it too
- jstimpfle 4y ago
  This is hilarious. SIZE_MAX is at least as large as the largest string that you can put in your address space / memory anyway. Which is what the strlen() API already assumes. That, plus you'd be a fool to store a huge string in this way anywhere (in or out of memory) in any case.
  - Someone 4y ago
    > SIZE_MAX is at least as large as the largest string that you can put in your address space / memory anyway. Not necessarily. A 64-bit system could give processes an address space that’s significantly larger than half the full 64-bit address space and have an allocator that allows you to allocate a block of more than SIZE_MAX bytes (malloc takes a size_t, but you can use calloc)
    - jstimpfle 4y ago
      This doesn't make sense to me. You can't "allocate" more than SIZE_MAX bytes by definition. If you take "allocate" to mean "make it available in the process's address space", that is.
      - unwind 4y ago
        Are you sure? The calloc() [1] function mentioned above takes two values of type size_t, and allocates their product bytes. I'm on mobile without (!) the C99 draft spec but at least the man page gives no such restriction. [1] https://linux.die.net/man/3/calloc https://linux.die.net/man/3/calloc
        mek6800d2 4y ago
        I read something about this recently, somewhere, maybe HN. Specifically, in calloc(), what is done and what should really be done if the multiplication overflows. As will happen, for example, if you try to calloc() two elements of size SIZE_MAX, when SIZE_MAX is the maximum representable unsigned integer value on the machine. So, I don't think calloc() is available or intended as a way to circumvent malloc()'s size restriction.
        Someone 4y ago
        I stand corrected. Initially, I thought that, even if it calloc can’t, an OS could provide a different way to obtain a pointer to a memory region that’s larger than SIZE_MAX. However, the standard says (https://en.cppreference.com/w/c/types/size_t https://en.cppreference.com/w/c/types/size_t): “size_t can store the maximum size of a theoretically possible object of any type (including array).” and (https://en.cppreference.com/w/c/language/pointer https://en.cppreference.com/w/c/language/pointer): “Pointer is a type of an object that refers to a function or an object of another type, possibly adding qualifiers. Pointer may also refer to nothing, which is indicated by the special null pointer value.” ⇒ pointers must either be null or point to an object, and objects aren’t larger than SIZE_MAX, so I think having a pointer pointing to a block larger than SIZE_MAX violates the standard.
  - pjmlp 4y ago
    Indeed, you just need to forget to put a terminator to get a nice memory dump.
aap_ 4y ago
Null-termination was not a C invention.
thaumasiotes 4y ago
> The advantage of relying on a terminator symbol is that the string size can be any length where as storing the size at the start forces the string to not exceed certain size. In the same way that since we identify unicode code points with a 16-bit value, it's impossible to include U+1D460 in a string? In the same way that since Matroska files encode the length of their segments, there's a hard upper limit on the length of a segment? Of course none of those things is actually true. Storing the string size has no implications for how long the string can be. It requires an amount of space, to store the string size, that is logarithmic in the length of the string, and completely insignificant.
- jstimpfle 4y ago
  For sake of simplicity, and for efficiency with really small strings, with a length-prefixed string representation you really want to keep the string length field fixed-size. In general.
  - thaumasiotes 4y ago
    Really small strings have a fixed-size length field in any variable-size encoding of the length. They're small, so they fit into whatever the smallest possible length field is. What do you gain in handling short strings from an inability to handle long ones?
    - jstimpfle 4y ago
      Ok I give you this one, but I still don't think that minimizing the size of a length field using a flexible width encoding is a good idea except when talking about extremely specialized string encodings (like compression schemes). Flexible width encoding is more complicated compared to simple member access to get at the first character. And how do you handle construction of a string whose size you don't know yet? You might have to move the string away to make space for a bigger string length field. I don't like it.
      - thaumasiotes 4y ago
deleted 4y ago
[deleted]
jstimpfle 4y ago
The biggest advantage of zero-terminated to me is simplicity, next would be efficiency for really small strings - although this is a fringe concern. Strings with explicit length should at least have a 32-bit length field (maybe 64) IMO - for example, it's common to read files (and store them in contiguous memory) that are larger than 64K.
- jbverschoor 4y ago
  Well you could easily use the first 4 bits to indicate how many bytes the length is + 1. c0 (0b0000) -> length is 0xc = 12 1341 (0b0001) -> length is 0x134 = 69,940 239a42 (0b0010) -> length is 0x239a42 = 145,828 deadbeaf239a47 (0b0111) -> length is 0xdeadbeaf239a4 = 3917404957718948. This gets you a 7-byte = 56bit number, minimal overhead for smaller strings. Maybe reserve 0x1111 for future use. Maybe the other endian makes more sense here, and maybe 0 should mean zero-length. It's probably not very performant compared to other solutions, but you can just shift 4 bits, and you're done I'm curious how many strings are allocated at a particular point in time (across everything, kernel, os, apps, etc)
  - jstimpfle 4y ago
    These considerations can make sense when thinking about storage formats (probably you want to compress the string too), but they are not convenient for in-memory representation where you want to get the location of the first character with a simple member access.
    - jbverschoor 4y ago
      It starts at the start of the frame + the first nibble + 1
      - deleted 4y ago
        [deleted]
- abcd_f 4y ago
  The length can be packed, e.g. like utf-8 does it or something similar. The caveat is the cost of unpacking on access, but the memory overhead will be minimal.
drfuchs 4y ago
Nit: Many Pascal compilers / runtimes extended the language in non-standard ways, including various schemes for storing string length in front of the string. But nothing like this was ever part of the ISO Pascal standard, and it was certainly not in the "PASCAL User Manual and Report" by Kathleen Jensen and Niklaus Wirth. In fact, in standard Pascal, string handling is extremely rudimentary; there was no way to express "this variable / parameter / pointer refers to a string with a length not known at compile-time".
- pjmlp 4y ago
  They were on the ISO Extended Pascal, which hardly mattered because by then, USCD Pascal and Object Pascal already had taken over the world of Pascal dialects, both of which had better ways to deal with strings. https://www.iso.org/standard/18237.html https://www.iso.org/standard/18237.html Additionally, Modula-2 was already available in 1978, sorting out all the issues of original Pascal, with all the features needed for a safe systems programming language in the late 70's.
  - drfuchs 4y ago
    In the late 70’s, there were production-quality Pascal compilers for DEC 20 / ITS / SAIL, Vax/VMS, IBM 360/370, together covering much of academic computing and most of the ARPAnet. Even consulting Wirth, Knuth couldn’t find suitable Modula-2 compilers available for these, so TeX used Pascal and not Modula-2. Near as we heard, it was only ever seriously used on the niche ETH workstation?
    - pjmlp 4y ago
      That is like complaining that C wasn't available in plenty of computer hardware outside Bell Labs until early 1980's, after UNIX V6 release, was it ever seriously used outside AT&T research units? Do you seriously expect in two years left of 70's for Modula-2 to be available everywhere?
      - drfuchs 4y ago
tored 4y ago
Another is Hollerith strings that was used by FORTRAN and TCP protocols. https://en.wikipedia.org/wiki/Hollerith_constant https://en.wikipedia.org/wiki/Hollerith_constant

by _448 4y ago

anonymoushn 4y ago

In execution environments with 64-bit pointers you may have trouble loading a string of more than 16 exabytes into RAM anyway

mh7 4y ago

strlen() returns a size_t so you're already constrained to a maximum length of SIZE_MAX.

jcelerier 4y ago
If you use a different data structure you would maybe use a different API for accessing it too
jstimpfle 4y ago
This is hilarious. SIZE_MAX is at least as large as the largest string that you can put in your address space / memory anyway. Which is what the strlen() API already assumes. That, plus you'd be a fool to store a huge string in this way anywhere (in or out of memory) in any case.
- Someone 4y ago
  > SIZE_MAX is at least as large as the largest string that you can put in your address space / memory anyway. Not necessarily. A 64-bit system could give processes an address space that’s significantly larger than half the full 64-bit address space and have an allocator that allows you to allocate a block of more than SIZE_MAX bytes (malloc takes a size_t, but you can use calloc)
  - jstimpfle 4y ago
    This doesn't make sense to me. You can't "allocate" more than SIZE_MAX bytes by definition. If you take "allocate" to mean "make it available in the process's address space", that is.
    - unwind 4y ago
      Are you sure? The calloc() [1] function mentioned above takes two values of type size_t, and allocates their product bytes. I'm on mobile without (!) the C99 draft spec but at least the man page gives no such restriction. [1] https://linux.die.net/man/3/calloc https://linux.die.net/man/3/calloc
      - mek6800d2 4y ago
        I read something about this recently, somewhere, maybe HN. Specifically, in calloc(), what is done and what should really be done if the multiplication overflows. As will happen, for example, if you try to calloc() two elements of size SIZE_MAX, when SIZE_MAX is the maximum representable unsigned integer value on the machine. So, I don't think calloc() is available or intended as a way to circumvent malloc()'s size restriction.
        Someone 4y ago
        I stand corrected. Initially, I thought that, even if it calloc can’t, an OS could provide a different way to obtain a pointer to a memory region that’s larger than SIZE_MAX. However, the standard says (https://en.cppreference.com/w/c/types/size_t https://en.cppreference.com/w/c/types/size_t): “size_t can store the maximum size of a theoretically possible object of any type (including array).” and (https://en.cppreference.com/w/c/language/pointer https://en.cppreference.com/w/c/language/pointer): “Pointer is a type of an object that refers to a function or an object of another type, possibly adding qualifiers. Pointer may also refer to nothing, which is indicated by the special null pointer value.” ⇒ pointers must either be null or point to an object, and objects aren’t larger than SIZE_MAX, so I think having a pointer pointing to a block larger than SIZE_MAX violates the standard.
- pjmlp 4y ago
  Indeed, you just need to forget to put a terminator to get a nice memory dump.

aap_ 4y ago

Null-termination was not a C invention.

thaumasiotes 4y ago

> The advantage of relying on a terminator symbol is that the string size can be any length where as storing the size at the start forces the string to not exceed certain size. In the same way that since we identify unicode code points with a 16-bit value, it's impossible to include U+1D460 in a string? In the same way that since Matroska files encode the length of their segments, there's a hard upper limit on the length of a segment? Of course none of those things is actually true. Storing the string size has no implications for how long the string can be. It requires an amount of space, to store the string size, that is logarithmic in the length of the string, and completely insignificant.

jstimpfle 4y ago
For sake of simplicity, and for efficiency with really small strings, with a length-prefixed string representation you really want to keep the string length field fixed-size. In general.
- thaumasiotes 4y ago
  Really small strings have a fixed-size length field in any variable-size encoding of the length. They're small, so they fit into whatever the smallest possible length field is. What do you gain in handling short strings from an inability to handle long ones?
  - jstimpfle 4y ago
    Ok I give you this one, but I still don't think that minimizing the size of a length field using a flexible width encoding is a good idea except when talking about extremely specialized string encodings (like compression schemes). Flexible width encoding is more complicated compared to simple member access to get at the first character. And how do you handle construction of a string whose size you don't know yet? You might have to move the string away to make space for a bigger string length field. I don't like it.
    - thaumasiotes 4y ago

deleted 4y ago

[deleted]

jstimpfle 4y ago

The biggest advantage of zero-terminated to me is simplicity, next would be efficiency for really small strings - although this is a fringe concern. Strings with explicit length should at least have a 32-bit length field (maybe 64) IMO - for example, it's common to read files (and store them in contiguous memory) that are larger than 64K.

jbverschoor 4y ago
Well you could easily use the first 4 bits to indicate how many bytes the length is + 1. c0 (0b0000) -> length is 0xc = 12 1341 (0b0001) -> length is 0x134 = 69,940 239a42 (0b0010) -> length is 0x239a42 = 145,828 deadbeaf239a47 (0b0111) -> length is 0xdeadbeaf239a4 = 3917404957718948. This gets you a 7-byte = 56bit number, minimal overhead for smaller strings. Maybe reserve 0x1111 for future use. Maybe the other endian makes more sense here, and maybe 0 should mean zero-length. It's probably not very performant compared to other solutions, but you can just shift 4 bits, and you're done I'm curious how many strings are allocated at a particular point in time (across everything, kernel, os, apps, etc)
- jstimpfle 4y ago
  These considerations can make sense when thinking about storage formats (probably you want to compress the string too), but they are not convenient for in-memory representation where you want to get the location of the first character with a simple member access.
  - jbverschoor 4y ago
    It starts at the start of the frame + the first nibble + 1
    - deleted 4y ago
      [deleted]
abcd_f 4y ago
The length can be packed, e.g. like utf-8 does it or something similar. The caveat is the cost of unpacking on access, but the memory overhead will be minimal.

drfuchs 4y ago

Nit: Many Pascal compilers / runtimes extended the language in non-standard ways, including various schemes for storing string length in front of the string. But nothing like this was ever part of the ISO Pascal standard, and it was certainly not in the "PASCAL User Manual and Report" by Kathleen Jensen and Niklaus Wirth. In fact, in standard Pascal, string handling is extremely rudimentary; there was no way to express "this variable / parameter / pointer refers to a string with a length not known at compile-time".

pjmlp 4y ago
They were on the ISO Extended Pascal, which hardly mattered because by then, USCD Pascal and Object Pascal already had taken over the world of Pascal dialects, both of which had better ways to deal with strings. https://www.iso.org/standard/18237.html https://www.iso.org/standard/18237.html Additionally, Modula-2 was already available in 1978, sorting out all the issues of original Pascal, with all the features needed for a safe systems programming language in the late 70's.
- drfuchs 4y ago
  In the late 70’s, there were production-quality Pascal compilers for DEC 20 / ITS / SAIL, Vax/VMS, IBM 360/370, together covering much of academic computing and most of the ARPAnet. Even consulting Wirth, Knuth couldn’t find suitable Modula-2 compilers available for these, so TeX used Pascal and not Modula-2. Near as we heard, it was only ever seriously used on the niche ETH workstation?
  - pjmlp 4y ago
    That is like complaining that C wasn't available in plenty of computer hardware outside Bell Labs until early 1980's, after UNIX V6 release, was it ever seriously used outside AT&T research units? Do you seriously expect in two years left of 70's for Modula-2 to be available everywhere?
    - drfuchs 4y ago

tored 4y ago

Another is Hollerith strings that was used by FORTRAN and TCP protocols. https://en.wikipedia.org/wiki/Hollerith_constant https://en.wikipedia.org/wiki/Hollerith_constant