Ah, that explains it. I'm not sure if there's a way to disable or warn on
non-const globals, but it's a good question. @code_warntype did a pretty
good job at pinpointing the problems they caused, and Lint.jl also might
have caught them (would need to try it).
On Monday, April 6, 2015 at 9:42:45 AM UTC-7, David Gleich wrote:
>
> 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
>>>
>>
