<div dir="ltr"><div dir="ltr"><div dir="ltr">Thanks Junchao,<div><br></div><div>Sorry for the late reply.</div><div><br></div><div><div>time mpirun -n 2 ./matrix_sparsity-opt -matstash_legacy</div><div>Close matrix for np = 2 ... </div><div>Matrix successfully closed</div><div><br></div><div>real<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>0m1.963s</div><div>user<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>0m3.256s</div><div>sys<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>0m0.554s</div></div><div><br></div><div><br></div><div><div>time mpirun -n 2 ./matrix_sparsity-opt </div><div>Close matrix for np = 2 ... </div><div>Matrix successfully closed</div><div><br></div><div>real<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>0m2.351s</div><div>user<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>0m4.052s</div><div>sys<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>0m0.519s</div></div><div><br></div><div><br></div><div>A bit slower, but it might do not matter much.</div><div><br></div><div>Thanks,</div><div><br></div><div>Fande,</div></div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Jul 10, 2019 at 3:51 PM Zhang, Junchao <<a href="mailto:jczhang@mcs.anl.gov">jczhang@mcs.anl.gov</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div>
<div dir="ltr">
<div>Fande,</div>
<div> I ran your code with two processes and found the poor performance of PetscSortIntWithArrayPair()<font color="#795e26" face="Menlo, Monaco, Courier New, monospace"><span style="font-size:14px;white-space:pre-wrap">
</span></font>was due to duplicates. In particular, rank 0 has array length = 0 and rank 1 has array length = 4,180,070. On rank 1, each unique array value has ~95 duplicates; The duplicates are already clustered together before sorting. </div>
<div> The old quick sort algorithm has an O(n^2) complexity on these duplicates. I added a three-way-partition algorithm to split the array into <, =, >pivot parts and get these numbers:<br>
</div>
<div><br>
</div>
<div>Master:</div>
<div>$ time mpirun -n 2 ./ex_petsc_only<br>
real 0m55.359s<br>
user 1m7.807s<br>
sys 0m42.651s<br>
</div>
<div><br>
</div>
<div>Master:<br>
</div>
$ time mpirun -n 2 ./ex_petsc_only -matstash_legacy<br>
real 0m0.987s
<div>user 0m1.565s<br>
sys 0m0.285s<br>
<div><br>
</div>
<div>Three way partition <br>
</div>
<div>$ time mpirun -n 2 ./ex_petsc_only<br>
real 0m1.015s<br>
user 0m1.535s<br>
sys 0m0.392s<br>
</div>
<div><br>
</div>
<div>We can see the new sort algorithm gives a 55x speedup and can almost catch up with -matstash_legacy. So I think it is good to have no matter whether we will do hashing or not in mat assembly.</div>
<div>Please try branch jczhang/feature-better-quicksort-pivot on your side to see if it helps and if the segfault persist.</div>
</div>
<div>Thanks.</div>
<div><br>
</div>
<div>
<div dir="ltr" class="gmail-m_-5733272481460290581m_-971351454325516352gmail_signature">
<div dir="ltr">--Junchao Zhang</div>
</div>
</div>
<br>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Tue, Jul 9, 2019 at 10:18 AM Fande Kong <<a href="mailto:fdkong.jd@gmail.com" target="_blank">fdkong.jd@gmail.com</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div dir="ltr">Hi Junchao,
<div><br>
</div>
<div>If you are struggling on building the right package environment, here is a native PETSc example.</div>
<div><br>
</div>
<div><br>
</div>
<div>Fande,</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Mon, Jul 8, 2019 at 3:00 PM Fande Kong <<a href="mailto:fdkong.jd@gmail.com" target="_blank">fdkong.jd@gmail.com</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div dir="ltr">I guess John has a pure PETSc example,
<div><br>
</div>
<div>John, could you share the pure PETSc example with Junchao?</div>
<div><br>
</div>
<div><br>
</div>
<div>Fande,</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Mon, Jul 8, 2019 at 2:58 PM Fande Kong <<a href="mailto:fdkong.jd@gmail.com" target="_blank">fdkong.jd@gmail.com</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">Yes, here it is <a href="https://github.com/fdkong/matrixsparsity" target="_blank">https://github.com/fdkong/matrixsparsity</a></div>
<div dir="ltr"><br>
</div>
<div dir="ltr"><br>
</div>
<div>You need to follow instructions here to install MOOSE <a href="https://www.mooseframework.org/getting_started/installation/mac_os.html" style="font-family:-webkit-standard" target="_blank">https://www.mooseframework.org/getting_started/installation/mac_os.html</a></div>
<div><br>
</div>
<div><br>
</div>
<div>Thanks for your help.</div>
<div><br>
</div>
<div><br>
</div>
<div>Fande</div>
<div><br>
</div>
<div><br>
</div>
</div>
</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Mon, Jul 8, 2019 at 2:28 PM Zhang, Junchao <<a href="mailto:jczhang@mcs.anl.gov" target="_blank">jczhang@mcs.anl.gov</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div>
<div dir="ltr">Is the code public for me to test?<br clear="all">
<div>
<div dir="ltr" class="gmail-m_-5733272481460290581gmail-m_-971351454325516352gmail-m_-9115061302458457682gmail-m_-2885166069776582232gmail-m_4573310892421204611gmail-m_3570921407916004996gmail_signature">
<div dir="ltr">--Junchao Zhang</div>
</div>
</div>
<br>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Mon, Jul 8, 2019 at 3:06 PM Fande Kong <<a href="mailto:fdkong.jd@gmail.com" target="_blank">fdkong.jd@gmail.com</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">Thanks Junchao,
<div><br>
</div>
<div>Tried your code. I did not hit seg fault this time, but the assembly was still slow</div>
<div><br>
</div>
<div><br>
</div>
<div>
<div><i>time mpirun -n 2 ./matrix_sparsity-opt -matstash_legacy</i></div>
<div><i>Close matrix for np = 2 ... </i></div>
<div><i>Matrix successfully closed</i></div>
<div><i><br>
</i></div>
<div><i>real<span class="gmail-m_-5733272481460290581gmail-m_-971351454325516352gmail-m_-9115061302458457682gmail-m_-2885166069776582232gmail-m_4573310892421204611gmail-m_3570921407916004996gmail-m_7010248962814663902gmail-Apple-tab-span" style="white-space:pre-wrap">
</span>0m2.009s</i></div>
<div><i>user<span class="gmail-m_-5733272481460290581gmail-m_-971351454325516352gmail-m_-9115061302458457682gmail-m_-2885166069776582232gmail-m_4573310892421204611gmail-m_3570921407916004996gmail-m_7010248962814663902gmail-Apple-tab-span" style="white-space:pre-wrap">
</span>0m3.324s</i></div>
<div><i>sys<span class="gmail-m_-5733272481460290581gmail-m_-971351454325516352gmail-m_-9115061302458457682gmail-m_-2885166069776582232gmail-m_4573310892421204611gmail-m_3570921407916004996gmail-m_7010248962814663902gmail-Apple-tab-span" style="white-space:pre-wrap">
</span>0m0.575s</i></div>
</div>
<div><i><br>
</i></div>
<div><i><br>
</i></div>
<div><i><br>
</i></div>
<div><i><br>
</i></div>
<div>
<div><i> time mpirun -n 2 ./matrix_sparsity-opt</i></div>
<div><i>Close matrix for np = 2 ... </i></div>
<div><i>Matrix successfully closed</i></div>
<div><i><br>
</i></div>
<div><i>real<span class="gmail-m_-5733272481460290581gmail-m_-971351454325516352gmail-m_-9115061302458457682gmail-m_-2885166069776582232gmail-m_4573310892421204611gmail-m_3570921407916004996gmail-m_7010248962814663902gmail-Apple-tab-span" style="white-space:pre-wrap">
</span>3m39.235s</i></div>
<div><i>user<span class="gmail-m_-5733272481460290581gmail-m_-971351454325516352gmail-m_-9115061302458457682gmail-m_-2885166069776582232gmail-m_4573310892421204611gmail-m_3570921407916004996gmail-m_7010248962814663902gmail-Apple-tab-span" style="white-space:pre-wrap">
</span>6m42.184s</i></div>
<div><i>sys<span class="gmail-m_-5733272481460290581gmail-m_-971351454325516352gmail-m_-9115061302458457682gmail-m_-2885166069776582232gmail-m_4573310892421204611gmail-m_3570921407916004996gmail-m_7010248962814663902gmail-Apple-tab-span" style="white-space:pre-wrap">
</span>0m35.084s</i></div>
</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div>Fande,</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
</div>
</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Mon, Jul 8, 2019 at 8:47 AM Fande Kong <<a href="mailto:fdkong.jd@gmail.com" target="_blank">fdkong.jd@gmail.com</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div dir="ltr">Will let you know soon.
<div><br>
</div>
<div>Thanks,</div>
<div><br>
</div>
<div>Fande,</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Mon, Jul 8, 2019 at 8:41 AM Zhang, Junchao <<a href="mailto:jczhang@mcs.anl.gov" target="_blank">jczhang@mcs.anl.gov</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div>
<div dir="ltr">Fande or John,
<div> Could any of you have a try? Thanks<br clear="all">
<div>
<div dir="ltr" class="gmail-m_-5733272481460290581gmail-m_-971351454325516352gmail-m_-9115061302458457682gmail-m_-2885166069776582232gmail-m_4573310892421204611gmail-m_3570921407916004996gmail-m_7010248962814663902gmail-m_-1895403056174635030gmail-m_-2155594228863412009gmail_signature">
<div dir="ltr">--Junchao Zhang</div>
</div>
</div>
<br>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">---------- Forwarded message ---------<br>
From: <strong class="gmail_sendername" dir="auto">Junchao Zhang</strong> <span dir="auto">
<<a href="mailto:jczhang@mcs.anl.gov" target="_blank">jczhang@mcs.anl.gov</a>></span><br>
Date: Thu, Jul 4, 2019 at 8:21 AM<br>
Subject: Re: [petsc-dev] Slowness of PetscSortIntWithArrayPair in MatAssembly<br>
To: Fande Kong <<a href="mailto:fdkong.jd@gmail.com" target="_blank">fdkong.jd@gmail.com</a>><br>
</div>
<br>
<br>
<div dir="ltr">Fande,
<div> I wrote tests but could not reproduce the error. I pushed a commit that changed the MEDIAN macro to a function to make it easier to debug. Could you run and debug it again? It should be easy to see what is wrong in gdb.</div>
<div> Thanks.<br clear="all">
<div>
<div dir="ltr" class="gmail-m_-5733272481460290581gmail-m_-971351454325516352gmail-m_-9115061302458457682gmail-m_-2885166069776582232gmail-m_4573310892421204611gmail-m_3570921407916004996gmail-m_7010248962814663902gmail-m_-1895403056174635030gmail-m_-2155594228863412009m_144035119615210192gmail_signature">
<div dir="ltr">--Junchao Zhang</div>
</div>
</div>
<br>
</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Wed, Jul 3, 2019 at 6:48 PM Fande Kong <<a href="mailto:fdkong.jd@gmail.com" target="_blank">fdkong.jd@gmail.com</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div dir="ltr">
<div dir="ltr">
<div>Process 3915 resuming</div>
<div>Process 3915 stopped</div>
<div>* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=2, address=0x7ffee9b91fc8)</div>
<div> frame #0: 0x000000010cbaa031 libpetsc.3.011.dylib`PetscSortIntWithArrayPair_Private(L=0x0000000119fc5480, J=0x000000011bfaa480, K=0x000000011ff74480, right=13291) at sorti.c:298</div>
<div> 295 }</div>
<div> 296 PetscFunctionReturn(0);</div>
<div> 297 }</div>
<div>-> 298 i = MEDIAN(L,right);</div>
<div> 299 SWAP3(L[0],L[i],J[0],J[i],K[0],K[i],tmp);</div>
<div> 300 vl = L[0];</div>
<div> 301 last = 0;</div>
<div>(lldb) </div>
<div><br>
</div>
</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Wed, Jul 3, 2019 at 4:32 PM Zhang, Junchao <<a href="mailto:jczhang@mcs.anl.gov" target="_blank">jczhang@mcs.anl.gov</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div>
<div dir="ltr">Could you debug it or paste the stack trace? Since it is a segfault, it should be easy.<br clear="all">
<div>
<div dir="ltr" class="gmail-m_-5733272481460290581gmail-m_-971351454325516352gmail-m_-9115061302458457682gmail-m_-2885166069776582232gmail-m_4573310892421204611gmail-m_3570921407916004996gmail-m_7010248962814663902gmail-m_-1895403056174635030gmail-m_-2155594228863412009m_144035119615210192gmail-m_1673344408242934540gmail-m_1468549783054480917gmail_signature">
<div dir="ltr">--Junchao Zhang</div>
</div>
</div>
<br>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Wed, Jul 3, 2019 at 5:16 PM Fande Kong <<a href="mailto:fdkong.jd@gmail.com" target="_blank">fdkong.jd@gmail.com</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div dir="ltr">
<div dir="ltr">Thanks Junchao,
<div><br>
</div>
<div>But there is still segment fault. I guess you could write some continuous integers to test your changes.</div>
<div><br>
</div>
<div><br>
</div>
<div>Fande</div>
</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Wed, Jul 3, 2019 at 12:57 PM Zhang, Junchao <<a href="mailto:jczhang@mcs.anl.gov" target="_blank">jczhang@mcs.anl.gov</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div>
<div dir="ltr">Fande and John,
<div> Could you try jczhang/feature-better-quicksort-pivot? It passed Jenkins tests and I could not imagine why it failed on yours.</div>
<div> Hash table has its own cost. We'd better get quicksort right and see how it performs before rewriting code.
<div>
<div>
<div dir="ltr" class="gmail-m_-5733272481460290581gmail-m_-971351454325516352gmail-m_-9115061302458457682gmail-m_-2885166069776582232gmail-m_4573310892421204611gmail-m_3570921407916004996gmail-m_7010248962814663902gmail-m_-1895403056174635030gmail-m_-2155594228863412009m_144035119615210192gmail-m_1673344408242934540gmail-m_1468549783054480917gmail-m_2709600366731929773gmail-m_6314895454840214167gmail_signature">
<div dir="ltr">--Junchao Zhang</div>
</div>
</div>
<br>
</div>
</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Tue, Jul 2, 2019 at 2:37 PM Fande Kong <<a href="mailto:fdkong.jd@gmail.com" target="_blank">fdkong.jd@gmail.com</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">YOUR APPLICATION TERMINATED WITH THE EXIT STRING: Segmentation fault: 11 (signal 11)<br>
</div>
<div dir="ltr"><br>
</div>
<div>Segmentation fault :-)</div>
<div><br>
</div>
<div><br>
</div>
<div>As Jed said, it might be a good idea to rewrite the code using the hashing table.</div>
<div><br>
</div>
<div><br>
</div>
<div>Fande,</div>
<div dir="ltr"><br>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Tue, Jul 2, 2019 at 1:27 PM Zhang, Junchao <<a href="mailto:jczhang@mcs.anl.gov" target="_blank">jczhang@mcs.anl.gov</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div>
<div dir="ltr">
<div>Try this to see if it helps:</div>
<div><br>
</div>
diff --git a/src/sys/utils/sorti.c b/src/sys/utils/sorti.c<br>
index 1b07205a..90779891 100644<br>
--- a/src/sys/utils/sorti.c<br>
+++ b/src/sys/utils/sorti.c<br>
@@ -294,7 +294,8 @@ static PetscErrorCode PetscSortIntWithArrayPair_Private(PetscInt *L,PetscInt *J,<br>
}<br>
PetscFunctionReturn(0);<br>
}<br>
- SWAP3(L[0],L[right/2],J[0],J[right/2],K[0],K[right/2],tmp);<br>
+ i = MEDIAN(L,right);<br>
+ SWAP3(L[0],L[i],J[0],J[i],K[0],K[i],tmp);<br>
vl = L[0];<br>
last = 0;<br>
for (i=1; i<=right; i++) {<br>
<br>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Tue, Jul 2, 2019 at 12:14 PM Fande Kong via petsc-dev <<a href="mailto:petsc-dev@mcs.anl.gov" target="_blank">petsc-dev@mcs.anl.gov</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">BTW,
<div><br>
</div>
<div>PetscSortIntWithArrayPair is used in MatStashSortCompress_Private.<br>
</div>
<div><br>
</div>
<div>Any way to avoid to use PetscSortIntWithArrayPair in MatStashSortCompress_Private? </div>
<div><br>
</div>
<div>Fande,</div>
</div>
</div>
</div>
</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Tue, Jul 2, 2019 at 11:09 AM Fande Kong <<a href="mailto:fdkong.jd@gmail.com" target="_blank">fdkong.jd@gmail.com</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">Hi Developers,<br>
<div><br>
</div>
<div>John just noticed that the matrix assembly was slow when having sufficient amount of off-diagonal entries. It was not a MPI issue since I was able to reproduce the issue using two cores on my desktop, that is, "mpirun -n 2".</div>
<div><br>
</div>
<div>I turned on a profiling, and 99.99% of the time was spent on PetscSortIntWithArrayPair (recursively calling). It took THREE MINUTES to get the assembly done. And then changed to use the option "-matstash_legacy" to restore </div>
<div>the code to the old assembly routine, and the same code took ONE SECOND to get the matrix assembly done. </div>
<div><br>
</div>
<div>Should write any better sorting algorithms?</div>
<div><br>
</div>
<div><br>
</div>
<div>Fande,</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</blockquote>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</blockquote>
</div>
</blockquote>
</div>
</div>
</blockquote>
</div>
</blockquote>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</blockquote>
</div>
</blockquote>
</div>
</div>
</blockquote>
</div>
</blockquote>
</div>
</blockquote>
</div>
</blockquote>
</div>
</div>
</blockquote></div>