<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body>
<div dir="ltr">Is the code public for me to test?<br clear="all">
<div>
<div dir="ltr" class="gmail_signature" data-smartmail="gmail_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">fdkong.jd@gmail.com</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid 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_7010248962814663902gmail-Apple-tab-span" style="white-space:pre-wrap">
</span>0m2.009s</i></div>
<div><i>user<span class="gmail-m_7010248962814663902gmail-Apple-tab-span" style="white-space:pre-wrap">
</span>0m3.324s</i></div>
<div><i>sys<span class="gmail-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_7010248962814663902gmail-Apple-tab-span" style="white-space:pre-wrap">
</span>3m39.235s</i></div>
<div><i>user<span class="gmail-m_7010248962814663902gmail-Apple-tab-span" style="white-space:pre-wrap">
</span>6m42.184s</i></div>
<div><i>sys<span class="gmail-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:1px solid 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:1px solid 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_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_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:1px solid 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:1px solid 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_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:1px solid 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:1px solid 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_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:1px solid 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:1px solid 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:1px solid 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:1px solid 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>
</body>
</html>