Making the change
length(nzrange(P.A,u)) for du and dv
fixes the issue. (Of course.)
Is there any way to disable non-const global variables within a function?
(Or warn when they are used?)
David
On Saturday, April 4, 2015 at 4:08:38 AM UTC-4, Tony Kelman wrote:
>
> This is an excellent use case for the @code_warntype macro. You can
> quickly see that rowval, n, x, r, pushval, nzi, v, rvold, rvnew, and
> several temporary variables are ending up as Any or underspecified Array
> type. A few things you can do to help:
>
> - give the A field of the PageRankProblem type more specific type
> parameters, A::SparseMatrixCSC{Float64, Int64} so the type of rowval can be
> inferred
> - change n = size(A,1) to n = size(P.A, 1); otherwise you're referring to
> the global variable A
> - use the colptr version instead of length(nzrange(A,u)) for du, and
> similarly for dv - for some reason the length of the output of nzrange
> can't be inferred as an Int, this might be a bug worth reporting
>
> Those 3 changes get it to within a factor of 2 of C++ on my machine.
>
> -Tony
>
>
> On Friday, April 3, 2015 at 6:22:43 PM UTC-7, David Gleich wrote:
>>
>> I'm trying to figure out why the following algorithm is so slow in Julia.
>>
>> $ julia pprpush_perf4.jl
>> elapsed time: 0.754419672 seconds # first run, no compiled
>> elapsed time: 0.627998826 seconds # second run, compiled
>> elapsed time: 0.616043857 seconds (292 MB allocated, 1.52% gc time in 14
>> pauses with 0 full sweep) # third run, with @time
>> True = 0.026124014066724 # make sure the result is correct
>> x[0] = 0.026124014066724
>>
>> $ rm a.out; g++ -O2 pprpush_perf.cpp; ./a.out
>>
>> Elapsed 0.010623 seconds. # second run of the algorithm in C++
>>
>> True = 0.026124014066724 # make sure the result is correct
>> x[0] = 0.026124014066724
>> y[0] = 0.026124014066724
>>
>> So Julia is ~60x slower than the equivalent C++ code.
>>
>> I've attached the code for both procedures for the complete code, but
>> here's the key algorithm. This is the PageRank "push" procedure due to
>> Andersen, Chung, and Lang (FOCS 2006).
>>
>> Basically, it does random access to the rows or columns of a sparse
>> matrix (whichever is faster, because it assumes the sparse matrix is the
>> adjacency matrix of an undirected graph).
>>
>> I tried a few different things to speed it up in Julia, but nothing
>> seemed to work. Any thoughts?
>>
>> function ppr_push(P::PageRankProblem, eps::Float64)
>> # extract the sparse data structure
>> #colptr = P.A.colptr
>> rowval = rowvals(P.A) # P.A is just a julia sparse matrix
>> n = size(A,1)
>>
>> # create the initial solution and residual
>> x = zeros(n,1)
>> r = zeros(n,1)
>>
>> r[P.seed] = 1.
>>
>> q = [P.seed]
>>
>> pushcount = 0
>> pushvol = 0
>> maxpush = 1./(eps*(1.-P.alpha))
>>
>> while length(q) > 0 && pushcount <= maxpush
>> pushcount += 1
>> u = shift!(q) # I've tried DataStructures Queue here, but no
>> change
>> #du = convert(Float64,colptr[u+1]-colptr[u]) # get the degree
>> #du = Float64(colptr[u+1]-colptr[u])
>> du = Float64(length(nzrange(A,u)))
>> pushval = r[u] - 0.5*eps*du
>> x[u] += (1-P.alpha)*pushval
>> r[u] = 0.5*eps*du
>>
>> #@printf("pushing on %4i with resid %.9f rho=%f\n", u, pushval,
>> rho)
>>
>> pushval = pushval*P.alpha/du
>>
>> #for nzi in colptr[u]:(colptr[u+1] - 1)
>> for nzi in nzrange(P.A,u)
>> pushvol += 1
>> v = rowval[nzi]
>> #dv = convert(Float64,colptr[v+1]-colptr[v]) # degree of v
>> dv = Float64(length(nzrange(A,v)))
>> rvold = r[v]
>> rvnew = rvold + pushval
>> r[v] = rvnew
>> if rvnew > eps*dv && rvold <= eps*dv
>> push!(q,v)
>> end
>> end
>> end
>>
>> return x, r, pushcount, pushvol
>>
>> end
>>
>> Thanks,
>> David Gleich
>>
>
