9 ms·

I always use antirez's (Redis creator) `sds` and advertise it whenvever I get the chance. Thanks to the someone who recommended it on HN some years ago. It's a

I always use antirez's (Redis creator) `sds` and advertise it whenvever I get the chance. Thanks to the someone who recommended it on HN some years ago. It's a joy to use. https://github.com/antirez/sds https://github.com/antirez/sds The trick is the size is hidden before the adress of the buffer.("Learn this one simple trick that will change your life for ever"). From the Readme: ``` Advantage #1: you can pass SDS strings to functions designed for C functions without accessing a struct member or calling a function Advantage #2: accessing individual chars is straightforward. Advantage #3: single allocation has better cache locality. Usually when you access a string created by a string library using a structure, you have two different allocations for the structure representing the string, and the actual buffer holding the string. Over the time the buffer is reallocated, and it is likely that it ends in a totally different part of memory compared to the structure itself. Since modern programs performances are often dominated by cache misses, SDS may perform better in many workloads. ```

kazinator 4y ago
Thus, sds it cannot be used for the use cases that this library allows. This library takes string slices without having to allocate or copy memory; it seems to be for use cases involving breaking down strings in complex ways, where good ergonomics and efficiency of obtaining a null-terminated C string are secondary.
quelsolaar 4y ago
Optimizing text is hard because you seldom up front know how much memory will be needed and allocations are slow. Another way to do it is to use: typedef struct{ size_t allocated; size_t used; char buffer[]; }String; This lets the header and the string be the same allocation. Thats a huge saving. Its also useful to store the allocation and use size separatly so that you can reuse / modify buffers. The used field lets you use memcpy without looking for string termination. You can make it even more complex by adding flags if the string is on the stack or on the heap. That way you can do things like: String buffer = MACRO_TO_CREATE_STRING_BUFFER_ON_STACK(256), *b; b = &buffer; b = do_processing_with_buffer(&b); // allocates on heap a larger buffer if needed string_free(b); // frees buffer if its on heap.
- jstimpfle 4y ago
  In general it's hard to get more efficient than a simple struct String { const char *buffer; u32 size; }. Your method removes an indirection from the allocated storage, but you'd still need an external pointer to point to that struct in most cases. That, plus retrieving the size now costs an additional dereference. So I wouldn't use your method unless I knew that I'd have to reference the string from multiple locations. The best way to be efficient is often to make assumptions about the data. Most strings don't need any dynamic allocation after having been "built". So it makes a ton of sense to make a string builder API that returns a final string when it's finished. In this way, you save at least the "allocated" member. The advantage of the simpler string representation is that it works for any string (or substring) that is contiguous in memory, and is completely decoupled from allocation concerns. E.g. I can easily #define STRING(string_literal) \ ((String) { string_literal "", sizeof string_literal - 1 }) , to be able to statically declare such strings like this: String my_string = STRING("Foo bar"); If you have many strings that you know are small, then just the normal nul-terminated C string (without any size field) is as storage-efficient as it gets. In practice, I find string handling so easy that I rarely even define this struct String. I just pass around strings to functions as two arguments - pointer + size. It feels so light and data flows so easily between APIs, I love it.
mh7 4y ago
Re #3: A big downside is that you you can't easily take ownership of an existing buffer and treat it as this string type. string s; char some_buf[]; string_take(&s, some_buf, some_capacity); Also you would of course never dynamically allocate string structs, just the data member if needed.
_448 4y ago
> The trick is the size is hidden before the adress of the buffer. That is how strings use to be stored before C made the choice of using null-terminator. Pascal stored the string size before the string data. The advantage of relying on a terminator symbol is that the string size can be any length where as storing the size at the start forces the string to not exceed certain size.
- anonymoushn 4y ago
  In execution environments with 64-bit pointers you may have trouble loading a string of more than 16 exabytes into RAM anyway
- mh7 4y ago
  strlen() returns a size_t so you're already constrained to a maximum length of SIZE_MAX.
  - jcelerier 4y ago
    If you use a different data structure you would maybe use a different API for accessing it too
  - jstimpfle 4y ago
    This is hilarious. SIZE_MAX is at least as large as the largest string that you can put in your address space / memory anyway. Which is what the strlen() API already assumes. That, plus you'd be a fool to store a huge string in this way anywhere (in or out of memory) in any case.
    - Someone 4y ago
      > SIZE_MAX is at least as large as the largest string that you can put in your address space / memory anyway. Not necessarily. A 64-bit system could give processes an address space that’s significantly larger than half the full 64-bit address space and have an allocator that allows you to allocate a block of more than SIZE_MAX bytes (malloc takes a size_t, but you can use calloc)
masklinn 4y ago
> The trick is the size is hidden before the adress of the buffer.("Learn this one simple trick that will change your life for ever"). This has drawbacks: 1. you can't convert an existing buffer to an sds buffer 2. you can't slice into a buffer, because the metadata is part of the string's buffer (even if it's before the pointer)
lifthrasiir 4y ago
I don't like SDS for multiple reasons. My biggest complaint is that it's a data structure disguised as a single naive pointer, which is actually harder to use correctly. This kind of "masquerading" pointer is conceptually a linear type, as you can't safely change its length in place and any potential change has to return the modified pointer somehow. No other type in C behaves like this, resulting in more confusion and thus more errors. And I have more counterpoints to those self-claimed advantages as well: Counterpoint #1: You can't pass SDS strings to functions that accept `char **` (which is a common way to return a string of unknown length, and often can act as an in-out parameter as well). Counterpoint #2: You rarely access individual "characters" (whatever this means). It is a conscious decision to whether you should iterate over bytes or Unicode scalar values or code points or grapheme clusters, and for this reason it is better to make the decision explicit even though it's C `char` in the surface level. I have no evidence for nor against advantage #3 though.
- kevin_thibedeau 4y ago
  > No other type in C behaves like this, Malloc does this.
  - lifthrasiir 4y ago
    Malloc is not a type. If you meant to say realloc, a good point and it's indeed a bad interface for the exact reason but still it's not a type.
    - Karellen 4y ago
      I believe malloc() was intended, as a number of old-school UNIX implementations of malloc() put the size of the allocation (and possibly other bookkeeping info?) "in front of" the pointer returned, in a similar way to how sds stores the size of its buffer.
  - deleted 4y ago
    [deleted]
schemescape 4y ago
That sounds like the same allocation scheme as used in Microsoft’s BSTR type: https://learn.microsoft.com/en-us/previous-versions/windows/desktop/automat/bstr https://learn.microsoft.com/en-us/previous-versions/windows/...
realgeniushere 4y ago
Makes me think less of antirez that he doesn’t acknowledge that this is the same design as Microsoft’s BSTRs, which predate sds by many many years.
- dixie_land 4y ago
  I also thought of BSTR but in all fairness this idea of prefixing metadata for string types aren't so unique: eg Delphi's string types use a similar scheme: https://docwiki.embarcadero.com/RADStudio/Alexandria/en/Internal_Data_Formats_(Delphi)#Long_String_Types https://docwiki.embarcadero.com/RADStudio/Alexandria/en/Inte... One obvious advantage of such scheme of course is that you can pass them as-is to C APIs
jlokier 4y ago
On point 3, you can achieve the same cache locality, without losing the ability to take slices or append, by having the string object contain a pointer to the string bytes, and allocating the bytes by default immediately after the string object. It is still single allocation, so the allocation is just as fast. The pointer is in the same cache line as the string bytes in all strings except for slices (and any other fancy indirect string types). Even though the code fetches indirectly via that pointer, the CPU will be able to fetch the initial string byte efficiently as soon as it has the pointer.
- estebank 4y ago
  How would this colocation of the string pointer work? Because these would be in the heap, right? Otherwise the pointer would get invalidated as soon as the enclosing function ends and its stack frame gets discarded. So if it is in the heap then you either have a pointer to the colocated pointer (not very useful, if negligible performance impact) or you're copying the colocated pointer (at which point you're back to square one, having a pointer in the stack and the underlying string in the heap). Am I missing something?
  - alcover 4y ago
    Good point. Some SSO (small str optimization) schemes achieve this by pointing back into the struct itself. Gcc String implementation for ex.
WalterBright 4y ago
> The trick is the size is hidden before the adress of the buffer.("Learn this one simple trick that will change your life for ever"). The length-prefix string has a major problem - it cannot be sliced to produce another length-prefix string. It has to be copied. Instead, using a phat pointer (size_t length, char* ptr) works very, very well. We've been using it in D for 20 years. I've proposed it for C, too: https://www.digitalmars.com/articles/C-biggest-mistake.html https://www.digitalmars.com/articles/C-biggest-mistake.html
- torstenvl 4y ago
  > it cannot be sliced to produce another length-prefix string Come again? Of course it can. It can't be done in place, mind you, but that's a pretty bad way to do any string slicing, regardless of implementation, in a manual memory management environment. Do most programmers expect their slices to result in undefined behavior if they release the larger string they were made from? I doubt it.
  - alcover 4y ago
    > Come again? Of course it can. Oh come on.. I'm pretty sure Walter meant taking a view kind of slice. Obviously one can always copy part of a string, but that's not what slice implies I think. > It can't be done in place, mind you, but that's a pretty bad way to do any string slicing, regardless of implementation, in a manual memory management environment. It's not bad. It's the best, most efficient way. O(1)-ish. > Do most programmers expect their slices to result in undefined behavior if they release the larger string they were made from? I doubt it. That's what copy-on-write is for : release of the parent is blocked until no views are left on it. I made a C String lib using CoW. It works well: https://github.com/alcover/buffet https://github.com/alcover/buffet
    - WalterBright 4y ago
      The length-ptr strings are very fast and efficient: 1. don't have to make a copy 2. don't have to scan to find the length 3. don't have to load the string into the cache to find its length As a bonus, they're memory safe.
gorgoiler 4y ago
Whoa. Jamming metadata in the address space before the string pointer is such a clever idea. I don’t know enough about C to know how many awkward bugs this might cause, but I know enough about programming to spot exceptional lateral thinking when I see it. Very neat. I guess the SDS authors might ship a linter to spot all the times you mistakenly use free() instead of sdsfree()? That could make the cleverness more tolerable?
- arcticbull 4y ago
  This is a common approach for things like malloc to use, since you are passing an opaque pointer to arbitrary data into free() which you then expect to quickly do something useful with. It can just walk back the pointer a little to find the header and act on it. It's pretty weird to see it anywhere other than malloc though especially masquerading as a basic type. It's incompatible with other common patterns like returning via (char *) and you can't identify which deallocator you're supposed to give the result to from the type alone.
  - Gibbon1 4y ago
    Random musing of a old firmware guy. In the past I've had issues with wanting to make sure a function isn't being passed a pointer to an object on the stack. Least in embedded land it's trivial to write a function that can tell you if an address points to something on the stack, heap, or is a global.
- deterministic 4y ago
  This is actually a very well known C trick.

kazinator 4y ago

Thus, sds it cannot be used for the use cases that this library allows. This library takes string slices without having to allocate or copy memory; it seems to be for use cases involving breaking down strings in complex ways, where good ergonomics and efficiency of obtaining a null-terminated C string are secondary.

quelsolaar 4y ago

Optimizing text is hard because you seldom up front know how much memory will be needed and allocations are slow. Another way to do it is to use: typedef struct{ size_t allocated; size_t used; char buffer[]; }String; This lets the header and the string be the same allocation. Thats a huge saving. Its also useful to store the allocation and use size separatly so that you can reuse / modify buffers. The used field lets you use memcpy without looking for string termination. You can make it even more complex by adding flags if the string is on the stack or on the heap. That way you can do things like: String buffer = MACRO_TO_CREATE_STRING_BUFFER_ON_STACK(256), *b; b = &buffer; b = do_processing_with_buffer(&b); // allocates on heap a larger buffer if needed string_free(b); // frees buffer if its on heap.

jstimpfle 4y ago
In general it's hard to get more efficient than a simple struct String { const char *buffer; u32 size; }. Your method removes an indirection from the allocated storage, but you'd still need an external pointer to point to that struct in most cases. That, plus retrieving the size now costs an additional dereference. So I wouldn't use your method unless I knew that I'd have to reference the string from multiple locations. The best way to be efficient is often to make assumptions about the data. Most strings don't need any dynamic allocation after having been "built". So it makes a ton of sense to make a string builder API that returns a final string when it's finished. In this way, you save at least the "allocated" member. The advantage of the simpler string representation is that it works for any string (or substring) that is contiguous in memory, and is completely decoupled from allocation concerns. E.g. I can easily #define STRING(string_literal) \ ((String) { string_literal "", sizeof string_literal - 1 }) , to be able to statically declare such strings like this: String my_string = STRING("Foo bar"); If you have many strings that you know are small, then just the normal nul-terminated C string (without any size field) is as storage-efficient as it gets. In practice, I find string handling so easy that I rarely even define this struct String. I just pass around strings to functions as two arguments - pointer + size. It feels so light and data flows so easily between APIs, I love it.

mh7 4y ago

Re #3: A big downside is that you you can't easily take ownership of an existing buffer and treat it as this string type. string s; char some_buf[]; string_take(&s, some_buf, some_capacity); Also you would of course never dynamically allocate string structs, just the data member if needed.

_448 4y ago

> The trick is the size is hidden before the adress of the buffer. That is how strings use to be stored before C made the choice of using null-terminator. Pascal stored the string size before the string data. The advantage of relying on a terminator symbol is that the string size can be any length where as storing the size at the start forces the string to not exceed certain size.

anonymoushn 4y ago
In execution environments with 64-bit pointers you may have trouble loading a string of more than 16 exabytes into RAM anyway
mh7 4y ago
strlen() returns a size_t so you're already constrained to a maximum length of SIZE_MAX.
- jcelerier 4y ago
  If you use a different data structure you would maybe use a different API for accessing it too
- jstimpfle 4y ago
  This is hilarious. SIZE_MAX is at least as large as the largest string that you can put in your address space / memory anyway. Which is what the strlen() API already assumes. That, plus you'd be a fool to store a huge string in this way anywhere (in or out of memory) in any case.
  - Someone 4y ago
    > SIZE_MAX is at least as large as the largest string that you can put in your address space / memory anyway. Not necessarily. A 64-bit system could give processes an address space that’s significantly larger than half the full 64-bit address space and have an allocator that allows you to allocate a block of more than SIZE_MAX bytes (malloc takes a size_t, but you can use calloc)

masklinn 4y ago

> The trick is the size is hidden before the adress of the buffer.("Learn this one simple trick that will change your life for ever"). This has drawbacks: 1. you can't convert an existing buffer to an sds buffer 2. you can't slice into a buffer, because the metadata is part of the string's buffer (even if it's before the pointer)

lifthrasiir 4y ago

I don't like SDS for multiple reasons. My biggest complaint is that it's a data structure disguised as a single naive pointer, which is actually harder to use correctly. This kind of "masquerading" pointer is conceptually a linear type, as you can't safely change its length in place and any potential change has to return the modified pointer somehow. No other type in C behaves like this, resulting in more confusion and thus more errors. And I have more counterpoints to those self-claimed advantages as well: Counterpoint #1: You can't pass SDS strings to functions that accept `char **` (which is a common way to return a string of unknown length, and often can act as an in-out parameter as well). Counterpoint #2: You rarely access individual "characters" (whatever this means). It is a conscious decision to whether you should iterate over bytes or Unicode scalar values or code points or grapheme clusters, and for this reason it is better to make the decision explicit even though it's C `char` in the surface level. I have no evidence for nor against advantage #3 though.

kevin_thibedeau 4y ago
> No other type in C behaves like this, Malloc does this.
- lifthrasiir 4y ago
  Malloc is not a type. If you meant to say realloc, a good point and it's indeed a bad interface for the exact reason but still it's not a type.
  - Karellen 4y ago
    I believe malloc() was intended, as a number of old-school UNIX implementations of malloc() put the size of the allocation (and possibly other bookkeeping info?) "in front of" the pointer returned, in a similar way to how sds stores the size of its buffer.
- deleted 4y ago
  [deleted]

schemescape 4y ago

That sounds like the same allocation scheme as used in Microsoft’s BSTR type: https://learn.microsoft.com/en-us/previous-versions/windows/desktop/automat/bstr https://learn.microsoft.com/en-us/previous-versions/windows/...

realgeniushere 4y ago

Makes me think less of antirez that he doesn’t acknowledge that this is the same design as Microsoft’s BSTRs, which predate sds by many many years.

dixie_land 4y ago
I also thought of BSTR but in all fairness this idea of prefixing metadata for string types aren't so unique: eg Delphi's string types use a similar scheme: https://docwiki.embarcadero.com/RADStudio/Alexandria/en/Internal_Data_Formats_(Delphi)#Long_String_Types https://docwiki.embarcadero.com/RADStudio/Alexandria/en/Inte... One obvious advantage of such scheme of course is that you can pass them as-is to C APIs

jlokier 4y ago

On point 3, you can achieve the same cache locality, without losing the ability to take slices or append, by having the string object contain a pointer to the string bytes, and allocating the bytes by default immediately after the string object. It is still single allocation, so the allocation is just as fast. The pointer is in the same cache line as the string bytes in all strings except for slices (and any other fancy indirect string types). Even though the code fetches indirectly via that pointer, the CPU will be able to fetch the initial string byte efficiently as soon as it has the pointer.

estebank 4y ago
How would this colocation of the string pointer work? Because these would be in the heap, right? Otherwise the pointer would get invalidated as soon as the enclosing function ends and its stack frame gets discarded. So if it is in the heap then you either have a pointer to the colocated pointer (not very useful, if negligible performance impact) or you're copying the colocated pointer (at which point you're back to square one, having a pointer in the stack and the underlying string in the heap). Am I missing something?
- alcover 4y ago
  Good point. Some SSO (small str optimization) schemes achieve this by pointing back into the struct itself. Gcc String implementation for ex.

WalterBright 4y ago

> The trick is the size is hidden before the adress of the buffer.("Learn this one simple trick that will change your life for ever"). The length-prefix string has a major problem - it cannot be sliced to produce another length-prefix string. It has to be copied. Instead, using a phat pointer (size_t length, char* ptr) works very, very well. We've been using it in D for 20 years. I've proposed it for C, too: https://www.digitalmars.com/articles/C-biggest-mistake.html https://www.digitalmars.com/articles/C-biggest-mistake.html

torstenvl 4y ago
> it cannot be sliced to produce another length-prefix string Come again? Of course it can. It can't be done in place, mind you, but that's a pretty bad way to do any string slicing, regardless of implementation, in a manual memory management environment. Do most programmers expect their slices to result in undefined behavior if they release the larger string they were made from? I doubt it.
- alcover 4y ago
  > Come again? Of course it can. Oh come on.. I'm pretty sure Walter meant taking a view kind of slice. Obviously one can always copy part of a string, but that's not what slice implies I think. > It can't be done in place, mind you, but that's a pretty bad way to do any string slicing, regardless of implementation, in a manual memory management environment. It's not bad. It's the best, most efficient way. O(1)-ish. > Do most programmers expect their slices to result in undefined behavior if they release the larger string they were made from? I doubt it. That's what copy-on-write is for : release of the parent is blocked until no views are left on it. I made a C String lib using CoW. It works well: https://github.com/alcover/buffet https://github.com/alcover/buffet
  - WalterBright 4y ago
    The length-ptr strings are very fast and efficient: 1. don't have to make a copy 2. don't have to scan to find the length 3. don't have to load the string into the cache to find its length As a bonus, they're memory safe.

gorgoiler 4y ago

Whoa. Jamming metadata in the address space before the string pointer is such a clever idea. I don’t know enough about C to know how many awkward bugs this might cause, but I know enough about programming to spot exceptional lateral thinking when I see it. Very neat. I guess the SDS authors might ship a linter to spot all the times you mistakenly use free() instead of sdsfree()? That could make the cleverness more tolerable?

arcticbull 4y ago
This is a common approach for things like malloc to use, since you are passing an opaque pointer to arbitrary data into free() which you then expect to quickly do something useful with. It can just walk back the pointer a little to find the header and act on it. It's pretty weird to see it anywhere other than malloc though especially masquerading as a basic type. It's incompatible with other common patterns like returning via (char *) and you can't identify which deallocator you're supposed to give the result to from the type alone.
- Gibbon1 4y ago
  Random musing of a old firmware guy. In the past I've had issues with wanting to make sure a function isn't being passed a pointer to an object on the stack. Least in embedded land it's trivial to write a function that can tell you if an address points to something on the stack, heap, or is a global.
deterministic 4y ago
This is actually a very well known C trick.