Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why is strlen so complex in C?

stackoverflow.com

Post reply on HN
Print view View original

51–60 of 74 posts

Re: Why is strlen so complex in C?

#51

Post by sytelus »

seisvelas wrote: post #7
saagarjha wrote: post #3

The accepted answer fails to understand that the standard library is exempt from following the C standard and makes a number of false or overly prescriptive assertions. (It also doesn't answer the question, but that's par for the course on Stack Overflow…)

>that's par for the course on Stack Overflow This is tangential to the meat of your comment but I feel compelled to nitpick based entirely on personal anecdote: I have been helped hundreds of times on StackOverflow by people who had nothing to gain from it and yet provided in depth, insightful answers. In my experience, the farther you get away from the big, overwhelmed tags, the better the quality is. But you don't…

Agreed. Parent commentor is statistically wrong. A large number of SO answers are helpful but he found an anecdote to wrongfully preach generalization. Also, OP's question violates SO guideline in the sense that answer to this question would be highly opinionated.

Re: Why is strlen so complex in C?

#52

Post by klingonopera »

pornel wrote: post #26
xenadu02 wrote: post #18

Earlier quoted context omitted.

In theory the standards committee could decide to add _array_ref to the language (or some variation on pointer+length). &myArray[10] could create an _array_ref where sizeof works against it and attempts to take a slice past the end of the array abort. I can even imagine compatibility shims like __attribute__((array_ref(1,2))) similar to printf-style format decorators that tell the compiler how to map function paramet…

It would be so nice if C had "fat pointers" (ptr+len). It's such an obvious small change that would have a massive impact on usability and safety. Unfortunately, C is dead. Microsoft thinks C is dead, and intentionally keeps their compiler awful. Even ISO WG doesn't seem to have a vision for C's future and have been rearranging deck chairs for the last 20 years.

Well, it has. You just said so, it's (ptr+len).

...it's the philosophy of the C language: There's minimal bloat on the upside, but you have to know what you're doing and how to be able get it on the downside.

Re: Why is strlen so complex in C?

#53

Post by klingonopera »

raverbashing wrote: post #4
Ididntdothis wrote: post #2

Have there been any efforts to add real string types and maybe arrays to C? Seems a lot of complications come from the primitive/not existing implementation of strings and arrays.

It's such a shame that C gets some things like strings so wrong. Writing in C shouldn't have to be so painful, but I guess they were the pioneers in a lot of things and the "high level assembly" idea stuck. (Premature optimization?) Also having objects and method calls, even if it's syntactic sugar deep down, is the best kind of syntactic sugar

"It's such a shame that human beings get some concepts like strings so wrong." - C language

Strings are "unnatural" to the binary system, it's a human concept.

Re: Why is strlen so complex in C?

#54

Post by BeeOnRope »

bjourne wrote: post #25

It wouldn't surprise me if the "unoptimized" strlen is just as fast or even faster on modern x86 hw. Both algorithms need to process the same amount of data. Thus they will fetch exactly the same number of cache lines from main memory. Likely, the cost of fetching those cache lines dominates, meaning that it doesn't matter that the "unoptimized" version does more processing per byte. Only way to find out for sure is…

It's not even close. A per-byte loop is going to be be 4-6 times slower than the 8-byte chunks + a little math shown in the question.

Let's say that all the stars align and you process an entire iteration of the byte-by-byte loop in 1 cycle. On a 4 GHz machine thats ... 4 GB/s. That's paltry compared to main memory bandwidth of 30-100 GB/s [1], not to mention say L1 bandwidth of ~ 256 GB/s (available to a single core).

This idea that everything is memory limited it just false: it's pretty hard to write code efficient enough that it can be limited by memory _bandwidth_ on a single core.

---

[1] Admittedly, a single core can usually only access 20-30 GB/s of that, but that's still >> 4 GB/s.

Re: Why is strlen so complex in C?

#55

Post by rurban »

m463 wrote: post #36

Optimization hacks aside, I swoon at the simple (and verified) seL4 implementation (note strNlen): word_t strnlen(const char *s, word_t maxlen) { word_t len; for (len = 0; len http://sel4.systems/ https://github.com/seL4/seL4 (from file src/string.c)

Nope, for sure not.

A good implementation would stick to the standard (size_t nor word_t), and would inc the pointer, not the counter. Formatting would be better (the final ; ouch).

This is junior stuff.

Re: Why is strlen so complex in C?

#56

Post by rurban »

saagarjha wrote: post #6
Ididntdothis wrote: post #2

Have there been any efforts to add real string types and maybe arrays to C? Seems a lot of complications come from the primitive/not existing implementation of strings and arrays.

None that have succeeded, obviously. There are a number of alternative string libraries, though; here's one: https://github.com/antirez/sds . And I'm sure some programmers would suggest C++ as the real "effort to add real string types and maybe arrays to C" ;)

We had that effort in C++. As we saw it backfired. C++ stdlib strings are so overengineered that they are much slower and bigger in the general case.

Re: Why is strlen so complex in C?

#57

Post by rurban »

xenadu02 wrote: post #18
Ididntdothis wrote: post #2

Have there been any efforts to add real string types and maybe arrays to C? Seems a lot of complications come from the primitive/not existing implementation of strings and arrays.

In theory the standards committee could decide to add _array_ref to the language (or some variation on pointer+length). &myArray[10] could create an _array_ref where sizeof works against it and attempts to take a slice past the end of the array abort. I can even imagine compatibility shims like __attribute__((array_ref(1,2))) similar to printf-style format decorators that tell the compiler how to map function paramet…

I wouldn't call ASCIIZ arrays "strings" anymore. Strings need to be nowadays all unicode, where most use utf-8. None of that is in the standard. Only very minor unicode support and no utf-8.

Re: Why is strlen so complex in C?

#58

Post by bjourne »

BeeOnRope wrote: post #54
bjourne wrote: post #25

It wouldn't surprise me if the "unoptimized" strlen is just as fast or even faster on modern x86 hw. Both algorithms need to process the same amount of data. Thus they will fetch exactly the same number of cache lines from main memory. Likely, the cost of fetching those cache lines dominates, meaning that it doesn't matter that the "unoptimized" version does more processing per byte. Only way to find out for sure is…

It's not even close. A per-byte loop is going to be be 4-6 times slower than the 8-byte chunks + a little math shown in the question. Let's say that all the stars align and you process an entire iteration of the byte-by-byte loop in 1 cycle. On a 4 GHz machine thats ... 4 GB/s. That's paltry compared to main memory bandwidth of 30-100 GB/s [1], not to mention say L1 bandwidth of ~ 256 GB/s (available to a single core…

Did you benchmark it? I did and found that on a Core-M with MSVC, the optimized strlen beats the naive one by about 20% and on Xeon with gcc, by about 40%. Depending on string length and other parameters. I would expect the difference to be smaller on more recent processors. But without benchmarking I don't think you can say.

Re: Why is strlen so complex in C?

#59

Post by saagarjha »

rurban wrote: post #56
saagarjha wrote: post #6

Earlier quoted context omitted.

None that have succeeded, obviously. There are a number of alternative string libraries, though; here's one: https://github.com/antirez/sds . And I'm sure some programmers would suggest C++ as the real "effort to add real string types and maybe arrays to C" ;)

We had that effort in C++. As we saw it backfired. C++ stdlib strings are so overengineered that they are much slower and bigger in the general case.

What? C++ strings have an overhead of 16 bytes+the space left in the backing buffer. That’s really not all that much.

Re: Why is strlen so complex in C?

#60

Post by BeeOnRope »

bjourne wrote: post #58
BeeOnRope wrote: post #54

Earlier quoted context omitted.

It's not even close. A per-byte loop is going to be be 4-6 times slower than the 8-byte chunks + a little math shown in the question. Let's say that all the stars align and you process an entire iteration of the byte-by-byte loop in 1 cycle. On a 4 GHz machine thats ... 4 GB/s. That's paltry compared to main memory bandwidth of 30-100 GB/s [1], not to mention say L1 bandwidth of ~ 256 GB/s (available to a single core…

Did you benchmark it? I did and found that on a Core-M with MSVC, the optimized strlen beats the naive one by about 20% and on Xeon with gcc, by about 40%. Depending on string length and other parameters. I would expect the difference to be smaller on more recent processors. But without benchmarking I don't think you can say.

Yes, I have benchmarked it in the past which is where I got the 4-6x figure from. Maybe it's worth a revisit, but unless the compiler is doing something special with the byte version, I would be surprised if the speedup was much less.

You may have to unroll both to get max speed.

If you could share your benchmark I would be interested to look at it.

Post reply on HN