{"action":"created","issue":{"url":"https://api.github.com/repos/freechipsproject/firrtl/issues/950","repository_url":"https://api.github.com/repos/freechipsproject/firrtl","labels_url":"https://api.github.com/repos/freechipsproject/firrtl/issues/950/labels{/name}","comments_url":"https://api.github.com/repos/freechipsproject/firrtl/issues/950/comments","events_url":"https://api.github.com/repos/freechipsproject/firrtl/issues/950/events","html_url":"https://github.com/freechipsproject/firrtl/pull/950","id":384549151,"node_id":"MDExOlB1bGxSZXF1ZXN0MjMzNzI2MjA4","number":950,"title":"Improve propagate performance for big annotations","user":{"login":"seldridge","id":1018530,"node_id":"MDQ6VXNlcjEwMTg1MzA=","avatar_url":"https://avatars0.githubusercontent.com/u/1018530?v=4","gravatar_id":"","url":"https://api.github.com/users/seldridge","html_url":"https://github.com/seldridge","followers_url":"https://api.github.com/users/seldridge/followers","following_url":"https://api.github.com/users/seldridge/following{/other_user}","gists_url":"https://api.github.com/users/seldridge/gists{/gist_id}","starred_url":"https://api.github.com/users/seldridge/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/seldridge/subscriptions","organizations_url":"https://api.github.com/users/seldridge/orgs","repos_url":"https://api.github.com/users/seldridge/repos","events_url":"https://api.github.com/users/seldridge/events{/privacy}","received_events_url":"https://api.github.com/users/seldridge/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2018-11-26T23:06:26Z","updated_at":"2018-11-27T01:05:26Z","closed_at":null,"author_association":"MEMBER","pull_request":{"url":"https://api.github.com/repos/freechipsproject/firrtl/pulls/950","html_url":"https://github.com/freechipsproject/firrtl/pull/950","diff_url":"https://github.com/freechipsproject/firrtl/pull/950.diff","patch_url":"https://github.com/freechipsproject/firrtl/pull/950.patch"},"body":"When passing around big annotations (e.g., the `FirrtlCircuitAnnotation` that #920 adds), the overhead of copying annotations in `Compiler.propagateAnnotations` explodes. This does three things to improve the performance if you have big annotations:\r\n\r\n1. The `mutable.LinkedHashSet` introduced by #855 is changed to an `immutable.ListSet`. I'm not sure exactly what's going on here, but construction of `LinkedHashSet` seems to be approximately 6x slower than `ListSet`. :woman_shrugging: No mutable operations are used here, so this is a straightforward change. The ordered requirement of #855 is still preserved.\r\n\r\n2. Any construction of `ListSet[Annotation]` is limited as much as possible. This removes the unnecessary construction of `created` and `unchangedSet`.\r\n\r\n3. Some `LinkedHashSet` that were only used for debugging (i.e., used inside of `logger.debug`) are moved to live inside of a `logger.debug` scope.\r\n\r\n#920, without this PR, results in a dramatic runtime increase for large designs. E.g., Rocket Chip `DefaultConfig` takes 16s to get through `ChirrtlToHighFirrtl`:\r\n\r\n```\r\nTime: 15187.3 ms\r\nForm: HighForm\r\n======== Finished Transform ChirrtlToHighFirrtl ========\r\n```\r\n\r\n#920, with this PR, gets this down to 2s:\r\n\r\n```\r\nTime: 1840.0 ms\r\nForm: HighForm\r\n======== Finished Transform ChirrtlToHighFirrtl ========\r\n```\r\n\r\n### Alternatives \r\n\r\nThere are two main alternatives:\r\n\r\n1. A `FirrtlCircuitAnnotation` (and other big annotations) shouldn't be passed around during lowering. This is a valid point and I plan to update #920 in this way. However, the problem outlined here will come up for any massive annotation that people want to move around.\r\n\r\n2. The debug-only code could be removed outright. I leave that decision up to @azidar. If left in, then debug will be substantially slower than non-debug. This seems fine generally, but this is really crawling... There may be a further refactor here that would remove the use of `LinkedHashSet`, use something faster, or rely on (1) to get rid of the big offender here."},"comment":{"url":"https://api.github.com/repos/freechipsproject/firrtl/issues/comments/441858646","html_url":"https://github.com/freechipsproject/firrtl/pull/950#issuecomment-441858646","issue_url":"https://api.github.com/repos/freechipsproject/firrtl/issues/950","id":441858646,"node_id":"MDEyOklzc3VlQ29tbWVudDQ0MTg1ODY0Ng==","user":{"login":"jackkoenig","id":8584418,"node_id":"MDQ6VXNlcjg1ODQ0MTg=","avatar_url":"https://avatars3.githubusercontent.com/u/8584418?v=4","gravatar_id":"","url":"https://api.github.com/users/jackkoenig","html_url":"https://github.com/jackkoenig","followers_url":"https://api.github.com/users/jackkoenig/followers","following_url":"https://api.github.com/users/jackkoenig/following{/other_user}","gists_url":"https://api.github.com/users/jackkoenig/gists{/gist_id}","starred_url":"https://api.github.com/users/jackkoenig/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jackkoenig/subscriptions","organizations_url":"https://api.github.com/users/jackkoenig/orgs","repos_url":"https://api.github.com/users/jackkoenig/repos","events_url":"https://api.github.com/users/jackkoenig/events{/privacy}","received_events_url":"https://api.github.com/users/jackkoenig/received_events","type":"User","site_admin":false},"created_at":"2018-11-27T01:05:26Z","updated_at":"2018-11-27T01:05:26Z","author_association":"CONTRIBUTOR","body":"I don't think it's the `copying` of annotations like `FirrtlCircuitAnnotation`, I think it's the hashing process. Thus every time you have to rehash it's going to be pretty expensive.\r\n\r\nI suspect that the performance gains come entirely from never having to hash the `FirrtlCircuitAnnotation` in a `ListSet` (since insertion and lookup is a linear search, no hashing. But for larger numbers of annotations I think we'll run into some pretty big problems using `ListSet`. In particular, I think the `(inSet -- resAnno)` is be `O(n^2)` for `ListSet` while merely `O(n)` for `LinkedHashMap`.\r\n\r\nAll of this being said, benchmarking is king. Have you benchmarked just using the default stuff in rocket-chip or have you run it with a larger number of annotations? I can run experiments with the large number of annotations we use internally tomorrow. We should probably create a more formal benchmarking suite including lots of annotations ([here's the script I'm currently using, but it doesn't do any annotations at the moment](https://github.com/jackkoenig/firrtlbench/blob/master/benchmark.py)).\r\n"}}
{"actor":{"display_login":"jackkoenig"}}