{"action":"created","comment":{"url":"https://api.github.com/repos/dealii/dealii/pulls/comments/28302695","id":28302695,"diff_hunk":"@@ -374,85 +393,85 @@ namespace SparsityTools\n           (numbers::invalid_dof_index, numbers::invalid_dof_index);\n           for (types::global_dof_index i=0; i<touched_nodes.size(); ++i)\n             if (touched_nodes[i] == numbers::invalid_dof_index)\n-              if (connectivity.row_length(i) < min_neighbors.second)\n-                min_neighbors = std::make_pair(i, connectivity.row_length(i));\n+              if (row_lengths[i] < min_neighbors.second)\n+                {\n+                  min_neighbors = std::make_pair(i, n_remaining_neighbors[i]);\n+                  if (n_remaining_neighbors[i] <= 1)\n+                    break;\n+                }\n           if (min_neighbors.first == numbers::invalid_dof_index)\n             break;\n \n+          Assert(min_neighbors.second > 0, ExcInternalError());\n+\n           current_neighbors.clear();\n           current_neighbors.insert(min_neighbors.first);\n           while (!current_neighbors.empty())\n             {\n-              // Find cell with minimum number of untouched neighbors among the\n+              // Find node with minimum number of untouched neighbors among the\n               // next set of possible neighbors\n               min_neighbors = std::make_pair (numbers::invalid_dof_index,\n                                               numbers::invalid_dof_index);\n               for (std::set<types::global_dof_index>::iterator it=current_neighbors.begin();\n                    it != current_neighbors.end(); ++it)\n                 {\n-                  AssertThrow(touched_nodes[*it] == numbers::invalid_dof_index,\n-                              ExcInternalError());\n-                  types::global_dof_index active_row_length = 0;\n-                  for (DynamicSparsityPattern::row_iterator rowit\n-                       = connectivity.row_begin(*it);\n-                       rowit != connectivity.row_end(*it); ++rowit)\n-                    if (touched_nodes[*rowit] == numbers::invalid_dof_index)\n-                      ++active_row_length;\n-                  if (active_row_length < min_neighbors.second)\n-                    min_neighbors = std::make_pair(*it, active_row_length);\n+                  Assert (touched_nodes[*it] == numbers::invalid_dof_index,\n+                          ExcInternalError());\n+                  if (n_remaining_neighbors[*it] < min_neighbors.second)\n+                    min_neighbors = std::make_pair(*it, n_remaining_neighbors[*it]);\n                 }\n-              // Among the set of cells with the minimal number of neighbors,\n+\n+              // Among the set of nodes with the minimal number of neighbors,\n               // choose the one with the largest number of touched neighbors,\n               // i.e., the one with the largest row length\n               const types::global_dof_index best_row_length = min_neighbors.second;\n               for (std::set<types::global_dof_index>::iterator it=current_neighbors.begin();\n                    it != current_neighbors.end(); ++it)\n-                {\n-                  types::global_dof_index active_row_length = 0;\n-                  for (DynamicSparsityPattern::row_iterator rowit\n-                       = connectivity.row_begin(*it);\n-                       rowit != connectivity.row_end(*it); ++rowit)\n-                    if (touched_nodes[*rowit] == numbers::invalid_dof_index)\n-                      ++active_row_length;\n-                  if (active_row_length == best_row_length)\n-                    if (connectivity.row_length(*it) > min_neighbors.second)\n-                      min_neighbors = std::make_pair(*it, connectivity.row_length(*it));\n-                }\n+                if (n_remaining_neighbors[*it] == best_row_length)\n+                  if (row_lengths[*it] > min_neighbors.second)\n+                    min_neighbors = std::make_pair(*it, row_lengths[*it]);\n \n-              // Add the pivot cell to the current list\n+              // Add the pivot and all direct neighbors of the pivot node not\n+              // yet touched to the list of new entries.\n               groups.push_back(std::vector<types::global_dof_index>());\n-              std::vector<types::global_dof_index> &new_entries = groups.back();\n-              new_entries.push_back(min_neighbors.first);\n-              touched_nodes[min_neighbors.first] = groups.size()-1;\n+              std::vector<types::global_dof_index> &next_group = groups.back();\n \n-              // Add all direct neighbors of the pivot cell not yet touched to\n-              // the current list\n+              next_group.push_back(min_neighbors.first);\n+              touched_nodes[min_neighbors.first] = groups.size()-1;\n               for (DynamicSparsityPattern::row_iterator it\n                    = connectivity.row_begin(min_neighbors.first);\n                    it != connectivity.row_end(min_neighbors.first); ++it)\n-                {\n-                  if (touched_nodes[*it] == numbers::invalid_dof_index)\n-                    {\n-                      new_entries.push_back(*it);\n-                      touched_nodes[*it] = groups.size()-1;\n-                    }\n-                }\n+                if (touched_nodes[*it] == numbers::invalid_dof_index)\n+                  {\n+                    next_group.push_back(*it);\n+                    touched_nodes[*it] = groups.size()-1;\n+                  }\n \n               // Add all neighbors of the current list not yet touched to the\n-              // set of possible next pivots. Delete the entries of the current\n-              // list from the set of possible next pivots.\n-              for (types::global_dof_index i=0; i<new_entries.size(); ++i)\n+              // set of possible next pivots. The added node is no longer a\n+              // valid neighbor (here we assume symmetry of the\n+              // connectivity). Delete the entries of the current list from\n+              // the set of possible next pivots.\n+              for (unsigned int i=0; i<next_group.size(); ++i)\n                 {\n                   for (DynamicSparsityPattern::row_iterator it\n-                       = connectivity.row_begin(new_entries[i]);\n-                       it != connectivity.row_end(new_entries[i]); ++it)\n-                    if (touched_nodes[*it] == numbers::invalid_dof_index)\n-                      current_neighbors.insert(*it);\n-                  current_neighbors.erase(new_entries[i]);\n+                       = connectivity.row_begin(next_group[i]);\n+                       it != connectivity.row_end(next_group[i]); ++it)\n+                    {\n+                      if (touched_nodes[*it] == numbers::invalid_dof_index)\n+                        current_neighbors.insert(*it);\n+                      n_remaining_neighbors[*it]--;\n+                    }\n+                  current_neighbors.erase(next_group[i]);\n                 }\n             }\n         }\n-      // If the number of groups is smaller than the number of nodes, we can\n+\n+      // Sanity check: for all nodes, there should not be any neighbors left\n+      for (types::global_dof_index row=0; row<connectivity.n_rows(); ++row)","path":"source/lac/sparsity_tools.cc","position":165,"original_position":165,"commit_id":"94a64cbbfd46bcd05460fe57e08e35f26c2010b9","original_commit_id":"94a64cbbfd46bcd05460fe57e08e35f26c2010b9","user":{"login":"kronbichler","id":8276200,"avatar_url":"https://avatars.githubusercontent.com/u/8276200?v=3","gravatar_id":"","url":"https://api.github.com/users/kronbichler","html_url":"https://github.com/kronbichler","followers_url":"https://api.github.com/users/kronbichler/followers","following_url":"https://api.github.com/users/kronbichler/following{/other_user}","gists_url":"https://api.github.com/users/kronbichler/gists{/gist_id}","starred_url":"https://api.github.com/users/kronbichler/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kronbichler/subscriptions","organizations_url":"https://api.github.com/users/kronbichler/orgs","repos_url":"https://api.github.com/users/kronbichler/repos","events_url":"https://api.github.com/users/kronbichler/events{/privacy}","received_events_url":"https://api.github.com/users/kronbichler/received_events","type":"User","site_admin":false},"body":"n_rows() simply returns the const variable 'rows' from DynamicSparsityPattern which is inline, so I am pretty sure there is no problem here. It's also little work compared to other things further up, so I trust in compilers and refrain from adding two lines here.","created_at":"2015-04-14T06:15:51Z","updated_at":"2015-04-14T06:15:51Z","html_url":"https://github.com/dealii/dealii/pull/792#discussion_r28302695","pull_request_url":"https://api.github.com/repos/dealii/dealii/pulls/792","_links":{"self":{"href":"https://api.github.com/repos/dealii/dealii/pulls/comments/28302695"},"html":{"href":"https://github.com/dealii/dealii/pull/792#discussion_r28302695"},"pull_request":{"href":"https://api.github.com/repos/dealii/dealii/pulls/792"}}},"pull_request":{"url":"https://api.github.com/repos/dealii/dealii/pulls/792","id":33180041,"html_url":"https://github.com/dealii/dealii/pull/792","diff_url":"https://github.com/dealii/dealii/pull/792.diff","patch_url":"https://github.com/dealii/dealii/pull/792.patch","issue_url":"https://api.github.com/repos/dealii/dealii/issues/792","number":792,"state":"open","locked":false,"title":"Increase performance of SparsityTools::reorder_hierarchical","user":{"login":"kronbichler","id":8276200,"avatar_url":"https://avatars.githubusercontent.com/u/8276200?v=3","gravatar_id":"","url":"https://api.github.com/users/kronbichler","html_url":"https://github.com/kronbichler","followers_url":"https://api.github.com/users/kronbichler/followers","following_url":"https://api.github.com/users/kronbichler/following{/other_user}","gists_url":"https://api.github.com/users/kronbichler/gists{/gist_id}","starred_url":"https://api.github.com/users/kronbichler/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kronbichler/subscriptions","organizations_url":"https://api.github.com/users/kronbichler/orgs","repos_url":"https://api.github.com/users/kronbichler/repos","events_url":"https://api.github.com/users/kronbichler/events{/privacy}","received_events_url":"https://api.github.com/users/kronbichler/received_events","type":"User","site_admin":false},"body":"I introduced a few basic optimizations to the new implementation. The most notable one is to avoid computing the 'active row length', i.e., the number of neighbors that are not yet assigned, over and over again. In particular in the loop that finds the best new neighbor, lines 413-432, a lot of time is saved, up to a factor of 10.","created_at":"2015-04-13T16:32:41Z","updated_at":"2015-04-14T06:15:51Z","closed_at":null,"merged_at":null,"merge_commit_sha":"1d79f737f5fe9d9a3382b21368f0a942c707931d","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/dealii/dealii/pulls/792/commits","review_comments_url":"https://api.github.com/repos/dealii/dealii/pulls/792/comments","review_comment_url":"https://api.github.com/repos/dealii/dealii/pulls/comments{/number}","comments_url":"https://api.github.com/repos/dealii/dealii/issues/792/comments","statuses_url":"https://api.github.com/repos/dealii/dealii/statuses/94a64cbbfd46bcd05460fe57e08e35f26c2010b9","head":{"label":"kronbichler:master","ref":"master","sha":"94a64cbbfd46bcd05460fe57e08e35f26c2010b9","user":{"login":"kronbichler","id":8276200,"avatar_url":"https://avatars.githubusercontent.com/u/8276200?v=3","gravatar_id":"","url":"https://api.github.com/users/kronbichler","html_url":"https://github.com/kronbichler","followers_url":"https://api.github.com/users/kronbichler/followers","following_url":"https://api.github.com/users/kronbichler/following{/other_user}","gists_url":"https://api.github.com/users/kronbichler/gists{/gist_id}","starred_url":"https://api.github.com/users/kronbichler/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kronbichler/subscriptions","organizations_url":"https://api.github.com/users/kronbichler/orgs","repos_url":"https://api.github.com/users/kronbichler/repos","events_url":"https://api.github.com/users/kronbichler/events{/privacy}","received_events_url":"https://api.github.com/users/kronbichler/received_events","type":"User","site_admin":false},"repo":{"id":22549298,"name":"dealii","full_name":"kronbichler/dealii","owner":{"login":"kronbichler","id":8276200,"avatar_url":"https://avatars.githubusercontent.com/u/8276200?v=3","gravatar_id":"","url":"https://api.github.com/users/kronbichler","html_url":"https://github.com/kronbichler","followers_url":"https://api.github.com/users/kronbichler/followers","following_url":"https://api.github.com/users/kronbichler/following{/other_user}","gists_url":"https://api.github.com/users/kronbichler/gists{/gist_id}","starred_url":"https://api.github.com/users/kronbichler/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kronbichler/subscriptions","organizations_url":"https://api.github.com/users/kronbichler/orgs","repos_url":"https://api.github.com/users/kronbichler/repos","events_url":"https://api.github.com/users/kronbichler/events{/privacy}","received_events_url":"https://api.github.com/users/kronbichler/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/kronbichler/dealii","description":"The development repository for the deal.II finite element library.","fork":true,"url":"https://api.github.com/repos/kronbichler/dealii","forks_url":"https://api.github.com/repos/kronbichler/dealii/forks","keys_url":"https://api.github.com/repos/kronbichler/dealii/keys{/key_id}","collaborators_url":"https://api.github.com/repos/kronbichler/dealii/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/kronbichler/dealii/teams","hooks_url":"https://api.github.com/repos/kronbichler/dealii/hooks","issue_events_url":"https://api.github.com/repos/kronbichler/dealii/issues/events{/number}","events_url":"https://api.github.com/repos/kronbichler/dealii/events","assignees_url":"https://api.github.com/repos/kronbichler/dealii/assignees{/user}","branches_url":"https://api.github.com/repos/kronbichler/dealii/branches{/branch}","tags_url":"https://api.github.com/repos/kronbichler/dealii/tags","blobs_url":"https://api.github.com/repos/kronbichler/dealii/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/kronbichler/dealii/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/kronbichler/dealii/git/refs{/sha}","trees_url":"https://api.github.com/repos/kronbichler/dealii/git/trees{/sha}","statuses_url":"https://api.github.com/repos/kronbichler/dealii/statuses/{sha}","languages_url":"https://api.github.com/repos/kronbichler/dealii/languages","stargazers_url":"https://api.github.com/repos/kronbichler/dealii/stargazers","contributors_url":"https://api.github.com/repos/kronbichler/dealii/contributors","subscribers_url":"https://api.github.com/repos/kronbichler/dealii/subscribers","subscription_url":"https://api.github.com/repos/kronbichler/dealii/subscription","commits_url":"https://api.github.com/repos/kronbichler/dealii/commits{/sha}","git_commits_url":"https://api.github.com/repos/kronbichler/dealii/git/commits{/sha}","comments_url":"https://api.github.com/repos/kronbichler/dealii/comments{/number}","issue_comment_url":"https://api.github.com/repos/kronbichler/dealii/issues/comments{/number}","contents_url":"https://api.github.com/repos/kronbichler/dealii/contents/{+path}","compare_url":"https://api.github.com/repos/kronbichler/dealii/compare/{base}...{head}","merges_url":"https://api.github.com/repos/kronbichler/dealii/merges","archive_url":"https://api.github.com/repos/kronbichler/dealii/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/kronbichler/dealii/downloads","issues_url":"https://api.github.com/repos/kronbichler/dealii/issues{/number}","pulls_url":"https://api.github.com/repos/kronbichler/dealii/pulls{/number}","milestones_url":"https://api.github.com/repos/kronbichler/dealii/milestones{/number}","notifications_url":"https://api.github.com/repos/kronbichler/dealii/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/kronbichler/dealii/labels{/name}","releases_url":"https://api.github.com/repos/kronbichler/dealii/releases{/id}","created_at":"2014-08-02T15:52:43Z","updated_at":"2015-04-13T16:29:01Z","pushed_at":"2015-04-13T16:29:01Z","git_url":"git://github.com/kronbichler/dealii.git","ssh_url":"git@github.com:kronbichler/dealii.git","clone_url":"https://github.com/kronbichler/dealii.git","svn_url":"https://github.com/kronbichler/dealii","homepage":"http://www.dealii.org/","size":111744,"stargazers_count":0,"watchers_count":0,"language":"C++","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"dealii:master","ref":"master","sha":"efdacd1efc2f0fe91bbaecde0511a0b2c78ff227","user":{"login":"dealii","id":7506070,"avatar_url":"https://avatars.githubusercontent.com/u/7506070?v=3","gravatar_id":"","url":"https://api.github.com/users/dealii","html_url":"https://github.com/dealii","followers_url":"https://api.github.com/users/dealii/followers","following_url":"https://api.github.com/users/dealii/following{/other_user}","gists_url":"https://api.github.com/users/dealii/gists{/gist_id}","starred_url":"https://api.github.com/users/dealii/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dealii/subscriptions","organizations_url":"https://api.github.com/users/dealii/orgs","repos_url":"https://api.github.com/users/dealii/repos","events_url":"https://api.github.com/users/dealii/events{/privacy}","received_events_url":"https://api.github.com/users/dealii/received_events","type":"Organization","site_admin":false},"repo":{"id":21943980,"name":"dealii","full_name":"dealii/dealii","owner":{"login":"dealii","id":7506070,"avatar_url":"https://avatars.githubusercontent.com/u/7506070?v=3","gravatar_id":"","url":"https://api.github.com/users/dealii","html_url":"https://github.com/dealii","followers_url":"https://api.github.com/users/dealii/followers","following_url":"https://api.github.com/users/dealii/following{/other_user}","gists_url":"https://api.github.com/users/dealii/gists{/gist_id}","starred_url":"https://api.github.com/users/dealii/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dealii/subscriptions","organizations_url":"https://api.github.com/users/dealii/orgs","repos_url":"https://api.github.com/users/dealii/repos","events_url":"https://api.github.com/users/dealii/events{/privacy}","received_events_url":"https://api.github.com/users/dealii/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/dealii/dealii","description":"The development repository for the deal.II finite element library.","fork":false,"url":"https://api.github.com/repos/dealii/dealii","forks_url":"https://api.github.com/repos/dealii/dealii/forks","keys_url":"https://api.github.com/repos/dealii/dealii/keys{/key_id}","collaborators_url":"https://api.github.com/repos/dealii/dealii/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/dealii/dealii/teams","hooks_url":"https://api.github.com/repos/dealii/dealii/hooks","issue_events_url":"https://api.github.com/repos/dealii/dealii/issues/events{/number}","events_url":"https://api.github.com/repos/dealii/dealii/events","assignees_url":"https://api.github.com/repos/dealii/dealii/assignees{/user}","branches_url":"https://api.github.com/repos/dealii/dealii/branches{/branch}","tags_url":"https://api.github.com/repos/dealii/dealii/tags","blobs_url":"https://api.github.com/repos/dealii/dealii/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/dealii/dealii/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/dealii/dealii/git/refs{/sha}","trees_url":"https://api.github.com/repos/dealii/dealii/git/trees{/sha}","statuses_url":"https://api.github.com/repos/dealii/dealii/statuses/{sha}","languages_url":"https://api.github.com/repos/dealii/dealii/languages","stargazers_url":"https://api.github.com/repos/dealii/dealii/stargazers","contributors_url":"https://api.github.com/repos/dealii/dealii/contributors","subscribers_url":"https://api.github.com/repos/dealii/dealii/subscribers","subscription_url":"https://api.github.com/repos/dealii/dealii/subscription","commits_url":"https://api.github.com/repos/dealii/dealii/commits{/sha}","git_commits_url":"https://api.github.com/repos/dealii/dealii/git/commits{/sha}","comments_url":"https://api.github.com/repos/dealii/dealii/comments{/number}","issue_comment_url":"https://api.github.com/repos/dealii/dealii/issues/comments{/number}","contents_url":"https://api.github.com/repos/dealii/dealii/contents/{+path}","compare_url":"https://api.github.com/repos/dealii/dealii/compare/{base}...{head}","merges_url":"https://api.github.com/repos/dealii/dealii/merges","archive_url":"https://api.github.com/repos/dealii/dealii/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/dealii/dealii/downloads","issues_url":"https://api.github.com/repos/dealii/dealii/issues{/number}","pulls_url":"https://api.github.com/repos/dealii/dealii/pulls{/number}","milestones_url":"https://api.github.com/repos/dealii/dealii/milestones{/number}","notifications_url":"https://api.github.com/repos/dealii/dealii/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/dealii/dealii/labels{/name}","releases_url":"https://api.github.com/repos/dealii/dealii/releases{/id}","created_at":"2014-07-17T14:00:26Z","updated_at":"2015-04-13T23:08:24Z","pushed_at":"2015-04-14T02:05:09Z","git_url":"git://github.com/dealii/dealii.git","ssh_url":"git@github.com:dealii/dealii.git","clone_url":"https://github.com/dealii/dealii.git","svn_url":"https://github.com/dealii/dealii","homepage":"http://www.dealii.org/","size":141273,"stargazers_count":50,"watchers_count":50,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":71,"mirror_url":null,"open_issues_count":88,"forks":71,"open_issues":88,"watchers":50,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/dealii/dealii/pulls/792"},"html":{"href":"https://github.com/dealii/dealii/pull/792"},"issue":{"href":"https://api.github.com/repos/dealii/dealii/issues/792"},"comments":{"href":"https://api.github.com/repos/dealii/dealii/issues/792/comments"},"review_comments":{"href":"https://api.github.com/repos/dealii/dealii/pulls/792/comments"},"review_comment":{"href":"https://api.github.com/repos/dealii/dealii/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/dealii/dealii/pulls/792/commits"},"statuses":{"href":"https://api.github.com/repos/dealii/dealii/statuses/94a64cbbfd46bcd05460fe57e08e35f26c2010b9"}}}}