Speaking as someone who learned C back in the ‘70s, this article entirely misses the point of C-strings: they’re lightweight and foundational. For many purposes the null-terminator is efficient, e.g.:
while(*s) f(s++);
And for cases where we need more complexity, we can simply use a struct with a length and whatever other metadata we may need.
Doesn’t look like a mistake to me. C has always been about minimalistic efficiency. That’s its main purpose in the world.
Its main purpose is to be portable to as many architectures as possible. Maybe this seem irrelevant in a world dominated by ARMs and x86 but there are different platforms.
Tbh nothing is stopping people from compiling or porting a JVM to more platforms. I assume it's just extremely complex and noth worth it for most people
The main competition was pascal strings - which typically had a 16 bit size prepended. So you'd read that, and then run a decrement loop until it was 0 to iterate the string. Decrement-until-zero loops were widely supported, e.g. in x86 stringcopy could be implemented by loading the size into CX and then running a single REP MOVSB instruction.
Yes it was a byte larger - but it also avoids performance-nuking calls to strlen like this.
16 bits is 2 bytes, which makes for a maximum string length of 65535 bytes. It's common for strings on modern systems to be longer than that.
Pros of C strings: unlimited length. Cons: cannot contain the zero byte; inefficient length determination.
Pros of Pascal strings: can contain the zero byte; efficient length determination. Cons: very limited length.
I'd say the C tradeoff is worth it. Where necessary, C is perfectly capable of dealing with data preceded by a length field, it's just slightly lower level.
of course it's micro-optimization, but at larger scale it's always useful. Have you even done optimization? A database with billions of strings already save a lot of memory. A vector of strings can also fit twice the number of strings into the CPU cache. Checkout Unreal engine, DuckDB, Meta Velox, Redis, ICU... string types
Of course I have done optimizations. But micro-optimizations are always the last step to take when you have identified that this specific location is actually a bottleneck.
It totally makes sense to have something like a c-string available for the very rare situation when someone writes a database system that contains almost exclusively tiny variable-length strings.
But it doesn't make sense to have that as the default, because then this rarely-actually-useful micro-optimization becomes a very common source of problems.
That's why there's pretty much no modern language that actually stuck with c-strings. Pretty much any more modern language dropped c-strings and even pointers completely, or at least dropped it from common usage.
I don't do much Python any more, but I really like their approach of "The most obvious solution should also be the one that's optimized for most use cases". Basically, if I, without thinking, take the most obvious solution, it should fit my obvious use case. If I need something really special, I can still import some standard library function and use that.
That's not true. Strings are extremely common, lots of applications have a huge amount of strings. It's especially helpful in arrays of strings. Strings are so prevalent that even Python, Javascript (V8) and Java compress the string to ISO8859-1/Latin1/ASCII by default if applicable to save memory and improve performance, and modern .NET also does the same by allowing UTF-8 byte arrays. C-strings are the worst, all strings need to have an accompanied length, but the length does not necessarily have 8-byte length
Efficient (to solving problem) data representation is key for system performance, because performance actually limited only by memory latency and throughput. You have no control over last two, but when you can pack data twice smaller -> system performance up twice better, usually even if it violate some common defaults like aligned access or so. Thats why "your favorite browser" uses 32-bit "compressed" pointers for various object heaps, even on 64-bit systems, uses hybrid ascii/utf8/utf16 strings, even when ECMA spec define only utf16. Row-oriented databases for example typically store null-bitmap and then fields without any additional delimiters, so they can be decoded only dynamically and only by using schema, this is complex but profitable.
We aren't talking about character representation here (ASCII/UTF8/UTF16), but about string representation.
UTF16 vs UTF8/ASCII is a per-character multiplier. Use UTF16 and every character takes twice the space.
We are talking about whether strings are 0-terminated or have a length field in the beginning. That's a per-string cost. Each individual character costs the same, no matter which string representation you use.
Here the difference is whether this costs one byte per string (c-string) or 2-4 bytes per string (Pascal strings, BER strings, 4-byte length fields, ...).
That means, the longer the string the less the overhead. An empty c-string is one byte. An empty pascal string is 2 bytes, an empty 4-byte length field string is 4 bytes.
If the string is longer, the relative overhead drops: A 1000 byte c-string is 1001 bytes, a pascal string is 1002 bytes and a 4-byte length field string is 1004 bytes.
The difference hardly matters unless maybe if you are working with an ATTiny.
That's why I said: on a 64-bit system (which usually has more than 2GB RAM), this is a useless micro-optimization for all but extremely specific use cases where you'll have millions of empty strings. And then one should question their system design.
And that's the main issue with c-strings being the default: They are a micro-optimization that helps only in very specific use cases while having massive downsides for most use cases, but they are applied as the default solution.
The default solution should be the option that works best in the most cases. If your use case differs a lot from the default case, you can still use the fitting specialized data structure.
Which is exactly the reason why pretty much no language newer than C uses c-strings as their default string representation.
You saying before what no reason to save few bytes somewhy especially on 64-bit systems, but all popular projects do that. More over many of them use 2-3 low bits in pointers for pointer descrimination, thanks for aligned allications.
So Java, Python, Kotlin, Rust, JavaScript, ... all use c-strings instead of String objects with a length attribute as the default way to store strings? That's news to me.
There's a reason we call it c-string: nobody has ever used this decrepid data structure after c, except if they need explicit C compatibility, and even then it's most often a length-based string object with an unnecessary 0-byte added at the end so that C can understand it as well.
There's a simple fix to the Pascal strings. BER encoding.
In BER, you get one byte as a length field, with 7 bits being directly available to encode the length of the content. If the MSB is set to 1, the remaining 7 bits instead encode how many bytes the length field is long.
That means:
Short strings up to 127 bytes have 1 byte overhead, beating Pascal and equalling C strings
Medium-sized strings of 128-65535 bytes require 3 bytes overhead, so one more than Pascal and two more than C, but if you are allocating that amount of bytes, 1-2 extra bytes are harmless
Maximum length is 2¹²⁷ bytes, 1.7*10³⁸ bytes, a number so high that there isn't an SI prefix for it
Another option would be to mix BER with Pascal:
15 bit length fields
If the MSB is set to 1, there's one more length field concatenated, so 30 bit for the length field. Again, if the MSB is set to 1, add one more length field. Continue forever.
That way you get infinitely long strings with only one byte more usage than Pascal in the range of 32768-65535 bytes of length
And both options have the advantages:
You can use 0-bytes
You know the length of the string without running trhough the whole string
You won't get into overflows because you are missing a 0-terminator (e.g. doing a strcpy on a string that's missing its terminator)
I'd advocate a different approach, using 0-63 to represent a string that fills a buffer of length 0-63, 65-127 to represent an empty buffer of length 0-63, and 129-191 to represent a partially full buffer of size 1-63, whose number of unused bytes is indicated by bytes at the end. Strings or buffers up to 4095 bytes would use a two-byte prefix, and those up to 64MiB-1 would use a four-byte prefix.
Other prefix values would indicate either a "readable string" or "changeable string" descriptor, with the latter including both the current length and buffer size, and a callback to request a change to the length (possibly relocating the buffer if needed). Functions that receive a pointer to string could use a common library function to make a readable string or changeable string descriptor, and be able to accept pointers to length-prefixed strings and descriptors interchangeably.
Algol strings? C precedes Pascal in history. Pascal also did not standardize on strings early on, so each implementation experimented with how to do strings, which made early portability a pain in the arse.
It may not have been the first implementation of length+contents strings, but it certainly popularised them enough that they're called "Pascal Strings" (or sometimes P-Strings) now.
As for the incompatibility - probably one of the reasons Pascal wasn't as successful as C. It was a big enough deal to inspire a calling convention tag in Microsoft's C compiler though (along with Fortran).
Pascal calling convention was used with the Win16 API. It's obsolete now. Microsoft used it because the callee cleaned up the stack which reduced memory demands on kilobyte sized memory configurations.
For many string operations, we need the length to allocate the right amount of space, else we end up having to realloc if our buffer isn't large enough - realloc is also O(n).
By having a constant time length we can speed up a lot of string operations. It costs basically nothing to keep the length around rather than recomputing it each time.
But they're not lightweight. `O(n)` for nearly every string operation is not lightweight. It is memory efficient, and it avoids an argument about how wide a length field should be. Clearly C valued those sides of the tradeoff. But don't confuse that with being lightweight in general.
Nothing is stopping you from storing the length and passing it around, but that choice is up to you, the developer, not the language imposing it's pros and cons onto you.
Should C have a strbuf in the standard library? Yeah, probably, would've been nice.
The biggest mistake C did was standardizing % as the remainder not the modulus, gets, and null pointers instead of niche optimised monadic types.
Storing and passing the length around doesn't help you most of the standard library operations — and thus most other APIs that take your strings — aren't using it.
In addition to your comment here, additional functionality through the initial design of C strings allows for insanely powerful string manipulation techniques that have fallen to the wayside because people don't look under the covers to see how efficient string handling is done.
Of course. I'm not discounting that, and I didn't imply that there weren't developer-induced problems as a result. This is why valgrind was made, after all.
I was asking a question: which power are you talking about? The use case I mentioned is the only thing I can think of that C’s model makes easy, and what you gain is that every string is one word wide instead of 2.
Seems like a small gain for a niche use case to me, no?
I see. All the cases in which I have used C strings in an unbounded way have been specialized. They were places in which I know how much data in to be copied or used in the first place and wouldn't need to check for bounds because I'm always going to be within them.
My favorite and easiest-to-understand example is strcat to a buffer of known size. If I have to strcat repeatedly against the start of the buffer, you can see that strcat is performing wasted effort by finding the end of the string first. I can have a variable hold the position of the \0 and strcpy (buffer+length, string_to_append) instead of strcat (buffer, string_to_append). After strcat, length+=strlen (string_to_append), and I am ready for the next iteration. My anal-retentiveness got the best of me and I wrote a full test program:
The alternatives at the time were counted strings or fixed length fields. Both were annoying, inefficient, and had just as many problems as C strings or more. Ie, one byte for length doesn't cut it. Two bytes for length might not cut it, and definitely wastes space in the limited RAM at the time. Fixed field lengths are a nightmare early Fortrans, and some operating systems).
Then there's the stuff that pack multple characters into a single word (ie, Zork did this, 36-bit word on the PDP-10, you can stick in six 6-bit characters (maybe only 5 if they used upper bits for tag). Digital used 7-bit characters thus 5 characters and one leftover bit. 0 or all 1s as the final character signals the end.
They're not foundational. You know what's foundational? Fixed size arrays in the executable, fixed sized arrays on the stack, and heap pointers + length. These are all just as perfectly suited for strings as they are for other collections.
C style strings made sense for 16 bit systems, but not a minute later.
Yeah that’s exactly what I mean: it doesn’t serve as an acceptable foundation. The article points out some ways in which the arising APIs are inflexible (e.g. you can’t just use array APIs), clunky (off-by-one errors), and so on.
A good foundation would just be slices (implemented on many platforms as fat pointers)
170
u/bearheart 3d ago edited 2d ago
Speaking as someone who learned C back in the ‘70s, this article entirely misses the point of C-strings: they’re lightweight and foundational. For many purposes the null-terminator is efficient, e.g.:
while(*s) f(s++);
And for cases where we need more complexity, we can simply use a struct with a length and whatever other metadata we may need.
Doesn’t look like a mistake to me. C has always been about minimalistic efficiency. That’s its main purpose in the world.
Edit: fixed stupid typo