7 ms·

Hi, author here. May make sense to make SDS in perspective given a few comments I'm reading here. 1. Yep, more than "strings" SDS may be consider a library for

Hi, author here. May make sense to make SDS in perspective given a few comments I'm reading here. 1. Yep, more than "strings" SDS may be consider a library for dynamic buffers, especially from people coming from C++ or higher level languages. However I think that for C, it makes sense to provide a very low level thing like that. 2. In practice, if you see how SDS is used (extensively) inside Redis, it normally models things where you would do realloc magics, pointer math, and so forth: from client output buffers, to actual strings to accumulate error messages, to the Redis String object itself. 3. Probably an UTF-32 layer could be implemented on top of that, but I would think the two modules completely separated from the POV of the implementation. Like having an additional utf32.c file that provides additional interfaces on top of SDS. 4. The peculiar approach used by SDS header-before-pointer creates some problem with Valgrind and similar tools, however Valgrind will just report "possibly lost", that are messages mostly safe to ignore. However the advantage of using SDS strings directly with C function libraries is very handy. SDS strings are not perfect and tend to be extremely optimized for Redis, if you look at the API, they allow to do things that are very low level, like pre-allocating the internal buffers to improve performances when you know you are going to read a big chunk of data from a socket or alike. However while imperfect and very tuned, these kind of libraries show how much you can easily improve C, with little work, and how many unsafe things in C are about lack of abstractions. The value of SDS is "less is more" in the simple API they provide that pretends that SDSs are just plain-strings++. You can see this in a few features: plain C pointers interface, and the policy of always terminate the string. They need more love anyway, and to be less specialized for Redis, adding more useful APIs. Maybe at some point I'll find the time.

CJefferson 7y ago
Whenever I've used functionality like this before, the inevitable problem is the string ends up with nulls in it, meaning C and the library disagree on the length of the string, which inevitably causes problems and corruption. How do you handle this?
- jdsully 7y ago
  You use sdslen() instead of strlen(). Ditto for everything else. Failure to do so results in subtle bugs.
  - CJefferson 7y ago
    Then (in my opinion) the library shouldn't advertise itself as compatible with Null terminated C strings, as users will assume that means they can use strlen (or more likely, other functions which use strlen themselves). In a similar system I work on, we have a list of functions (like strlen, Strcat), where we carefully vet every occurrence in the code base. It's annoying but the only way to stop subtle bugs we've found.
    - jdsully 7y ago
      Redis doesn’t really have this problem because its mostly developed by Antirez.
  - stouset 7y ago
    Then why bother making these strings superficially compatible with C strings? Just printf or am I missing something?
    - jdsully 7y ago
      The same reason std::string has the c_str() method. It’s convenient.
poiuyt098 7y ago
> show how much you can easily improve C, with little work, and how many unsafe things in C are about lack of abstractions C has always badly needed built-in strings (and arrays with size info, generally). To save a byte, C designers committed The Most Expensive One-byte Mistake https://queue.acm.org/detail.cfm?id=2010365 https://queue.acm.org/detail.cfm?id=2010365
- phs318u 7y ago
  Thanks for the link. Great analysis of a real sliding-doors moment.
- m463 7y ago
  A shortcoming (or outright failure) of C is the lack of an extensive "batteries included" library. Maybe not C + Knuth, but some way of portably advancing the language over time.
  - ndesaulniers 7y ago
    Why? So we could be stuck with horrible interfaces forever (most of string.h comes to mind)? No thanks.
    - m463 7y ago
      don't you think it could evolve?
  - hsaliak 7y ago
    glib
    - m463 7y ago
      That would be a start, but my though is more closely related to the C standard, not an add-on like boost.
microcolonel 7y ago
> Probably an UTF-32 layer could be implemented on top of that UTF-32 is, in all but extreme niche cases, a supremely wasteful and inefficient way to store and process strings, even in light of the cost of variable-length codepoints. The longest UTF-8 sequence is now four bytes anyway, so UTF-8 is never ever less compact than UTF-32. The only conceivable practical use of UTF-32 is a case where the upper 11 bits are used to tag characters with metadata, but in that case you'll have to mask those to display them anyway. In practice, if your application must be aware of codepoints, it most likely should be aware of extended grapheme clusters as well, and those have an arbitrary number of codepoints in them. UTF-16 is closer to being useful in some locales, but the marginal benefit (one byte less per BMP CJK codepoint) is, in my view, outweighed by the incompatibility with ASCII. Even a small number of ASCII strings in a given transmission will wipe out any advantage UTF-16 could have in CJK locales, and most transmissions these days have enough ASCII to do so. For example, today's Japanese Wikipedia main page is 102,620 bytes in UTF-8, and 182,480 bytes in UTF-16, despite most of the visible graphemes being CJK characters (which require three bytes in UTF-8). The Korean Wikipedia main page has larger text, and less of it, so the difference is even more stark (81,072 bytes in UTF-8, and 146,630 bytes in UTF-16). Even after aggressive gzip compression (with zopfli), text-heavy UTF-16 Japanese and Korean HTML documents are about 10% larger than their UTF-8 equivalent; and this is before you've transmitted any CSS or JavaScript.
- nimish 7y ago
  Utf-32 allows for constant time indexing of a codepoint which may be important. Utf-16 is the worst of all worlds with its bloat and surrogate pair nonsense
- Const-me 7y ago
  With UTF16, simple string handling code runs faster. When you're iterating over characters, with UTF8 branch prediction mispredicts all the time. Characters in UTF-8 have random length from 1 to 3 bytes. This might be good for bandwidth, but the tradeoff is slower processing, all modern CPUs have branch prediction hardware, and deep pipelines. With UTF-16 CPUs predict these branches all the time, surrogate pairs are extremely rare, the rest of languages are 2 bytes/character. While it's technically possible to optimize UTF-8 with clever programming like manual SIMD, that code gonna be much more complex than just a while or for loop, i.e. more expensive to develop and harder to support. I think that's the reason why all platforms with rich GUI ecosystem (Windows, OSX, iOS, Android, JavaScript) use UTF-16 almost exclusively.

CJefferson 7y ago

Whenever I've used functionality like this before, the inevitable problem is the string ends up with nulls in it, meaning C and the library disagree on the length of the string, which inevitably causes problems and corruption. How do you handle this?

jdsully 7y ago
You use sdslen() instead of strlen(). Ditto for everything else. Failure to do so results in subtle bugs.
- CJefferson 7y ago
  Then (in my opinion) the library shouldn't advertise itself as compatible with Null terminated C strings, as users will assume that means they can use strlen (or more likely, other functions which use strlen themselves). In a similar system I work on, we have a list of functions (like strlen, Strcat), where we carefully vet every occurrence in the code base. It's annoying but the only way to stop subtle bugs we've found.
  - jdsully 7y ago
    Redis doesn’t really have this problem because its mostly developed by Antirez.
- stouset 7y ago
  Then why bother making these strings superficially compatible with C strings? Just printf or am I missing something?
  - jdsully 7y ago
    The same reason std::string has the c_str() method. It’s convenient.

poiuyt098 7y ago

> show how much you can easily improve C, with little work, and how many unsafe things in C are about lack of abstractions C has always badly needed built-in strings (and arrays with size info, generally). To save a byte, C designers committed The Most Expensive One-byte Mistake https://queue.acm.org/detail.cfm?id=2010365 https://queue.acm.org/detail.cfm?id=2010365

phs318u 7y ago
Thanks for the link. Great analysis of a real sliding-doors moment.
m463 7y ago
A shortcoming (or outright failure) of C is the lack of an extensive "batteries included" library. Maybe not C + Knuth, but some way of portably advancing the language over time.
- ndesaulniers 7y ago
  Why? So we could be stuck with horrible interfaces forever (most of string.h comes to mind)? No thanks.
  - m463 7y ago
    don't you think it could evolve?
- hsaliak 7y ago
  glib
  - m463 7y ago
    That would be a start, but my though is more closely related to the C standard, not an add-on like boost.

microcolonel 7y ago

> Probably an UTF-32 layer could be implemented on top of that UTF-32 is, in all but extreme niche cases, a supremely wasteful and inefficient way to store and process strings, even in light of the cost of variable-length codepoints. The longest UTF-8 sequence is now four bytes anyway, so UTF-8 is never ever less compact than UTF-32. The only conceivable practical use of UTF-32 is a case where the upper 11 bits are used to tag characters with metadata, but in that case you'll have to mask those to display them anyway. In practice, if your application must be aware of codepoints, it most likely should be aware of extended grapheme clusters as well, and those have an arbitrary number of codepoints in them. UTF-16 is closer to being useful in some locales, but the marginal benefit (one byte less per BMP CJK codepoint) is, in my view, outweighed by the incompatibility with ASCII. Even a small number of ASCII strings in a given transmission will wipe out any advantage UTF-16 could have in CJK locales, and most transmissions these days have enough ASCII to do so. For example, today's Japanese Wikipedia main page is 102,620 bytes in UTF-8, and 182,480 bytes in UTF-16, despite most of the visible graphemes being CJK characters (which require three bytes in UTF-8). The Korean Wikipedia main page has larger text, and less of it, so the difference is even more stark (81,072 bytes in UTF-8, and 146,630 bytes in UTF-16). Even after aggressive gzip compression (with zopfli), text-heavy UTF-16 Japanese and Korean HTML documents are about 10% larger than their UTF-8 equivalent; and this is before you've transmitted any CSS or JavaScript.

nimish 7y ago
Utf-32 allows for constant time indexing of a codepoint which may be important. Utf-16 is the worst of all worlds with its bloat and surrogate pair nonsense
Const-me 7y ago
With UTF16, simple string handling code runs faster. When you're iterating over characters, with UTF8 branch prediction mispredicts all the time. Characters in UTF-8 have random length from 1 to 3 bytes. This might be good for bandwidth, but the tradeoff is slower processing, all modern CPUs have branch prediction hardware, and deep pipelines. With UTF-16 CPUs predict these branches all the time, surrogate pairs are extremely rare, the rest of languages are 2 bytes/character. While it's technically possible to optimize UTF-8 with clever programming like manual SIMD, that code gonna be much more complex than just a while or for loop, i.e. more expensive to develop and harder to support. I think that's the reason why all platforms with rich GUI ecosystem (Windows, OSX, iOS, Android, JavaScript) use UTF-16 almost exclusively.