Re:Why is strlen so complex in C?
by bjourne on Monday August 26, 2019 @06:52PM
(#20804538)
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.
[ Parent
| on HN ]
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.
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.
Benchmarks are always worth revisits. Mine is here https://github.com/bjourne/c-examples/blob/master/programs/s...
Re:Why is strlen so complex in C?
by adrianmonk on Monday August 26, 2019 @07:45PM
(#20804850)
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.
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.
Re:Why is strlen so complex in C?
by slovenlyrobot on Monday August 26, 2019 @07:09PM
(#20804629)
Curious to know if this still holds for hyperthreads (i.e. all? modern clouds)