Efficient string copying and concatenation in C

http://www.etalabs.net/compare_libcs.html

For the .a size:

musl: 426k

uClibc: 500k

dietlibc: 120k

If you statically link to these, your final binary will only pull what is actually needed and be smaller than this.

Adding better string functions or CPU-specific optims is nothing compared to that.

musl is mostly so small because it only does the C locale and basic unicode towlower. Nothing like the monstruous glibc unicode tables or internationalized error messages.

People have a range of technical and aesthetic reasons for hating bloat and C attracts a lot of them.

Off the top of my head:

- Smaller memory footprints

- Easier reimplementation

- Lower attack surface

- Less room for breaking changes

- Less baggage for when we inevitably wish we could deprecate things

A lot of embedded development still have very tight requirements. We're still talking about things discussed in tens or if generous, hundreds of kilobytes.

As a more mainstream example you might have heard of, the Arduino, I think the baseline Arduino has around 32KB available.

Also, in the embedded space, the compilers used are notorious for not having a complete standard library implementation. Lots of things are missing. Thus, developers who care about porting their code to different chips, are cautious about limiting what standard library functions they depend on.

Again, as a more mainstream example you might have heard of, look at Lua, which is implemented in 100% ANSI C. Because they care about Lua truly being portable to everywhere, they try to constrain their dependence on the standard library, and they supply some #ifdefs in luaconf.h to implement or workaround some standard library functions they know to be often missing.

And as a more mainstream example of an incomplete C standard library, look at Android. Bionic is the name of their C standard library. It is missing a lot of things. (And you have to use one of those #ifdefs in luaconf.h to compile Lua successfully on Android to workaround Bionic.)

C++ has a large standard library. This ends up being one of C++'s biggest downfalls: the various libraries don't play nicely with each other, have many different ways of doing the same or similar things, each have complex gotchas--and it's impossible to know them all, so you never really know C++. It's full of dark corners, and the result is bugs, and difficult debugging, and teams that try to enforce only using subsets of the language (and inevitably fail a little). This problem is only getting worse over time. The reason C++'s new features haven't just been backported back into the C standard is that people saw this coming and didn't want it happening. C is already a complex language, but it's still simple enough that you can actually reasonably read the entire C standard library (I have; QED).

A large standard library doesn't have to be this way. Python has a large standard library--this is the "batteries included" of Python. The reason Python can get away with this is that they can deprecate their mistakes. And they are: quite a few modules in the standard library will disappear with the Python 2 sunset. But this is not without downsides--everyone who has been working on a major Python project in the past few years has felt the pain at some point. And C is not Python: it's the backbone of a lot of other applications, so breaking changes are far more costly for C than for Python. C is "once supported, always supported", and for very good reason, so we can't afford to introduce mistakes to the standard.

So, if you don't want the problems of all the cruft in C++'s standard library, and you don't want the deprecations of Python's standard library, your only remaining choice, by process of elimination, is to have a very slim standard library, and make VERY conservative choices about what to add to it.

I think that we should add a new string library to C when strings are a solved problem. But contrary to what people are saying, strings aren't a solved problem. We shouldn't add a string library that doesn't solve internationalization, for example. And in fact, with that problem, the fox is in charge of the henhouse, making the problem worse: we've got people in the Unicode team adding fsking emoji to the standard. Unfortunately, I think we're going to have to wait until Unicode collapses under its own bad decisions and is replaced by a better standard, and that standard becomes mature, before committing to that proven solution. Otherwise we end up with ICU-related crap into the "once supported, always supported" C standard library.

While FizzBuzz has become notorious for weeding out total incompetence [1], there are some variations of the problem that are unexpectedly nuanced.

1. https://thedailywtf.com/articles/The-Fizz-Buzz-from-Outer-Sp...

It's why call it "stupid", "insidious", but "somewhat relevant", as the parent comment proposes a better stdlib in C to handle strings.

    struct string {
        union {
            struct {
                char *ptr;
                size_t capacity;
            };
            char str[16];
        } data;
        size_t length;
    };

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
    };

    ((struct string_header *)p)[-1]

Something anything is better than the total shit design we've been living with.

sys/queue.h provides four different linked list implementations: standard singly-linked lists, standard doubly-linked lists, a singly-linked list with a tail pointer (for fast tail insertion) and a doubly-linked list without a head pointer. All come complete with

sys/tree.h provides two types of balanced search trees: splay trees and red-black trees. Both provide ordered dictionaries

Both libraries make quite extensive use of macros, but they are quite reasonably implemented and documented via man-page. I've successfully used them a few times. Shame that, like other nice BSD innovations (e.g. strlcpy/strlcat) they haven't made it into other libcs.

Then compilers wanting to support the "with-batteries" superset standard could just allow their flag that looks like "-std=c90" to be extended like "-std=c90+batteries".

I have seen much, much better designs, that take into account that these functions are rarely called in isolation. In those, calls cooperate with previous and subsequent calls to share the burdens of maintaining correctness and safety.

Something like:

   if (str1 && str2) {
      size_t len1 = strlen(str1);
      size_t len2 = strlen(str2);
      size_t buf_len = len1 + len2 + 1;
      if (len1 < buf_len && len2 < buf_len) {
         char *buf = malloc(buf_len);
         if (buf) {
            memcpy(buf, str1, len1);
            memcpy(buf + len1, str2, buf_len - len1 - 1);
            buf[buf_len - 1] = '\0';
         }
      }
   }

As you suggest, you'll probably run out of memory before you'll overflow, so in reality, you want to check len1 and len2 are some sane value, but of course, library functions don't usually have that luxury. Take a hint from git:

    #define unsigned_add_overflows(a, b) \
        ((b) > maximum_unsigned_value_of_type(a) - (a))

    if (unsigned_add_overflows(extra, 1) ||
        unsigned_add_overflows(sb->len, extra + 1))
          die("you want to use way too much memory");

https://github.com/git/git/blob/9d418600f4d10dcbbfb0b5fdbc71...

> making such assumptions can be a bad idea

It's always a bad idea, especially in an unsafe language. Never trust user input.

No, the stack size is implementation-defined anyway. Instead, you have a classic off-by-one error because you didn't reserve any space for the final null terminator.

Correctly used memccpy would protect against an issue like this, although the destination string would not be correctly terminated, as it's not a safe string function. Also, if your memccpy version had the correct arguments inside the loop, you wouldn't have needed the extra call before the loop to hide the issue, as the memccpy call would have been functionally identical to strcpy except for the last pass of the loop.

>What do you mean exactly? I did observe the results of the buffer. See the printf, or are you not referring to that?

At least in the link you provided, all the printf's that would observe the contents of buf after the loop are commented out. No observable change happens in the execution of the program even if your compiler decides to just remove any calls to strcpy or memccpy.

--

That being said, strcpy is quite efficient at what you're benchmarking; that is, "multiplying" short strings. The task doesn't highlight its shortcomings. (strcpy wouldn't be too bad even if the strings were longer, although memcpy might be slightly faster.)

But consider the following silly example (not checked for errors) that does highlight the issue:

  char *next_insert;
  size_t remaining_size;

  void append_memccpy(const char *str)
  {
    char *tmp = memccpy(next_insert, str, '\0', remaining_size); // single pass over str
    if (tmp) {
      --tmp; // move pointer to terminator from one past it
      remaining_size -= tmp - next_insert;
      next_insert = tmp;
    } else { // insufficient size remaining
      str += remaining_size; // first remaining_size bytes are already copied
      allocate_more();
      append_memccpy(str);
    }
  }

  void append_strcpy(const char *str)
  {
    size_t len = strlen(str); // first pass over str
    if (len + 1 < remaining_size) {
      strcpy(next_insert, str); // second pass over str
      remaining_size -= len;
      next_insert += len;
    } else {
      allocate_more();
      append_strcpy(str);
    }
  }

There are sensible answers. But they are weird.