[julia-users] Avoid memory allocations when reading from matrices
Reposting this from Gitter chat since it seems this is more active.
I'm writing a GloVe module to learn Julia.
How can I avoid memory allocations? My main function deals with a lot of
random indexing in Matrices.
A[i, :] = 0.5 * B[i, :]
In this case* i* isn't from a linear sequence. I'm not sure that matters.
Anyway, I've done analysis and I know B[i, :] is the issue here since it's
creating a copy.
https://github.com/JuliaLang/julia/blob/master/base/array.jl#L309 makes the
copy
I tried to do it via loop but it looks like that doesn't help either. In
fact, it seems to allocate slight more memory which seems really odd.
Here's some of the code, it's a little messy since I'm commenting different
approaches I'm trying out.
type Model{T}
W_main::Matrix{T}
W_ctx::Matrix{T}
b_main::Vector{T}
b_ctx::Vector{T}
W_main_grad::Matrix{T}
W_ctx_grad::Matrix{T}
b_main_grad::Vector{T}
b_ctx_grad::Vector{T}
covec::Vector{Cooccurence}
end
# Each vocab word in associated with a main vector and a context vector.
# The paper initializes the to values [-0.5, 0.5] / vecsize+1 and
# the gradients to 1.0.
#
# The +1 term is for the bias.
function Model(comatrix; vecsize=100)
vs = size(comatrix, 1)
Model(
(rand(vecsize, vs) - 0.5) / (vecsize + 1),
(rand(vecsize, vs) - 0.5) / (vecsize + 1),
(rand(vs) - 0.5) / (vecsize + 1),
(rand(vs) - 0.5) / (vecsize + 1),
ones(vecsize, vs),
ones(vecsize, vs),
ones(vs),
ones(vs),
CoVector(comatrix), # not required in 0.4
)
end
# TODO: figure out memory issue
# the memory comments are from 500 loop test with vecsize=100
function train!(m::Model, s::Adagrad; xmax=100, alpha=0.75)
J = 0.0
shuffle!(m.covec)
vecsize = size(m.W_main, 1)
eltype = typeof(m.b_main[1])
vm = zeros(eltype, vecsize)
vc = zeros(eltype, vecsize)
grad_main = zeros(eltype, vecsize)
grad_ctx = zeros(eltype, vecsize)
for n=1:s.niter
# shuffle indices
for i = 1:length(m.covec)
@inbounds l1 = m.covec[i].i # main index
@inbounds l2 = m.covec[i].j # context index
@inbounds v = m.covec[i].v
vm[:] = m.W_main[:, l1]
vc[:] = m.W_ctx[:, l2]
diff = dot(vec(vm), vec(vc)) + m.b_main[l1] + m.b_ctx[l2] -
log(v)
fdiff = ifelse(v < xmax, (v / xmax) ^ alpha, 1.0) * diff
J += 0.5 * fdiff * diff
fdiff *= s.lrate
# inc memory by ~200 MB && running time by 2x
grad_main[:] = fdiff * m.W_ctx[:, l2]
grad_ctx[:] = fdiff * m.W_main[:, l1]
# Adaptive learning
# inc ~ 600MB + 0.75s
#= @inbounds for ii = 1:vecsize =#
#= m.W_main[ii, l1] -= grad_main[ii] /
sqrt(m.W_main_grad[ii, l1]) =#
#= m.W_ctx[ii, l2] -= grad_ctx[ii] / sqrt(m.W_ctx_grad[ii,
l2]) =#
#= m.b_main[l1] -= fdiff ./ sqrt(m.b_main_grad[l1]) =#
#= m.b_ctx[l2] -= fdiff ./ sqrt(m.b_ctx_grad[l2]) =#
#= end =#
m.W_main[:, l1] -= grad_main ./ sqrt(m.W_main_grad[:, l1])
m.W_ctx[:, l2] -= grad_ctx ./ sqrt(m.W_ctx_grad[:, l2])
m.b_main[l1] -= fdiff ./ sqrt(m.b_main_grad[l1])
m.b_ctx[l2] -= fdiff ./ sqrt(m.b_ctx_grad[l2])
# Gradients
fdiff *= fdiff
m.W_main_grad[:, l1] += grad_main .^ 2
m.W_ctx_grad[:, l2] += grad_ctx .^ 2
m.b_main_grad[l1] += fdiff
m.b_ctx_grad[l2] += fdiff
end
#= if n % 10 == 0 =#
#= println("iteration $n, cost $J") =#
#= end =#
end
end
Here's the entire repo https://github.com/domluna/GloVe.jl. Might be
helpful.
I tried doing some loops but it allocates more memory (oddly enough) and
gets slower.
You'll notice the word vectors are indexed by column, I changed the
representation to that
seeing if it would make a difference during the loop. It didn't seem to.
The memory analysis showed
Julia Version 0.4.0-dev+4893
Commit eb5da26* (2015-05-19 11:51 UTC)
Platform Info:
System: Darwin (x86_64-apple-darwin14.4.0)
CPU: Intel(R) Core(TM) i5-2557M CPU @ 1.70GHz
WORD_SIZE: 64
BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Sandybridge)
LAPACK: libopenblas
LIBM: libopenlibm
LLVM: libLLVM-3.3
Here model consists of 100x19 Matrices and 100 element vectors, 19 words in
the vocab, 100 element word vector.
@time GloVe.train!(model, GloVe.Adagrad(500))
1.990 seconds (6383 k allocations: 1162 MB, 10.82% gc time)
0.3 has is a bit slower due to worse gc but same memory.
Any help would be greatly appreciated!
Re: [julia-users] Avoid memory allocations when reading from matrices
Loops should run without allocations. Can you post your loop-code?
> A[i, :] = 0.5 * B[i, :]
To state the obvious, as loop:
for j=1:size(A,2)
A[i,j] = 0.5 * B[i,j]
end
this shouldn't allocate, if i is an integer. Unless A and B have
different type, then allocation might happen.
On Sun, 2015-05-24 at 05:00, Dom Luna wrote:
> Reposting this from Gitter chat since it seems this is more active.
>
> I'm writing a GloVe module to learn Julia.
>
> How can I avoid memory allocations? My main function deals with a lot of
> random indexing in Matrices.
>
> A[i, :] = 0.5 * B[i, :]
>
> In this case* i* isn't from a linear sequence. I'm not sure that matters.
> Anyway, I've done analysis and I know B[i, :] is the issue here since it's
> creating a copy.
>
> https://github.com/JuliaLang/julia/blob/master/base/array.jl#L309 makes the
> copy
>
>
> I tried to do it via loop but it looks like that doesn't help either. In
> fact, it seems to allocate slight more memory which seems really odd.
>
> Here's some of the code, it's a little messy since I'm commenting different
> approaches I'm trying out.
>
> type Model{T}
> W_main::Matrix{T}
> W_ctx::Matrix{T}
> b_main::Vector{T}
> b_ctx::Vector{T}
> W_main_grad::Matrix{T}
> W_ctx_grad::Matrix{T}
> b_main_grad::Vector{T}
> b_ctx_grad::Vector{T}
> covec::Vector{Cooccurence}
> end
>
> # Each vocab word in associated with a main vector and a context vector.
> # The paper initializes the to values [-0.5, 0.5] / vecsize+1 and
> # the gradients to 1.0.
> #
> # The +1 term is for the bias.
> function Model(comatrix; vecsize=100)
> vs = size(comatrix, 1)
> Model(
> (rand(vecsize, vs) - 0.5) / (vecsize + 1),
> (rand(vecsize, vs) - 0.5) / (vecsize + 1),
> (rand(vs) - 0.5) / (vecsize + 1),
> (rand(vs) - 0.5) / (vecsize + 1),
> ones(vecsize, vs),
> ones(vecsize, vs),
> ones(vs),
> ones(vs),
> CoVector(comatrix), # not required in 0.4
> )
> end
>
> # TODO: figure out memory issue
> # the memory comments are from 500 loop test with vecsize=100
> function train!(m::Model, s::Adagrad; xmax=100, alpha=0.75)
> J = 0.0
> shuffle!(m.covec)
>
> vecsize = size(m.W_main, 1)
> eltype = typeof(m.b_main[1])
> vm = zeros(eltype, vecsize)
> vc = zeros(eltype, vecsize)
> grad_main = zeros(eltype, vecsize)
> grad_ctx = zeros(eltype, vecsize)
>
> for n=1:s.niter
> # shuffle indices
> for i = 1:length(m.covec)
> @inbounds l1 = m.covec[i].i # main index
> @inbounds l2 = m.covec[i].j # context index
> @inbounds v = m.covec[i].v
>
> vm[:] = m.W_main[:, l1]
> vc[:] = m.W_ctx[:, l2]
>
> diff = dot(vec(vm), vec(vc)) + m.b_main[l1] + m.b_ctx[l2] -
> log(v)
> fdiff = ifelse(v < xmax, (v / xmax) ^ alpha, 1.0) * diff
> J += 0.5 * fdiff * diff
>
> fdiff *= s.lrate
> # inc memory by ~200 MB && running time by 2x
> grad_main[:] = fdiff * m.W_ctx[:, l2]
> grad_ctx[:] = fdiff * m.W_main[:, l1]
>
> # Adaptive learning
> # inc ~ 600MB + 0.75s
> #= @inbounds for ii = 1:vecsize =#
> #= m.W_main[ii, l1] -= grad_main[ii] /
> sqrt(m.W_main_grad[ii, l1]) =#
> #= m.W_ctx[ii, l2] -= grad_ctx[ii] / sqrt(m.W_ctx_grad[ii,
> l2]) =#
> #= m.b_main[l1] -= fdiff ./ sqrt(m.b_main_grad[l1]) =#
> #= m.b_ctx[l2] -= fdiff ./ sqrt(m.b_ctx_grad[l2]) =#
> #= end =#
>
> m.W_main[:, l1] -= grad_main ./ sqrt(m.W_main_grad[:, l1])
> m.W_ctx[:, l2] -= grad_ctx ./ sqrt(m.W_ctx_grad[:, l2])
> m.b_main[l1] -= fdiff ./ sqrt(m.b_main_grad[l1])
> m.b_ctx[l2] -= fdiff ./ sqrt(m.b_ctx_grad[l2])
>
> # Gradients
> fdiff *= fdiff
> m.W_main_grad[:, l1] += grad_main .^ 2
> m.W_ctx_grad[:, l2] += grad_ctx .^ 2
> m.b_main_grad[l1] += fdiff
> m.b_ctx_grad[l2] += fdiff
> end
>
> #= if n % 10 == 0 =#
> #= println("iteration $n, cost $J") =#
> #= end =#
> end
> end
>
>
> Here's the entire repo https://github.com/domluna/GloVe.jl. Might be
> helpful.
>
> I tried doing some loops but it allocates more memory (oddly enough) and
> gets slower.
>
> You'll notice the word vectors are indexed by column, I changed the
> representation to that
> seeing if it would make a difference during the loop. It didn't seem to.
>
> The memory analysis showed
>
> Julia Version 0.4.0-dev+4893
> Commit eb5da26* (2015-05-19 11:51 UTC)
> Platform Info:
> System: Darwin (x86_64-apple-darwin14.4.0)
> CPU: Intel(R) Core(TM) i5-2557M CPU @ 1.70GHz
> WORD_SIZE: 64
> BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Sandybridge)
> LAPACK: libopenblas
> LIBM: libopenlibm
> LLVM: lib
Re: [julia-users] Avoid memory allocations when reading from matrices
Loop code
# TODO: figure out memory issuefunction train!(m::Model, s::Adagrad; xmax=100,
alpha=0.75)J = 0.0shuffle!(m.covec)vecsize = size(m.W_main, 1)
eltype = typeof(m.b_main[1])vm = zeros(eltype, vecsize)vc =
zeros(eltype, vecsize)grad_main = zeros(eltype, vecsize)grad_ctx =
zeros(eltype, vecsize)for n=1:s.niter# shuffle indicesfor i
= 1:length(m.covec)@inbounds l1 = m.covec[i].i # main index
@inbounds l2 = m.covec[i].j # context index@inbounds v =
m.covec[i].v#= vm[:] = m.W_main[:, l1] =##= vc[:] =
m.W_ctx[:, l2] =#@inbounds for j = 1:vecsizevm[j] =
m.W_main[j, l1]vc[j] = m.W_ctx[j, l2]end
diff = dot(vec(vm), vec(vc)) + m.b_main[l1] + m.b_ctx[l2] - log(v)
fdiff = ifelse(v < xmax, (v / xmax) ^ alpha, 1.0) * diffJ += 0.5 *
fdiff * difffdiff *= s.lrate# inc memory by ~200 MB &&
running time by 2x#= grad_main[:] = fdiff * m.W_ctx[:, l2] =#
#= grad_ctx[:] = fdiff * m.W_main[:, l1] =#@inbounds for j =
1:vecsizegrad_main[j] = fdiff * m.W_ctx[j, l2]
grad_ctx[j] = fdiff * m.W_main[j, l1]end# Adaptive
learning# inc ~ 600MB + 0.75s#= m.W_main[:, l1] -=
grad_main ./ sqrt(m.W_main_grad[:, l1]) =##= m.W_ctx[:, l2] -=
grad_ctx ./ sqrt(m.W_ctx_grad[:, l2]) =##= m.b_main[l1] -= fdiff ./
sqrt(m.b_main_grad[l1]) =##= m.b_ctx[l2] -= fdiff ./
sqrt(m.b_ctx_grad[l2]) =#@inbounds for j = 1:vecsize
m.W_main[j, l1] -= grad_main[j] / sqrt(m.W_main_grad[j, l1])
m.W_ctx[j, l2] -= grad_ctx[j] / sqrt(m.W_ctx_grad[j, l2])end
m.b_main[l1] -= fdiff ./ sqrt(m.b_main_grad[l1])m.b_ctx[l2] -=
fdiff ./ sqrt(m.b_ctx_grad[l2])# Gradientsfdiff *=
fdiff#= m.W_main_grad[:, l1] += grad_main .^ 2 =##=
m.W_ctx_grad[:, l2] += grad_ctx .^ 2 =##= m.b_main_grad[l1] +=
fdiff =##= m.b_ctx_grad[l2] += fdiff =#@inbounds for j
= 1:vecsizem.W_main_grad[j, l1] += grad_main[j] ^ 2
m.W_ctx_grad[j, l2] += grad_ctx[j] ^ 2end
m.b_main_grad[l1] += fdiffm.b_ctx_grad[l2] += fdiffend
#= if n % 10 == 0 =##= println("iteration $n, cost $J") =#
#= end =#endend
Mixmax [https://emailapps.mixmax.com/img/badge_mixmax.png]
[https://mixmax.com/r/YQkS9vBkBR3wSpESz] Not using Mixmax yet?
[https://mixmax.com/r/YQkS9vBkBR3wSpESz]
And the respective timings
@time GloVe.train!(model, GloVe.Adagrad(500)) 7.097 seconds (96237 k
allocations: 1468 MB, 7.01% gc time)
Slower and more memory.
On Sun, May 24, 2015 at 4:21 AM, Mauro < mauro...@runbox.com
[mauro...@runbox.com] > wrote:
Loops should run without allocations. Can you post your loop-code?
> A[i, :] = 0.5 * B[i, :]
To state the obvious, as loop:
for j=1:size(A,2)
A[i,j] = 0.5 * B[i,j]
end
this shouldn't allocate, if i is an integer. Unless A and B have
different type, then allocation might happen.
On Sun, 2015-05-24 at 05:00, Dom Luna < dluna...@gmail.com [dluna...@gmail.com]
> wrote:
> Reposting this from Gitter chat since it seems this is more active.
>
> I'm writing a GloVe module to learn Julia.
>
> How can I avoid memory allocations? My main function deals with a lot of
> random indexing in Matrices.
>
> A[i, :] = 0.5 * B[i, :]
>
> In this case* i* isn't from a linear sequence. I'm not sure that matters.
> Anyway, I’ve done analysis and I know B[i, :] is the issue here since it’s
> creating a copy.
>
> https://github.com/JuliaLang/ julia/blob/master/base/array. jl#L309
[https://github.com/JuliaLang/julia/blob/master/base/array.jl#L309] makes the
> copy
>
>
> I tried to do it via loop but it looks like that doesn’t help either. In
> fact, it seems to allocate slight more memory which seems really odd.
>
> Here’s some of the code, it’s a little messy since I’m commenting different
> approaches I’m trying out.
>
> type Model{T}
> W_main::Matrix{T}
> W_ctx::Matrix{T}
> b_main::Vector{T}
> b_ctx::Vector{T}
> W_main_grad::Matrix{T}
> W_ctx_grad::Matrix{T}
> b_main_grad::Vector{T}
> b_ctx_grad::Vector{T}
> covec::Vector{Cooccurence}
> end
>
> # Each vocab word in associated with a main vector and a context vector.
> # The paper initializes the to values [-0.5, 0.5] / vecsize+1 and
> # the gradients to 1.0.
> #
> # The +1 term is for the bias.
> function Model(comatrix; vecsize=100)
> vs = size(comatrix, 1)
> Model(
> (rand(vecsize, vs) - 0.5) / (vecsize + 1),
> (rand(vecsize, vs) - 0.5) / (vecsize + 1),
> (rand(vs) - 0.5) / (vecsize + 1),
> (rand(vs) - 0.5) / (vecsize + 1),
> ones(vecsize, vs),
> ones(vecsize, vs),
> ones(vs),
> ones(vs),
> CoVector(comatrix), # n
Re: [julia-users] Avoid memory allocations when reading from matrices
The problem is in:
type Model{T}
W_main::Matrix{T}
W_ctx::Matrix{T}
b_main::Vector{T}
b_ctx::Vector{T}
W_main_grad::Matrix{T}
W_ctx_grad::Matrix{T}
b_main_grad::Vector{T}
b_ctx_grad::Vector{T}
covec::Vector{Cooccurence} # <- needs to be concrete type
end
Instead use
covec::Vector{Cooccurence{Int,Int,T}}
or some more complicated parameterisation.
Then, when testing timings you usually do one warm-up to exclude
compilation time:
GloVe.train!(model, solver) # warm up
@time 1 # @time needs a warm up too
@time GloVe.train!(model, solver)
Timings I get:
stock clone from github:
elapsed time: 0.001617218 seconds (2419024 bytes allocated)
with improvements mentioned above:
elapsed time: 0.001344645 seconds (2335552 bytes allocated)
with improvements mentioned above and your loop-version:
elapsed time: 0.00030488 seconds (3632 bytes allocated)
Hope that helps.
On Sun, 2015-05-24 at 19:21, Dominique Luna wrote:
> Loop code
>
>
> # TODO: figure out memory issue
> function train!(m::Model, s::Adagrad; xmax=100, alpha=0.75)
> J = 0.0
> shuffle!(m.covec)
> vecsize = size(m.W_main, 1)
> eltype = typeof(m.b_main[1])
> vm = zeros(eltype, vecsize)
> vc = zeros(eltype, vecsize)
> grad_main = zeros(eltype, vecsize)
> grad_ctx = zeros(eltype, vecsize)
> for n=1:s.niter
> # shuffle indices
> for i = 1:length(m.covec)
> @inbounds l1 = m.covec[i].i # main index
> @inbounds l2 = m.covec[i].j # context index
> @inbounds v = m.covec[i].v
> #= vm[:] = m.W_main[:, l1] =#
> #= vc[:] = m.W_ctx[:, l2] =#
> @inbounds for j = 1:vecsize
> vm[j] = m.W_main[j, l1]
> vc[j] = m.W_ctx[j, l2]
> end
> diff = dot(vec(vm), vec(vc)) + m.b_main[l1] + m.b_ctx[l2] - log(v)
> fdiff = ifelse(v < xmax, (v / xmax) ^ alpha, 1.0) * diff
> J += 0.5 * fdiff * diff
> fdiff *= s.lrate
> # inc memory by ~200 MB && running time by 2x
> #= grad_main[:] = fdiff * m.W_ctx[:, l2] =#
> #= grad_ctx[:] = fdiff * m.W_main[:, l1] =#
> @inbounds for j = 1:vecsize
> grad_main[j] = fdiff * m.W_ctx[j, l2]
> grad_ctx[j] = fdiff * m.W_main[j, l1]
> end
> # Adaptive learning
> # inc ~ 600MB + 0.75s
> #= m.W_main[:, l1] -= grad_main ./ sqrt(m.W_main_grad[:, l1]) =#
> #= m.W_ctx[:, l2] -= grad_ctx ./ sqrt(m.W_ctx_grad[:, l2]) =#
> #= m.b_main[l1] -= fdiff ./ sqrt(m.b_main_grad[l1]) =#
> #= m.b_ctx[l2] -= fdiff ./ sqrt(m.b_ctx_grad[l2]) =#
> @inbounds for j = 1:vecsize
> m.W_main[j, l1] -= grad_main[j] / sqrt(m.W_main_grad[j, l1])
> m.W_ctx[j, l2] -= grad_ctx[j] / sqrt(m.W_ctx_grad[j, l2])
> end
> m.b_main[l1] -= fdiff ./ sqrt(m.b_main_grad[l1])
> m.b_ctx[l2] -= fdiff ./ sqrt(m.b_ctx_grad[l2])
> # Gradients
> fdiff *= fdiff
> #= m.W_main_grad[:, l1] += grad_main .^ 2 =#
> #= m.W_ctx_grad[:, l2] += grad_ctx .^ 2 =#
> #= m.b_main_grad[l1] += fdiff =#
> #= m.b_ctx_grad[l2] += fdiff =#
> @inbounds for j = 1:vecsize
> m.W_main_grad[j, l1] += grad_main[j] ^ 2
> m.W_ctx_grad[j, l2] += grad_ctx[j] ^ 2
> end
> m.b_main_grad[l1] += fdiff
> m.b_ctx_grad[l2] += fdiff
> end
> #= if n % 10 == 0 =#
> #= println("iteration $n, cost $J") =#
> #= end =#
> end
> end
>
>
>
> Mixmax Not using Mixmax yet?
>
> And the respective timings
>
> @time GloVe.train!(model, GloVe.Adagrad(500))
>7.097 seconds (96237 k allocations: 1468 MB, 7.01% gc time)
>
> Slower and more memory.
>
> On Sun, May 24, 2015 at 4:21 AM, Mauro wrote:
>
> Loops should run without allocations. Can you post your loop-code?
>
> > A[i, :] = 0.5 * B[i, :]
>
> To state the obvious, as loop:
>
> for j=1:size(A,2)
> A[i,j] = 0.5 * B[i,j]
> end
>
> this shouldn't allocate, if i is an integer. Unless A and B have
> different type, then allocation might happen.
>
> On Sun, 2015-05-24 at 05:00, Dom Luna wrote:
> > Reposting this from Gitter chat since it seems this is more active.
> >
> > I'm writing a GloVe module to learn Julia.
> >
> > How can I avoid memory allocations? My main function deals with a lot of
> > random indexing in Matrices.
> >
> > A[i, :] = 0.5 * B[i, :]
> >
> > In this case* i* isn't from a linear sequence. I'm not sure that
> matters.
> > Anyway, I’ve done analysis and I know B[i, :] is the issue here since
> it’s
> > creating a copy.
> >
> > https://github.com/JuliaLang/julia/blob/master/base/arr
Re: [julia-users] Avoid memory allocations when reading from matrices
Thanks Mauro! I made the change it works wonderfully.
I’m still a little confused why this change in particular makes such a big
difference. Is it
when using l1, l2 to index (they still have the constraint of <: Int)? Or is it
that v isn’t concrete and that gets propagated to everything else through
diff = dot(vec(vm), vec(vc)) + m.b_main[l1] + m.b_ctx[l2] - log(v)
?
Lastly, are there tools I could use check this sort of thing in the future?
On Sun, May 24, 2015 at 2:38 PM, Mauro < mauro...@runbox.com
[mauro...@runbox.com] > wrote:
The problem is in:
type Model{T}
W_main::Matrix{T}
W_ctx::Matrix{T}
b_main::Vector{T}
b_ctx::Vector{T}
W_main_grad::Matrix{T}
W_ctx_grad::Matrix{T}
b_main_grad::Vector{T}
b_ctx_grad::Vector{T}
covec::Vector{Cooccurence} # <- needs to be concrete type
end
Instead use
covec::Vector{Cooccurence{Int, Int,T}}
or some more complicated parameterisation.
Then, when testing timings you usually do one warm-up to exclude
compilation time:
GloVe.train!(model, solver) # warm up
@time 1 # @time needs a warm up too
@time GloVe.train!(model, solver)
Timings I get:
stock clone from github:
elapsed time: 0.001617218 seconds (2419024 bytes allocated)
with improvements mentioned above:
elapsed time: 0.001344645 seconds (2335552 bytes allocated)
with improvements mentioned above and your loop-version:
elapsed time: 0.00030488 seconds (3632 bytes allocated)
Hope that helps.
On Sun, 2015-05-24 at 19:21, Dominique Luna < dluna...@gmail.com
[dluna...@gmail.com] > wrote:
> Loop code
>
>
> # TODO: figure out memory issue
> function train!(m::Model, s::Adagrad; xmax=100, alpha=0.75)
> J = 0.0
> shuffle!(m.covec)
> vecsize = size(m.W_main, 1)
> eltype = typeof(m.b_main[1])
> vm = zeros(eltype, vecsize)
> vc = zeros(eltype, vecsize)
> grad_main = zeros(eltype, vecsize)
> grad_ctx = zeros(eltype, vecsize)
> for n=1:s.niter
> # shuffle indices
> for i = 1:length(m.covec)
> @inbounds l1 = m.covec[i].i # main index
> @inbounds l2 = m.covec[i].j # context index
> @inbounds v = m.covec[i].v
> #= vm[:] = m.W_main[:, l1] =#
> #= vc[:] = m.W_ctx[:, l2] =#
> @inbounds for j = 1:vecsize
> vm[j] = m.W_main[j, l1]
> vc[j] = m.W_ctx[j, l2]
> end
> diff = dot(vec(vm), vec(vc)) + m.b_main[l1] + m.b_ctx[l2] - log(v)
> fdiff = ifelse(v < xmax, (v / xmax) ^ alpha, 1.0) * diff
> J += 0.5 * fdiff * diff
> fdiff *= s.lrate
> # inc memory by ~200 MB && running time by 2x
> #= grad_main[:] = fdiff * m.W_ctx[:, l2] =#
> #= grad_ctx[:] = fdiff * m.W_main[:, l1] =#
> @inbounds for j = 1:vecsize
> grad_main[j] = fdiff * m.W_ctx[j, l2]
> grad_ctx[j] = fdiff * m.W_main[j, l1]
> end
> # Adaptive learning
> # inc ~ 600MB + 0.75s
> #= m.W_main[:, l1] -= grad_main ./ sqrt(m.W_main_grad[:, l1]) =#
> #= m.W_ctx[:, l2] -= grad_ctx ./ sqrt(m.W_ctx_grad[:, l2]) =#
> #= m.b_main[l1] -= fdiff ./ sqrt(m.b_main_grad[l1]) =#
> #= m.b_ctx[l2] -= fdiff ./ sqrt(m.b_ctx_grad[l2]) =#
> @inbounds for j = 1:vecsize
> m.W_main[j, l1] -= grad_main[j] / sqrt(m.W_main_grad[j, l1])
> m.W_ctx[j, l2] -= grad_ctx[j] / sqrt(m.W_ctx_grad[j, l2])
> end
> m.b_main[l1] -= fdiff ./ sqrt(m.b_main_grad[l1])
> m.b_ctx[l2] -= fdiff ./ sqrt(m.b_ctx_grad[l2])
> # Gradients
> fdiff *= fdiff
> #= m.W_main_grad[:, l1] += grad_main .^ 2 =#
> #= m.W_ctx_grad[:, l2] += grad_ctx .^ 2 =#
> #= m.b_main_grad[l1] += fdiff =#
> #= m.b_ctx_grad[l2] += fdiff =#
> @inbounds for j = 1:vecsize
> m.W_main_grad[j, l1] += grad_main[j] ^ 2
> m.W_ctx_grad[j, l2] += grad_ctx[j] ^ 2
> end
> m.b_main_grad[l1] += fdiff
> m.b_ctx_grad[l2] += fdiff
> end
> #= if n % 10 == 0 =#
> #= println("iteration $n, cost $J") =#
> #= end =#
> end
> end
>
>
>
> Mixmax Not using Mixmax yet?
>
> And the respective timings
>
> @time GloVe.train!(model, GloVe.Adagrad(500))
> 7.097 seconds (96237 k allocations: 1468 MB, 7.01% gc time)
>
> Slower and more memory.
>
> On Sun, May 24, 2015 at 4:21 AM, Mauro < mauro...@runbox.com
> [mauro...@runbox.com] > wrote:
>
> Loops should run without allocations. Can you post your loop-code?
>
> > A[i, :] = 0.5 * B[i, :]
>
> To state the obvious, as loop:
>
> for j=1:size(A,2)
> A[i,j] = 0.5 * B[i,j]
> end
>
> this shouldn't allocate, if i is an integer. Unless A and B have
> different type, then allocation might happen.
>
> On Sun, 2015-05-24 at 05:00, Dom Luna < dluna...@gmail.com
> [dluna...@gmail.com] > wrote:
> > Reposting this from Gitter chat since it seems this is more active.
> >
> > I'm writing a GloVe module to learn Julia.
> >
> > How can I avoid memory allocations? My main function deals with a lot of
> > random indexing in Matrices.
> >
> > A[i, :] = 0.5 * B[i, :]
> >
> > In this case* i* isn't from a linear sequence. I'm not sure that matters.
> > Anyway, I’ve done analysis and I know B[i, :] is the issue here since
> it’s
> > creating a copy.
> >
> > https://github.com/JuliaLang/ julia/blob/master/base/array. jl#L309
[https://github.com/JuliaLang/julia/blob/master/base/array.jl#L309] makes
> the
> > copy
> >
> >
> > I tried to do it via loop but it looks li
Re: [julia-users] Avoid memory allocations when reading from matrices
I can't pretend to be able to explain the full story, but you may find this
section helpful:
http://docs.julialang.org/en/release-0.3/manual/performance-tips/#avoid-containers-with-abstract-type-parameters
That whole section on performance tips is worth reading.
On Monday, May 25, 2015 at 9:31:49 AM UTC-4, Dom Luna wrote:
>
> Thanks Mauro! I made the change it works wonderfully.
>
> I’m still a little confused why this change in particular makes such a big
> difference. Is it
> when using l1, l2 to index (they still have the constraint of <: Int)? Or
> is it that v isn’t concrete and that gets propagated to everything else
> through
>
> diff = dot(vec(vm), vec(vc)) + m.b_main[l1] + m.b_ctx[l2] - log(v)
>
> ?
>
> Lastly, are there tools I could use check this sort of thing in the future?
>
>
> On Sun, May 24, 2015 at 2:38 PM, Mauro >
> wrote:
>
>> The problem is in:
>> type Model{T}
>> W_main::Matrix{T}
>> W_ctx::Matrix{T}
>> b_main::Vector{T}
>> b_ctx::Vector{T}
>> W_main_grad::Matrix{T}
>> W_ctx_grad::Matrix{T}
>> b_main_grad::Vector{T}
>> b_ctx_grad::Vector{T}
>> covec::Vector{Cooccurence} # <- needs to be concrete type
>> end
>>
>> Instead use
>> covec::Vector{Cooccurence{Int,Int,T}}
>> or some more complicated parameterisation.
>>
>> Then, when testing timings you usually do one warm-up to exclude
>> compilation time:
>>
>> GloVe.train!(model, solver) # warm up
>> @time 1 # @time needs a warm up too
>> @time GloVe.train!(model, solver)
>>
>> Timings I get:
>>
>> stock clone from github:
>> elapsed time: 0.001617218 seconds (2419024 bytes allocated)
>>
>> with improvements mentioned above:
>> elapsed time: 0.001344645 seconds (2335552 bytes allocated)
>>
>> with improvements mentioned above and your loop-version:
>> elapsed time: 0.00030488 seconds (3632 bytes allocated)
>>
>> Hope that helps.
>>
>> On Sun, 2015-05-24 at 19:21, Dominique Luna > > wrote:
>> > Loop code
>> >
>> >
>> > # TODO: figure out memory issue
>> > function train!(m::Model, s::Adagrad; xmax=100, alpha=0.75)
>> > J = 0.0
>> > shuffle!(m.covec)
>> > vecsize = size(m.W_main, 1)
>> > eltype = typeof(m.b_main[1])
>> > vm = zeros(eltype, vecsize)
>> > vc = zeros(eltype, vecsize)
>> > grad_main = zeros(eltype, vecsize)
>> > grad_ctx = zeros(eltype, vecsize)
>> > for n=1:s.niter
>> > # shuffle indices
>> > for i = 1:length(m.covec)
>> > @inbounds l1 = m.covec[i].i # main index
>> > @inbounds l2 = m.covec[i].j # context index
>> > @inbounds v = m.covec[i].v
>> > #= vm[:] = m.W_main[:, l1] =#
>> > #= vc[:] = m.W_ctx[:, l2] =#
>> > @inbounds for j = 1:vecsize
>> > vm[j] = m.W_main[j, l1]
>> > vc[j] = m.W_ctx[j, l2]
>> > end
>> > diff = dot(vec(vm), vec(vc)) + m.b_main[l1] + m.b_ctx[l2] -
>> log(v)
>> > fdiff = ifelse(v < xmax, (v / xmax) ^ alpha, 1.0) * diff
>> > J += 0.5 * fdiff * diff
>> > fdiff *= s.lrate
>> > # inc memory by ~200 MB && running time by 2x
>> > #= grad_main[:] = fdiff * m.W_ctx[:, l2] =#
>> > #= grad_ctx[:] = fdiff * m.W_main[:, l1] =#
>> > @inbounds for j = 1:vecsize
>> > grad_main[j] = fdiff * m.W_ctx[j, l2]
>> > grad_ctx[j] = fdiff * m.W_main[j, l1]
>> > end
>> > # Adaptive learning
>> > # inc ~ 600MB + 0.75s
>> > #= m.W_main[:, l1] -= grad_main ./ sqrt(m.W_main_grad[:,
>> l1]) =#
>> > #= m.W_ctx[:, l2] -= grad_ctx ./ sqrt(m.W_ctx_grad[:, l2])
>> =#
>> > #= m.b_main[l1] -= fdiff ./ sqrt(m.b_main_grad[l1]) =#
>> > #= m.b_ctx[l2] -= fdiff ./ sqrt(m.b_ctx_grad[l2]) =#
>> > @inbounds for j = 1:vecsize
>> > m.W_main[j, l1] -= grad_main[j] / sqrt(m.W_main_grad[j,
>> l1])
>> > m.W_ctx[j, l2] -= grad_ctx[j] / sqrt(m.W_ctx_grad[j,
>> l2])
>> > end
>> > m.b_main[l1] -= fdiff ./ sqrt(m.b_main_grad[l1])
>> > m.b_ctx[l2] -= fdiff ./ sqrt(m.b_ctx_grad[l2])
>> > # Gradients
>> > fdiff *= fdiff
>> > #= m.W_main_grad[:, l1] += grad_main .^ 2 =#
>> > #= m.W_ctx_grad[:, l2] += grad_ctx .^ 2 =#
>> > #= m.b_main_grad[l1] += fdiff =#
>> > #= m.b_ctx_grad[l2] += fdiff =#
>> > @inbounds for j = 1:vecsize
>> > m.W_main_grad[j, l1] += grad_main[j] ^ 2
>> > m.W_ctx_grad[j, l2] += grad_ctx[j] ^ 2
>> > end
>> > m.b_main_grad[l1] += fdiff
>> > m.b_ctx_grad[l2] += fdiff
>> > end
>> > #= if n % 10 == 0 =#
>> > #= println("iteration $n, cost $J") =#
>> > #= end =#
>> > end
>> > end
>> >
>> >
>> >
>> > Mixmax Not using Mixmax yet?
>> >
>> >
Re: [julia-users] Avoid memory allocations when reading from matrices
> Thanks Mauro! I made the change it works wonderfully.
> I’m still a little confused why this change in particular makes such a big
> difference. Is it
> when using l1, l2 to index (they still have the constraint of <: Int)? Or is
> it
> that v isn’t concrete and that gets propagated to everything else through
> diff = dot(vec(vm), vec(vc)) + m.b_main[l1] + m.b_ctx[l2] - log(v)
> ?
The manual section David mentioned covers this.
> Lastly, are there tools I could use check this sort of thing in the future?
@code_warntype can help.
> On Sun, May 24, 2015 at 2:38 PM, Mauro < mauro...@runbox.com
> [mauro...@runbox.com] > wrote:
> The problem is in:
> type Model{T}
> W_main::Matrix{T}
> W_ctx::Matrix{T}
> b_main::Vector{T}
> b_ctx::Vector{T}
> W_main_grad::Matrix{T}
> W_ctx_grad::Matrix{T}
> b_main_grad::Vector{T}
> b_ctx_grad::Vector{T}
> covec::Vector{Cooccurence} # <- needs to be concrete type
> end
>
> Instead use
> covec::Vector{Cooccurence{Int, Int,T}}
> or some more complicated parameterisation.
>
> Then, when testing timings you usually do one warm-up to exclude
> compilation time:
>
> GloVe.train!(model, solver) # warm up
> @time 1 # @time needs a warm up too
> @time GloVe.train!(model, solver)
>
> Timings I get:
>
> stock clone from github:
> elapsed time: 0.001617218 seconds (2419024 bytes allocated)
>
> with improvements mentioned above:
> elapsed time: 0.001344645 seconds (2335552 bytes allocated)
>
> with improvements mentioned above and your loop-version:
> elapsed time: 0.00030488 seconds (3632 bytes allocated)
>
> Hope that helps.
>
> On Sun, 2015-05-24 at 19:21, Dominique Luna < dluna...@gmail.com
> [dluna...@gmail.com] > wrote:
>> Loop code
>>
>>
>> # TODO: figure out memory issue
>> function train!(m::Model, s::Adagrad; xmax=100, alpha=0.75)
>> J = 0.0
>> shuffle!(m.covec)
>> vecsize = size(m.W_main, 1)
>> eltype = typeof(m.b_main[1])
>> vm = zeros(eltype, vecsize)
>> vc = zeros(eltype, vecsize)
>> grad_main = zeros(eltype, vecsize)
>> grad_ctx = zeros(eltype, vecsize)
>> for n=1:s.niter
>> # shuffle indices
>> for i = 1:length(m.covec)
>> @inbounds l1 = m.covec[i].i # main index
>> @inbounds l2 = m.covec[i].j # context index
>> @inbounds v = m.covec[i].v
>> #= vm[:] = m.W_main[:, l1] =#
>> #= vc[:] = m.W_ctx[:, l2] =#
>> @inbounds for j = 1:vecsize
>> vm[j] = m.W_main[j, l1]
>> vc[j] = m.W_ctx[j, l2]
>> end
>> diff = dot(vec(vm), vec(vc)) + m.b_main[l1] + m.b_ctx[l2] - log(v)
>> fdiff = ifelse(v < xmax, (v / xmax) ^ alpha, 1.0) * diff
>> J += 0.5 * fdiff * diff
>> fdiff *= s.lrate
>> # inc memory by ~200 MB && running time by 2x
>> #= grad_main[:] = fdiff * m.W_ctx[:, l2] =#
>> #= grad_ctx[:] = fdiff * m.W_main[:, l1] =#
>> @inbounds for j = 1:vecsize
>> grad_main[j] = fdiff * m.W_ctx[j, l2]
>> grad_ctx[j] = fdiff * m.W_main[j, l1]
>> end
>> # Adaptive learning
>> # inc ~ 600MB + 0.75s
>> #= m.W_main[:, l1] -= grad_main ./ sqrt(m.W_main_grad[:, l1]) =#
>> #= m.W_ctx[:, l2] -= grad_ctx ./ sqrt(m.W_ctx_grad[:, l2]) =#
>> #= m.b_main[l1] -= fdiff ./ sqrt(m.b_main_grad[l1]) =#
>> #= m.b_ctx[l2] -= fdiff ./ sqrt(m.b_ctx_grad[l2]) =#
>> @inbounds for j = 1:vecsize
>> m.W_main[j, l1] -= grad_main[j] / sqrt(m.W_main_grad[j, l1])
>> m.W_ctx[j, l2] -= grad_ctx[j] / sqrt(m.W_ctx_grad[j, l2])
>> end
>> m.b_main[l1] -= fdiff ./ sqrt(m.b_main_grad[l1])
>> m.b_ctx[l2] -= fdiff ./ sqrt(m.b_ctx_grad[l2])
>> # Gradients
>> fdiff *= fdiff
>> #= m.W_main_grad[:, l1] += grad_main .^ 2 =#
>> #= m.W_ctx_grad[:, l2] += grad_ctx .^ 2 =#
>> #= m.b_main_grad[l1] += fdiff =#
>> #= m.b_ctx_grad[l2] += fdiff =#
>> @inbounds for j = 1:vecsize
>> m.W_main_grad[j, l1] += grad_main[j] ^ 2
>> m.W_ctx_grad[j, l2] += grad_ctx[j] ^ 2
>> end
>> m.b_main_grad[l1] += fdiff
>> m.b_ctx_grad[l2] += fdiff
>> end
>> #= if n % 10 == 0 =#
>> #= println("iteration $n, cost $J") =#
>> #= end =#
>> end
>> end
>>
>>
>>
>> Mixmax Not using Mixmax yet?
>>
>> And the respective timings
>>
>> @time GloVe.train!(model, GloVe.Adagrad(500))
>> 7.097 seconds (96237 k allocations: 1468 MB, 7.01% gc time)
>>
>> Slower and more memory.
>>
>> On Sun, May 24, 2015 at 4:21 AM, Mauro < mauro...@runbox.com
>> [mauro...@runbox.com] > wrote:
>>
>> Loops should run without allocations. Can you post your loop-code?
>>
>> > A[i, :] = 0.5 * B[i, :]
>>
>> To state the obvious, as loop:
>>
>> for j=1:size(A,2)
>> A[i,j] = 0.5 * B[i,j]
>> end
>>
>> this shouldn't allocate, if i is an integer. Unless A and B have
>> different type, then allocation might happen.
>>
>> On Sun, 2015-05-24 at 05:00, Dom Luna < dluna...@gmail.com
>> [dluna...@gmail.com] > wrote:
>> > Reposting this from Gitter chat since it seems this is more active.
>> >
>> > I'm writing a GloVe module to learn Julia.
>> >
>> > How can I avoid memory allocations? My main function deals with a lot of
>> > random indexing in Matrices.
>> >
>> > A[i, :] = 0.5 * B[i, :]
>> >
>> > In this case* i* isn't from a linear sequence. I'm not sure that matters.
>> > Anyway, I’ve done analysis and I know B[i
Re: [julia-users] Avoid memory allocations when reading from matrices
@code_warntype is your friend in these
situations.
http://julia.readthedocs.org/en/latest/manual/performance-tips/#man-code-warntype
On Monday, May 25, 2015 at 3:31:49 PM UTC+2, Dom Luna wrote:
>
> Thanks Mauro! I made the change it works wonderfully.
>
> I’m still a little confused why this change in particular makes such a big
> difference. Is it
> when using l1, l2 to index (they still have the constraint of <: Int)? Or
> is it that v isn’t concrete and that gets propagated to everything else
> through
>
> diff = dot(vec(vm), vec(vc)) + m.b_main[l1] + m.b_ctx[l2] - log(v)
>
> ?
>
> Lastly, are there tools I could use check this sort of thing in the future?
>
>
> On Sun, May 24, 2015 at 2:38 PM, Mauro >
> wrote:
>
>> The problem is in:
>> type Model{T}
>> W_main::Matrix{T}
>> W_ctx::Matrix{T}
>> b_main::Vector{T}
>> b_ctx::Vector{T}
>> W_main_grad::Matrix{T}
>> W_ctx_grad::Matrix{T}
>> b_main_grad::Vector{T}
>> b_ctx_grad::Vector{T}
>> covec::Vector{Cooccurence} # <- needs to be concrete type
>> end
>>
>> Instead use
>> covec::Vector{Cooccurence{Int,Int,T}}
>> or some more complicated parameterisation.
>>
>> Then, when testing timings you usually do one warm-up to exclude
>> compilation time:
>>
>> GloVe.train!(model, solver) # warm up
>> @time 1 # @time needs a warm up too
>> @time GloVe.train!(model, solver)
>>
>> Timings I get:
>>
>> stock clone from github:
>> elapsed time: 0.001617218 seconds (2419024 bytes allocated)
>>
>> with improvements mentioned above:
>> elapsed time: 0.001344645 seconds (2335552 bytes allocated)
>>
>> with improvements mentioned above and your loop-version:
>> elapsed time: 0.00030488 seconds (3632 bytes allocated)
>>
>> Hope that helps.
>>
>> On Sun, 2015-05-24 at 19:21, Dominique Luna > > wrote:
>> > Loop code
>> >
>> >
>> > # TODO: figure out memory issue
>> > function train!(m::Model, s::Adagrad; xmax=100, alpha=0.75)
>> > J = 0.0
>> > shuffle!(m.covec)
>> > vecsize = size(m.W_main, 1)
>> > eltype = typeof(m.b_main[1])
>> > vm = zeros(eltype, vecsize)
>> > vc = zeros(eltype, vecsize)
>> > grad_main = zeros(eltype, vecsize)
>> > grad_ctx = zeros(eltype, vecsize)
>> > for n=1:s.niter
>> > # shuffle indices
>> > for i = 1:length(m.covec)
>> > @inbounds l1 = m.covec[i].i # main index
>> > @inbounds l2 = m.covec[i].j # context index
>> > @inbounds v = m.covec[i].v
>> > #= vm[:] = m.W_main[:, l1] =#
>> > #= vc[:] = m.W_ctx[:, l2] =#
>> > @inbounds for j = 1:vecsize
>> > vm[j] = m.W_main[j, l1]
>> > vc[j] = m.W_ctx[j, l2]
>> > end
>> > diff = dot(vec(vm), vec(vc)) + m.b_main[l1] + m.b_ctx[l2] -
>> log(v)
>> > fdiff = ifelse(v < xmax, (v / xmax) ^ alpha, 1.0) * diff
>> > J += 0.5 * fdiff * diff
>> > fdiff *= s.lrate
>> > # inc memory by ~200 MB && running time by 2x
>> > #= grad_main[:] = fdiff * m.W_ctx[:, l2] =#
>> > #= grad_ctx[:] = fdiff * m.W_main[:, l1] =#
>> > @inbounds for j = 1:vecsize
>> > grad_main[j] = fdiff * m.W_ctx[j, l2]
>> > grad_ctx[j] = fdiff * m.W_main[j, l1]
>> > end
>> > # Adaptive learning
>> > # inc ~ 600MB + 0.75s
>> > #= m.W_main[:, l1] -= grad_main ./ sqrt(m.W_main_grad[:,
>> l1]) =#
>> > #= m.W_ctx[:, l2] -= grad_ctx ./ sqrt(m.W_ctx_grad[:, l2])
>> =#
>> > #= m.b_main[l1] -= fdiff ./ sqrt(m.b_main_grad[l1]) =#
>> > #= m.b_ctx[l2] -= fdiff ./ sqrt(m.b_ctx_grad[l2]) =#
>> > @inbounds for j = 1:vecsize
>> > m.W_main[j, l1] -= grad_main[j] / sqrt(m.W_main_grad[j,
>> l1])
>> > m.W_ctx[j, l2] -= grad_ctx[j] / sqrt(m.W_ctx_grad[j,
>> l2])
>> > end
>> > m.b_main[l1] -= fdiff ./ sqrt(m.b_main_grad[l1])
>> > m.b_ctx[l2] -= fdiff ./ sqrt(m.b_ctx_grad[l2])
>> > # Gradients
>> > fdiff *= fdiff
>> > #= m.W_main_grad[:, l1] += grad_main .^ 2 =#
>> > #= m.W_ctx_grad[:, l2] += grad_ctx .^ 2 =#
>> > #= m.b_main_grad[l1] += fdiff =#
>> > #= m.b_ctx_grad[l2] += fdiff =#
>> > @inbounds for j = 1:vecsize
>> > m.W_main_grad[j, l1] += grad_main[j] ^ 2
>> > m.W_ctx_grad[j, l2] += grad_ctx[j] ^ 2
>> > end
>> > m.b_main_grad[l1] += fdiff
>> > m.b_ctx_grad[l2] += fdiff
>> > end
>> > #= if n % 10 == 0 =#
>> > #= println("iteration $n, cost $J") =#
>> > #= end =#
>> > end
>> > end
>> >
>> >
>> >
>> > Mixmax Not using Mixmax yet?
>> >
>> > And the respective timings
>> >
>> > @time GloVe.train!(model, GloVe.Adagrad(500))
>> >7.097 seconds (96237 k allocations:
