Much faster count function in plain Haskell

[chrisdone]

The count function is implemented in terms of some C code that looks at each byte: https://github.com/haskell/bytestring/blob/master/cbits/fpstring.c#L75

If you implement count with elemIndex (which uses C's memchr underneath), it's much faster on non-consecutive chars:

count1 :: Word8 -> ByteString -> Int
count1 w8 = go 0
  where
    go c str =
      case S.elemIndex w8 str of
        Nothing -> c
        Just off -> go (c + 1) (S.drop (off+1) str)
{-# INLINE count1 #-}

For non-consecutive characters, such as finding all < in an XML document, it's obviously way faster because memchr inspects more than one byte at a time.

For consecutive chars, this is slower. It might be worth including both, or mentioning it in the docs.

[chrisdone]

If I had more time I'd contribute benchmarks to the suite, but I didn't manage to get the repo building.

Maybe put a bang pattern on c?

[gregorycollins]

You can use unsafeDrop here to omit the bounds check (elemIndex guarantees that off+1 <= length s).

[gregorycollins]

And P.S., now that I've had my morning coffee, this isn't the best way to implement count either. I did extensive microbenchmarking of many similar search loops when I was writing the hashtables package. My recommendation is:

• use SSE 4.2's PCMPESTRM instruction to compare 128 bits at a time against the target character, then run POPCNT on the result. Do a cache line at a time without branching. Use C.
• if you don't have SSE, implement PCMPESTRM yourself. Do a cache line at a time without branching. Use C. Here's an example with 16-bit values but for bytes the principle is the same.
• do number 2 in pure Haskell. In my benchmarks, even for medium-sized inputs it was much faster to blast through a cache line at a time without branching vs. writing a simpler loop.

For count on strings where c is sparse, memchr will be close to best possible because it is already using these tricks --- and because C compilers have special magic to inline memchr to the tightest possible loops for your platform. When c is not sparse, the recommendation above should beat it handily.

use SSE 4.2

Should be unnecessary to hand code that. The current C implementation when compiled with the appropriate flags on my machine uses vpcmpeqb (which is an AVX256 instruction). You could argue that hand-vectorized code is more efficient than auto-vectorized code, but that's usually a small price worth paying for portability (unless there's concrete benchmarking results showing otherwise).

In my benchmarks, even for medium-sized inputs it was much faster to blast through a cache line at a time without branching vs. writing a simpler loop.

Interesting. Did you also benchmark with the LLVM backend?

[gregorycollins]

Interesting. Did you also benchmark with the LLVM backend?

No, stock GHC only. It's nice that this loop can be compiled efficiently; I wasn't getting any autoparallelization for the loops I was writing at the time (and I looked at the .s output). What flags are you passing?

What flags are you passing?

-Ofast -march=native -mtune=native

And probably worth mentioning the compiler version as well: gcc (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609