findIndexOrEnd is faster in Data.ByteString than in Data.ByteString.Lazy for no reason.

[noughtmare]

The findIndexOrEnd function defined in Data.ByteString.Lazy is slower, I think because it uses two parameters in its loop:

bytestring/Data/ByteString/Lazy.hs

Lines 1411 to 1423 in 34f972c

	-- | 'findIndexOrEnd' is a variant of findIndex, that returns the length
	-- of the string if no element is found, rather than Nothing.
	findIndexOrEnd :: (Word8 -> Bool) -> P.ByteString -> Int
	findIndexOrEnd k (S.BS x l) =
	S.accursedUnutterablePerformIO $
	withForeignPtr x $ \f -> go f 0
	where
	go !ptr !n | n >= l = return l
	| otherwise = do w <- peek ptr
	if k w
	then return n
	else go (ptr `plusPtr` 1) (n+1)
	{-# INLINE findIndexOrEnd #-}

The strict findIndexOrEnd is here:

bytestring/Data/ByteString.hs

Lines 2026 to 2039 in 34f972c

	-- | 'findIndexOrEnd' is a variant of findIndex, that returns the length
	-- of the string if no element is found, rather than Nothing.
	findIndexOrEnd :: (Word8 -> Bool) -> ByteString -> Int
	findIndexOrEnd k (BS x l) =
	accursedUnutterablePerformIO $ withForeignPtr x g
	where
	g ptr = go 0
	where
	go !n | n >= l = return l
	| otherwise = do w <- peek $ ptr `plusPtr` n
	if k w
	then return n
	else go (n+1)
	{-# INLINE findIndexOrEnd #-}

This difference is significant, I get about a 1.5x speedup with my benchmark. I still need to clean it up and I don't know if you are interested in seeing it. If you want I can link it in a gist or something. (EDIT: take these results with a grain of salt, I don't think my benchmark is completely correct)

EDIT: I have done some more benchmarks: the performance difference between the two versions is about 1.4x, but marking dropWhile inlineable makes it 3x faster than that for my benchmark. Here is the benchmark: https://gist.github.com/noughtmare/f2478b9ea7a466d33b3f0185dc51f0dd

I think it would be best if this function could be deduplicated, preferably by exporting it in Data.ByteString.Internal.

Additionally, the dropWhile function in Data.ByteString.Lazy is not marked INLINE and not even INLINABLE. I think this also causes a big performance difference in my code. Should I open a separate issue for this?

[sjakobi]

Nice catch!

Indeed I see no reason why D.B.Lazy shouldn't simply use the findIndexOrEnd defined in Data.ByteString. A PR to fix this would be welcome.

Additionally, the dropWhile function in Data.ByteString.Lazy is not marked INLINE and not even INLINABLE. I think this also causes a big performance difference in my code. Should I open a separate issue for this?

Thanks for pointing this out! There are quite a few definitions in D.B.Lazy that suspiciously lack INLINE or INLINABLE pragmas. It would be good to check whether we're leaving any performance on the table there. Recording this in a separate issue sounds like a good idea! 👍

[noughtmare]

I'm actually not quite sure why findIndexOrEnd is not just exported in Data.ByteString. Maybe it has to do with its use of accursedUnutterablePerformIO?

[sjakobi]

I'm actually not quite sure why findIndexOrEnd is not just exported in Data.ByteString.

I believe it's not exported because of its somewhat crude semantics where the return value has special meaning when equal to the bytestring's length.

I think we can export findIndexOrEnd from D.B.Internal, so we can use it from D.B.Lazy.