5 ms·

> The character \0 marks the end so we call this zero-termination. [...] The only advantage of this representation is space efficency. Sort of a tangent, but z

> The character \0 marks the end so we call this zero-termination. [...] The only advantage of this representation is space efficency. Sort of a tangent, but zero termination (aka null termination) can make parsing from a string slightly simpler. Without a null terminator, in addition to processing each character, you need to check if you've hit the end of the string. With a null terminator, the end-of-input checking is elegantly part of the "processing each character" step. You can always add a null terminator character to the end of your string in the length+data representations as well, but if your strings don't come that way you end up having to make a full copy.

tyingq 8y ago
Sds is somewhat nice in that you can work both ways. https://github.com/antirez/sds https://github.com/antirez/sds
- cakoose 8y ago
  That's similar to C++11 std::string, which has a length indicator and a null terminator. (I believe this was often true for std::string implementations before C++11, but apparently C++11 made it a requirement.)
  - romed 8y ago
    C++11 mandatory null termination has the advantage that a call to data() or c_str() need not store the null byte. On the other hand, mandatory termination costs one additional store in some of the constructors, and burns one byte of the capacity for inline data.
    - kazinator 8y ago
      How does it burn one byte of capacity for inline data? Are you saying there is a zero-byte way to encode the length that could instead be used, avoiding that one byte overhead?
      - romed 8y ago
        What I meant was the standard requires the null byte at the end of the string, which reduces by one the possible length of the string when stored inline. If the null byte wasn't mandatory, it would be possible to store slightly longer strings inline, but then the implementation would have to conditionally materialize the contents to the heap in case of a call to c_str or data.
        saagarjha 8y ago
        Only since C++11. In C++03 no guarantees were given on the time complexity on c_str, and std::strings could lay their contents our however they wished (and cause a heap allocation in the process of materializing a C string, if necessary).
      - dwaite 8y ago
        std::string has a byte length,an allocation capacity, a nil terminator and the content. A string implementation will typically store this as a structure with size + capacity + content pointer, with the content having a nil terminator. You could technically put capacity as a prefix of the content as well (I believe one of the apple GC string representations stores capacity as well as a reference count in the content block, and uses the reference count to determine exclusive ownership for inline mutation.) These may have two other representations: - size, capacity and content all initialized to zero is the only representation of the empty string - a embedded flag (such as a tagged contents pointer) indicates that instead the string holds inlined data. In this inlined case on a 64-bit platform, you have 24 bytes to work with. You store the length in the LSB byte of the content pointer (making sure not to interfere with the tagging), and capacity is hard coded and omitted. You then have 23 bytes to work with, which would be 23 bytes of content - but you need to remember to add space for a nil byte at the end of the inlined content, bringing your capacity down to 22.
        saagarjha 8y ago
        > std::string has a byte length,an allocation capacity, a nil terminator and the content. This is only true post C++11, I believe. C++03 was much more permissive about how std::strings were laid out internally.
theoh 8y ago
Saying the "only advantage" is space efficiency is definitely weird. Null-termination means that a string can't contain \0, which has both good and bad consequences. Maybe what the author means is that the technique of just running through the string until you hit a null has been an unmitigated disaster from a security perspective. (Buffer overflows often result from a strcpy() which receives a longer string than expected as an argument.) See this proposal which takes that problem as its starting point: https://cr.yp.to/proto/netstrings.txt https://cr.yp.to/proto/netstrings.txt More generally, the implication that space efficiency is the justification for null-termination is probably not historically true. It was a form of in-band signalling, just like getchar() returning EOF. When null-termination is used in network protocols, the data to be sent has to be prepared in order to remove/escape any nulls. This process is called byte stuffing, and naturally it could result in serious inefficiency if a long string of nulls occurred in the input data: https://en.wikipedia.org/wiki/Consistent_Overhead_Byte_Stuffing https://en.wikipedia.org/wiki/Consistent_Overhead_Byte_Stuff...

tyingq 8y ago

Sds is somewhat nice in that you can work both ways. https://github.com/antirez/sds https://github.com/antirez/sds

cakoose 8y ago
That's similar to C++11 std::string, which has a length indicator and a null terminator. (I believe this was often true for std::string implementations before C++11, but apparently C++11 made it a requirement.)
- romed 8y ago
  C++11 mandatory null termination has the advantage that a call to data() or c_str() need not store the null byte. On the other hand, mandatory termination costs one additional store in some of the constructors, and burns one byte of the capacity for inline data.
  - kazinator 8y ago
    How does it burn one byte of capacity for inline data? Are you saying there is a zero-byte way to encode the length that could instead be used, avoiding that one byte overhead?
    - romed 8y ago
      What I meant was the standard requires the null byte at the end of the string, which reduces by one the possible length of the string when stored inline. If the null byte wasn't mandatory, it would be possible to store slightly longer strings inline, but then the implementation would have to conditionally materialize the contents to the heap in case of a call to c_str or data.
      - saagarjha 8y ago
        Only since C++11. In C++03 no guarantees were given on the time complexity on c_str, and std::strings could lay their contents our however they wished (and cause a heap allocation in the process of materializing a C string, if necessary).
    - dwaite 8y ago
      std::string has a byte length,an allocation capacity, a nil terminator and the content. A string implementation will typically store this as a structure with size + capacity + content pointer, with the content having a nil terminator. You could technically put capacity as a prefix of the content as well (I believe one of the apple GC string representations stores capacity as well as a reference count in the content block, and uses the reference count to determine exclusive ownership for inline mutation.) These may have two other representations: - size, capacity and content all initialized to zero is the only representation of the empty string - a embedded flag (such as a tagged contents pointer) indicates that instead the string holds inlined data. In this inlined case on a 64-bit platform, you have 24 bytes to work with. You store the length in the LSB byte of the content pointer (making sure not to interfere with the tagging), and capacity is hard coded and omitted. You then have 23 bytes to work with, which would be 23 bytes of content - but you need to remember to add space for a nil byte at the end of the inlined content, bringing your capacity down to 22.
      - saagarjha 8y ago
        > std::string has a byte length,an allocation capacity, a nil terminator and the content. This is only true post C++11, I believe. C++03 was much more permissive about how std::strings were laid out internally.

theoh 8y ago

Saying the "only advantage" is space efficiency is definitely weird. Null-termination means that a string can't contain \0, which has both good and bad consequences. Maybe what the author means is that the technique of just running through the string until you hit a null has been an unmitigated disaster from a security perspective. (Buffer overflows often result from a strcpy() which receives a longer string than expected as an argument.) See this proposal which takes that problem as its starting point: https://cr.yp.to/proto/netstrings.txt https://cr.yp.to/proto/netstrings.txt More generally, the implication that space efficiency is the justification for null-termination is probably not historically true. It was a form of in-band signalling, just like getchar() returning EOF. When null-termination is used in network protocols, the data to be sent has to be prepared in order to remove/escape any nulls. This process is called byte stuffing, and naturally it could result in serious inefficiency if a long string of nulls occurred in the input data: https://en.wikipedia.org/wiki/Consistent_Overhead_Byte_Stuffing https://en.wikipedia.org/wiki/Consistent_Overhead_Byte_Stuff...