On Wed, May 31, 2017 at 03:46:17PM -0700, Jonathan M Davis via Digitalmars-d-learn wrote: > On Wednesday, May 31, 2017 12:13:04 H. S. Teoh via Digitalmars-d-learn > wrote: > > I did some digging around, and it seems that wc is using glibc's > > memchr, which is highly-optimized, whereas std.algorithm.count just > > uses a simplistic loop. Which is strange, because I'm pretty sure > > somebody optimized std.algorithm some time ago to use memchr() > > instead of a loop when searching for a byte value in an array. > > Whatever happened to that?? > > I don't know, but memchr wouldn't work with CTFE, so someone might > have removed it to make it work in CTFE (though that could be done > with a different branch for CTFE). Or maybe it never made it into > std.algorithm for one reason or another. [...]
I checked the Phobos code again, and it appears that my memory deceived me. Somebody *did* add memchr optimization to find() and its friends, but not to count(). CTFE compatibility is not a problem, since we can just if(__ctfe) the optimized block away. I'm currently experimenting with a memchr-optimized version of count(), but I'm getting mixed results: on small arrays or large arrays densely packed with matching elements, the memchr version runs rather slowly, because it involves a function call into the C library per matching element. On large arrays only sparsely populated with matching elements, though, the memchr-optimized version beats the current code by about an order of magnitude. Since it wouldn't be a wise idea to assume sparsity of matches in Phobos, I decided to do a little more digging, and looked up the glibc implementation of memchr. The main optimization is that it iterates over the array not by byte, as a naïve loop would do, but by ulong's. (Of course, the first n bytes and last n bytes that are not ulong-aligned are checked with a per-byte loop; so for very short arrays it doesn't lose out to the naïve loop.) In each iteration over ulong, it performs the bit-twiddling hack alluded to by Nitram to detect the presence of matching bytes, upon which it breaks out to the closing per-byte loop to find the first match. For short arrays, or arrays where a match is quickly found, it's comparable in performance to the naïve loop; for large arrays where the match is not found until later, it easily outperforms the naïve loop. My current thought is to adopt the same approach: iterate over size_t or some such larger unit, and adapt the bit-twiddling hack to be able to count the number of matches in each size_t. This is turning out to be trickier than I'd like, though, because there is a case where carry propagation makes it unclear how to derive the number of matches without iterating over the bytes a second time. But this may not be a big problem, since size_t.sizeof is relatively small, so I can probably loop over individual bytes when one or more matches is detected, and a sufficiently-capable optimizer like ldc or gdc would be able to unroll this into a series of sete + add instructions, no branches that might stall the CPU pipeline. For densely-matching arrays, this should still have comparable performance to the naïve loops; for sparsely-matching arrays this should show significant speedups. T -- My program has no bugs! Only unintentional features...
