5 ms·

I wonder, why not use a string buffer paired with its length? For example, maybe use struct that has char pointer, and 2 ints (occupied length + total buffer le

by senfiaj 4mo ago

I wonder, why not use a string buffer paired with its length? For example, maybe use struct that has char pointer, and 2 ints (occupied length + total buffer length). Almost like c++'s std::string. This null terminator thing really sucks, it's potentially insecure and often unperformant.

GalaxyNova 4mo ago
Yes I have seen it happen a few times with `strlen` being called in a loop silently causing O(N) to turn to O(N^2)
- senfiaj 4mo ago
  Exactly, you can't write clean concise code when working with c strings. Almost every c string manipulation requires cognitive load: "Is the buffer size enough (including null terminator), should I reallocate it?", "I need to have the offset from the last concat, to make next concats performant", "Umm, shold I put null terminator at i or i + 1?"... It really sucks, it's akin to death by thousands of cuts.
- jkrejcha 4mo ago
  Reminds me of an article[1] that described how he cut GTA Online loading times by 70% because strlen was getting called for effectively every character in a string [1]: https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times-by-70/ https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times...
  - sweetjuly 4mo ago
    I remember reading this blog post when it was first published, but the subsequent updates are better than I would've ever expected this to turn out. Worth checking it out again if you've seen it before :)
- sgerenser 4mo ago
  Joel Spolsky coined the term “Shlemiel the Painter’s Algorithm” for this type of thing back in 2001: https://www.joelonsoftware.com/2001/12/11/back-to-basics/ https://www.joelonsoftware.com/2001/12/11/back-to-basics/
chiph 4mo ago
Pascal did/does this, but eventually someone wants a string longer than the size portion can handle. Or wants the number of characters not the number of bytes.
- jerf 4mo ago
  I wasn't a programmer in these days, so I don't know if there's some other major concern that would kill this, but I sometimes wonder about whether we could have / should have used variable-length integers. That is, something like, 0-127 byte strings get their length prefixed, 128 - 16383 get two bytes of prefix, and the probably-rare 16384 - 2097151 strings would end up with three, though proportionally by that point it's hardly anything. Or you could use the UTF-8 mechanism for packing the bytes, though that costs more and probably doesn't get anything we'd care about in the 1980s or 1990s. It's a bit of extra code, yes. Not necessarily all that much, but some. On average it is only slightly more expensive than null termination, and considered as a proportion of the size of the strings themselves it's hardly anything. It's probably better than the strings getting hard-limited to 0-255, though, which was quite frequently a user-visible quirk.
  - senfiaj 4mo ago
    32-bit int isn't too much overhead. Just 3 additional bytes. I bet it's almost always better than c style strings. In the vast majority of situations the price isn't that bad, considering you make strings much more secure and potentially faster in string manipulations.
    - jerf 4mo ago
      32-bit is so little overhead that we don't blink at adding 64 to our strings nowadays, because of the benefits we get from alignment. But remember the first Macintosh shipped with 128KB of RAM, 131,072 bytes. Three more bytes per string hurts a lot more there... ... although, that said, even in that era given the number of errors that null-terminated strings caused, even completely ignoring security, I do still wonder if at least defaulting to 2 bytes of length and doing something special for strings over 64K still wouldn't have been the right tradeoff, even in the case of short strings. Today we mostly focus on security, but null-terminated strings also caused a lot of just plain-old bugs. But so did 1-byte length strings... it's way too easy to run out of 256 characters even on those old systems.
none_to_remain 4mo ago
The size overhead of that is 2*sizeof(int) while the overhead of null termination is sizeof(char). If I remember the standard right, the former is worse by at least sizeof(char), and usually more in practice. This used to matter, sometimes still does.
- senfiaj 4mo ago
  Well, not saying to always use it, but if the string size is big enough, the overhead of 2 ints becomes relatively vanishing. For generic dynamically sized strings it probably has more advantages than disadvantages. But in any case, sure, if every single byte matters or some structure requires specific memory layout, then fine. I just don't think these things are the majority of use cases. Keep in mind that the cached lengths can increase performance, since you don't have to recalculate string lengths.
  - lelanthran 4mo ago
    > Well, not saying to always use it, but if the string size is big enough, the overhead of 2 ints becomes relatively vanishing. In that case, the fix is not to change C strings (breaking a lot of existing code), but to introduce a stringbuilder type.
    - senfiaj 4mo ago
      You can still use null terminator for compatibility (std::string does use this), but just not rely on that in your own code.
  - ekaryotic 4mo ago
    I am a terrible hobby c programmer that doesn't understand pointers but surely a symmetric approach doesn't have the overhead or the bug. that is to say that if the language was designed to work in single bit pairs of a string character in conjunction of a string length character assuming a fail safe design of one dummy string character then if a bug happens in the code then there's no overflow because the length can never be shorter than the character.
bnolsen 4mo ago
That's called a fat pointer. Null terminated c strings is the majority of memory errors out there.
WalterBright 4mo ago
Wonder no longer! https://dlang.org/spec/arrays.html#dynamic-arrays https://dlang.org/spec/arrays.html#dynamic-arrays and https://dlang.org/spec/arrays.html#strings https://dlang.org/spec/arrays.html#strings and for C: https://digitalmars.com/articles/C-biggest-mistake.html https://digitalmars.com/articles/C-biggest-mistake.html
MBCook 4mo ago
A lot of them are strings coming from or going to user space right? So wouldn’t you have to do constant conversions?
maxlybbert 4mo ago
It's definitely possible. And common, at least in some projects. The only real drawback is that sloppiness will lead to multiple slightly different nonstandard string types in the same project.

by senfiaj 4mo ago

GalaxyNova 4mo ago

Yes I have seen it happen a few times with `strlen` being called in a loop silently causing O(N) to turn to O(N^2)

senfiaj 4mo ago
Exactly, you can't write clean concise code when working with c strings. Almost every c string manipulation requires cognitive load: "Is the buffer size enough (including null terminator), should I reallocate it?", "I need to have the offset from the last concat, to make next concats performant", "Umm, shold I put null terminator at i or i + 1?"... It really sucks, it's akin to death by thousands of cuts.
jkrejcha 4mo ago
Reminds me of an article[1] that described how he cut GTA Online loading times by 70% because strlen was getting called for effectively every character in a string [1]: https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times-by-70/ https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times...
- sweetjuly 4mo ago
  I remember reading this blog post when it was first published, but the subsequent updates are better than I would've ever expected this to turn out. Worth checking it out again if you've seen it before :)
sgerenser 4mo ago
Joel Spolsky coined the term “Shlemiel the Painter’s Algorithm” for this type of thing back in 2001: https://www.joelonsoftware.com/2001/12/11/back-to-basics/ https://www.joelonsoftware.com/2001/12/11/back-to-basics/

chiph 4mo ago

Pascal did/does this, but eventually someone wants a string longer than the size portion can handle. Or wants the number of characters not the number of bytes.

jerf 4mo ago
I wasn't a programmer in these days, so I don't know if there's some other major concern that would kill this, but I sometimes wonder about whether we could have / should have used variable-length integers. That is, something like, 0-127 byte strings get their length prefixed, 128 - 16383 get two bytes of prefix, and the probably-rare 16384 - 2097151 strings would end up with three, though proportionally by that point it's hardly anything. Or you could use the UTF-8 mechanism for packing the bytes, though that costs more and probably doesn't get anything we'd care about in the 1980s or 1990s. It's a bit of extra code, yes. Not necessarily all that much, but some. On average it is only slightly more expensive than null termination, and considered as a proportion of the size of the strings themselves it's hardly anything. It's probably better than the strings getting hard-limited to 0-255, though, which was quite frequently a user-visible quirk.
- senfiaj 4mo ago
  32-bit int isn't too much overhead. Just 3 additional bytes. I bet it's almost always better than c style strings. In the vast majority of situations the price isn't that bad, considering you make strings much more secure and potentially faster in string manipulations.
  - jerf 4mo ago
    32-bit is so little overhead that we don't blink at adding 64 to our strings nowadays, because of the benefits we get from alignment. But remember the first Macintosh shipped with 128KB of RAM, 131,072 bytes. Three more bytes per string hurts a lot more there... ... although, that said, even in that era given the number of errors that null-terminated strings caused, even completely ignoring security, I do still wonder if at least defaulting to 2 bytes of length and doing something special for strings over 64K still wouldn't have been the right tradeoff, even in the case of short strings. Today we mostly focus on security, but null-terminated strings also caused a lot of just plain-old bugs. But so did 1-byte length strings... it's way too easy to run out of 256 characters even on those old systems.

none_to_remain 4mo ago

The size overhead of that is 2*sizeof(int) while the overhead of null termination is sizeof(char). If I remember the standard right, the former is worse by at least sizeof(char), and usually more in practice. This used to matter, sometimes still does.

senfiaj 4mo ago
Well, not saying to always use it, but if the string size is big enough, the overhead of 2 ints becomes relatively vanishing. For generic dynamically sized strings it probably has more advantages than disadvantages. But in any case, sure, if every single byte matters or some structure requires specific memory layout, then fine. I just don't think these things are the majority of use cases. Keep in mind that the cached lengths can increase performance, since you don't have to recalculate string lengths.
- lelanthran 4mo ago
  > Well, not saying to always use it, but if the string size is big enough, the overhead of 2 ints becomes relatively vanishing. In that case, the fix is not to change C strings (breaking a lot of existing code), but to introduce a stringbuilder type.
  - senfiaj 4mo ago
    You can still use null terminator for compatibility (std::string does use this), but just not rely on that in your own code.
- ekaryotic 4mo ago
  I am a terrible hobby c programmer that doesn't understand pointers but surely a symmetric approach doesn't have the overhead or the bug. that is to say that if the language was designed to work in single bit pairs of a string character in conjunction of a string length character assuming a fail safe design of one dummy string character then if a bug happens in the code then there's no overflow because the length can never be shorter than the character.

bnolsen 4mo ago

That's called a fat pointer. Null terminated c strings is the majority of memory errors out there.

WalterBright 4mo ago

Wonder no longer! https://dlang.org/spec/arrays.html#dynamic-arrays https://dlang.org/spec/arrays.html#dynamic-arrays and https://dlang.org/spec/arrays.html#strings https://dlang.org/spec/arrays.html#strings and for C: https://digitalmars.com/articles/C-biggest-mistake.html https://digitalmars.com/articles/C-biggest-mistake.html

MBCook 4mo ago

A lot of them are strings coming from or going to user space right? So wouldn’t you have to do constant conversions?

maxlybbert 4mo ago

It's definitely possible. And common, at least in some projects. The only real drawback is that sloppiness will lead to multiple slightly different nonstandard string types in the same project.