# Reduce number of allocations

**URL:** <https://discourse.julialang.org/t/reduce-number-of-allocations/66990>\
**Category:** Performance\
**Tags:** memory-allocation\
**Created:** [August 25, 2021, 4:54pm UTC](https://discourse.julialang.org/t/reduce-number-of-allocations/66990 "2021-08-25T16:54:24Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![daviddoij](https://avatars.discourse-cdn.com/v4/letter/d/87869e/32.png) [@daviddoij](https://discourse.julialang.org/u/daviddoij)\
**Post date:** [August 25, 2021, 4:54pm UTC](https://discourse.julialang.org/t/reduce-number-of-allocations/66990/1 "2021-08-25T16:54:24Z")

</div>

I would like to reduce the number of allocations in this particular problem (for context, that’s problem 30 of project euler). I got it right, but I think there are too many allocations.

```julia
function power_digit_sum(pow, n)
    return sum(c^pow for c in reverse(digits(n)))
end

function Problem30()
    ans = sum(i for i in 2:1_000_000 if i == power_digit_sum(5, i))
    return ans
end

```

By using the Benchmarks package, I’m getting these numbers:  
238.513 ms (2000005 allocations: 243.83 MiB)

---

<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 25, 2021, 4:58pm UTC](https://discourse.julialang.org/t/reduce-number-of-allocations/66990/2 "2021-08-25T16:58:05Z")

</div>

for start, don’t `reverse` the digits because it doesn’t matter?

```julia

julia> function power_digit_sum(pow, n)
           return sum(c->c^pow, digits(n))
       end
power_digit_sum (generic function with 1 method)

julia> @benchmark Problem30()
BenchmarkTools.Trial: 73 samples with 1 evaluation.
 Range (min … max): 67.670 ms … 76.800 ms ┊ GC (min … max): 2.73% … 2.34%
 Time (median): 68.717 ms ┊ GC (median): 2.72%
 Time (mean ± σ): 69.106 ms ± 1.293 ms ┊ GC (mean ± σ): 3.24% ± 0.66%

  █                                                            
  █▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▁
  76.8 ms Histogram: frequency by time 70.8 ms <

 Memory estimate: 105.27 MiB, allocs estimate: 999999.

```

---

<div class="post-metadata">

**Author:** ![daviddoij](https://avatars.discourse-cdn.com/v4/letter/d/87869e/32.png) [@daviddoij](https://discourse.julialang.org/u/daviddoij)\
**Post date:** [August 25, 2021, 5:02pm UTC](https://discourse.julialang.org/t/reduce-number-of-allocations/66990/3 "2021-08-25T17:02:40Z")

</div>

Thanks! TIL 🙂

---

<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 25, 2021, 5:31pm UTC](https://discourse.julialang.org/t/reduce-number-of-allocations/66990/4 "2021-08-25T17:31:25Z")

</div>

```julia
julia> mutable struct Ds{T<:Integer}
           n::T
       end

julia> Base.length(d::Ds) = floor(Int, log10(d.n)+1.0)

julia> Base.eltype(::Type{Ds{T}}) where T = T

julia> function Base.iterate(d::Ds, state=0)
           quo, rem = divrem(d.n, 10)
           iszero(quo) && iszero(rem) && return nothing
           d.n = quo
           return rem, state+1
       end

julia> sum(abs2, Ds(1120))
6

julia> function power_digit_sum(pow, n)
           return sum(c->c^pow, Ds(n))
       end
power_digit_sum (generic function with 1 method)

julia> function Problem30()
           ans = sum(i for i in 2:1_000_000 if i == power_digit_sum(5, i))
           return ans
       end
Problem30 (generic function with 1 method)

julia> Problem30()
443839

julia> @benchmark Problem30()
BenchmarkTools.Trial: 180 samples with 1 evaluation.
 Range (min … max): 27.493 ms … 31.108 ms ┊ GC (min … max): 0.00% … 1.83%
 Time (median): 27.687 ms ┊ GC (median): 0.00%
 Time (mean ± σ): 27.882 ms ± 492.082 μs ┊ GC (mean ± σ): 0.71% ± 0.96%

  █                                                             
  █▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▄
  30 ms Histogram: log(frequency) by time 28.2 ms <

 Memory estimate: 15.26 MiB, allocs estimate: 1000004.

```

here’s an attempt to make `digits` allocate less.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [August 25, 2021, 5:43pm UTC](https://discourse.julialang.org/t/reduce-number-of-allocations/66990/5 "2021-08-25T17:43:37Z")

</div>

This thing should have zero allocations:

```julia
function powsum(pow, n)
    s = 0
    while n > 0
        (n, r) = divrem(n, 10)
        s += r^pow
    end
    return s
end

problem30() = sum(i for i in 2:1_000_000 if i == powsum(5, i))

```

```julia
jl> @btime problem30()
  30.112 ms (0 allocations: 0 bytes)
443839

```

---

<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 25, 2021, 5:45pm UTC](https://discourse.julialang.org/t/reduce-number-of-allocations/66990/6 "2021-08-25T17:45:40Z")

</div>

that’s indeed what I tried and realized `divrem` doesn’t allocate, but I still want it to be `digits` for not “cheating” 😉

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [August 25, 2021, 5:56pm UTC](https://discourse.julialang.org/t/reduce-number-of-allocations/66990/7 "2021-08-25T17:56:25Z")

</div>

But this _is_ `digits`😉 It does exactly the same thing as `digits`, except doesn’t store anything in a vector.

I think I have one `divrem` call too many, btw. Could try to get rid of that.

---

<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 25, 2021, 5:59pm UTC](https://discourse.julialang.org/t/reduce-number-of-allocations/66990/8 "2021-08-25T17:59:06Z")

</div>

the point is you don’t have handle on the digits themselves. i.e. you can’t apply arbitrary function to each digits, and you can’t recover the old digits – i.e. `collect` them.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [August 25, 2021, 6:02pm UTC](https://discourse.julialang.org/t/reduce-number-of-allocations/66990/9 "2021-08-25T18:02:10Z")

</div>

You can rewrite it to be `fsum(f, n)`, where `f` is an arbitrary function.

But I don’t really understand the reason for such an expansion of scope. Why collect the digits when your doing a reduction?

---

<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 25, 2021, 6:05pm UTC](https://discourse.julialang.org/t/reduce-number-of-allocations/66990/10 "2021-08-25T18:05:45Z")

</div>

> [@DNF](#):
>
> Why collect the digits when your doing a reduction?

The answer to this question in vacuum is a sound “no”. I’m just saying it’s not always safe to assume OP does and only does this specific one thing → it’s not safe to be too smart.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [August 25, 2021, 6:25pm UTC](https://discourse.julialang.org/t/reduce-number-of-allocations/66990/11 "2021-08-25T18:25:40Z")

</div>

It’s project Euler 30, I think it’s specific enough. I don’t like bending over backwards to do things the same way as the OP, I normally assume they’re asking the wrong question anyway, so we’ll have to agree to disagree on this 😉

Here’s a version that is more specific and faster:

```julia
function pow5(x)
    y = x^2
    return y^2 * x
end

function pow5sum(n)
    s = 0
    while n >= 10
        (n, r) = divrem(n, 10)
        s += pow5(r)
    end
    return s + pow5(n)
end

problem30() = sum(i for i in 2:1_000_000 if i == pow5sum(i))

```

```julia
jl> @btime problem30()
  11.453 ms (0 allocations: 0 bytes)
443839

```

But there must be some less brute-force way to go about this.

---

<div class="post-metadata">

**Author:** ![genkuroki](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/genkuroki/32/18030_2.png) [@genkuroki](https://discourse.julialang.org/u/genkuroki)\
**Post date:** [August 25, 2021, 10:03pm UTC](https://discourse.julialang.org/t/reduce-number-of-allocations/66990/12 "2021-08-25T22:03:26Z")

</div>

Original code:

```julia
using BenchmarkTools

function power_digit_sum(pow, n)
    return sum(c^pow for c in reverse(digits(n)))
end

function Problem30()
    ans = sum(i for i in 2:1_000_000 if i == power_digit_sum(5, i))
    return ans
end

@show Problem30();
@btime Problem30();

```

```julia
Problem30() = 443839
  128.256 ms (2000004 allocations: 243.83 MiB)

```

The easiest way to reduce the allocation in this code is to use [`digits!`](https://docs.julialang.org/en/v1/base/numbers/#Base.digits!):

```julia
module Rev1

function power_digit_sum!(pow, n, ws)
    return sum(c^pow for c in digits!(ws, n))
end

function Problem30(N, m)
    ws = Vector{Int}(undef, N)
    ans = sum(i for i in 2:(10^N - 1) if i == power_digit_sum!(m, i, ws))
    return ans
end

end

@show Rev1.Problem30(6, 5);
@btime Rev1.Problem30(6, 5);

```

```julia
Rev1.Problem30(6, 5) = 443839
  54.770 ms (1 allocation: 128 bytes)

```

128.256 ms (2000004 allocations: 243.83 MiB)  
↓  
54.770 ms (1 allocation: 128 bytes)

The naive simplest way to solve [Project Euler Problem 30](https://projecteuler.net/index.php?section=problems&id=30) is to use a 6-fold for loop that runs from 0 to 9 for each of i\_1, i\_2, \ldots, i\_6. Using [the Base.Cartesian macros](https://docs.julialang.org/en/v1/devdocs/cartesian/), we can simply write a 6-fold for loop in Julia.

```julia
function projecteuler30()
    s = 0
    x = 0
    @nloops 6 i d -> 0:9 begin
        y = 0
        @nexprs 6 d -> y += (z = i_d^2; z^2*i_d)
        s += (x == y) * x
        x += 1
    end
    s - 1
end

@show projecteuler30();
@btime projecteuler30();

```

```julia
projecteuler30() = 443839
  237.800 μs (0 allocations: 0 bytes)

```

128.256 ms (2000004 allocations: 243.83 MiB)  
↓  
54.770 ms (1 allocation: 128 bytes)  
↓  
237.800 μs (0 allocations: 0 bytes)

**That’s over 500 times faster than the original code!** It’s only using one CPU thread! The readability of the code has been reduced, but it is simple enough!

It can be generalized with only a 30% performance sacrifice by using a generated function as follows:

```julia
@generated function _projecteuler30(::Val{N}, ::Val{m}) where {N, m}
    quote
        p = @ntuple 10 i -> (i - 1) ^ $m
        s = 0
        x = 0
        @inbounds @nloops $N i d -> 0:9 begin
            y = 0
            @nexprs $N d -> y += p[i_d+1]
            s += (x == y) * x
            x += 1
        end
        s - 1
    end
end
projecteuler30(N, m) = _projecteuler30(Val(N), Val(m))

@show projecteuler30(6, 5);
@btime projecteuler30(6, 5);

```

```julia
projecteuler30(6, 5) = 443839
  315.700 μs (0 allocations: 0 bytes)

```

I think one of the great joys of Julia is that calculations can be made hundreds of times faster with a little effort.

[Jupyter notebook](https://github.com/genkuroki/public/blob/main/0017/Project%20Euler%2030.ipynb) (I have left the trial and error part.)