{"action":"closed","issue":{"url":"https://api.github.com/repos/rust-lang/rust/issues/41215","repository_url":"https://api.github.com/repos/rust-lang/rust","labels_url":"https://api.github.com/repos/rust-lang/rust/issues/41215/labels{/name}","comments_url":"https://api.github.com/repos/rust-lang/rust/issues/41215/comments","events_url":"https://api.github.com/repos/rust-lang/rust/issues/41215/events","html_url":"https://github.com/rust-lang/rust/issues/41215","id":220937652,"number":41215,"title":"Review which hash algorithm to use for incremental compilation hashes.","user":{"login":"michaelwoerister","id":1825894,"avatar_url":"https://avatars2.githubusercontent.com/u/1825894?v=4","gravatar_id":"","url":"https://api.github.com/users/michaelwoerister","html_url":"https://github.com/michaelwoerister","followers_url":"https://api.github.com/users/michaelwoerister/followers","following_url":"https://api.github.com/users/michaelwoerister/following{/other_user}","gists_url":"https://api.github.com/users/michaelwoerister/gists{/gist_id}","starred_url":"https://api.github.com/users/michaelwoerister/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/michaelwoerister/subscriptions","organizations_url":"https://api.github.com/users/michaelwoerister/orgs","repos_url":"https://api.github.com/users/michaelwoerister/repos","events_url":"https://api.github.com/users/michaelwoerister/events{/privacy}","received_events_url":"https://api.github.com/users/michaelwoerister/received_events","type":"User","site_admin":false},"labels":[{"id":307747675,"url":"https://api.github.com/repos/rust-lang/rust/labels/A-incr-comp","name":"A-incr-comp","color":"d7e012","default":false},{"id":650846969,"url":"https://api.github.com/repos/rust-lang/rust/labels/C-tracking-issue","name":"C-tracking-issue","color":"f5f1fd","default":false}],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":42,"created_at":"2017-04-11T12:38:34Z","updated_at":"2017-10-20T10:31:27Z","closed_at":"2017-10-20T10:31:27Z","author_association":"CONTRIBUTOR","body":"For incremental compilation we are hashing lots of things, HIR, crate metadata and soon also type checking tables. These hashes are used purely as fingerprints, that is, we compare these hashes in order to find out if the things having been hashed are equal or not. Consequently the primary qualities we require from the hash algorithm are:\r\n1. That it acts as a pseudo-random-function, i.e. whatever we feed in, the resulting hashes should have a collision probability that is roughly the same as that of random numbers.\r\n2. That it produces wide enough hash values so the collision probabilities are low enough (128 bits should be fine).\r\n3. That it is fast.\r\n\r\nIt remains to be clarified whether it makes sense to use a cryptographic hash function, i.e. that it is hard to find/construct collisions. My guess is no:\r\n* Incremental compilation caches are not meant to be distributed. They are platform dependent files created locally by your compiler and there is little use in distributing them.\r\n* A 128 bit hash is probably susceptible to a brute force attack anyway.\r\n* I cannot think of an attack that exploits a hash collision here. If one wants to tamper with an incremental compilation cache, one could just replace the object file in the cache without a need to ever touch item hashes.\r\n\r\nI'd be very interested though if someone could come up with an attack scenario. But even then the solution would probably be to implement some general code signing scheme for these caches.\r\n\r\nAt the moment we are using BLAKE2 as our hashing algorithm which is a cryptographic hash function and thus fulfills requirements (1) and (2) very well. However, compared to non-cryptographic hash functions it is rather slow. For raw throughput SipHash would be about three times as fast and fast hash functions like [Metrohash](https://github.com/arthurprs/metrohash-rs) can be 20 times as fast. Before you get too excited though: Most of the time computing hashes is spent gathering the data that is fed into the hash function, not actually running the function on it. But there are still some gains to be had, here are some preliminary tests of using BLAKE2 -- which is our \"worst case\" -- and MetroHash -- which is among the fastest hash functions providing 128 bit hashes:\r\n\r\n|                          | BLAKE2 | MetroHash | SipHash 1-3 | SipHash 2-4 |\r\n|:------------------------:|:------:|:---------:|:----------:|:----------:|\r\n| libcore                  | 0.258s | 0.193s (-25%)    | 0.189s (-26%)    | 0.201s (-22%)    |\r\n| librustc                 | 0.435s | 0.345s (-20%)    | 0.320s (-26%)    | 0.327s (-25%)    |\r\n| syntex_syntax (HIR)      | 0.221s | 0.166s (-25%)    | 0.168s (-24%)    | 0.176s (-20%)    |\r\n| syntex_syntax (Metadata) | 0.456s | 0.326s (-28%)    | 0.312s (-31%)    | 0.347s (-24%)    |\r\n\r\nSo it seems that a fast hash functions allows to save 20-30% spent during ICH computation. If we could get some confidence that:\r\n\r\n* a function like MetroHash provides low enough collision probability and \r\n* we really don't need a cryptographic hash function\r\n\r\nthen we could have some free speedups here.\r\n\r\nUPDATE:\r\nI added the 128 bit version of SipHash to the table and the timings are as good as the ones for MetroHash. "}}
{"actor":{"display_login":"bors"}}