haskell / haskell/bytestring

Uncons should not produce thunks

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

Description

Consider `Lazy.uncons`. Today, we have in [`Data.ByteString.Lazy`](https://github.com/haskell/bytestring/blob/f301ccf4416f6127b9305c2e2cc600ff8ab8e1e7/Data/ByteString/Lazy.hs#L354-L358):
```haskell
uncons :: ByteString -> Maybe (Word8, ByteString)
uncons Empty = Nothing
uncons (Chunk c cs)
= Just (S.unsafeHead c,
if S.length c == 1 then cs else Chunk (S.unsafeTail c) cs)
```

Both components of the returned tuple internally perform a small amount of work before constructing a result:
* The first component has to read from the underlying buffer before it can construct its `I#` result. Since the compiler doesn't know that this read should not fail, it cannot perform the read eagerly; it must create a thunk. (The `StrictByteString` version of `uncons` has the same issue here.)
* The second component has to actually perform the if-then-else before either evaluating `cs` or allocating a new `Chunk` object. This is just an comparison between evaluated `Int`s, and certainly succeeds in little time, so a compiler would be well within its rights to eagerly compare `S.length c` with `1`, but GHC today does not do so for what-ever reason.

What should we do about this?
* We could make `uncons` strict in `S.unsafeHead c`, but then the resulting `readWord8OffAddr#` read-effect operations will stick around even if the result is un-used, which is a bit unfortunate. (Maybe Cmm assignment sinking or the register allocator can clean it up very late in the pipeline. I haven't checked.) And users pattern-matching on the result of `uncons` have an easy work-around: Use a bang-pattern themselves. So I'm not convinced this behavior should be changed before GHC starts to discard unused read-effects in its simplifier.
* I think we definitely should perform the `S.length` check eagerly: Since the thunk that would be allocated is one word larger than the `Chunk` cell allocated in the else branch, I expect eagerly performing this comparison to be cheaper on average _even if the thunk would never be evaluated_. And users pattern-matching on the result of `uncons` have no comfortable workaround, since a bang-pattern may force the lazy tail prematurely. I will put up a merge request implementing this momentarily.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start in Data.ByteString.Lazy at uncons, especially the Chunk case and its S.length c == 1 check. Review the discussion and the linked merge request before changing anything, since the proposed work may already have been addressed. Done means the relevant allocation behavior is improved without changing uncons's result or laziness semantics.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
performance
Issue type
Refactor
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.