9 ms·

Why is strlen so complex in C?

63 points by azhenley 7y ago

Ididntdothis 7y ago
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.
- raverbashing 7y ago
  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
  - saagarjha 7y ago
    I think you're looking for C++, or maybe Rust.
  - compiler-guy 7y ago
    There was nothing "premature" about C's "high-level assembly" idea. It is somewhat archaic now, but C took off because it was so, so much better than normal assembly. If handling strings in plain C is hard, handling them in assembly is 10x as hard.
    - saagarjha 7y ago
      repne scasb disagrees with you :)
      - compiler-guy 7y ago
        As would many other assembly instructions on many other architectures.... and thereby proving my point. :-)
  - MadWombat 7y ago
    This is kind of the point of C. It maps directly to the hardware. There are very few decisions the compiler has to make about the code. And it is for that reason that C does not allow for higher level abstractions. On one hand, it is a pain to write. On the other hand, you know exactly what is going on under the hood and nothing is ever going to stop you from shooting yourself in a body part of your choice :)
    - kllrnohj 7y ago
      > This is kind of the point of C. It maps directly to the hardware. No it doesn't. It didn't in the past, it was a high-level abstraction. And it doesn't today, because CPUs don't behave at all like C's defined virtual machine.
      - justinmeiners 7y ago
        > CPUs don't behave at all like C's defined virtual machine What "virtual machine" are you referring to?
        saagarjha 7y ago
        The one defined in the standard.
        anticensor 7y ago
        One that ISO 9899 refers to as its abstract machine.
    - ncmncm 7y ago
      C gives the illusion of mapping to the hardware. Hardware manufacturers have moved heaven and earth to help maintain the illusion. It finally got too hard and they had to admit atomics and cores ro the model. The next watershed will be along soon enough, but the ability to present as a C machine has long been the gateway to success or failure of a new hardware architecture. Myriads of arguably superior machine designs have foundered on "but can I code for it in C?"
    - 7y ago
  - wahern 7y ago
    C's model is great for implementing complex, efficient data structures. Pointers are an amazing abstraction. But in many respects strings are the antithesis of a data structure, and unsurprisingly C falters hard. The problem is that most programmers don't build data structures; they build Rube Goldberg machines for munging strings, even when they're using low-level languages. Data structures to most programmers are things you import into your Rube Goldberg machine. They don't understand that good programs are made of layers of meticulously crafted, bespoke data structures where the final product is effectively one giant data structure tailored for a particular task, with interfaces to match. It follows that good C programs don't do very much strings munging even if all they do is process text. The text is systematically atomized from the very beginning. The same is true for good programs in any other language.
  - klingonopera 7y ago
    "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.
- saagarjha 7y ago
  None that have succeeded, obviously. There are a number of alternative string libraries, though; here's one: https://github.com/antirez/sds 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" ;)
  - ncmncm 7y ago
    I, in fact, do suggest C++ as the right answer, where it is not precluded for practical or silly reasons. It is generally quite easy to compile a C program with a C++ compiler, and then the sky's the limit on code improvements. I recommend it, and suggest starting with improvements to memory safety. There is really no excuse for writing a new C program anymore.
    - anmorgan 7y ago
      An 8-bit microcontroller where memory is constrained and all the vendor libraries are written in C, is a good example. Your 32-bit ARM M3/M4 cores are probably crossing that line where the memory cost of using C++ is worth it, but I would say there are still real world reasons to use C. Though I would love to see more microcontroller vendors (or any) support C++ or Rust as part of they HAL libraries, but I think you will still find C to be perfectly viable for the low cost microcontroller application.
      - ncmncm 7y ago
        If it's too small for C++, it's also too small for C. Arduino is 8 bits, and it's C++ from here to the horizon. On ARM it is no contest, at any size. Funny little $.10 PICcy things may not have a C++ compiler available. Then, the C compiler is better than asm, if you can fit. Otherwise, no excuse.
        anmorgan 7y ago
        On Arduino, from my experience, it is easy to run into memory constraints, especially when using dynamically allocated memory like strings. And I'm taking about both the flash memory for code and the ram for data, stack, and heap. I don't think C is always a win, but to say to never use for new projects seems overly biased. Why is your opinion about C so strong? I am curious.
- scarface74 7y ago
  Sure, Microsoft has added plenty of them over the years... - BSTR - CString - bstr_t - basic_string - and a bunch of typedefs...
- xenadu02 7y ago
  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 parameters of pointer+length to _array_ref. There are many technical details to be worked out and choices to be made but there is no fundamental intractable problem preventing it. We'd have incremental adoption over many years. Maybe some legacy code would never be updated. The primary blocker is getting the committee members to admit this is a problem that should be solved. That is difficult enough here on HN, where some people are still arguing that C is fine as-is and we just need to invent better programmers / better tools. Ultimately C's lack of better string support comes from its lack of better array support. That comes from a certain subset of the programmer community that believes the status-quo is fine and isn't interested in such changes.
  - pornel 7y ago
    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.
    - ncmncm 7y ago
      We already know C's future. The people using old C are self-selected as those who like it the way it is. They accepted atomics because of new hardware. The place to ask for new, better stuff is at the C++ desk, and it has lots already.
    - klingonopera 7y ago
      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.
- user5994461 7y ago
  If you mean string as in text string, it's not done and I doubt it could ever be achieved in C++. It's too complicated because of unicode and string encoding aspects. The new type wouldn't be usable either, because it would have to be converted down to another representation all the time when calling functions and libraries that are not aware of it. Think of C string to C++ string to boost string to whatever. I think the closest usable thing is QString if you are using Qt.
  - kevin_thibedeau 7y ago
    Length counted, sliceable arrays would be sufficient to upgrade C. D has these.
- CameronNemo 7y ago
  As for arrays, I frequently find implementations of hash maps and linked lists that come with macros for iteration, appending, etc. libnih is the first to come to mind (GPLv2 only), but I also know that the LXC project has some similar code floating around in there... probably LGPLv2+.
saagarjha 7y ago
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…)
- marmaduke 7y ago
  The first comment on that answer mentions this. I would never take an answer on SO w/o a grain of salt w/o reading comments.
- seisvelas 7y ago
  >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 want to get so obscure that you are just ignored. The Racket community on SO is particularly fantastic, and (in my experience) the more 'web' related your question is, the worse answers you get.
  - saagarjha 7y ago
    Yes, I'm not saying that Stack Overflow doesn't have "birdies". For example, I really enjoy this user's consistently high quality answers: https://stackoverflow.com/users/224132/peter-cordes https://stackoverflow.com/users/224132/peter-cordes
    - seisvelas 7y ago
      He once answered a question of mine about recursion with x86!
  - sytelus 7y ago
    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.
bcaa7f3a8bbc 7y ago
It's worth pointing out that the author was reading an outdated implementation of strlen() from glibc. The generic implementation is still here with the same code, and would be complied if no ARCH-specific implementation is written, as seen here, https://github.com/bminor/glibc/blob/master/string/strlen.c https://github.com/bminor/glibc/blob/master/string/strlen.c. But it's probably irrelevant to most systems today, as the assembly version is almost always used, e.g. * i386: https://github.com/bminor/glibc/blob/master/sysdeps/i386/strlen.S https://github.com/bminor/glibc/blob/master/sysdeps/i386/str... * i586/i686: https://github.com/bminor/glibc/blob/master/sysdeps/i386/i586/strlen.S https://github.com/bminor/glibc/blob/master/sysdeps/i386/i58... * i686 w/ SSE2: https://github.com/bminor/glibc/blob/master/sysdeps/i386/i686/multiarch/strlen-sse2.S https://github.com/bminor/glibc/blob/master/sysdeps/i386/i68... * i686 w/ SSE2 + BSF: https://github.com/bminor/glibc/blob/master/sysdeps/i386/i686/multiarch/strlen-sse2-bsf.S https://github.com/bminor/glibc/blob/master/sysdeps/i386/i68... * x86_64 w/ SSE2: https://github.com/bminor/glibc/blob/master/sysdeps/x86_64/strlen.S https://github.com/bminor/glibc/blob/master/sysdeps/x86_64/s... * ARM: https://github.com/bminor/glibc/blob/master/sysdeps/arm/strlen.S https://github.com/bminor/glibc/blob/master/sysdeps/arm/strl... * ARMv6: https://github.com/bminor/glibc/blob/master/sysdeps/arm/armv6/strlen.S https://github.com/bminor/glibc/blob/master/sysdeps/arm/armv... * ARMv6T2: https://github.com/bminor/glibc/blob/master/sysdeps/arm/armv6t2/strlen.S https://github.com/bminor/glibc/blob/master/sysdeps/arm/armv... * ARMv8a/AArch64: https://github.com/bminor/glibc/blob/master/sysdeps/aarch64/strlen.S https://github.com/bminor/glibc/blob/master/sysdeps/aarch64/... * ARMv8a/AArch64 w/ ASIMD: https://github.com/bminor/glibc/blob/master/sysdeps/aarch64/multiarch/strlen_asimd.S https://github.com/bminor/glibc/blob/master/sysdeps/aarch64/... etc.
- zamalek 7y ago
  I was wondering how it would compare to the code produced by auto-vectorization, I guess it doesn't matter with hand-crafted assembly.
  - kllrnohj 7y ago
    https://godbolt.org/z/QP3H-d https://godbolt.org/z/QP3H-d There isn't any auto-vectorization. Clang & GCC both do basically the same thing here.
bjourne 7y ago
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 to run the benchmarks.
- slovenlyrobot 7y ago
  Curious to know if this still holds for hyperthreads (i.e. all? modern clouds)
- saagarjha 7y ago
  I would expect a vectorized implementation to perform better than this one.
- adrianmonk 7y ago
  The optimized implementation might use less power, though. With a slower algorithm, the CPU isn't the bottleneck, but it might still have more work to do.
- megous 7y ago
  At least on one ARM platform, I can clear/copy memory faster (perhaps 2-3x) with NEON intrinsics than with a byte adressing inside a for() loop.
- BeeOnRope 7y ago
  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.
m463 7y ago
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 < maxlen && s[len]; len++); return len; } http://sel4.systems/ http://sel4.systems/ https://github.com/seL4/seL4 https://github.com/seL4/seL4 (from file src/string.c)
- ridiculous_fish 7y ago
  The trailing semicolon on that for loop is quite load-bearing. I would have some code review feedback.
  - goalieca 7y ago
    Looks very simple to me. I love it.
  - anticensor 7y ago
    It can be replaced by continue; in this specific case.
- rurban 7y ago
  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.
  - m463 7y ago
    Maybe verification tools choke on pointer incrementing? Having worked on a variety of code bases and coding styles, I think if there are coding rules and they are consistent across all the source files, it becomes easy to read even with wierdnesses. I hated perl with @_ and $_, but after working with it enough they became known quantities. And you can probably read all the lines of code in your lifetime, since the whole microkernel is ~30k lines of code.

63 points by azhenley 7y ago

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.

raverbashing 7y ago
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
- saagarjha 7y ago
  I think you're looking for C++, or maybe Rust.
- compiler-guy 7y ago
  There was nothing "premature" about C's "high-level assembly" idea. It is somewhat archaic now, but C took off because it was so, so much better than normal assembly. If handling strings in plain C is hard, handling them in assembly is 10x as hard.
  - saagarjha 7y ago
    repne scasb disagrees with you :)
    - compiler-guy 7y ago
      As would many other assembly instructions on many other architectures.... and thereby proving my point. :-)
- MadWombat 7y ago
  This is kind of the point of C. It maps directly to the hardware. There are very few decisions the compiler has to make about the code. And it is for that reason that C does not allow for higher level abstractions. On one hand, it is a pain to write. On the other hand, you know exactly what is going on under the hood and nothing is ever going to stop you from shooting yourself in a body part of your choice :)
  - kllrnohj 7y ago
    > This is kind of the point of C. It maps directly to the hardware. No it doesn't. It didn't in the past, it was a high-level abstraction. And it doesn't today, because CPUs don't behave at all like C's defined virtual machine.
    - justinmeiners 7y ago
      > CPUs don't behave at all like C's defined virtual machine What "virtual machine" are you referring to?
      - saagarjha 7y ago
        The one defined in the standard.
      - anticensor 7y ago
        One that ISO 9899 refers to as its abstract machine.
  - ncmncm 7y ago
    C gives the illusion of mapping to the hardware. Hardware manufacturers have moved heaven and earth to help maintain the illusion. It finally got too hard and they had to admit atomics and cores ro the model. The next watershed will be along soon enough, but the ability to present as a C machine has long been the gateway to success or failure of a new hardware architecture. Myriads of arguably superior machine designs have foundered on "but can I code for it in C?"
  - 7y ago
- wahern 7y ago
  C's model is great for implementing complex, efficient data structures. Pointers are an amazing abstraction. But in many respects strings are the antithesis of a data structure, and unsurprisingly C falters hard. The problem is that most programmers don't build data structures; they build Rube Goldberg machines for munging strings, even when they're using low-level languages. Data structures to most programmers are things you import into your Rube Goldberg machine. They don't understand that good programs are made of layers of meticulously crafted, bespoke data structures where the final product is effectively one giant data structure tailored for a particular task, with interfaces to match. It follows that good C programs don't do very much strings munging even if all they do is process text. The text is systematically atomized from the very beginning. The same is true for good programs in any other language.
- klingonopera 7y ago
  "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.
saagarjha 7y ago
None that have succeeded, obviously. There are a number of alternative string libraries, though; here's one: https://github.com/antirez/sds 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" ;)
- ncmncm 7y ago
  I, in fact, do suggest C++ as the right answer, where it is not precluded for practical or silly reasons. It is generally quite easy to compile a C program with a C++ compiler, and then the sky's the limit on code improvements. I recommend it, and suggest starting with improvements to memory safety. There is really no excuse for writing a new C program anymore.
  - anmorgan 7y ago
    An 8-bit microcontroller where memory is constrained and all the vendor libraries are written in C, is a good example. Your 32-bit ARM M3/M4 cores are probably crossing that line where the memory cost of using C++ is worth it, but I would say there are still real world reasons to use C. Though I would love to see more microcontroller vendors (or any) support C++ or Rust as part of they HAL libraries, but I think you will still find C to be perfectly viable for the low cost microcontroller application.
    - ncmncm 7y ago
      If it's too small for C++, it's also too small for C. Arduino is 8 bits, and it's C++ from here to the horizon. On ARM it is no contest, at any size. Funny little $.10 PICcy things may not have a C++ compiler available. Then, the C compiler is better than asm, if you can fit. Otherwise, no excuse.
      - anmorgan 7y ago
        On Arduino, from my experience, it is easy to run into memory constraints, especially when using dynamically allocated memory like strings. And I'm taking about both the flash memory for code and the ram for data, stack, and heap. I don't think C is always a win, but to say to never use for new projects seems overly biased. Why is your opinion about C so strong? I am curious.
scarface74 7y ago
Sure, Microsoft has added plenty of them over the years... - BSTR - CString - bstr_t - basic_string - and a bunch of typedefs...
xenadu02 7y ago
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 parameters of pointer+length to _array_ref. There are many technical details to be worked out and choices to be made but there is no fundamental intractable problem preventing it. We'd have incremental adoption over many years. Maybe some legacy code would never be updated. The primary blocker is getting the committee members to admit this is a problem that should be solved. That is difficult enough here on HN, where some people are still arguing that C is fine as-is and we just need to invent better programmers / better tools. Ultimately C's lack of better string support comes from its lack of better array support. That comes from a certain subset of the programmer community that believes the status-quo is fine and isn't interested in such changes.
- pornel 7y ago
  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.
  - ncmncm 7y ago
    We already know C's future. The people using old C are self-selected as those who like it the way it is. They accepted atomics because of new hardware. The place to ask for new, better stuff is at the C++ desk, and it has lots already.
  - klingonopera 7y ago
    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.
user5994461 7y ago
If you mean string as in text string, it's not done and I doubt it could ever be achieved in C++. It's too complicated because of unicode and string encoding aspects. The new type wouldn't be usable either, because it would have to be converted down to another representation all the time when calling functions and libraries that are not aware of it. Think of C string to C++ string to boost string to whatever. I think the closest usable thing is QString if you are using Qt.
- kevin_thibedeau 7y ago
  Length counted, sliceable arrays would be sufficient to upgrade C. D has these.
CameronNemo 7y ago
As for arrays, I frequently find implementations of hash maps and linked lists that come with macros for iteration, appending, etc. libnih is the first to come to mind (GPLv2 only), but I also know that the LXC project has some similar code floating around in there... probably LGPLv2+.

saagarjha 7y ago

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

marmaduke 7y ago
The first comment on that answer mentions this. I would never take an answer on SO w/o a grain of salt w/o reading comments.
seisvelas 7y ago
>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 want to get so obscure that you are just ignored. The Racket community on SO is particularly fantastic, and (in my experience) the more 'web' related your question is, the worse answers you get.
- saagarjha 7y ago
  Yes, I'm not saying that Stack Overflow doesn't have "birdies". For example, I really enjoy this user's consistently high quality answers: https://stackoverflow.com/users/224132/peter-cordes https://stackoverflow.com/users/224132/peter-cordes
  - seisvelas 7y ago
    He once answered a question of mine about recursion with x86!
- sytelus 7y ago
  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.

bcaa7f3a8bbc 7y ago

It's worth pointing out that the author was reading an outdated implementation of strlen() from glibc. The generic implementation is still here with the same code, and would be complied if no ARCH-specific implementation is written, as seen here, https://github.com/bminor/glibc/blob/master/string/strlen.c https://github.com/bminor/glibc/blob/master/string/strlen.c. But it's probably irrelevant to most systems today, as the assembly version is almost always used, e.g. * i386: https://github.com/bminor/glibc/blob/master/sysdeps/i386/strlen.S https://github.com/bminor/glibc/blob/master/sysdeps/i386/str... * i586/i686: https://github.com/bminor/glibc/blob/master/sysdeps/i386/i586/strlen.S https://github.com/bminor/glibc/blob/master/sysdeps/i386/i58... * i686 w/ SSE2: https://github.com/bminor/glibc/blob/master/sysdeps/i386/i686/multiarch/strlen-sse2.S https://github.com/bminor/glibc/blob/master/sysdeps/i386/i68... * i686 w/ SSE2 + BSF: https://github.com/bminor/glibc/blob/master/sysdeps/i386/i686/multiarch/strlen-sse2-bsf.S https://github.com/bminor/glibc/blob/master/sysdeps/i386/i68... * x86_64 w/ SSE2: https://github.com/bminor/glibc/blob/master/sysdeps/x86_64/strlen.S https://github.com/bminor/glibc/blob/master/sysdeps/x86_64/s... * ARM: https://github.com/bminor/glibc/blob/master/sysdeps/arm/strlen.S https://github.com/bminor/glibc/blob/master/sysdeps/arm/strl... * ARMv6: https://github.com/bminor/glibc/blob/master/sysdeps/arm/armv6/strlen.S https://github.com/bminor/glibc/blob/master/sysdeps/arm/armv... * ARMv6T2: https://github.com/bminor/glibc/blob/master/sysdeps/arm/armv6t2/strlen.S https://github.com/bminor/glibc/blob/master/sysdeps/arm/armv... * ARMv8a/AArch64: https://github.com/bminor/glibc/blob/master/sysdeps/aarch64/strlen.S https://github.com/bminor/glibc/blob/master/sysdeps/aarch64/... * ARMv8a/AArch64 w/ ASIMD: https://github.com/bminor/glibc/blob/master/sysdeps/aarch64/multiarch/strlen_asimd.S https://github.com/bminor/glibc/blob/master/sysdeps/aarch64/... etc.

zamalek 7y ago
I was wondering how it would compare to the code produced by auto-vectorization, I guess it doesn't matter with hand-crafted assembly.
- kllrnohj 7y ago
  https://godbolt.org/z/QP3H-d https://godbolt.org/z/QP3H-d There isn't any auto-vectorization. Clang & GCC both do basically the same thing here.

bjourne 7y ago

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 to run the benchmarks.

slovenlyrobot 7y ago
Curious to know if this still holds for hyperthreads (i.e. all? modern clouds)
saagarjha 7y ago
I would expect a vectorized implementation to perform better than this one.
adrianmonk 7y ago
The optimized implementation might use less power, though. With a slower algorithm, the CPU isn't the bottleneck, but it might still have more work to do.
megous 7y ago
At least on one ARM platform, I can clear/copy memory faster (perhaps 2-3x) with NEON intrinsics than with a byte adressing inside a for() loop.
BeeOnRope 7y ago
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.

m463 7y ago

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 < maxlen && s[len]; len++); return len; } http://sel4.systems/ http://sel4.systems/ https://github.com/seL4/seL4 https://github.com/seL4/seL4 (from file src/string.c)

ridiculous_fish 7y ago
The trailing semicolon on that for loop is quite load-bearing. I would have some code review feedback.
- goalieca 7y ago
  Looks very simple to me. I love it.
- anticensor 7y ago
  It can be replaced by continue; in this specific case.
rurban 7y ago
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.
- m463 7y ago
  Maybe verification tools choke on pointer incrementing? Having worked on a variety of code bases and coding styles, I think if there are coding rules and they are consistent across all the source files, it becomes easy to read even with wierdnesses. I hated perl with @_ and $_, but after working with it enough they became known quantities. And you can probably read all the lines of code in your lifetime, since the whole microkernel is ~30k lines of code.