The Sad State of C Strings | Hacker News Reader

The Sad State of C Strings

symas.com

41 pointshyc_symas42 comments

http://webcache.googleusercontent.com/search?q=cache:PptRk2k...

This topic is a triviality of C programming. You run into performance (or usability) issues with standard strings - you roll out your own. It takes... what?... 20 minutes? OK, maybe an hour. Would it help to have an alternative standardized? Perhaps. Is it critical to have it? Hell, no.

I presume the majority of the point of standardizing is in controlling what implementation third-party libraries use. It's not like libraries are grabbing opaque String* handles from some String.new-alike in libc, where all the strings in your final linked program could be replaced with a better implementation of the same ADT just by linking in a better String.new.

The C standard says that "strings" are examinable buffers of bytes you can do arithmetic to and stream until NUL—and thus, every single library that uses C strings ends up baking in a bunch of pointer arithmetic and NUL-checks on buffers of bytes.

It doesn't matter how optimized your own code's string implementation is if 99% of your time is spent in, for example, OpenSSL's string implementation.

In what other context anywhere in programming is it considered a good idea for everyone to hand-roll their own, separate, subtly-incompatible, surely-bug-ridden implementation of functionality that everyone needs? Gahhh.

Exactly. We can't kill strcpy/strcat, for backward compatibility reasons. But the standard ought to have a spec that is actually useful and not ridiculously sub-optimal. strlcpy() doesn't fit the bill either.

I'm late to this discussion, but did you possibly miss stpcpy() and its variants? Or is something about them that doesn't meet your needs?

  STPCPY(3)      Linux Programmer's Manual                                      

  NAME
       stpcpy - copy a string returning a pointer to its end

  SYNOPSIS
       #include <string.h>

       char *stpcpy(char *dest, const char *src);

   Feature Test Macro Requirements for glibc (see feature_test_macros(7)):

       stpcpy():
           Since glibc 2.10:
               _XOPEN_SOURCE >= 700 || _POSIX_C_SOURCE >= 200809L
           Before glibc 2.10:
               _GNU_SOURCE

  DESCRIPTION
       The  stpcpy()  function  copies the string pointed to
       by src (including the terminating null byte ('\0')) to the
       array pointed to by dest.  The strings may not overlap,
       and the destination string dest must be large enough  to
       receive the copy.

  RETURN VALUE
       stpcpy()  returns  a  pointer  to the end of the string
       dest (that is, the address of the terminating null byte)
       rather than the beginning.

  CONFORMING TO
       This function was added to POSIX.1-2008.  Before that, it
       was not part of the C or POSIX.1 standards,  nor  customary
       on UNIX systems, but was not a GNU invention either. Perhaps 
       it came from MS-DOS.  It is also present on the BSDs.

  BUGS
       This function may overrun the buffer dest.

  EXAMPLE
       For example, this program uses stpcpy() to concatenate foo 
       and bar to produce foobar, which it then prints.

           #define _GNU_SOURCE
           #include <string.h>
           #include <stdio.h>

           int
           main(void)
           {
               char buffer[20];
               char *to = buffer;

               to = stpcpy(to, "foo");
               to = stpcpy(to, "bar");
               printf("%s\n", buffer);
           }

  SEE ALSO
       memccpy(3), stpncpy(3), wcpcpy(3)

Added to POSIX is good, but not sufficient. E.g., there is no reason for Windows to implement a function merely because it's in the POSIX spec. It needs to be in the C spec to actually be viable.

stpncpy is equivalent to strncpy - it NUL-pads dest if the src is shorter than N. Frankly I have never found a use for this behavior. The desired behavior is to simply copy src without additional padding. That is what my proposed strecopy() does, and that's what would be required of a replacement for strlcpy().

Eh...

  // This code is licensed under CC0.
  // A copy of the license can be obtained at https://creativecommons.org/publicdomain/zero/1.0/
  // May you forever catenate in peace.
  #define strcatm(...) strcat_multi(__VA_ARGS__, NULL);
  char* strcat_multi(char *dest, ...) {
    va_list srcs;
    char *dest_end;
    const char *src;
    size_t src_sz;
    va_start(srcs, dest);
    for (dest_end = dest; *dest_end; dest_end++);
    for (src = va_arg(srcs, const char *); src; src = va_arg(srcs, const char *)) {
      src_sz = strlen(src);
      memmove(dest_end, src, src_sz);
      dest_end += src_sz;
      *dest_end = '\0';
    }
    va_end(srcs);
    return dest_end;
  }

There. Now go and catenate, children.

As a bonus, this works with e.g.

  char buf[256]; buf[0] = 'x'; buf[1] = '\0';
  strcatm(buf, buf, buf, buf);

producing a string of 16 'x's

  strcatm(..., NULL);

and it's 8 x/s, not 16. Also fix , to ; in the second for loop.

strcatm is the convenience macro that adds a last NULL arg. And it's 16, because it doubles each time. Already fixed.

strcatm - aye, missed that, but I must insist on 8.

Right, 8. I miscounted it as 4 loops :)

I'll concatenate the hell out of the buffer and whatever comes after it.

  // This code is licensed under CC0.
  // A copy of the license can be obtained at https://creativecommons.org/publicdomain/zero/1.0/
  // May you forever catenate in peace.
  #define strncatm(dest, sz, ...) strncat_multi((dest), (sz), __VA_ARGS__, NULL);
  char* strncat_multi(char *dest, size_t dest_sz, ...) {
    va_list srcs;
    char *dest_end;
    const char *src;
    size_t src_sz;
    size_t dest_off;
    size_t copy_sz;
    va_start(srcs, dest_sz);
    for (dest_end = dest, dest_off = 0; *dest_end && dest_off < dest_sz; dest_end++, dest_sz++);
    for (src = va_arg(srcs, const char *); src && dest_off < dest_sz; src = va_arg(srcs, const char *)) {
      src_sz = strlen(src);
      copy_sz = src_sz < (dest_sz - dest_off) ? src_sz : (dest_sz - dest_off);
      memmove(dest_end, src, copy_sz);
      dest_end += copy_sz;
      dest_off += copy_sz;
      if (dest_off < dest_sz)
      {
        *dest_end = '\0';
      }
    }
    va_end(srcs);
    return dest_end;
  }

Good, but I'd do one modification -- always write a null byte at the end. Otherwise you end up with a non-null-terminated string and that's bad.

So,

  copy_sz = src_sz < (dest_sz - dest_off) ? src_sz : (dest_sz - dest_off - 1);
  ...
  *dest_end = '\0';

But remember to rename the function, since all function names starting with "str" are reserved in C.

To keep with the spirit of the article, calling strlen() just to allow convenient use of memmove() seems a bit counter-intuitive, I'd roll the two together into a copying loop instead.

And then you do infinite copying if you're catenating a string with itself.

Reading this made me remember Zed Shaw's rant on C-strings and his recommendation to use a "Safer" string library:

http://c.learncodethehardway.org/book/ex36.html

I'm not an experienced enough programmer to be able to evaluate how much "safer" the bstrlib library actually is. I'm sure the various HN Engineers can chime in with their insights.

I am pretty convinced by the argument of this article. but, this looks to good to be true. Are there some drawbacks I can not see ? Why nobody has thought about this simple api ?

Of all the problems with C strings, the one mentioned in the article (inefficient strcat() function) is really small.

I think unicode support would be much more important, but not everyone agrees (for example, on embedded devices unicode support can be dead-weight). And adding to C without consensus leads to lousy decisions.

I have already noticed some performance issue with strncpy (and big destination buffers) vs strlcpy. The two functions introduced in the article have the good complexity and seem to be more handy than usual api.

If you need to copy big strings, memcpy is worth checking out, too.

IMO it is usefull to have the "return result paradigm". You can do things like: bar(foo(x, y)) and chain function results. Notice how this applies to strcpy:

  char *heap_ptr, *stack_ptr; ...    fn_needs_heap_ptr(strcpy(heap_ptr, stack_ptr));

Another example (dma address space != buf a.s):

  char *dma_ptr, *buf; ... fn_needs_dma_ptr(strcpy(dma_ptr, buf)) ...

IOW, foo(strcpy(dst, src)) is VERY different than strcpy(dst, src); foo(src);

Because the performance hit of extraneous strlen() calls is generally negligible. This in turn is because strlen() maps to "repne scasb" assembly instructions, which run in 4 cycles per byte + 8 cycles of fixed cost. That's cheap as dirt.

You will indeed have a problem if you strcat() excessively, but then it will be a marginal case, so you will optimize for it in your own code rather than dragging it into the standard.

> which run in 4 cycles per byte + 8 cycles of fixed cost. That's cheap as dirt.

Cheap? 12 precious clock cycles is enough for up to 384 floating point operations (FMA).

Not sure how fast or slow rep sca/mov is these days. Regardless, strlen that is not scanning at least 4 bytes per clock is hopelessly slow. I think you can do at least about ~16 bytes per clock.

Anyways, the problem with strlen is unnecessary extra (potentially mispredicted) branches and memory accesses.

I have seen enough cases where strlen has dominated cost in the profile. Of course this depends entirely what you are doing, there are plenty of workloads where strlen just doesn't occur.

Isn't a modern strlen optimized into vector operations if possible anyway?

Yes.

Though you still pay for the memory/branch prediction stalls.

so...are we trying to micro-optimize the standard library?

There will be bottlenecks narrower (is that the right term?) than string operation in any project not dealing exclusively with strings. In the latter case, rolling your own string utilities may make sense

Of course you shouldn't optimize unless it's the biggest bottleneck and more performance (or battery life) is desired.

C string operations might have been elegant 40 years ago, but nowadays they're like rerouting a 747 to check if office lights are on.

Strlen is doing a lot of work for little benefit. It does slow and power hungry memory accesses. Because it's scanning for terminating 0x00 byte, it needs to contain a branch -- and loop terminating branch must be a costly mis-predicted one.

C printf and friends are even more insane. It scans "bytecode" instructions from a string and does dynamic formatting. You can do format options like this:

  printf("% 0#*.*f\n", 15, 5, 1.234);

Or say print five chars of an unterminated string, left padded to total length of 10:

  printf("%10.5s\n", unterminated_str);

It won't (at least it shouldn't) crash even if 6th character is on an unreadable memory page.

I don't think they are insane. It is safe if you follow some rules. Flag -Wformat=2 catches every mistake at compile time. (It wont guard against overflow of course, but this is C)

The last example is explicitly defined in the Standard.

The performance cost is crazy when format string is parsed at runtime.

Implementing all that subtle functionality correctly takes up a lot of CPU time.

According to my quick test, on Visual Studio 2012, even simplest sprintf with just one parameter seemed to take about 1 microsecond to execute.

Of course clang and gcc seem to sometimes compile whole format parser away. At least...

  printf ("Hello World!\n");

... is optimized into a simple "puts("Hello World!");".

Of course iostream << operator runtime performance is also pretty horrible. Each << invocation seem to call streambuf::sputn (or sputc) separately. On VS2012, simplest stringstream test...

  ss << "value: " << intVal << endl;

... outputting one variable into it and turning the result into a std::string took about 3 microseconds. (Although it was a very quick test, a number of things might be suboptimal in the test code.)

All string manipulation code in C deals with trailing NULL bytes, so if you try doing something different, you may get issues when you try to link to other code. It's not a great system, but good C programmers should know the shortfalls.

As an example of the alternate approach, the Rust language uses (ptr, size) to represent all arrays (called slices) and strings internally. This seems like a much better method, allowing you to reference substrings without allocating a buffer, and perform out-of-bounds checking at runtime.

That's nothing, you should see the sad sad state of strings in assembly... Oh you're supposed to manage them yourself? Huh, what a concept.

Seriously though, a C programmer should know the downsides of C strings, and act accordingly, i.e. use a library if necessary.

"should" - yes. "does" - apparently not. "use a library if necessary" - that's really the point of this - the standard library's offerings suck. What is the point of a standard that is actually unusable?

strlcpy() also sucks. The solutions I proposed solve both the overflow protection aspect that strlcpy aims to solve and solves the inefficiency problems of strcpy/strcat/memcpy.

Somehow, I was expecting a piece about musical instrument tuning.

Heh, maybe next time. I could tell ya about the viola C string I tried on my baritone fiddle - it really wasn't very usable.

The premise is wrong: "constructing a larger string out of multiple smaller strings is a pretty common programming task"

No, it's not.

"strcat(strcat(strcat(strcpy(buf, "This "),"is "),"a long "),"string.");"

Just checked 20 years of C/C++ repositories ... not a single strcat. Actually I can't remember ever using c-strings for more than args parsing or debug logging.

I just did a quick GitHub search, strcat seems to have been used about 5 million times across all repositories, as compared to (e.g.) memcpy at about 80 million. Clearly somebody is using it. I would hate to try to get a measure of how often it's used in other languages; it's not the sort of thing anyone would think twice about. I believe you have made an inductive error based on your own sample and that the original premise is entirely correct.

The missing length field was a selling point back then: you could have strings of unlimited length unlike Pascal's 255-byte strings. People liked overcoming that limit with the same storage overhead of an extra byte.

  "strcat(strcat(strcat(strcpy(buf, "This "),"is "),"a long "),"string.");
  len = strlen(buf);

> The above example executes in exponential time with the length of the strings.

This statement is obviously not true. The example is linear with the length of the strings (assuming the number of strings is constant) and O(n^2) with the number of strings (assuming each string has non-zero length).

What a nightmare, I know C but wouldn't want to touch it for anything that does any type of anything with strings.

And of course you have the crowd that's been writing C for 20 years saying "it's not that bad". Folks, the god damn plane has crashed into the mountain.

Exactly. Any time I start a project, if it's going to working with strings, I automatically pick something else, anything else, besides C, no matter how great C would have been for the task for performance, because its string-handling is just that bad. C++ isn't great, but it's a lot better.

Personally, my favorite for good performance is C++ with Qt. The QString class lets you do a lot of amazing stuff very easily.

Reply on news.ycombinator.com