4 ms·

While I often implement strings along the lines you suggest I disagree that this feature belongs in the standard library. For one thing how big (sizeof) should

While I often implement strings along the lines you suggest I disagree that this feature belongs in the standard library. For one thing how big (sizeof) should the length prefix be? 16-bits? 32-bits? 64-bits? The beauty of the C string is that it is minimal and straightforward: if you have a pointer to it, you know where it ends. And it works with pretty much any OS out there. (My personal variant of dynamic strings are refcounted, length prefixed and nul-terminated with the pointer pointing to the traditional C string.)

kzrdude 7y ago
Using size_t as the common solution seems like the way to go. struct string { char *data; size_t size; size_t alloc_size; }; struct string_view { char *data; size_t size; }; And we have the same design that C++ uses.
- billziss 7y ago
  I do not think I have ever seen a string that needs more than 64K, but then again I do not read whole files in memory in C. (I do in Python.) So this would be wasteful in many cases. My personal variant uses 32-bits for length and 32-bits for refcount, which aligns well on most platforms, including 64-bit ones. Something like: struct string_header { int32_t refcnt; int32_t length; // character content starts here }; Given a char pointer to get to the header you must do: ((struct string_header *)p)[-1]
  - saagarjha 7y ago
    How would you use the refcount?
    - billziss 7y ago
      I use the refcount to avoid copying the string when passing it around. I just refcount it instead. To clarify this is part of a larger library that includes other memory management machinery, such as autorelease pools, etc.
  - papermachete 7y ago
    >I >I >I There is no 'I' in standard libraries :)
- nneonneo 7y ago
  C++ implementations sometimes optimize for storing short strings inside the string structure itself. One approach looks something like this on 64-bit machines: struct string { union { struct { char *ptr; size_t capacity; }; char str[16]; } data; size_t length; }; It looks complex, but it’s actually a really nice design because it requires no separate allocation for strings less than 16 bytes long, which is a common case, and the strings are relatively compact. And, it stores a capacity parameter which allows you to know when it’s safe to grow the string without allocating, making it possible to implement efficient repeated concatenation.
jcranmer 7y ago
> For one thing how big (sizeof) should the length prefix be? 16-bits? 32-bits? 64-bits? size_t, or uintptr_t [1]. Maybe uint32_t, although given pointer alignment, smaller-than-pointer for size doesn't help all that much. > The beauty of the C string is that it is minimal and straightforward: if you have a pointer to it, you know where it ends. And if you screw up adding a null byte, client code will happily keep running through the rest of memory to find it. And if your string has embedded nulls, you're SOL anyways. > And it works with pretty much any OS out there. And for safety reasons, the OS generally has to assume a maximum length anyways, otherwise, you tend to have security vulnerabilities. [1] size_t is not necessarily the same size as uintptr_t. An architecture with a 64-bit base pointer shared across several 32-bit indexes is an interesting idea that could use some more programming exploration.
benj111 7y ago
Why not go full Pascal strings, and go for 8 bit? The good thing about 64 bit lengths is you never need to worry about overflowing the string. The bad thing is no one know what to do, or codes for the possibility of the string overflowing. 8 bits 'should' avoid people making that assumption.
- Gibbon1 7y ago
  The was my thought earlier this morning. Something anything is better than the total shit design we've been living with.
kreco 7y ago
> For one thing how big (sizeof) should the length prefix be? 16-bits? 32-bits? 64-bits? Exactly like what is returned by strlen... ?
chrisdew 7y ago
Is your string library open sourced? Could you provide a link?

kzrdude 7y ago

Using size_t as the common solution seems like the way to go. struct string { char *data; size_t size; size_t alloc_size; }; struct string_view { char *data; size_t size; }; And we have the same design that C++ uses.

billziss 7y ago
I do not think I have ever seen a string that needs more than 64K, but then again I do not read whole files in memory in C. (I do in Python.) So this would be wasteful in many cases. My personal variant uses 32-bits for length and 32-bits for refcount, which aligns well on most platforms, including 64-bit ones. Something like: struct string_header { int32_t refcnt; int32_t length; // character content starts here }; Given a char pointer to get to the header you must do: ((struct string_header *)p)[-1]
- saagarjha 7y ago
  How would you use the refcount?
  - billziss 7y ago
    I use the refcount to avoid copying the string when passing it around. I just refcount it instead. To clarify this is part of a larger library that includes other memory management machinery, such as autorelease pools, etc.
- papermachete 7y ago
  >I >I >I There is no 'I' in standard libraries :)
nneonneo 7y ago
C++ implementations sometimes optimize for storing short strings inside the string structure itself. One approach looks something like this on 64-bit machines: struct string { union { struct { char *ptr; size_t capacity; }; char str[16]; } data; size_t length; }; It looks complex, but it’s actually a really nice design because it requires no separate allocation for strings less than 16 bytes long, which is a common case, and the strings are relatively compact. And, it stores a capacity parameter which allows you to know when it’s safe to grow the string without allocating, making it possible to implement efficient repeated concatenation.

jcranmer 7y ago

> For one thing how big (sizeof) should the length prefix be? 16-bits? 32-bits? 64-bits? size_t, or uintptr_t [1]. Maybe uint32_t, although given pointer alignment, smaller-than-pointer for size doesn't help all that much. > The beauty of the C string is that it is minimal and straightforward: if you have a pointer to it, you know where it ends. And if you screw up adding a null byte, client code will happily keep running through the rest of memory to find it. And if your string has embedded nulls, you're SOL anyways. > And it works with pretty much any OS out there. And for safety reasons, the OS generally has to assume a maximum length anyways, otherwise, you tend to have security vulnerabilities. [1] size_t is not necessarily the same size as uintptr_t. An architecture with a 64-bit base pointer shared across several 32-bit indexes is an interesting idea that could use some more programming exploration.

benj111 7y ago

Why not go full Pascal strings, and go for 8 bit? The good thing about 64 bit lengths is you never need to worry about overflowing the string. The bad thing is no one know what to do, or codes for the possibility of the string overflowing. 8 bits 'should' avoid people making that assumption.

Gibbon1 7y ago
The was my thought earlier this morning. Something anything is better than the total shit design we've been living with.

kreco 7y ago

> For one thing how big (sizeof) should the length prefix be? 16-bits? 32-bits? 64-bits? Exactly like what is returned by strlen... ?

chrisdew 7y ago

Is your string library open sourced? Could you provide a link?