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.

[sjakobi]

Profiling with the cost centres added in #1808 reveals what kind of expressions we spend most decoding time on:

Prelude

COST CENTRE            MODULE                     SRC                                                 %time %alloc

deserialiseIncremental Codec.CBOR.Read            src/Codec/CBOR/Read.hs:(165,1)-(167,46)              22.2   17.9
dEI_builtin            Dhall.Binary               src/Dhall/Binary.hs:(159,51)-(197,91)                16.7   12.7
dEI_Merge              Dhall.Binary               src/Dhall/Binary.hs:(343,56)-(358,124)               16.7    2.5
dEI_Var-_-UInt         Dhall.Binary               src/Dhall/Binary.hs:(129,54)-(132,53)                11.1    7.2
dEI_App                Dhall.Binary               src/Dhall/Binary.hs:(236,54)-(245,56)                11.1   14.3
evalParser             Options.Applicative.Common src/Options/Applicative/Common.hs:(237,1)-(241,56)    5.6    0.0
dEI_RecordLit          Dhall.Binary               src/Dhall/Binary.hs:(372,60)-(382,75)                 5.6    2.2
dEI_Lam                Dhall.Binary               src/Dhall/Binary.hs:(247,54)-(270,118)                5.6    7.1
dEI_BoolLit            Dhall.Binary               src/Dhall/Binary.hs:(154,49)-(157,34)                 5.6    0.4
dEI_operator           Dhall.Binary               src/Dhall/Binary.hs:(297,59)-(321,47)                 0.0    1.5
dEI_Union              Dhall.Binary               src/Dhall/Binary.hs:(420,57)-(441,71)                 0.0    3.6
dEI_TextLit            Dhall.Binary               src/Dhall/Binary.hs:(503,59)-(513,63)                 0.0    1.3
dEI_Record             Dhall.Binary               src/Dhall/Binary.hs:(360,57)-(370,72)                 0.0   18.5
dEI_ListLit            Dhall.Binary               src/Dhall/Binary.hs:(323,58)-(334,92)                 0.0    2.9
dEI_Field              Dhall.Binary               src/Dhall/Binary.hs:(384,56)-(389,50)                 0.0    2.0
dEI_BoolIf             Dhall.Binary               src/Dhall/Binary.hs:(443,58)-(450,53)                 0.0    3.2

cpkg

COST CENTRE            MODULE          SRC                                      %time %alloc

deserialiseIncremental Codec.CBOR.Read src/Codec/CBOR/Read.hs:(165,1)-(167,46)   42.5   27.1
dEI_builtin            Dhall.Binary    src/Dhall/Binary.hs:(159,51)-(197,91)     15.4    8.3
dEI_TextLit            Dhall.Binary    src/Dhall/Binary.hs:(503,59)-(513,63)      9.6   13.7
dEI_Record             Dhall.Binary    src/Dhall/Binary.hs:(360,57)-(370,72)      7.1    7.6
dEI_Union              Dhall.Binary    src/Dhall/Binary.hs:(420,57)-(441,71)      5.0   16.5
dEI_Merge              Dhall.Binary    src/Dhall/Binary.hs:(343,56)-(358,124)     4.2    4.5
dEI_Field              Dhall.Binary    src/Dhall/Binary.hs:(384,56)-(389,50)      3.3    2.5
dEI_Lam                Dhall.Binary    src/Dhall/Binary.hs:(247,54)-(270,118)     2.9    5.5
dEI_Var-_-UInt         Dhall.Binary    src/Dhall/Binary.hs:(129,54)-(132,53)      2.5    3.0
dEI_RecordLit          Dhall.Binary    src/Dhall/Binary.hs:(372,60)-(382,75)      2.5    2.7
dEI_App                Dhall.Binary    src/Dhall/Binary.hs:(236,54)-(245,56)      2.1    4.2
dEI_BoolIf             Dhall.Binary    src/Dhall/Binary.hs:(443,58)-(450,53)      0.8    1.1
dEI_BoolLit            Dhall.Binary    src/Dhall/Binary.hs:(154,49)-(157,34)      0.4    1.7

Note that for dEI_Merge, dEI_Record, etc., much of the time and allocations are inherited from decoding the subexpressions.

dEI_builtin looks promising though. While looking at the Core, I had already noticed that this section of the code is absolutely massive. I think it's mostly the string (Text) matching that is so expensive.

We could try optimizing this by

1. Not decoding to Text, thereby avoiding the conversion to UTF-16. Instead we could use decodeUtf8ByteArray.
2. Optimize the string matching, for example by checking the length or the first character first.

I also wonder why the builtins are encoded in this string format at all. It would be much cheaper if they were encoded with simple integer tags like the operators.

Regarding the other strings, for variables, map keys, etc. we'd probably also profit to switching to UTF8, for example by using text-short. Of course we'd have to pay for conversion to UTF16 in other places then…

---

For App, I'll soon submit a patch that avoids the intermediate list representation.

[Gabriella439]

@sjakobi: The original rationale for encoding built-ins in that way was to treat them essentially the same as free variables

I agree that not decoding built-ins to UTF8 is probably a performance win

[bgamari]

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.

In my test (which only involved --quiet) it was (IIRC) a very small, but still positive, effect.