5 ms·

Not everyone is going to be happy about 8 bytes overhead for every buffer. Also, not every C-style API will migrate. If you consume one of those, you may still

Not everyone is going to be happy about 8 bytes overhead for every buffer. Also, not every C-style API will migrate. If you consume one of those, you may still have to count the length, which costs cycles.

WalterBright 5y ago
The proposal does not take away any C features.
scottlamb 5y ago
> Not everyone is going to be happy about 8 bytes overhead for every buffer. Then prefix it with four bytes (which, if you omit the trailing NUL, adds three bytes in total). If your C strings are longer than 2^32 bytes, you're probably doing something wrong. I also should point out that memory is typically cheap. Cache is more precious, and I'd expect on balance adding a length would pollute the cache less than scanning through the whole string unnecessarily. But I agree with your second point: > Also, not every C-style API will migrate. If you consume one of those, you may still have to count the length, which costs cycles. Similarly, the article started with this text: > Like them or not, null-terminated strings are essential to C, and working with them is necessary in all but the most trivial programs. You can do things nicely in your own code, but you still need NUL-terminated strings when dealing with existing code. And dealing with existing code is often the reason to pick C...
- iib 5y ago
  I would assume the people bothered by an increase in byte-sized overhead are not the ones that are using 2^32 length strings. About the cache, I think for small strings, scanning the whole string may still be faster. Though adding a four-byte length prefix would make certain functions like strlen almost go away.
- attractivechaos 5y ago
  Four bytes are still overhead. Also, you often need to keep the capacity of a string. Another four bytes. The C string APIs are like the lowest denominator of all use cases. When you know string lengths, you can avoid quadratic strcat() or other performance pitfalls with the existing APIs. On the other hand, if the APIs forced everyone to keep string lengths, performance/memory/convenience would be affected for certain use cases. Memory is not cheap when you deal with many short strings or when you do embedded programming.
  - scottlamb 5y ago
    > Four bytes are still overhead. I hedged with "typically" but I'm a little skeptical about the environments in which this is a problem. Embedded stuff that's severely memory constrained probably doesn't deal with that many strings. But you could use a variable-sized length prefix as another commenter suggested to have no overhead on short strings. Its size would be decided at allocation time so you're not shifting the string. You could indicate it via high bits of the length or low bits of 4-byte-aligned string pointers. It's an extra branch or table lookup or the like on access though. > Also, you often need to keep the capacity of a string. Another four bytes Nonsense. There are exactly no situations where you need to keep a capacity with this scheme and not with traditional C strings.
    - deleted 5y ago
      [deleted]
    - attractivechaos 5y ago
      For two standard formats in our field, you sometimes need to keep billions of short strings in memory. Many of these strings are 2 bytes or several bytes in length. The parser in C packs them as NULL terminated strings. The C++ and Java parsers use the std::string or the string type. They use a lot more memory. Even a 4-byte overhead would double the memory. Yes, you can have a smart way to keep short strings to waste less or even no memory (one of the two formats is using this trick), but it makes code harder to read and hurts performance due to the extra check/conversion. As to the capacity field, we sometimes have to keep it around. The question is: do you keep it inside the string struct/memory block (like std::string) or let users handle it? We have varying preferences in different cases. It is hard to design APIs optimal in all cases.
      - scottlamb 5y ago
        Do you mind sharing the field / formats? I'm curious. I think situations like this are special enough that they shouldn't drive discussion for general-purpose types. fwiw, some ideas for what you're describing based on what understanding I can have from your two-paragraph description: * If many of billions of text strings are that short, there must be a huge number of duplicates. If they have similar lifetimes (e.g., all freed with the parsed file handle) and are immutable or mutations are rare and can follow a "get_mut()", I'd consider aliasing them with an intern table. (You could do that for all strings or for just the strings under a certain length.) There's some CPU and memory overhead from the hash table but it'd make duplicates use no RAM in a way that's orthogonal to the representation of a particular string. * Or you could have an 8-byte type that can represent a pointer or a 7-byte text string. With a general-purpose allocator, the low bits of a pointer are guaranteed to be zero, and many of the high bits are also effectively unused (all the same) depending on platform. (Either of the above might be what you're referring to with "a smart way to keep short strings to waste less or even no memory".) * On most platforms, malloc returns pointers with a minimum alignment of two words or so and thus a similar minimum allocation size. If you're on a 64-bit platform (must be, with billions of 2+ byte strings in RAM), that's 16 bytes. A lot of waste. A custom allocator might be better. It doesn't have to be anything complex. Again depending on lifetime and mutability, you could use a simple arena (bump allocator). Its handle could be indexes that are valid across reallocation or they could be stable pointers by just making a single upper bound allocation and depending on the OS's lazy minor page faulting to keep the unused part from being backed by real physical memory. * C++: if you pass these to interfaces that take an absl::string_view or the like rather than const std::string&, you have a lot more flexibility in your representation without copying/reallocating on use. * Java: GCed languages double memory requirements to begin with for the GC to work efficiently, and Java historically uses a UTF-16 string type (maybe there's an optimization in latest versions?), so it's almost hopeless. Hard for me to reconcile "we need to save RAM" with Java at all. The most RAM-efficient way to store them would be outside Java's heap (native code or mmaped region) but then you have to deal with non-idiomatic handles and likely copying/allocating (generating garbage) on use, yuck. > As to the capacity field, we sometimes have to keep it around. The question is: do you keep it inside the string struct/memory block (like std::string) or let users handle it? We have varying preferences in different cases. It is hard to design APIs optimal in all cases. Keep it around long-term, as in you have lots of mutable strings at once rather than having them for a short time then "freezing" them into a more efficient immutable type that can assume length=capacity, can use interning and arenas, etc? Then you want to make sure you're not paying 8 bytes for that capacity field, as you can easily end up with having the caller keep it due to padding. (That'd be a more error-prone API too.) You could have your handles be a single word that uses unused pointer bits for size of capacity and length fields and points to a capacity+length+data allocation. That's likely what I would do if efficiency really matters.
- mkcg 5y ago
  You could also prefix it with a varint : in this case it would not require any extra byte compared to the NUL terminated string when the length of the string is less than 128 chars.
- jjav 5y ago
  > I also should point out that memory is typically cheap. Not in the early 70s, no. Even in the late 80s I was writing code very conscious of every single byte that could be saved anywhere.
loup-vaillant 5y ago
Actually, it's 7 bytes (you can remove `\0` at the end), and that's if you insist on being able to exceed 4GB with your strings. Personally, depending on the use case, I'd be willing to have strings limited to 256 bytes (no overhead), 64K bytes (1 byte of overhead), and 4G bytes (3 bytes of overhead). Though combining them all might be quite the nightmare…
- codesnik 5y ago
  you can also have something akin to MIDI encoding with higher bit reserved to mark that next byte is a part of length field, too. up to 128 bytes with no overhead, up to 16kb with one byte overhead, and so on. Such a detail would be easy to hide in the library. But I wouldn't be surprised that alignment and other troubles would eat any possible gain.
  - WalterBright 5y ago
    Won't work with UTF-8.
    - thrwaeasddsaf 5y ago
      Works with any encoding and arbitrary binary data. The last byte of the length field doesn't have the high bit set, and whatever follows after that is completely irrelevant. But still needless complexity for this.
    - moonchild 5y ago
      Sure it is, the length is out of band. In fact, you could even use utf-8 to encode the length!
  - habibur 5y ago
    > But I wouldn't be surprised that alignment ... troubles would eat any possible gain. It's string. Alignment shouldn't be a problem. Rather alignment issues are for the pointers to that string.
- dnr 5y ago
rectang 5y ago
Saving 8 bytes, and saving a few cycles by scanning rather than counting... is an argument for using NUL-terminated strings as an optimization in specialized circumstances. In the common case, the extra 8 bytes and the cycles saved (if any) don't matter — and are not worth the sacrifice of making it harder to program correctly.
- kevin_thibedeau 5y ago
  > the extra 8 bytes and the cycles saved (if any) don't matter You wouldn't last in embedded development with that sort of attitude. When you're nearly out of RAM you can't afford to waste overhead of fat strings.
  - pkaye 5y ago
    Not every embedded system is memory constrained these days.
    - rectang 5y ago
      Indeed. And besides, didn't I account for precisely that scenario? Memory-constrained embedded development is a specialized situation that could call for using NUL-terminated strings.
  - pjmlp 5y ago
    I was using Turbo Basic, Turbo Pascal, Turbo C++ (with C++ collections), and Clipper on MS-DOS, with 640 KB of memory. It was just fine, then there are those that nowadays even toy with C++17 on C64. “Rich Code for Tiny Computers: A Simple Commodore 64 Game in C++17” https://www.youtube.com/watch?v=zBkNBP00wJE https://www.youtube.com/watch?v=zBkNBP00wJE Really, unless we are talking about PIC and AVRs with like 4KB, we are optimizing for the wrong target.
  - mh7 5y ago
    You can't afford to waste cycles on O(n) strlen either.

WalterBright 5y ago

The proposal does not take away any C features.

scottlamb 5y ago

> Not everyone is going to be happy about 8 bytes overhead for every buffer. Then prefix it with four bytes (which, if you omit the trailing NUL, adds three bytes in total). If your C strings are longer than 2^32 bytes, you're probably doing something wrong. I also should point out that memory is typically cheap. Cache is more precious, and I'd expect on balance adding a length would pollute the cache less than scanning through the whole string unnecessarily. But I agree with your second point: > Also, not every C-style API will migrate. If you consume one of those, you may still have to count the length, which costs cycles. Similarly, the article started with this text: > Like them or not, null-terminated strings are essential to C, and working with them is necessary in all but the most trivial programs. You can do things nicely in your own code, but you still need NUL-terminated strings when dealing with existing code. And dealing with existing code is often the reason to pick C...

iib 5y ago
I would assume the people bothered by an increase in byte-sized overhead are not the ones that are using 2^32 length strings. About the cache, I think for small strings, scanning the whole string may still be faster. Though adding a four-byte length prefix would make certain functions like strlen almost go away.
attractivechaos 5y ago
Four bytes are still overhead. Also, you often need to keep the capacity of a string. Another four bytes. The C string APIs are like the lowest denominator of all use cases. When you know string lengths, you can avoid quadratic strcat() or other performance pitfalls with the existing APIs. On the other hand, if the APIs forced everyone to keep string lengths, performance/memory/convenience would be affected for certain use cases. Memory is not cheap when you deal with many short strings or when you do embedded programming.
- scottlamb 5y ago
  > Four bytes are still overhead. I hedged with "typically" but I'm a little skeptical about the environments in which this is a problem. Embedded stuff that's severely memory constrained probably doesn't deal with that many strings. But you could use a variable-sized length prefix as another commenter suggested to have no overhead on short strings. Its size would be decided at allocation time so you're not shifting the string. You could indicate it via high bits of the length or low bits of 4-byte-aligned string pointers. It's an extra branch or table lookup or the like on access though. > Also, you often need to keep the capacity of a string. Another four bytes Nonsense. There are exactly no situations where you need to keep a capacity with this scheme and not with traditional C strings.
  - deleted 5y ago
    [deleted]
  - attractivechaos 5y ago
    For two standard formats in our field, you sometimes need to keep billions of short strings in memory. Many of these strings are 2 bytes or several bytes in length. The parser in C packs them as NULL terminated strings. The C++ and Java parsers use the std::string or the string type. They use a lot more memory. Even a 4-byte overhead would double the memory. Yes, you can have a smart way to keep short strings to waste less or even no memory (one of the two formats is using this trick), but it makes code harder to read and hurts performance due to the extra check/conversion. As to the capacity field, we sometimes have to keep it around. The question is: do you keep it inside the string struct/memory block (like std::string) or let users handle it? We have varying preferences in different cases. It is hard to design APIs optimal in all cases.
    - scottlamb 5y ago
      Do you mind sharing the field / formats? I'm curious. I think situations like this are special enough that they shouldn't drive discussion for general-purpose types. fwiw, some ideas for what you're describing based on what understanding I can have from your two-paragraph description: * If many of billions of text strings are that short, there must be a huge number of duplicates. If they have similar lifetimes (e.g., all freed with the parsed file handle) and are immutable or mutations are rare and can follow a "get_mut()", I'd consider aliasing them with an intern table. (You could do that for all strings or for just the strings under a certain length.) There's some CPU and memory overhead from the hash table but it'd make duplicates use no RAM in a way that's orthogonal to the representation of a particular string. * Or you could have an 8-byte type that can represent a pointer or a 7-byte text string. With a general-purpose allocator, the low bits of a pointer are guaranteed to be zero, and many of the high bits are also effectively unused (all the same) depending on platform. (Either of the above might be what you're referring to with "a smart way to keep short strings to waste less or even no memory".) * On most platforms, malloc returns pointers with a minimum alignment of two words or so and thus a similar minimum allocation size. If you're on a 64-bit platform (must be, with billions of 2+ byte strings in RAM), that's 16 bytes. A lot of waste. A custom allocator might be better. It doesn't have to be anything complex. Again depending on lifetime and mutability, you could use a simple arena (bump allocator). Its handle could be indexes that are valid across reallocation or they could be stable pointers by just making a single upper bound allocation and depending on the OS's lazy minor page faulting to keep the unused part from being backed by real physical memory. * C++: if you pass these to interfaces that take an absl::string_view or the like rather than const std::string&, you have a lot more flexibility in your representation without copying/reallocating on use. * Java: GCed languages double memory requirements to begin with for the GC to work efficiently, and Java historically uses a UTF-16 string type (maybe there's an optimization in latest versions?), so it's almost hopeless. Hard for me to reconcile "we need to save RAM" with Java at all. The most RAM-efficient way to store them would be outside Java's heap (native code or mmaped region) but then you have to deal with non-idiomatic handles and likely copying/allocating (generating garbage) on use, yuck. > As to the capacity field, we sometimes have to keep it around. The question is: do you keep it inside the string struct/memory block (like std::string) or let users handle it? We have varying preferences in different cases. It is hard to design APIs optimal in all cases. Keep it around long-term, as in you have lots of mutable strings at once rather than having them for a short time then "freezing" them into a more efficient immutable type that can assume length=capacity, can use interning and arenas, etc? Then you want to make sure you're not paying 8 bytes for that capacity field, as you can easily end up with having the caller keep it due to padding. (That'd be a more error-prone API too.) You could have your handles be a single word that uses unused pointer bits for size of capacity and length fields and points to a capacity+length+data allocation. That's likely what I would do if efficiency really matters.
mkcg 5y ago
You could also prefix it with a varint : in this case it would not require any extra byte compared to the NUL terminated string when the length of the string is less than 128 chars.
jjav 5y ago
> I also should point out that memory is typically cheap. Not in the early 70s, no. Even in the late 80s I was writing code very conscious of every single byte that could be saved anywhere.

loup-vaillant 5y ago

Actually, it's 7 bytes (you can remove `\0` at the end), and that's if you insist on being able to exceed 4GB with your strings. Personally, depending on the use case, I'd be willing to have strings limited to 256 bytes (no overhead), 64K bytes (1 byte of overhead), and 4G bytes (3 bytes of overhead). Though combining them all might be quite the nightmare…

codesnik 5y ago
you can also have something akin to MIDI encoding with higher bit reserved to mark that next byte is a part of length field, too. up to 128 bytes with no overhead, up to 16kb with one byte overhead, and so on. Such a detail would be easy to hide in the library. But I wouldn't be surprised that alignment and other troubles would eat any possible gain.
- WalterBright 5y ago
  Won't work with UTF-8.
  - thrwaeasddsaf 5y ago
    Works with any encoding and arbitrary binary data. The last byte of the length field doesn't have the high bit set, and whatever follows after that is completely irrelevant. But still needless complexity for this.
  - moonchild 5y ago
    Sure it is, the length is out of band. In fact, you could even use utf-8 to encode the length!
- habibur 5y ago
  > But I wouldn't be surprised that alignment ... troubles would eat any possible gain. It's string. Alignment shouldn't be a problem. Rather alignment issues are for the pointers to that string.
dnr 5y ago

rectang 5y ago

Saving 8 bytes, and saving a few cycles by scanning rather than counting... is an argument for using NUL-terminated strings as an optimization in specialized circumstances. In the common case, the extra 8 bytes and the cycles saved (if any) don't matter — and are not worth the sacrifice of making it harder to program correctly.

kevin_thibedeau 5y ago
> the extra 8 bytes and the cycles saved (if any) don't matter You wouldn't last in embedded development with that sort of attitude. When you're nearly out of RAM you can't afford to waste overhead of fat strings.
- pkaye 5y ago
  Not every embedded system is memory constrained these days.
  - rectang 5y ago
    Indeed. And besides, didn't I account for precisely that scenario? Memory-constrained embedded development is a specialized situation that could call for using NUL-terminated strings.
- pjmlp 5y ago
  I was using Turbo Basic, Turbo Pascal, Turbo C++ (with C++ collections), and Clipper on MS-DOS, with 640 KB of memory. It was just fine, then there are those that nowadays even toy with C++17 on C64. “Rich Code for Tiny Computers: A Simple Commodore 64 Game in C++17” https://www.youtube.com/watch?v=zBkNBP00wJE https://www.youtube.com/watch?v=zBkNBP00wJE Really, unless we are talking about PIC and AVRs with like 4KB, we are optimizing for the wrong target.
- mh7 5y ago
  You can't afford to waste cycles on O(n) strlen either.