# Which line is resulting is huge memory allocation?

This code below is running very very slow must be due to the ridiculous number of memory allocations.

``````input = "1113222113"

function lookandsay(s::AbstractString)::AbstractString
result = ""
i = 1
while i <= length(s)
c = 1
while i < length(s) && s[i+1] == s[i]
c += 1
i += 1
end
result *= string(c)*s[i]
i += 1
end
return result
end

function solve(s::AbstractString)
for i in 1:50
s = lookandsay(s)
end

println(length(s))
end

solve(input)
``````

Can someone help me to identify and rectify the problem here?

all the strings are being allocated, what does this program do?

It is an attempt for Advent of Code 2015 day 10.
Aim is to apply look-and-say to a string 40 times.
Please have a look at the problem.
Thanks

Does it have to be with strings? That’s the slowest part. Working with a vector of `Int`s I can get it to be a fraction of a second to get to 50.

Not really. It can be anything other than strings.
Can you please share you code?

``````function lookandsay(s)
result = similar(s, 0)
sizehint!(result, 2*length(s))

i = 1
while i <= length(s)
c = 1
while i < length(s) && s[i+1] == s[i]
c += 1
i += 1
end
if c < 10
push!(result, c)
else
append!(result, reverse(digits(c)))
end
push!(result, s[i])
i += 1
end

return result
end

function sol(s, n)
for i in 1:n
s = lookandsay(s)
end
length(s)
end
``````
``````julia> using BenchmarkTools

julia> @btime sol(parse.(Int, collect(input)), 50)
278.920 ms (106 allocations: 179.90 MiB)
3579328
``````
2 Likes

Amazing!
Can you please explain these two lines? I am new to this language.

Also, if I remove the zero from the similar function, the kernel crashes. Why does it crash?
Thanks!

1 Like

Sure. `similar` creates a vector of the same type and length as the input. The 0 specifies that the vector should be length 0 instead of length(s)

``````julia> a = rand(1:3, 3)
3-element Array{Int64,1}:
1
3
3

julia> similar(a)
3-element Array{Int64,1}:
4438204720
4543276208
4438204752

julia> similar(a, 0)
0-element Array{Int64,1}
``````

`sizehint!` suggests that `result` should reserve enough memory for `2*length(s)` entries (you can think of it as a preallocation). I picked this number as a heuristic, and I noted it gives a minor improvement.

1 Like

Thanks for the explanation!
Why is the kernel crashing is I remove the `0` from this `result = similar(s, 0)` line?

Not sure off the top of my head, but my guess is that it’s because `similar(s)` allocates a vector of size `length(s)`, and then starts pushing/appending to it. Next iteration that will be the input, so the length of this vector doubles every iteration. As the iteration count gets large, maybe it’s failing to allocate the vector, or to push/append to it, and this is causing the crash.

1 Like

I just noticed also that since each digit can’t exceed `9`, you can convert the input to `Vector{Int8}` and get it about 2x faster.