3 ms·

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

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.

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.