Improve performance by caching

[aleator]

I have a rather large dhall configuration and it is really taking far too long to process. I believe an order of magnitude improvement could be had just by caching the imports.

> echo "./MySetup" | fsatrace r trace -- dhall
... Output clipped
> wc -l trace
550
>sort trace|uniq -c |wc -l
37
> dhall version
1.12.0

For the record, there are 68 files in my directory, most of them small dhall files that are eventually collected in the huge list above.

I thought that dhall already had some caching in place?

[Gabriella439]

Dhall does have caching in place, so this seems like a bug. Let me see if I can reproduce this issue locally

[aleator]

Let me know if you want the blob of files I used.

[Gabriella439]

@aleator: I think the main thing that would help if you have time is a minimal reproducing example of a file being imported twice

[aleator]

I'll try to cook one up, but I probably won't manage to have time until next week.

[Gabriella439]

Also, it might not be necessary. I'm in the process of formalizing the import semantics and updating the Haskell implementation to match the standard semantics so the problem might disappear after that. I'll let you know when that is complete so that you can check again if the problem still persists.

[sellout]

I haven’t yet been able to run fsatrace (on a Mac), but if this is the case, it would explain some of the slow performance we’ve been seeing. We have a couple files that take a few seconds to normalize on their own, but when referenced by other files (that reference those slower files indirectly through a few different imports), it extends to minutes.

[sellout]

I’m digging into this now. I’ve identified two bugs and fixed one of them so far, but I feel like there is a third one lingering. Should have a PR soon.

[Gabriella439]

Awesome! Thanks for doing this :)

[sellout]

Ok, so the second bug that I identified is maybe a bit tricky. FilePath.normalize doesn’t eliminate .. from paths, so you can end up importing the same file multiple times based on where you imported it from. System.Directory.canonicalizePath fixes this, but it actually looks at the filesystem, so uses IO. We could simply remove /[^/]+/\.\. (i.e., the .. and the next directory up), but that wouldn’t behave properly around symlinks (which is why canonicalizePath uses IO.

In my simple testing, I had a dhall file trigger 532 imports. Fixing the first bug (imports containing imports don’t get cached) brought that down to 240, and if I manually canonicalize .., I get down to 82.

[sellout]

And the reason I think there’s a third issue is that I can only get down to Dhall attempting 181 imports, but when I sort | uniq | wc -l the list of attempted imports, it’s half that.

[Gabriella439]

@sellout: If something is hard to fix, it's fine to defer the harder fixes for later. Keep in mind that I'm still in the process of updating the import code to match the standard and that actually simplifies the logic a lot and fixes a lot of canonicalization issues, too, and that might actually fix these harder bugs

[sellout]

Yeah, this issue is more of a jumping off point for me to try to improve performance, so I’m jumping around to a few different places seeing what I can do. (And also just an excuse to finally contribute to Dhall proper.) So far, fewer imports hasn’t had much of an impact, so getting the path normalization fixed or whatever isn’t a priority for me.

One thing I thought might help is caching normalized imports rather than only normalizing the full expression at the end. However, when I added Dhall.Core.normalize before caching, I get a “Handlers should have the same output type” error that doesn’t occur without normalization there (but none of the unit tests break). Any idea why that would be happening? My naïve assumption was that normalization should work anywhere (as long as the Expr is well-typed).

[Gabriella439]

The last time I checked, the number one thing that will improve performance is fixing the parser to use attoparsec to lex the input. See: #108

Normalizing something shouldn't change its type (it's one of the four soundness rules for Dhall), so that latter issue sounds like a bug