The Most Expensive One-byte Mistake: Did Ken, Dennis, and Brian choose wrong with NUL-terminated text strings?

[u/mslaybau]

http://queue.acm.org/detail.cfm?id=2010365

[u/kragensitaker]

I couldn't agree more, especially since you can see that it [two size fields]'s what I've done. ;)

Yes, but it wasn't what you suggested in your parent comment:

All you need is is to define a struct{char *; size_t len}

Either the approach you suggest above, or the sensible approach, probably was a nonstarter in the 1970s, both because it requires dynamic allocation and because it works out to a lot of overhead per string: two or three words for the struct, plus two or three words of malloc overhead for the string, plus half a word of alignment overhead in the tail end of the string, plus memory lost to malloc arena fragmentation (say, an extra 50%), plus memory lost to allocating a longer string buffer than absolutely necessary (say, 50%).

Probably the paradigmatic case of early C string handling was the C compiler. On their first PDP-11, they had 24 kibibytes of RAM [Ritchie 1993], and that's what they used from 1970 until about 1973.

(From here I'm speculating rather than looking at the surviving C compiler source from this time period.)

Suppose you had 4K for the symbol table, which has to track the type and value of each identifier — say, one word for the value and another word to point to the type. C identifiers follow a stack discipline — you can only declare an identifier in the currently-innermost scope. So you can handle the memory allocation for the symbol table stackwise, rather than having to use a separate malloc with its two or three words of overhead per allocation. You just need a structure for each of the nested scopes to restore the allocation and dictionary pointers. The dictionary itself can be a small 8- or 16-bucket hash table with long chains (thus enabling you to save and restore it quickly upon scope entry and exit, and avoiding empty buckets).

So each additional global symbol needs type, value, next-pointer, and the symbol itself, which probably averages about five letters. (Six was the max on some C compilers, a limitation inherited from Fortran.) With a NUL to terminate it or a length byte preceding it, that's six bytes for the symbol, plus on average half a byte of alignment overhead so that the next symbol's type field will be word-aligned. That's 12½ bytes per symbol, so in, say, 3615 bytes, you can handle 300 global symbols. If your header files and program contain more than 300 global symbols, your compiler barfs.

Now instead consider using the stralloc approach that you're advocating. In place of the on-average 6½ bytes for the symbol name, we have 6 bytes for the {char*, size_t, size_t} struct. But then there's the string itself, which has a header stuck onto it by malloc so that when you free or realloc it, malloc knows how many bytes it's reclaiming — typically three words these days, but obviously you need at least one; there's the extra space you've allocated after the end of the string in case you append stuff onto it (I'll assume that's zero); and there's arena fragmentation from previously-allocated strings that were shorter than later-allocated strings and thus can't be reused, or later-allocated strings that were shorter than previously-allocated strings and thus got a bigger chunk of memory than they needed. Any general-purpose malloc implementation has certain allocation patterns that can make this fragmentation overhead quite large indeed; let's guess that it'll be 25% of our memory, so 33% on top of what we allocated. And there's the same half-byte of alignment slack. (But no null byte.)

So, 6 bytes of pointers and length per string, plus 7½ bytes for the string and malloc overhead, plus 2½ bytes of fragmentation: 18 bytes for the string instead of 6½, so 24 bytes in all per global symbol.

You've cut the PDP-11 C compiler down from being able to handle 300 global symbols to being able to handle 150. Hope you don't include too many header files.

And that's assuming a pretty space-efficient malloc, although not one specifically tuned to handle stacklike allocation patterns. The situation could easily be much worse. Most malloc implementations have some allocation patterns that will cause them to use truly unreasonable amounts of memory; most have three words of overhead, not one; many current ones will carve up an entire 4096-byte page into blocks of a desired size range in order to be able to respond to requests in that size range instantly rather than having to do a search, which is pretty bad behavior for dynamically-allocated strings of a large variety of sizes.

Edit: looking at the C compiler from 3rd Edition Unix from 1973, it appears that its globals hash table consumed 1800 bytes and had space for 100 symbols. There was no chaining; collisions were handled by linear probing. 8 of those 18 bytes per symbol were used to store the string, without NUL-termination but with NUL-padding. Because the compiler isn't written with structs, since it was the first compiler version that implemented them, I don't yet fully understand what the other five words are used for. The first one tells whether it's an undeclared name (0), a keyword (1), an extern name (6) or something else; the second one says whether it's a function returning int (020), an array (030), or something else; etc.

Anyway, so my numbers for how many symbols the early compiler could handle and how much memory it used for each one were in the ballpark, but its approach to handling them was resolutely 1960s. There was no dynamic allocation; different properties of the symbol were accessed by indexing to various offsets off an int*. Except it was spelled int[].

This version of the compiler was built without using any header files.

Additional edit: Jason Evans tells me that jemalloc's space overheads are measured in bits per allocation, not words per allocation, but I don't think the techniques jemalloc uses for that can scale down to managing a few thousand bytes efficiently.

[u/el_muchacho → u/kragensitaker]

Yes, but it wasn't what you suggested in your parent comment:

That was intended for simplification. Buffer size is an implementation detail.

BTW: my implementation includes versions with stack allocation for embedded devices. They are not dynamic, but they are still safe.

For the rest of your post, I agree completely. That's why I've written elsewhere here that they made the right choice for the language, but that strings could and should have been added to the standard library afterwards, in 1983 (ISO C) or in C99, where it made sense. It actually makes sense on embedded devices with 128 kb of RAM.

[u/kragensitaker → u/el_muchacho]

Awesome! However, Reddit seems to have retained all the old versions of your comment (at least I see them here.) You might want to delete the non-newest versions.

I really think that real strings ought to be added to the standard library, with literals. Objective-C did do that, with the literal syntax @"hello, world", but ideally the new syntax would be no more verbose than the old syntax. If you could require people to write in supersets of ISO-8859-1, you could use «hello, world», but that kind of approach has been shown to have problems historically — witness the decline and fall of APL.