5 ms·

The Most Expensive One-byte Mistake (2011)

8 points by eric59 12y ago

lysium 12y ago
I find this article very interesting, but I'd still like to point out it is from 2011.
kazinator 12y ago
Betteridge's Law strikes again. No, null-terminated strings are fine. Rants against null-terminated string are a good way to spot nutjobs. Null-terminated strings have virtues, such as being recursively defined: the tail of a string is a string. So strchr could be written like this (let's drop the const for simplicity): char *strchr(char *s, int ch) { if (*s == ch) return s; if (*s == 0) return NULL; return strchr(s + 1, ch); } It's easy to break a string with delimiters into the individual pieces in place, just by writing nulls over the separating characters, and keeping a vector of pointers to the pieces. This can't be done with some other string representations like length + data. When one null terminated string is a suffix of another (and ideally both are treated as immutable), then they can share storage. char *excon = "excon", *con = excon + 2; Catenating null terminating strings is efficient if you keep a tail pointer. A repeated strcat-like operation will be O(N*N) of course, so don't do that in some critical inner loop, with a large amount of text. Length + data strings have various disadvantages. For one thing, how wide should be the length? Two bytes? Four? Eight? If you make it two bytes today and store binary data somewhere, it will be incompatible with tomorrow's four byte length. And then there is endiannness. A binary file with strings produced on one machine will have byte swapped lengths on another. Null terminated strings can be blasted over a serial line or network, or written to disks, as they are; they are already marshaled and ready to go! (Though I must hastily acknowledge that this isn't true of wide character null term'd strings, of course.) Dynamic strings (management record plus pointer to data) are heavyweight representations that will show their weaknesses at virtual machine boundaries. You cannot pass them between address spaces or share them without marshaling to some flat form and back. Also, regarding another point in the article, MS-DOS did not invent the backslash as a path separator instead of the slash. This is a common misconception. MS-DOS supports both forward and backslash as separators! And so does Windows (every version between then and now). Early versions of COMMAND.COM had a variable whereby you could set this as a preference: whether you want to display and input path separators as slash or as backslash. This was later removed. Today, when you have trouble with forward slashes in Windows, this is due to the application you are using (including, sadly that application known as the Windows Explorer, and its "Shell API"). The underlying kernel handles the slashes just fine.
- hyperliner 12y ago
  Bingo: "Length + data strings have various disadvantages. For one thing, how wide should be the length? Two bytes? Four? Eight? "
  - andreasvc 12y ago
    That's easy, it should be of type size_t. Yes that is wasteful for short strings, but then again I believe null-terminated strings are the most widespread and worst case of premature optimization, and correctness & safety should take precedence.
- andreasvc 12y ago
  I don't find the advantages of null-terminated strings you cite compelling. They sound like relatively rare operations, and compared to the severity and quantity of security problems caused by null-terminated strings it seems like a particularly bad trade-off. An advantage of storing strings with length and optionally start positions is that arbitrary slices can be defined, which reuse underlying data; this covers your examples of splitting by a delimiter and reusing suffixes. The argument that serialization would be harder is not really particular to the string format in question, that is always something that needs to be defined well, preferably with static typing (encoding issues make file formats complicated either way, if anything, storing a length attribute encourages to also store an encoding attribute while you're at it).
- sjolsen 12y ago
  Edit: It occurred to me after posting this that by "length + data" you might mean actually storing the length with the string data. If so, you're right, that's stupid. The correct solution (well, it's better than C/Pascal strings, anyway) is to store just the string data in the string proper, and use references that consist of pointer+length or pointer+pointer pairs instead of single char-pointers. > It's easy to break a string with delimiters into the individual pieces in place, just by writing nulls over the separating characters This assumes you're free to modify the input. If you don't want/are unable to modify the input, you're forced to allocate memory to hold the output; you've totally unnecessarily doubled the space requirement. It also assumes that there is a separating character to overwrite, which may not be the case, causing the same problem. > just by writing nulls over the separating characters > This can't be done with some other string representations like length + data Obviously. It is, however, perfectly possible to tokenize a string into a vector of length+data pairs without mangling the input. > When one null terminated string is a suffix of another (and ideally both are treated as immutable), then they can share storage. And only when one is a suffix of another. If you want to share storage between strings between which this relationship does not hold, you must again allocate extra memory, and again this is not necessary if you use a data+length representation. > Catenating null terminating strings is efficient if you keep a tail pointer In other words, if you use a pointer+length or arithmetically equivalent representation—except that you don't even bother binding the data into a coherent data structure, and instead force any code without access to your local tail-pointer variable to derive the length/end of the string on its own. > For one thing, how wide should be the length? Wide enough to represent the length of the longest possible string. Generally, this is less than or equal to the length of a pointer. > If you make it two bytes today and store binary data somewhere, it will be incompatible with tomorrow's four byte length > Null terminated strings can be blasted over a serial line or network, or written to disks, as they are You are making the incorrect assumption that the most appropriate on-disk/serialization representation is necessarily the same as the most appropriate in-memory representation. > And then there is endiannness 1. See above. 2. You're right that "this isn't true of wide character null term'd strings," so unless you and everyone you communicate with are still living in 1985, NTBSes don't even have that advantage. > You cannot pass them between address spaces or share them without marshaling to some flat form and back You can't do this with NTBSes, either, unless you have a way of translating the address of the string across address spaces, in which case you could just as well pass a pointer+length as you could pass a pointer. NTBSes are a perfectly fine representation if: your string is known at compile time; your string will never be modified; your string will only be scanned through from front to back; and your string does not contain a null character. From a technical standpoint, the only reason to bother with them in the first place is that you have extremely tight memory requirements and can't even afford the extra byte or three needed for a sane string-reference representation. If any of these conditions does not hold, NTBSes are a Terrible, Horrible, No Good, Very Bad representation. All they accomplish in practice is to make strlen a linear-time operation, defeat a great number of data-sharing opportunities, and generally plague the world with buffer overruns.
DanBC 12y ago
See also discussion here: https://hn.algolia.com/?q=The+Most+Expensive+One-byte+Mistake#!/story/forever/0/The%20Most%20Expensive%20One-byte%20Mistake https://hn.algolia.com/?q=The+Most+Expensive+One-byte+Mistak...

8 points by eric59 12y ago

I find this article very interesting, but I'd still like to point out it is from 2011.

Betteridge's Law strikes again. No, null-terminated strings are fine. Rants against null-terminated string are a good way to spot nutjobs. Null-terminated strings have virtues, such as being recursively defined: the tail of a string is a string. So strchr could be written like this (let's drop the const for simplicity): char *strchr(char *s, int ch) { if (*s == ch) return s; if (*s == 0) return NULL; return strchr(s + 1, ch); } It's easy to break a string with delimiters into the individual pieces in place, just by writing nulls over the separating characters, and keeping a vector of pointers to the pieces. This can't be done with some other string representations like length + data. When one null terminated string is a suffix of another (and ideally both are treated as immutable), then they can share storage. char *excon = "excon", *con = excon + 2; Catenating null terminating strings is efficient if you keep a tail pointer. A repeated strcat-like operation will be O(N*N) of course, so don't do that in some critical inner loop, with a large amount of text. Length + data strings have various disadvantages. For one thing, how wide should be the length? Two bytes? Four? Eight? If you make it two bytes today and store binary data somewhere, it will be incompatible with tomorrow's four byte length. And then there is endiannness. A binary file with strings produced on one machine will have byte swapped lengths on another. Null terminated strings can be blasted over a serial line or network, or written to disks, as they are; they are already marshaled and ready to go! (Though I must hastily acknowledge that this isn't true of wide character null term'd strings, of course.) Dynamic strings (management record plus pointer to data) are heavyweight representations that will show their weaknesses at virtual machine boundaries. You cannot pass them between address spaces or share them without marshaling to some flat form and back. Also, regarding another point in the article, MS-DOS did not invent the backslash as a path separator instead of the slash. This is a common misconception. MS-DOS supports both forward and backslash as separators! And so does Windows (every version between then and now). Early versions of COMMAND.COM had a variable whereby you could set this as a preference: whether you want to display and input path separators as slash or as backslash. This was later removed. Today, when you have trouble with forward slashes in Windows, this is due to the application you are using (including, sadly that application known as the Windows Explorer, and its "Shell API"). The underlying kernel handles the slashes just fine.

hyperliner 12y ago
Bingo: "Length + data strings have various disadvantages. For one thing, how wide should be the length? Two bytes? Four? Eight? "
- andreasvc 12y ago
  That's easy, it should be of type size_t. Yes that is wasteful for short strings, but then again I believe null-terminated strings are the most widespread and worst case of premature optimization, and correctness & safety should take precedence.
andreasvc 12y ago
I don't find the advantages of null-terminated strings you cite compelling. They sound like relatively rare operations, and compared to the severity and quantity of security problems caused by null-terminated strings it seems like a particularly bad trade-off. An advantage of storing strings with length and optionally start positions is that arbitrary slices can be defined, which reuse underlying data; this covers your examples of splitting by a delimiter and reusing suffixes. The argument that serialization would be harder is not really particular to the string format in question, that is always something that needs to be defined well, preferably with static typing (encoding issues make file formats complicated either way, if anything, storing a length attribute encourages to also store an encoding attribute while you're at it).
sjolsen 12y ago
Edit: It occurred to me after posting this that by "length + data" you might mean actually storing the length with the string data. If so, you're right, that's stupid. The correct solution (well, it's better than C/Pascal strings, anyway) is to store just the string data in the string proper, and use references that consist of pointer+length or pointer+pointer pairs instead of single char-pointers. > It's easy to break a string with delimiters into the individual pieces in place, just by writing nulls over the separating characters This assumes you're free to modify the input. If you don't want/are unable to modify the input, you're forced to allocate memory to hold the output; you've totally unnecessarily doubled the space requirement. It also assumes that there is a separating character to overwrite, which may not be the case, causing the same problem. > just by writing nulls over the separating characters > This can't be done with some other string representations like length + data Obviously. It is, however, perfectly possible to tokenize a string into a vector of length+data pairs without mangling the input. > When one null terminated string is a suffix of another (and ideally both are treated as immutable), then they can share storage. And only when one is a suffix of another. If you want to share storage between strings between which this relationship does not hold, you must again allocate extra memory, and again this is not necessary if you use a data+length representation. > Catenating null terminating strings is efficient if you keep a tail pointer In other words, if you use a pointer+length or arithmetically equivalent representation—except that you don't even bother binding the data into a coherent data structure, and instead force any code without access to your local tail-pointer variable to derive the length/end of the string on its own. > For one thing, how wide should be the length? Wide enough to represent the length of the longest possible string. Generally, this is less than or equal to the length of a pointer. > If you make it two bytes today and store binary data somewhere, it will be incompatible with tomorrow's four byte length > Null terminated strings can be blasted over a serial line or network, or written to disks, as they are You are making the incorrect assumption that the most appropriate on-disk/serialization representation is necessarily the same as the most appropriate in-memory representation. > And then there is endiannness 1. See above. 2. You're right that "this isn't true of wide character null term'd strings," so unless you and everyone you communicate with are still living in 1985, NTBSes don't even have that advantage. > You cannot pass them between address spaces or share them without marshaling to some flat form and back You can't do this with NTBSes, either, unless you have a way of translating the address of the string across address spaces, in which case you could just as well pass a pointer+length as you could pass a pointer. NTBSes are a perfectly fine representation if: your string is known at compile time; your string will never be modified; your string will only be scanned through from front to back; and your string does not contain a null character. From a technical standpoint, the only reason to bother with them in the first place is that you have extremely tight memory requirements and can't even afford the extra byte or three needed for a sane string-reference representation. If any of these conditions does not hold, NTBSes are a Terrible, Horrible, No Good, Very Bad representation. All they accomplish in practice is to make strlen a linear-time operation, defeat a great number of data-sharing opportunities, and generally plague the world with buffer overruns.

DanBC 12y ago

See also discussion here: https://hn.algolia.com/?q=The+Most+Expensive+One-byte+Mistake#!/story/forever/0/The%20Most%20Expensive%20One-byte%20Mistake https://hn.algolia.com/?q=The+Most+Expensive+One-byte+Mistak...