haskell / haskell/bytestring

elemIndexEnd non-optimally implemented in terms of findIndexEnd

Open
#278 1 comment 0 reactions 0 assignees View on GitHub
performance
Dominant language
Haskell
Stars
301
Forks
144
Avg merge
7d 22h
Merged PRs (30d)
1

Description

The current implementations of the `elemIndexEnd` function in modules `Data.ByteString` and `Data.ByteString.Lazy` are uniformly defined as `findIndexEnd . (==)` (the `Char8` version merely invokes the strict bytestring definition after converting from `Char` to `Word8`).

This seems counterintuitive when compared with `elemIndex`, which is *more* optimized than `findIndex` through the use of the `memchr` C FFI call to avoid costly byte-by-byte predicate testing.

There exists a GNU extension for `string.h` that defines an operation `memrchr` that performs a similar operation to `memchr` but returns the final occurrence of a byte rather than the first, which could be used when available. Even without such platform-specific optimizations, it should still be possible to either add a `memrchr`-like function to the cbits code.

Even without FFI calls, `elemIndexEnd` could use the same logic as `findIndexEnd` and perform a byte-by-byte direct equality test at least as efficiently as `findIndexEnd . (==)`, but without the indirection.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.