payload: {"action":"closed","issue":{"url":"https://api.github.com/repos/dhall-lang/dhall-haskell/issues/1098","repository_url":"https://api.github.com/repos/dhall-lang/dhall-haskell","labels_url":"https://api.github.com/repos/dhall-lang/dhall-haskell/issues/1098/labels{/name}","comments_url":"https://api.github.com/repos/dhall-lang/dhall-haskell/issues/1098/comments","events_url":"https://api.github.com/repos/dhall-lang/dhall-haskell/issues/1098/events","html_url":"https://github.com/dhall-lang/dhall-haskell/issues/1098","id":467411955,"node_id":"MDU6SXNzdWU0Njc0MTE5NTU=","number":1098,"title":"Proposal: Semi-semantic caching","user":{"login":"EggBaconAndSpam","id":757280,"node_id":"MDQ6VXNlcjc1NzI4MA==","avatar_url":"https://avatars0.githubusercontent.com/u/757280?v=4","gravatar_id":"","url":"https://api.github.com/users/EggBaconAndSpam","html_url":"https://github.com/EggBaconAndSpam","followers_url":"https://api.github.com/users/EggBaconAndSpam/followers","following_url":"https://api.github.com/users/EggBaconAndSpam/following{/other_user}","gists_url":"https://api.github.com/users/EggBaconAndSpam/gists{/gist_id}","starred_url":"https://api.github.com/users/EggBaconAndSpam/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/EggBaconAndSpam/subscriptions","organizations_url":"https://api.github.com/users/EggBaconAndSpam/orgs","repos_url":"https://api.github.com/users/EggBaconAndSpam/repos","events_url":"https://api.github.com/users/EggBaconAndSpam/events{/privacy}","received_events_url":"https://api.github.com/users/EggBaconAndSpam/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":21,"created_at":"2019-07-12T13:23:12Z","updated_at":"2019-08-16T09:53:08Z","closed_at":"2019-08-16T09:53:08Z","author_association":"COLLABORATOR","body":"## Introduction\r\n\r\nI propose ‘semi-semantic’ hashing as a solution to caching of non-frozen imports. The semi-semantic approach to caching is motivated by the fact that parsing is computationally trivial compared to typechecking and normalisation. See #888 for the detailed reasoning.\r\n\r\nI use *semi-semantic* to mean that any two *semantically* different (i.e. differing in their normal forms) inputs are mapped to distinct hashes, while semantically equivalent inputs that differ *syntactically* may result in different hashes. We could compute the semi-semantic hash of a dhall import/file/expression as follows:\r\n- Parse the input;\r\n- compute the *semantic hashes* of all imports referenced in the AST, i.e. the hashes of their normal forms;\r\n- compute the *syntactic hash* of the input (for example hashing the unparsed input, or alternatively by hashing the parsed AST);\r\n- concatenate the syntactic hash of the input with the semantic hashes of its imports and hash the result.\r\n\r\n### Update\r\nThe current implementation #1154 substitutes any imports by their normal form and hashes the resulting expression to obtain a *semi-semantic* hash. This is easier to implement and, since we store normal forms anyway, only incurs a constant-factor cost.\r\n\r\n## Discussion\r\n\r\nA cache indexed by semi-semantic hashes has the following properties:\r\n- For a given input we can quickly find out if it is in the cache: we only need to parse the input – we don't need to typecheck or normalise it!\r\n- The cache stays consistent, that is, we don't need to ‘invalidate’ old cache entries if their dependencies change!\r\n\r\nComparison to alternative approaches:\r\n- Naive syntactic hashing is problematic because two syntactically equivalent dhall expressions may have different semantics depending on the context (e.g. if they contain relative imports).\r\n- We can fix syntactic hashing by ‘resolving’ the absolute location of all imports before hashing. However, in this case we still need to worry about invalidating cached results if their imports change.\r\n- Local caching as implemented in #1073. Here we simply dump all loaded imports after each invocation of dhall. The problem here is again keeping the cache consistent; additionally, the user experience is suboptimal since for example changing to a different directory causes dhall to start from scratch with an empty cache. Also, we leave cache files everywhere.\r\n\r\nThe main disadvantage of a ‘semi-semantic’ approach is that it\r\n- incures a slight performance penalty when evaluating an expression with a clean cache since every import needs to be separately encoded and written to disk (currently we only ever encode and write ‘frozen’ imports to disk)\r\n- is slightly slower than a plain syntactic hashing approach since all transitive imports (except for frozen imports loaded from the semantic cache) have to be loaded as well. Using a syntactic cache we would only have to check their timestamps (or perhaps syntactic hashes) to see if they changed.\r\n\r\n## Preliminary benchmarks\r\n\r\n- cpk: Cloned from https://github.com/vmchale/cpkg. I changed any references to the dhall prelude to point to a local copy. I tested dhall hash <<< pkgs/pkg-set.dhall\r\n  - ‘main branch’: 14s with clean cache, same with populated cache.\r\n  - ‘cache dump’ syntactic: 14s with clean cache, ca. 3.6s with populated cache.\r\n  - ‘semi-semantic’ 15.5-16s with clean cache, ca. 4.6s with populated cache.\r\n\r\n- dhall-nethack: Cloned from https://github.com/dhall-lang/dhall-nethack. I set the environment variable ‘DHALL-PRELUDE’ to point at a local copy of the prelude.\r\n  - ‘main branch’: 0.36s with clean cache, same with populated cache.\r\n  - ‘cache dump’ syntactic: 0.36s with clean cache, 0.18s with populated cache.\r\n  - ‘semi-semantic’ 0.42s with clean cache, 0.25s with populated cache.\r\n\r\n## Merge Plan\r\n\r\nThis is assuming public opinion turns out in favour of this proposal.\r\n\r\n1. Change Dhall.Import from the current ‘imperative’ approach to a recursive one. This is needed because in order to be able to query the semi-semantic cache we already need to know the values of all transitive imports; currently, imports are first loaded in their unevaluated parsed form, and their imports loaded in a next step.\r\n\r\n    This will be quite a big change (cf. my prototype over at #1095). At the same time this should not have any performance impact.\r\n\r\n2. Implement semi-semantic caching. This is straightforward assuming Step 1.\r\n\r\n3. Discuss ‘unsafe’ caching of remote imports as a possible next step."}}
other: {"actor":{"display_login":"EggBaconAndSpam"}}