8 ms·

A defense of C's null-terminated strings

• eru 11y ago
  > C's null byte terminator imposes a fixed and essentially minimal size penalty regardless of the length of the string. From an information theoretic point of view, making 1 out of 256 values of each byte unusable as the content of the string, is an overhead linear in the size of the string, not constant.
  • marcoperaza 11y ago
    Null is one of many non-printing ascii and utf characters. Its existence predates its use as a string terminator. The overhead of having its own code point is totally independent of its use in C strings.
    • Dylan16807 11y ago
      Yes, it already exists and has other uses. So when your code wants to use it, yet your language is reserving it, the overhead balloons tremendously.
  • Fradow 11y ago
    That's not what he is saying. He is saying that there is an overhead in term of string length. Example: a string with 0 character has a length of 1 (it contains NULL), a 100% overhead. A string with 1 character has a length of 2, a 50% overhead. It gets better with larger strings.
    • eru 11y ago
      I am saying the same thing. Strings that can't make use of 0 have to be a small constant factor longer to store the same entropy, because each byte can only store log_2 (255) ~ 7.994 bits, instead of log_2 (256) = 8 bits. Of course, if you are storing printable ascii characters only, that doesn't matter, since you are using far less than 256 possibilities per byte, and so don't care that some of them unused onces are used for in-band signalling (https://en.wikipedia.org/wiki/In-band_signaling https://en.wikipedia.org/wiki/In-band_signaling). As vardump points out in another comment, that's equivalent to 1 in 177 bytes. (See also https://en.wikipedia.org/wiki/Control_character https://en.wikipedia.org/wiki/Control_character)
  • vardump 11y ago
    Good point. We lose linearly one bit per ~177 characters that way. So zero termination does have linear cost. 1/(log2(256)-log2(255)) Assuming 8-bit char, at 1417 chars, zero terminated string overhead is 2 chars.
    • std_throwaway 11y ago
      But you start with a constant cost of 8 bits. For 255 characters you lose 9.4 bits which is bigger than the cost of an 8 bit size field. For 65535 characters you lose 378 bits which is much bigger than the cost of a 16 bit size field. On the other hand you have only one string type for arbitrarily sized strings and most strings are short. What would really be needed to be more space efficient for short and long strings is a size field with a variable length encoding. E.g. 1 byte for string lengths up to 64, 2 bytes for string lengths up to 8k, etc.
      • vardump 11y ago
        > What would really be needed to be more space efficient for short and long strings is a size field with a variable length encoding. E.g. 1 byte for string lengths up to 64, 2 bytes for string lengths up to 8k, etc. It's just decoding that requires pipeline busting branches. Well, I guess it's fine if you take branch mispredict for the large string case. Maybe 1 byte with highest bit zero, 0-127, 2 bytes for 128-32767, etc? The irony is of course now we have variable length encoding for the string size... I think just using size_t instead makes more sense than saving a byte or two per string. Memory is cheap, but CPUs aren't getting much faster. When size is an issue and nothing else prevents it either, just LZ4 (or similar memcpy order of magnitude speed compression) the string.
        • std_throwaway 11y ago
          I think it depends on the use case. In embedded systems bits consume energy and therefore increase cost. The battery of a satellite is much more expensive than a Chinese coal power plant. Yes, "size_t" should be just about right for everybody except the guys who _need_ to program in C/C++ and Assembler due to the hard requirements of their systems. Not very many people but very important systems.
  • chongli 11y ago
    It's even worse than that (from a practical standpoint, not a complexity theory standpoint) when you get into the realm of interpreted languages written in C. Try processing text containing null bytes in bash, for example.
    • jstimpfle 11y ago
      Data containing null bytes is not text. I like to think of bash / sh as just a job control system. It enables you to setup process pipelines. Everything is just processes and files (streams). Variables only serve as programs arguments. Since program arguments are also null terminated, variables containing null bytes just make no sense. (Of course it gets dirty as soon as you feed the output of a job into a variable, for example. I think that isn't even defined by POSIX for non-text streams).
      • chongli 11y ago
        Feeding the output of a job into a variable is a common enough task. One example I worked on recently was to use the results of one find(1) command as an array of arguments to another. Perhaps this was a very ugly way of comparing two directories, but it worked. This is why it surprised me when I realized (without having thought about it) that variables can't contain null bytes. It made my quick id3 tag parsing script a bit trickier to write, since I could no longer just use read(1P).
• pjc50 11y ago
  Well, yes: these are the original design constraints that led to null-terminated strings. The result is a data structure a bit like a linked list: finding the length is an O(n) operation. So long as all your operations on the string are char-at-a-time, and your first act is to check the char against zero, this works fine. In fact, so long as you stay in the original UNIX batch processing model, where you're reading bytes from stdin and writing to stdout, the whole program works fine. Inconvenient buffer-size issues are avoided: don't keep intermediate buffers, just write to stdout a char at a time. (Have a look at lex/yacc generated code for this model, for example, with their not-easily-resettable parsers and trouble handling errors other than by calling `exit`). The problem is not so much "string is not a type" as "buffers for composing strings are not a type".
  • marvy 11y ago
    What do you mean by that last sentence?
    • pjc50 11y ago
      Roughly the distinction Java makes between String and StringBuffer. I observed that buffer overflows require a buffer: if you do all your IO a character at a time, this is less risky. For security you need not "string first char + length of string" but "string first char + length of allocated region into which it is safe to write", which (unlike the length of the string) cannot be inferred from the string head pointer in any way.
      • marvy 11y ago
        thanks
• antirez 11y ago
  The SDS library (http://github.com/antirez/sds http://github.com/antirez/sds) is the middle ground between the two approaches. SDS strings are apparently C null-terminated strings, but before the pointer that you pass around there is metadata with the length. This makes SDS strings compatible with everything there is in the C standard, but has allows to easily manipulate the string without managing the allocation manually. Also sdslen() is O(1) and binary safe. The main drawback is that most functions have to reassign the pointer back, like in: sds foo = sdsnew("foo"); // Creates an SDS string printf("%s\n", foo); // You can print it with printf() foo = sdscatlen(foo,buffer,10); // Append 10 bytes. Failing to reassign sdscatlen() return value back to "foo" creates a bug. SDS originated with Redis but is now a standalone library. Recently version 2.0 was released that makes it synchronized with the version we have inside Redis.
  • JoshTriplett 11y ago
    Seems like you could avoid that potential for error by making functions that modify an SDS take &foo rather than just foo, and modify it in place. As a stopgap, though, SDS could use GCC's attribute "warn_unused_result" on all of those return values.
    • jzwinck 11y ago
      Last time I tried it, that GCC attribute was only implemented for C, not C++. It seems like a good idea anyway.
  • tonyedgecombe 11y ago
    I seem to remember BSTR in COM is similar to this.
• lugus35 11y ago
  Take a look at bstring[0] and you'll see how to circumvent C's null-terminated string in a clean and light way. [0] http://bstring.sourceforge.net/ http://bstring.sourceforge.net/
  • anon1385 11y ago
    bstring relies on undefined behaviour for security. Do not use it. >Bstrlib is, by design, impervious to memory size overflow attacks. The reason is it is resiliant to length overflows is that bstring lengths are bounded above by INT_MAX, instead of ~(size_t)0. So length addition overflows cause a wrap around of the integer value making them negative causing balloc() to fail before an erroneous operation can occurr. Attempted conversions of char * strings which may have lengths greater than INT_MAX are detected and the conversion is aborted. >It is unknown if this property holds on machines that don't represent integers as 2s complement. It is recommended that Bstrlib be carefully auditted by anyone using a system which is not 2s complement based.
    • tomjakubowski 11y ago
      What might go wrong if you only deploy to architectures with the necessary signed integer representation and compile with -fno-strict-overflow? (not that I can imagine an optimization which would make this particular use of overflow go wrong)
    • fhars 11y ago
      It is not only unknown if this holds on machines that don't use 2s complement, it is quite likely that this doesn't even hold on machines that do use 2s complement, but have an optimizing compiler. In many cases, the overflow checks contains terms like (b->slen+1) < 0 which an optimizing compiler could compile as b->slen < -1 effectively switching the overflow test off (as there is no non-overflowing execution where this code will produce other behaviour than the original code, and behaviour on overflow is undefined, so the compiler can safely get rid of the addition).
      • fhars 11y ago
• bluetomcat 11y ago
  Another nice feature of C strings is that a substring spanning to the end is essentially p + something. You can also insert temporary null-chars in the middle and have copy-free substrings. Most other high-level languages would let you copy the substring even if you don't intend to modify it.
  • vardump 11y ago
    > Most other high-level languages would let you copy the substring even if you don't intend to modify it. C++, std::string yes. But for example Java, C# and Go (slices) substring doesn't copy data.
    • joosters 11y ago
      Didn't java change its behaviour?
      • anon1385 11y ago
        Yes: https://news.ycombinator.com/item?id=9862556 https://news.ycombinator.com/item?id=9862556
        • vardump 11y ago
          That's a bit scary. Some of older Java code relies a bit too much on substring not copying. I think most devs understood it pins the original String char[] buffer until all references are gone.
          • pjmlp 11y ago
            That was always a JVM specific behavior. Like C, any dev that makes language assumptions based on the installed compiler, is bound to get burned.
            • joosters 11y ago
• cousin_it 11y ago
  What I want from strings in a programming language: 1) Memory-safe (can't touch memory that you don't own) 2) Opaque (standard library can change the implementation later) 3) Immutable (can be passed around like values) 4) Unicode (no fixed width chars, no default conversion to bytes) I don't know any good reason to deviate from these rules. Even systems languages would do well to follow them, IMO.
  • std_throwaway 11y ago
    Zero terminated strings make a lot of sense when programming 8 bit microcontrollers: 1) No protection exists there. 2) Abstraction costs too much. 3) Store it in Flash. 4) Be happy your characters may even use the 8th bit.
    • pjmlp 11y ago
      Except even there, there were computers using safer system programming languages in the 60's where a modern 8 bit microcontroller would seem like a workstation in those days.
  • josteink 11y ago
    > 3) Immutable (can be passed around like values) > I don't know any good reason to deviate from these rules. Even systems languages would do well to follow them, IMO. Systems-languages are used for things like OS kernels and god knows what where other equally important rules apply: 1. being able to manipulate things directly, in place, without having to allocate additional memory (i.e. creating a new copy) 2. efficiency may be more crucial than type-system guaranteed safety. Not saying I disagree with your general position, I'm just open to the fact that there's always valid exceptions to any rules.
    • pjmlp 11y ago
      And that is why sane system programming languages like Burroughs Algol, Mesa, Modula-2, Modula-3, Ada, .... provide escape hatches for the few uses where breaking the rules is really required. But, importantly, they don't do it by default as C does.
• leni536 11y ago
  >A fixed size length field commits you to a maximum string size size_t would be enough, but I guess it would be too much of an overhead.
  • kzrdude 11y ago
    Debating the size of the size field is a folly: It's a struct with one char pointer, and a length field. For alignment / padding reasons, the length field with use the size of a pointer anyway, so `size_t` is entirely appropriate (and never too small).
    • gpderetta 11y ago
      A relatively common implementation of strings (as compared to slices) is to store the length before the char array. The length field can be encoded with a variable size encoding. The string itself is just a single pointer. If you have a real garbage collector of course using the same representation for strings and slices (two pointers or pointer+len) is appropriate.
• pjmlp 11y ago
  Regarding the comments on the OP site " D is the first example to have array slices that I can think, of so this might be slightly a-historical." No, D wasn't the first one. There were already systems programming languages with proper string types with the same age or older than C. Usually there was a clear distinction between array of characters and strings, both in any case safer than C's approach.
• lmm 11y ago
  C strings may well have made sense for the time. The point is they don't do now. I don't blame the people who created C, I blame the people who continue to use it today.
  • signa11 11y ago
    > I don't blame the people who created C, I blame the people who continue to use it today. that's pretty harsh, and far-reaching. is it really justified to paint _everything_ with that brush ?
    • lmm 11y ago
      Probably not; I probably should remain open-minded. But I've seen so much written in C, and so rarely has C been a good choice, that I don't feel like wasting any more of my time.
    • Dylan16807 11y ago
      What's harsh about it?
    • unscaled 11y ago
      That's harsh, but probably true. There might have been good reason to make null-terminated strings the default in the past (e.g. K&R C not passing structs by value), but it has little meaning today. The arguable memory overhead of length-prefixed strings is outweighed by the significant performance and safety benefits. Considering that stubborn programmers are still using strcpy() and its ilk to this very day and the billions of dollars lost every year to cybercrime, then I don't think it's harsh.
• kzrdude 11y ago
  Explicitly sized strings are so much easier to work with efficiently. SIMDified algorithms, for example.
• _ph_ 11y ago
  The article tries to make its point with unnecessarily complex code examples. They seem to be locked in a C way of thinking. But Pascal was created about the same as C and had proper types. Strings could be represented as length checked arrays. They could come in two types, short ones, having a length byte at the beginning and are limited to 256 elements, and long ones, having an "int" size marker and corresponding length limits. The type handling could be handled by the compiler, the length() function would always return an int, and the elements addressed by a[i]. Thats it. This would have saved us more than 3 decades of nasty bugs if not security problems.
  • cefstat 11y ago
    > But Pascal was created about the same as C and had proper types. The Pascal I remember (some version of Turbo Pascal in the early 90s) had strings where you had to declare the length as part of the type. Strings of different length had different types and you could not pass a string of length 30 to a procedure that expected a string of length 31. The way to solve this is to declare that all your strings had the same length and hope that it would be enough. It was horrible and at the time I found the C approach much more reasonable. Of course Pascal improved through the years and the C approach turned out to be a huge security problem.
    • valarauca1 11y ago
      Pascal strings are weird. The first byte tells you the string's length. If the MSB of the first bit is set, the string's first 4 bytes tell you the length of the string. I mean yes its not a horrible system, but there are better systems. I'll be honest I like Rust's. Just keep the length and the pointer on the stack in a tuple.
    • _ph_ 11y ago
      I didn't meant to say that Pascal hat the perfect solution, but that with that times technology, better solutions than the C one were possible, and more so with any language more modern than ancient Pascal.
    • pjmlp 11y ago
• camperman 11y ago
  Can't remember where I read it because it was such a long time ago but one explicit benefit of null-terminated strings is that they take a single instruction to check for the end on nearly all processors: jump if zero. That allows for elegant constructions in C such as: while (*p++ = *q++);
  • justncase80 11y ago
    It may be syntactically terse but I'm not sure it's elegant as you would need to do several checks before this line or else you could end up with some pretty major bugs. For example, you would need to ensure that sizeof p is >= sizeof q, or else you will end up with a buffer overflow. This then implies that q has a length and therefore a \0. So you will need to iterate through the string once to find the \0 (which may not be there). Failure to do this can lead to execution of arbitrary code, which is why null terminated strings are indefensible frankly.
    • camperman 11y ago
      I read (and used) this during a more civilized age when everyone and his dog wasn't trying to get your program to execute arbitrary code, although I have still used the construct on a recent project on the Raspberry Pi and it worked just fine.
      • justncase80 11y ago
        You're very naughty ;)
  • vardump 11y ago
    > That allows for elegant constructions in C such as: > while (*p++ = *q++); Elegant? It's short, if you don't include code for buffer management and validation. It maps very poorly to modern CPUs as-is, unless the compiler recognizes it as strcpy and replaces it with appropriate code. Luckily most compilers are capable of that. Otherwise loop termination condition causes (most?) compilers not to even try vectorization and an order of magnitude of performance is lost.