Re:The Most Expensive One-byte Mistake (2011)
by kazinator on Tuesday September 30, 2014 @11:33AM
(#8388746)
What I mean by shared memory is that the null-terminated strnig is self-describing. If two processes attach a region of shared memory (at a different virtual address in each process), one process can put a null-terminated string into that memory, and the other process sees a string object. No length or pointer value have to be communicated, just the bytes of the self-describing string object itself.
This is not the case with your proposed string representation.
I never claimed that there is a best string representation, or that the same representation should be used externally and internally. (I can prove that I don't believe that by pointing to programs I have written which don't do that; for instance my TXR language, written in C, has garbage collected strings that are arrays of wide characters internally, all I/O is done using UTF-8, and most string operations are applicative rather than destructive. Yet, those underlying character arrays are null terminated, for pragmatic reasons of environmental interoperability.)
The "fat reference" representation of strings is interesting, but has the disadvantage of splitting the string into two (or more) objects: the data, which is in one location, and meta-data which is in another location. This is fine for internal representations, but creates obstacles if we do want to use this as an external representation. Yet, by itself, it is not a sufficiently robust internal representation that it warrant outrageous claims of superior safety: after all, the underlying storage is a simple C-like array which doesn't know how long it is. It is not null terminated strings which cause buffer overflows, but the underlying unchecked array data type.
What's good about the representation is that you can play even more representational tricks, like have N references to the same storage, all representing different strings. (This is prone to errors if the storage is mutated; I don't know how you can possibly accuse null terminated strings for only being useful and safe when they are compile-time immutable, while in the same posting you propose a hack that is more similar than it is different.)
"Fat reference strings" are subject to buffer overruns (length field being wrong), aliasing problems (deleting a character from a string but not decrementing the length in all of the references that exist), dangling pointer problems (references to storage that has been deleted) and so on. (Note by the way that null terminated strings at least have the property that if we have multiple pointers aimed at the same string, and we edit that string in place, all the pointers see the new string, and not some half-baked string. We can even insert characters, if the underlying buffer has enough slack.)
It is not reasonable to believe that programmers who make mistakes when programming with null-terminated strings will suddenly write correct code when using fat-referenced strings.
If you use a language like C++ instead of C, and represent these fat references as smart pointer classes, then you can achieve a lot of safety. Basically C++'s std::basic_string template can already be implemented this way. But then you're tied to a particular memory management scheme and programming language. Also, safely and correctly implementing those tricks whereby one string's storage is displaced into another one, requires a lot more baggage in the smart pointer. std::basic_string implementations typically use reference counting to manage the lifetime of the underlying array, and so the underlying array needs a refcount. And so it goes.
In any case, null-terminated strings serve requirements which are poorly suited by such managed strings.
This is not the case with your proposed string representation.
I never claimed that there is a best string representation, or that the same representation should be used externally and internally. (I can prove that I don't believe that by pointing to programs I have written which don't do that; for instance my TXR language, written in C, has garbage collected strings that are arrays of wide characters internally, all I/O is done using UTF-8, and most string operations are applicative rather than destructive. Yet, those underlying character arrays are null terminated, for pragmatic reasons of environmental interoperability.)
The "fat reference" representation of strings is interesting, but has the disadvantage of splitting the string into two (or more) objects: the data, which is in one location, and meta-data which is in another location. This is fine for internal representations, but creates obstacles if we do want to use this as an external representation. Yet, by itself, it is not a sufficiently robust internal representation that it warrant outrageous claims of superior safety: after all, the underlying storage is a simple C-like array which doesn't know how long it is. It is not null terminated strings which cause buffer overflows, but the underlying unchecked array data type.
What's good about the representation is that you can play even more representational tricks, like have N references to the same storage, all representing different strings. (This is prone to errors if the storage is mutated; I don't know how you can possibly accuse null terminated strings for only being useful and safe when they are compile-time immutable, while in the same posting you propose a hack that is more similar than it is different.)
"Fat reference strings" are subject to buffer overruns (length field being wrong), aliasing problems (deleting a character from a string but not decrementing the length in all of the references that exist), dangling pointer problems (references to storage that has been deleted) and so on. (Note by the way that null terminated strings at least have the property that if we have multiple pointers aimed at the same string, and we edit that string in place, all the pointers see the new string, and not some half-baked string. We can even insert characters, if the underlying buffer has enough slack.)
It is not reasonable to believe that programmers who make mistakes when programming with null-terminated strings will suddenly write correct code when using fat-referenced strings.
If you use a language like C++ instead of C, and represent these fat references as smart pointer classes, then you can achieve a lot of safety. Basically C++'s std::basic_string template can already be implemented this way. But then you're tied to a particular memory management scheme and programming language. Also, safely and correctly implementing those tricks whereby one string's storage is displaced into another one, requires a lot more baggage in the smart pointer. std::basic_string implementations typically use reference counting to manage the lifetime of the underlying array, and so the underlying array needs a refcount. And so it goes.
In any case, null-terminated strings serve requirements which are poorly suited by such managed strings.