null terminated bytestrings?
- Dominant language
- Haskell
- Stars
- 301
- Forks
- 144
- Avg merge
- 7d 22h
- Merged PRs (30d)
- 1
Description
This is more of a discussion/question than an issue.
I was looking into calling into the libc function [strpbrk](https://man7.org/linux/man-pages/man3/strpbrk.3.html), because it is much faster than any equivalent of `findIndex` could be, see:
* https://github.com/bminor/glibc/blob/master/string/strpbrk.c
* https://github.com/bminor/glibc/blob/master/string/strcspn.c
* https://github.com/bminor/glibc/commit/d3496c9f4f27d3009b71be87f6108b4fed7314bd
But then I noticed... Haskell bytestrings are not null-terminated and doing so would require an entire memcpy, which kind of defeats the purpose when looking for optimization.
So I wondered:
1. what if ByteStrings were null-terminated internally, without changing any of the external API? That would make it easier to just pass them to C functions expecting null-terminated strings without copying. Yes, I'm aware that a bytestring can have null bytes anywhere and that you'd potentially get divergent behavior between `strpbrk` and a "pure Haskell implementation"
2. what if there was another module enforcing the variant? Via a newtype maybe?
3. are there other tricks that could be employed? Lazy bytestrings, obviously, don't help here. Could `Text` be an alternative? The main reason I use ByteString for this task is because it has those very fast `elemIndex` functions implemented via `memchr`.
I think there might be many more such C functions, that are not re-implemented for ByteString exactly for that reason.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start with the linked libc strpbrk and strcspn implementations and compare them with ByteString's elemIndex and memchr behavior. Determine whether null termination, a newtype or module, or another approach can avoid copying while preserving embedded-NUL semantics; done means a decided design or documented answer.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c, haskell
- Domain
- performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100