The Sad State of C Strings

https://symas.com/the-sad-state-of-c-strings/

by hyc_symas • 10 years ago

41 42 10 years ago

asgfoi3• 10 years ago

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.

hyc_symas4• 10 years ago

"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.

endymi0n• 10 years ago

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

hyc_symas4• 10 years ago

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.

reacweb2• 10 years ago

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 ?

ktRolster2• 10 years ago

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.

reacweb2• 10 years ago

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.

int0x80• 10 years ago

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

huhtenberg4• 10 years ago

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.

vardump4• 10 years ago

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.

keeperofdakeys• 10 years ago

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.

sedatk• 10 years ago

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.

huhtenberg4• 10 years ago

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.

derefr• 10 years ago

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.

draw_down2• 10 years ago

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.

hyc_symas4• 10 years ago

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.

anon46• 10 years ago

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.

anon46• 10 years ago

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

huhtenberg4• 10 years ago

  strcatm(..., NULL);

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

Kristine1975• 10 years ago

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

efaref• 10 years ago

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

anon46• 10 years ago

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

unwind• 10 years ago

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.

anon46• 10 years ago

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

AdmiralAsshat• 10 years ago

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.

sirmiller• 10 years ago

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.

sethrin• 10 years ago

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.

draw_down2• 10 years ago

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.

Grishnakh• 10 years ago

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.

pkolaczk• 10 years ago

  "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).

The Sad State of C Strings

Related Stories