# Which line is resulting is huge memory allocation?

**URL:** <https://discourse.julialang.org/t/which-line-is-resulting-is-huge-memory-allocation/44822>\
**Category:** Performance\
**Created:** [August 12, 2020, 7:04pm UTC](https://discourse.julialang.org/t/which-line-is-resulting-is-huge-memory-allocation/44822 "2020-08-12T19:04:14Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![Sanji\_Vinsmoke](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sanji_vinsmoke/32/9015_2.png) [@Sanji\_Vinsmoke](https://discourse.julialang.org/u/Sanji_Vinsmoke)\
**Post date:** [August 12, 2020, 7:04pm UTC](https://discourse.julialang.org/t/which-line-is-resulting-is-huge-memory-allocation/44822/1 "2020-08-12T19:04:14Z")

</div>

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

```julia
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?

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [August 12, 2020, 7:15pm UTC](https://discourse.julialang.org/t/which-line-is-resulting-is-huge-memory-allocation/44822/2 "2020-08-12T19:15:48Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Sanji\_Vinsmoke](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sanji_vinsmoke/32/9015_2.png) [@Sanji\_Vinsmoke](https://discourse.julialang.org/u/Sanji_Vinsmoke)\
**Post date:** [August 12, 2020, 7:19pm UTC](https://discourse.julialang.org/t/which-line-is-resulting-is-huge-memory-allocation/44822/3 "2020-08-12T19:19:52Z")

</div>

It is an attempt for [Advent of Code 2015 day 10](https://adventofcode.com/2015/day/10).  
Aim is to apply look-and-say to a string 40 times.  
Please have a look at the problem.  
Thanks

---

<div class="post-metadata">

**Author:** ![tomerarnon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tomerarnon/32/3170_2.png) [@tomerarnon](https://discourse.julialang.org/u/tomerarnon)\
**Post date:** [August 12, 2020, 7:23pm UTC](https://discourse.julialang.org/t/which-line-is-resulting-is-huge-memory-allocation/44822/4 "2020-08-12T19:23:14Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Sanji\_Vinsmoke](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sanji_vinsmoke/32/9015_2.png) [@Sanji\_Vinsmoke](https://discourse.julialang.org/u/Sanji_Vinsmoke)\
**Post date:** [August 12, 2020, 7:24pm UTC](https://discourse.julialang.org/t/which-line-is-resulting-is-huge-memory-allocation/44822/5 "2020-08-12T19:24:53Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![tomerarnon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tomerarnon/32/3170_2.png) [@tomerarnon](https://discourse.julialang.org/u/tomerarnon)\
**Post date:** [August 12, 2020, 7:27pm UTC](https://discourse.julialang.org/t/which-line-is-resulting-is-huge-memory-allocation/44822/6 "2020-08-12T19:27:58Z")

</div>

```julia
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
julia> using BenchmarkTools

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

```

---

<div class="post-metadata">

**Author:** ![Sanji\_Vinsmoke](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sanji_vinsmoke/32/9015_2.png) [@Sanji\_Vinsmoke](https://discourse.julialang.org/u/Sanji_Vinsmoke)\
**Post date:** [August 12, 2020, 7:39pm UTC](https://discourse.julialang.org/t/which-line-is-resulting-is-huge-memory-allocation/44822/7 "2020-08-12T19:39:42Z")

</div>

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

> [@tomerarnon](#):
>
> ```julia
> result = similar(s, 0)
> sizehint!(result, 2*length(s))
> 
> ```

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

---

<div class="post-metadata">

**Author:** ![tomerarnon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tomerarnon/32/3170_2.png) [@tomerarnon](https://discourse.julialang.org/u/tomerarnon)\
**Post date:** [August 12, 2020, 8:02pm UTC](https://discourse.julialang.org/t/which-line-is-resulting-is-huge-memory-allocation/44822/8 "2020-08-12T20:02:31Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Sanji\_Vinsmoke](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sanji_vinsmoke/32/9015_2.png) [@Sanji\_Vinsmoke](https://discourse.julialang.org/u/Sanji_Vinsmoke)\
**Post date:** [August 12, 2020, 8:04pm UTC](https://discourse.julialang.org/t/which-line-is-resulting-is-huge-memory-allocation/44822/9 "2020-08-12T20:04:42Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![tomerarnon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tomerarnon/32/3170_2.png) [@tomerarnon](https://discourse.julialang.org/u/tomerarnon)\
**Post date:** [August 12, 2020, 8:10pm UTC](https://discourse.julialang.org/t/which-line-is-resulting-is-huge-memory-allocation/44822/10 "2020-08-12T20:10:14Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![tomerarnon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tomerarnon/32/3170_2.png) [@tomerarnon](https://discourse.julialang.org/u/tomerarnon)\
**Post date:** [August 12, 2020, 8:23pm UTC](https://discourse.julialang.org/t/which-line-is-resulting-is-huge-memory-allocation/44822/11 "2020-08-12T20:23:30Z")

</div>

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.