{"action":"created","issue":{"url":"https://api.github.com/repos/dealii/dealii/issues/3663","repository_url":"https://api.github.com/repos/dealii/dealii","labels_url":"https://api.github.com/repos/dealii/dealii/issues/3663/labels{/name}","comments_url":"https://api.github.com/repos/dealii/dealii/issues/3663/comments","events_url":"https://api.github.com/repos/dealii/dealii/issues/3663/events","html_url":"https://github.com/dealii/dealii/pull/3663","id":194090930,"number":3663,"title":"Distribute dofs linear time","user":{"login":"drwells","id":3917035,"avatar_url":"https://avatars.githubusercontent.com/u/3917035?v=3","gravatar_id":"","url":"https://api.github.com/users/drwells","html_url":"https://github.com/drwells","followers_url":"https://api.github.com/users/drwells/followers","following_url":"https://api.github.com/users/drwells/following{/other_user}","gists_url":"https://api.github.com/users/drwells/gists{/gist_id}","starred_url":"https://api.github.com/users/drwells/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/drwells/subscriptions","organizations_url":"https://api.github.com/users/drwells/orgs","repos_url":"https://api.github.com/users/drwells/repos","events_url":"https://api.github.com/users/drwells/events{/privacy}","received_events_url":"https://api.github.com/users/drwells/received_events","type":"User","site_admin":false},"labels":[{"id":413106497,"url":"https://api.github.com/repos/dealii/dealii/labels/Reviewed%20and%20ready%20to%20merge","name":"Reviewed and ready to merge","color":"006b75","default":false}],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":10,"created_at":"2016-12-07T16:06:20Z","updated_at":"2016-12-07T20:19:16Z","closed_at":"2016-12-07T20:17:36Z","pull_request":{"url":"https://api.github.com/repos/dealii/dealii/pulls/3663","html_url":"https://github.com/dealii/dealii/pull/3663","diff_url":"https://github.com/dealii/dealii/pull/3663.diff","patch_url":"https://github.com/dealii/dealii/pull/3663.patch"},"body":"This PR fixes a serious performance problem with `hp::DoFHandler::distribute_dofs`. I am working on a project that requires `hp::DoFHandler` and I have been working with relatively large grids (something like 60 million dofs) so it is possible that no one has run into this particular issue before.\r\n\r\nInterestingly, the current distribution algorithm works well for squares, but takes quadratic time for the circular grid @kostyfisik contributed to step-6.\r\n\r\nHere is a plot of the run time of a test I wrote (second commit) with the current algorithm:\r\n![quadratic](https://cloud.githubusercontent.com/assets/3917035/20974781/5eb6efe0-bc6b-11e6-9dd5-00bc19a2b8fc.png)\r\n\r\nthe dotted green has slope 2 on a loglog plot and the blue line is how long `distribute_dofs` took as a function of the number of dofs.\r\n\r\nHere is the same thing (now the dotted green line has slope 1) with the proposed algorithm:\r\n![linear](https://cloud.githubusercontent.com/assets/3917035/20975096/5ccbff44-bc6c-11e6-902a-ee01eb2a2d23.png)\r\n\r\nfor the sake of completeness, here are all four at once:\r\n![combined](https://cloud.githubusercontent.com/assets/3917035/20975178/a39b96fa-bc6c-11e6-9cc5-24126e5e5a65.png)\r\n\r\nAs was discussed at PDEsoft, the test I included should time out if we use the quadratic algorithm. I also check the least squares fit of the timing information with a large error tolerance (which is somewhat risky). I included a commit hash in the test file so if this is not merged next let me know and I can fix it :)"},"comment":{"url":"https://api.github.com/repos/dealii/dealii/issues/comments/265561623","html_url":"https://github.com/dealii/dealii/pull/3663#issuecomment-265561623","issue_url":"https://api.github.com/repos/dealii/dealii/issues/3663","id":265561623,"user":{"login":"drwells","id":3917035,"avatar_url":"https://avatars.githubusercontent.com/u/3917035?v=3","gravatar_id":"","url":"https://api.github.com/users/drwells","html_url":"https://github.com/drwells","followers_url":"https://api.github.com/users/drwells/followers","following_url":"https://api.github.com/users/drwells/following{/other_user}","gists_url":"https://api.github.com/users/drwells/gists{/gist_id}","starred_url":"https://api.github.com/users/drwells/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/drwells/subscriptions","organizations_url":"https://api.github.com/users/drwells/orgs","repos_url":"https://api.github.com/users/drwells/repos","events_url":"https://api.github.com/users/drwells/events{/privacy}","received_events_url":"https://api.github.com/users/drwells/received_events","type":"User","site_admin":false},"created_at":"2016-12-07T20:19:16Z","updated_at":"2016-12-07T20:19:16Z","body":"True, but for standard containers `end()` is computed in constant time and I frequently forget that that is not true when we do `end(level)`."}}
{"actor":{"display_login":"drwells"}}