Performance

[ocharles]

The gcc branch gives us ./example/gcc.dhall, which is used to build GCC. This has 3 dependencies - GMP, MPFR and MPC. However, just evaluating gcc.dhall takes minutes:

time ./bin/dhall +RTS -s <<< ./examples/gcc.dhall

285,234,734,472 bytes allocated in the heap
   2,149,148,384 bytes copied during GC
       8,560,952 bytes maximum residency (89 sample(s))
         341,888 bytes maximum slop
              26 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0     274811 colls,     0 par    4.488s   4.463s     0.0000s    0.0004s
  Gen  1        89 colls,     0 par    0.559s   0.559s     0.0063s    0.0123s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time   92.299s  ( 92.484s elapsed)
  GC      time    5.047s  (  5.022s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time   97.346s  ( 97.507s elapsed)

  %GC     time       5.2%  (5.2% elapsed)

  Alloc rate    3,090,343,422 bytes per MUT second

  Productivity  94.8% of total user, 94.8% of total elapsed

./bin/dhall +RTS -s <<< ./examples/gcc.dhall  96.82s user 0.54s system 99% cpu 1:37.51 total

Applying dhall freeze everywhere actually makes things worse:

find ./examples -name '*.dhall' -exec ./bin/dhall freeze --inplace '{}' ';'

time ./bin/dhall +RTS -s <<< ./examples/gcc.dhall

343,492,628,992 bytes allocated in the heap
   2,511,808,920 bytes copied during GC
       9,187,192 bytes maximum residency (94 sample(s))
          46,576 bytes maximum slop
              28 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0     330961 colls,     0 par    5.495s   5.461s     0.0000s    0.0008s
  Gen  1        94 colls,     0 par    0.520s   0.521s     0.0055s    0.0137s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time  113.356s  (113.629s elapsed)
  GC      time    6.015s  (  5.982s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time  119.372s  (119.611s elapsed)

  %GC     time       5.0%  (5.0% elapsed)

  Alloc rate    3,030,198,903 bytes per MUT second

  Productivity  95.0% of total user, 95.0% of total elapsed

./bin/dhall +RTS -s <<< ./examples/gcc.dhall  118.75s user 0.63s system 99% cpu 1:59.62 total

[ocharles]

CC @Gabriel439

[ocharles]

The (huge) normalized expression can be found at https://github.com/dhallix/nix-derivation/blob/gcc/nf.dhall

[ocharles]

Here is the derivation dependency graph, to give an idea of what nf.dhall represents.

[Gabriella439]

@ocharles: I can think of two possible ways to solve this:

Approach 1: Use lamping's algorithm for normalization in Dhall so that it can internally represent the abstract syntax tree as a graph so that it doesn't need to materialize the entire result except to display to the user. This is a significant amount of work.

Approach 2: Use the support for custom type-checking and custom normalization so that mkDerivation is now a built-in that when evaluated actually builds the derivation and replaces it with a Text value pointing to the built path. In other words, exactly how Nix works

[ocharles]

Approach 2 has the same problems that always come up with this, namely siloing yourself from any other Dhall tool in the field. That does feel like a shame for something like dhallix. I'm also not convinced it really solves the problem, but perhaps more just delays when it actually becomes problematic. I was wondering how much normalisation would benefit from parallel reduction and memoisation - my hunch is a lot of similar terms are repeatedly normalised. The former is suggested as dhall-nix only uses a single core on my 8 core machine to normalise this term, but I think a lot of normalisation could happen in parallel. It doesn't change the asymptotics, but may still be helpful.

[Gabriella439]

@ocharles: Right, the graph representation is the way to avoid repeated work and Lamping's algorithm is the most efficient graph representation that I know of. I also believe it is an algorithm that's amenable to parallelization, too (cc: @MaiaVictor to confirm)

Given that this is quite a bit of work to I'll probably have to set up a KickStarter or something similar to fund somebody to do this because I know that I won't have the bandwidth to do this myself

[ocharles]

While that might be the most optimal it is, as you say, a lot of work. My approach would be to do a pass on the input to normalize to replace identical terms with shared terms, and then use sharing as memoisation in normalisation. It at least shares duplicate work, even if it's not optimal. I'll have a play.

[ocharles]

Unfortunately even adding derivation as a built-in doesn't really seem to help. I forked dhall-nix and added an extra step in dhallToNix to convert derivation {...} into a Nix derivation call. Then, I changed everything to just use the new derivation : DerivationArgs -> Text function. Just trying to generate the Nix expression corresponding to gcc.dhall still takes 3 minutes on my laptop (Dhall 1.17). Dhall 1.18 takes 1min 30s on this laptop to normalize the original approach, which does suggest the 1.18 improvements might make a difference, but it still feels like it'll be too slow to be practical.

[Gabriella439]

@ocharles: That seems unusual. I think you'll have to profile it to see what is the bottleneck

[ocharles]

I'll have a look in the week. I took out the Nix specific stuff and switched to Dhall 1.18. Going from examples/gcc.dhall to a normal form (Dhall.Core.normalizeWith) still takes 1min 30s so I don't think it's a problem particularly unique to Dhallix.

[Gabriella439]

Yeah, what makes this weird is that it seems like the AST should be small from what I've skimmed so far, unless it is duplicating calls to derivation which cause that to be unnecessarily called repeatedly

[ocharles]

The normal form is still pretty huge - 6MB formatted: https://github.com/dhallix/nix-derivation/blob/builtin-derivation/normal-form.dhall

[ocharles]

I'm not sure what you mean about derivation calls be duplicated unnecessarily. Everything builds on top of bootstrap stuff, so the bootstrapping derivation gets inlined into everything that needs it. I can't see how else Dhall could represent that sharing

[Gabriella439]

Ah, okay, now I see why you didn't get a performance speed up.

What I meant was to use normalizeWith to add a custom hook for evaluating calls of the derivation function, instead of evaluating the derivation function in a post-processing step after normalize. The reason for doing so is that if you evaluate derivation as you are normalizing the tree then it will never get an opportunity to grow so large.

[ocharles]

I actually don't think it's normalization that is the problem. If I take examples/gcc.dhall and just pass it through importing and type checking it still takes 1min 28s. I've gotta leave soon though so I can't do much more testing for now.