An even better solution:
https://www.digitalmars.com/articles/C-biggest-mistake.html
With the lengths of strings known, copying becomes fast, safe, and trivial.
https://www.digitalmars.com/articles/C-biggest-mistake.html
With the lengths of strings known, copying becomes fast, safe, and trivial.
And just generally doing that for all arrays. That way if you're passed ONLY a pointer to the array, you can always tell how long it is without requiring the caller to tell you how long it is, which seems to be a common theme among C functions. And that also allows your string to contain null characters, which is useful in many circumstances.
Of course, null termination also means that slicing is restricted to being a tail.
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.
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...
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.
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.
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.
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.
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.
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.
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.
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.
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
Really, unless we are talking about PIC and AVRs with like 4KB, we are optimizing for the wrong target.
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…
It's string. Alignment shouldn't be a problem. Rather alignment issues are for the pointers to that string.
But still needless complexity for this.