Binary decoding is slow

[sjakobi]

There have been a few reports of slow binary decoding performance on Discourse recently:

• https://discourse.dhall-lang.org/t/figuring-out-performance-bottlenecks/251
• https://discourse.dhall-lang.org/t/high-memory-use-when-decoding-dhall-expressions/171

In general, people seem to get only about 10 MB/s.

I've tried profiling dhall decode with the new --quiet option, but the output only points at two functions from cborg:

COST CENTRE            MODULE              SRC                                      %time %alloc

getDecodeAction        Codec.CBOR.Decoding src/Codec/CBOR/Decoding.hs:311:1-55       81.5   88.7
deserialiseIncremental Codec.CBOR.Read     src/Codec/CBOR/Read.hs:(165,1)-(167,46)   18.5   11.0

---

Things to investigate:

• Might high rates of branch mispredictions slow us down?

Things to try:

• Map and Set deserialization in the style of Deserializing maps and sets haskell/containers#405
• Adopt a UTF8-based string type for record and union labels etc.: Try ShortText or Basement.String instead of Text for strings in Expr #1032
• Tweak RTS options. A larger nursery might be useful?

[sjakobi]

I've also tried looking at the core, but it's fairly impenetrable to me.

@Gabriel439 do you have any other suggestions what we could do except ask for help on the cborg issue tracker?

[Gabriella439]

@sjakobi: I ran into the same issue and I also don't know how to make progress

[sjakobi]

I've opened well-typed/cborg#236.

[sjakobi]

While looking at decodeExpressionInternal I noticed that we're frequently using Control.Monad.replicateM, which I suspected to be lazier than ideal. I tried replacing it with

replicateM :: Int -> Decoder s a -> Decoder s [a]
replicateM n d = Vector.toList <$> Vector.replicateM n d

Vector.replicateM has a Monad constraint instead of Applicative. But that didn't seem to impact performance at all.

I've also just tried this version:

replicateM :: Int -> Decoder s a -> Decoder s [a]
replicateM n d = go n
  where
    go 0 = return []
    go n = do
        !x <- d
        (x :) <$> go (n - 1)

That seems to improve speed in the range of 5-10%. PR incoming.

---

Given the sheer size of decodeExpressionInternal, I've also wondered whether it might be worth trying to move some things "off the hot path". I believe I've read some comments by Harendra Kumar regarding such an optimization. I don't really expect a lot of benefit from that, though.

[Gabriella439]

@sjakobi: Another thing that might further improve performance is eliminating the list intermediate. In many cases the list returned by replicateM is then being transformed into yet another data structure (such as nested Apps or a Dhall.Map). If we were to directly assemble the target data structure without going through the list intermediate it might be faster.

[sjakobi]

@Gabriel439 Yeah. For ListLit we could try Data.Sequence.replicateM.

Regarding Map (and Set) we could look at haskell/containers#405, but I think we shouldn't rely on the input being in ascending order already.

[Gabriella439]

@sjakobi: Well, if it is an expression protected by an integrity check we could rely on the input being sorted. The Serialise instance could make no such assumptions, but we could expose extra utilities outside that type-class that are faster for the case where the fields are sorted. It's probably worth checking to at least see if the sorted assumption leads to a performance improvement

[sjakobi]

For ListLit we could try Data.Sequence.replicateM.

I've tried this. It seems to actually reduce performance for my cpkg benchmark, possibly due the Applicative constraint impacting strictness analysis.

[Gabriella439]

@sjakobi: Also, if the profile is not very informative, you can fix that by adding extra cost annotations to the code using the {-# SCC "myAnnotation" #-} pragma. That's what I do whenever I need to narrow things down. See also:

https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/profiling.html#inserting-cost-centres-by-hand

Also, I highly recommend using the profiteur tool for better understanding a profile:

https://github.com/jaspervdj/profiteur

[sjakobi]

I've experimented a bit with the map decoding (the branch is here), but haven't seen any substantial speed-ups yet. I suspect that maybe benchmarking this stuff with dhall decode --quiet isn't such a good idea after all, since that doesn't actually force the resulting expression. ;)

I'll try some more profiling too, although I do wonder how the profiling might affect the structure of the generated code and its optimizations.