CHOLMOD default ordering options: METIS vs AMD #548
Comments
|
It seems the first order of business should be to see what is driving those allocations and fix that. |
|
Can you reproduce this behaviour? If I see it correctly, |
|
Yes, I see the same thing with 1.10.4. The allocations are all in |
|
@KristofferC Any ideas? |
|
Not immediately, but I will do a bisection and start from there. |
|
Bisected to JuliaLang/julia#48977 on the julia side. |
|
Reverting to SuiteSparse_jll 5.10.1 seems to fix it (basically reverting the cc @rayegun |
|
But the offending line is just a 1-liner that is showing 2M Julia allocations - that suggests the issue is not in SuiteSparse. |
This is not accurate because we register the CHOLMOD allocation functions with our GC: SparseArrays.jl/src/solvers/cholmod.jl Lines 242 to 246 in e61663a so even allocations within CHOLMOD are counted in julia> @profile CHOLMOD.cholmod_l_analyze(S, g)
julia> Profile.print(noisefloor=2, C=true)it seems to be in CHOLMOD a lot: |
|
I don't know if the lack of multithreading is coupled to the increase in allocations but both performance and allocations seems to be worse when going from v5 -> v7. |
|
Ok - that's good to know. So should we report the issue upstream then? |
|
On v5, I only see the following in the profile: |
|
SuiteSparse 7 comes with METIS built in for partitioning, which is where it seems most of the time is being spent. Is this kind of thing expected from METIS? Perhaps @fredrikekre has some experience with it. |
Maybe, assuming it isn't our fault due to different build options etc. The following is a decent Julia reproducer at least: using SparseArrays, LinearAlgebra
using SparseArrays: CHOLMOD, LibSuiteSparse
function setup(n)
e = ones(n)
e2 = -ones(n-1)
K = spdiagm(n, n, 0 => 2.0e, 1 => e2, -1 => e2)
Id = sparse(1.0*I, n, n)
return kron(K, Id) + kron(Id, K)
end
n = 1157;
A = setup(n);
F = ones(n^2);
S = CHOLMOD.Sparse(A);
g = CHOLMOD.getcommon()
using .LibSuiteSparse: libcholmod, cholmod_l_analyze, cholmod_sparse, cholmod_common, cholmod_factor
@time @ccall libcholmod.cholmod_l_analyze(S::Ptr{cholmod_sparse},
g::Ptr{cholmod_common})::Ptr{cholmod_factor}1.9: 1.10: |
|
@DrTimothyAldenDavis Is this kind of slowdown expected when METIS kicks in? |
|
METIS produces good orderings but it takes a very long time, particularly for single analyze/factorize/solves. The default ordering is to try AMD. Then if AMD produces a good ordering I use that. Otherwise, I try METIS. You can disable METIS. See page 104 of the user guide for CHOLMOD 5.2.1. Or the cholmod.h include file here: |
|
@DrTimothyAldenDavis I assume METIS can also be disabled in SuiteSparse 7. |
|
Yes, CHOLMOD 5.2.1 is the most recent stable release of CHOLMOD, in SuiteSparse 7.7.0. |
|
Ah thank you. I misread CHOLMOD 5 to mean SuiteSparse 5. |
|
Thank you for all the discussion. Running @SparseArrays.CHOLMOD.cholmod_param nmethods = 2 solve(1157);gives back the behaviour from julia 1.9.3. Now, I am wondering whether this should be used automatically if the user just wants to solve a single system? |
That might be a good idea. It would be the least disruptive to the performance seen in julia. |
|
p.s. The title of this issue could be revised, to something like "CHOLMOD default ordering options: METIS vs AMD". |
gerw
changed the title
cholmod no longer uses multithreading?
And somewhere in the documentation, one should point to the possibility of increasing This being said, I cannot find any reference to the cholesky decomposition from SparseArrays in the documentation? |
|
The documentation for the solvers has been, uh, sparse. But I don't know why it doesn't show up at all. We should at least have the solvers show up in Julia docs like they do in SparseArrays docs. I suspect the index.md from SparseArrays just gets picked up and none of the other files do when Julia stdlib docs are built. So perhaps we should just integrate solvers.md in to index.md and have one big file for all SparseArrays.jl documentation. Based on the discussion and findings here, METIS should certainly opt-in and documented. As for threads, I suppose we should use threading by default. Would you be up for making a PR? |
Uh, I don't know, rather not. I do not have set up the infrastructure to build julia (or at least SparseArrays)... |
|
I'll get around to it in the next few days, unless someone beats me to it. |
|
@DrTimothyAldenDavis Is it possible to change the number of threads for |
|
Yes, just change the Common->nthreads_max, for the "Common" object passed in as the last parameter to all CHOLMOD methods. |
Consider the following snippet
It just builds a discretization of a PDE and solves it. Now let us execute
Using
julia 1.9.3I getand all is fine. With
julia 1.10.4instead I getThus, the second solve on a slightly larger system is suddenly much slower and allocates memory. The profiling shows that
cholmod_l_analyzeruns much longer. The same happens with the RC of 1.11.Digging a little bit deeper with
and looking at the output of
top, one can see thatsymbolicruns only on a single core and allocates memory,cholesky!seems to be fine (and seems to run in parallel).I also tried to fiddle around with
(which is
1) after startup, but it does not seem to change anything.The text was updated successfully, but these errors were encountered: