Thanks so much for the help. Lint.jl does catch the use of global. Well, it
says it's "undefined" because it hasn't been defined yet... I guess this is
a good reason to put methods first.
Let me see how this does after a few more complex modifications!
David
On Monday, April 6, 2015 at 3:35:58 PM UTC-4, Tony Kelman wrote:
>
> 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
>>>>
>>>
