Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Halve the calls of FindCommonElements #21

Open
pvc1989 opened this issue Sep 23, 2020 · 1 comment
Open

Halve the calls of FindCommonElements #21

pvc1989 opened this issue Sep 23, 2020 · 1 comment

Comments

@pvc1989
Copy link
Contributor

pvc1989 commented Sep 23, 2020

When I run mpmetis on a 4,000,000-element mesh, the function named FindCommonElements() costs about 11% of the total running time:

  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 19.52      0.98     0.98     1510     0.00     0.00  libmetis__Match_SHEM
 18.13      1.89     0.91     1511     0.00     0.00  libmetis__CreateCoarseGraph
 13.15      2.55     0.66        1     0.66     0.66  libmetis__Match_RM
 11.36      3.12     0.57  8000000     0.00     0.00  libmetis__FindCommonElements
  5.58      3.40     0.28        1     0.28     0.85  libmetis__CreateGraphDual

It is called in two loops in CreateGraphDual():

  • The only purpose for the first loop is to get the total number of neighbours, i.e. xadj[ne] after L208, which is then used to allocate adjncy in L213.
  • The second loop then do the real job, which has already done by the first one.

These two loops could be merged into one, if something supports push_back() like std::vector<int> was introduced.
If so, the total running time might be reduced by about 5%.

@karypis
Copy link
Contributor

karypis commented Oct 27, 2020

Good call.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants