Which line is resulting is huge memory allocation?

General Usage Performance
1

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?

2

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

3

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

4

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

5

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

6 
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
7

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
8

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
9

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

10

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
11

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.