# Sum over BigInt better performance without generator

**URL:** <https://discourse.julialang.org/t/sum-over-bigint-better-performance-without-generator/40332>\
**Category:** Performance\
**Created:** [May 28, 2020, 11:17am UTC](https://discourse.julialang.org/t/sum-over-bigint-better-performance-without-generator/40332 "2020-05-28T11:17:56Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![bernb](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bernb/32/17377_2.png) [@bernb](https://discourse.julialang.org/u/bernb)\
**Post date:** [May 28, 2020, 11:17am UTC](https://discourse.julialang.org/t/sum-over-bigint-better-performance-without-generator/40332/1 "2020-05-28T11:17:56Z")

</div>

I use the following script:

```julia
using BenchmarkTools

total_gen(k) = sum(BigInt(2)^(n-1) for n in 1:k)
total_arr(k) = sum([BigInt(2)^(n-1) for n in 1:k])

display(@benchmark total_gen(10_000))
display(@benchmark total_arr(10_000))

```

This results in:

```julia
BenchmarkTools.Trial: 
  memory estimate: 13.37 MiB
  allocs estimate: 69996
  --------------
  minimum time: 3.899 ms (0.00% GC)
  median time: 4.628 ms (0.00% GC)
  mean time: 9.792 ms (21.02% GC)
  maximum time: 141.717 ms (84.33% GC)
  --------------
  samples: 511
  evals/sample: 1
BenchmarkTools.Trial: 
  memory estimate: 7.07 MiB
  allocs estimate: 50159
  --------------
  minimum time: 3.242 ms (0.00% GC)
  median time: 3.894 ms (0.00% GC)
  mean time: 7.158 ms (19.16% GC)
  maximum time: 141.290 ms (83.02% GC)
  --------------
  samples: 698
  evals/sample: 1

```

I wonder why giving sum a generator instead of an array leads to more allocations.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [May 28, 2020, 12:46pm UTC](https://discourse.julialang.org/t/sum-over-bigint-better-performance-without-generator/40332/2 "2020-05-28T12:46:17Z")

</div>

> [@bernb](#):
>
> I wonder why giving sum a generator instead of an array leads to more allocations.

`sum` calls a [specialized routine](https://github.com/JuliaLang/julia/blob/adf6d521afd125f2de12a3209b342148d78981c2/base/gmp.jl#L633) that does the additions in-place for an `Array`.

```julia
julia> @which sum(BigInt[3,4,5])
sum(arr::AbstractArray{BigInt,N} where N) in Base.GMP at gmp.jl:556

```

It can’t do that for a generic iterator like a generator because it doesn’t know in advance that the elements are `BigInt`.

---

<div class="post-metadata">

**Author:** ![bernb](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bernb/32/17377_2.png) [@bernb](https://discourse.julialang.org/u/bernb)\
**Post date:** [May 28, 2020, 1:19pm UTC](https://discourse.julialang.org/t/sum-over-bigint-better-performance-without-generator/40332/3 "2020-05-28T13:19:23Z")

</div>

I see, thanks a lot. I also found `methods(sum)` which gives me a nice overview of specializations.

---

<div class="post-metadata">

**Author:** ![ColinCaine](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/colincaine/32/7211_2.png) [@ColinCaine](https://discourse.julialang.org/u/ColinCaine)\
**Post date:** [May 31, 2020, 10:54am UTC](https://discourse.julialang.org/t/sum-over-bigint-better-performance-without-generator/40332/4 "2020-05-31T10:54:39Z")

</div>

This is probably faster still:

sum(n → BigInt(2)^n, 0:k-1)

That doesn’t allocate so much, but is still predictable to compiler, iirc.