# Why summing a generator is slightly slower?

**URL:** <https://discourse.julialang.org/t/why-summing-a-generator-is-slightly-slower/23629>\
**Category:** General Usage\
**Tags:** performance\
**Created:** [April 28, 2019, 8:51pm UTC](https://discourse.julialang.org/t/why-summing-a-generator-is-slightly-slower/23629 "2019-04-28T20:51:15Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![e3c6](https://avatars.discourse-cdn.com/v4/letter/e/e79b87/32.png) [@e3c6](https://discourse.julialang.org/u/e3c6)\
**Post date:** [April 28, 2019, 8:51pm UTC](https://discourse.julialang.org/t/why-summing-a-generator-is-slightly-slower/23629/1 "2019-04-28T20:51:15Z")

</div>

Why is this:

```julia
@btime (s = 0; for i = 1:10^6 s += i end; s)
# 4.449 ns (0 allocations: 0 bytes)
# 500000500000

```

significantly faster than this:

```julia
@btime sum(i for i = 1:10^6)
# 7.038 ns (0 allocations: 0 bytes)
# 500000500000

```

Though the difference is small, it’s noticeable.  
What is the extra operation that the generator approach is doing?

---

<div class="post-metadata">

**Author:** ![ffevotte](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ffevotte/32/6587_2.png) [@ffevotte](https://discourse.julialang.org/u/ffevotte)\
**Post date:** [April 28, 2019, 9:35pm UTC](https://discourse.julialang.org/t/why-summing-a-generator-is-slightly-slower/23629/2 "2019-04-28T21:35:48Z")

</div>

First, notice that a few ns is much faster than what would be expected for 10^6 ops. In fact, in both cases, the compiler translated the code into a constant-complexity algorithm similar to  
\displaystyle\sum\_{i=1}^n i = \frac{n(n+1)}{2}

This can be shown by making n vary, and observing that the computing time stays the same.

```julia
julia> @btime sum(i for i = 1:1_000_000)
  4.316 ns (0 allocations: 0 bytes)
500000500000

julia> @btime sum(i for i = 1:10_000)
  3.962 ns (0 allocations: 0 bytes)
50005000

julia> @btime sum(i for i = 1:100)
  4.323 ns (0 allocations: 0 bytes)
5050

```

  

Now, as to your real question, looking at the output of `@code_native` for both variants, it looks like one of the function calls in the generator version has not been inlined, whereas the for loop of course involves no function call at all.

This difference would not have been noticeable in any other “regular” case where the compiler would not have known a handy trick to transform a loop into a mere arithmetic formula.

---

<div class="post-metadata">

**Author:** ![e3c6](https://avatars.discourse-cdn.com/v4/letter/e/e79b87/32.png) [@e3c6](https://discourse.julialang.org/u/e3c6)\
**Post date:** [April 28, 2019, 9:47pm UTC](https://discourse.julialang.org/t/why-summing-a-generator-is-slightly-slower/23629/3 "2019-04-28T21:47:14Z")

</div>

> [@ffevotte](#):
>
> First, notice that a few ns is much faster than what would be expected for 10^6 ops. In fact, in both cases, the compiler translated the code into a constant-complexity algorithm similar to  
> n(n+1)/2

Wow… I had no idea the compiler could be so clever.

> [@ffevotte](#):
>
> Now, as to your real question, looking at the output of `@code_native` for both variants, it looks like one of the function calls in the generator version has not been inlined, whereas the for loop of course involves no function call at all.

How exactly are you using `@code_native` here? I am wondering because my original examples are not function calls and you cannot apply `@code_native` directly on them.

---

<div class="post-metadata">

**Author:** ![ffevotte](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ffevotte/32/6587_2.png) [@ffevotte](https://discourse.julialang.org/u/ffevotte)\
**Post date:** [April 28, 2019, 9:54pm UTC](https://discourse.julialang.org/t/why-summing-a-generator-is-slightly-slower/23629/4 "2019-04-28T21:54:11Z")

</div>

> [@e3c6](#):
>
> How exactly are you using `@code_native` here? I am wondering because my original examples are not function calls and you cannot apply `@code_native` directly on them.

Well, I wrap your expressions into functions 🙂

```julia
function f(n)
    s = 0
    for i in 1:n
        s += i
    end
    s
end

g(n) = sum(i for i in 1:n)

```

```julia
julia> @btime f(1_000_000)
  1.881 ns (0 allocations: 0 bytes)
500000500000

julia> @btime g(1_000_000)
  4.108 ns (0 allocations: 0 bytes)
500000500000

```

```julia
julia> @code_native f(10)
        .text
; special case: if n==0 return 0
        testq %rdi, %rdi
        jle L32
; general case: n != 0
; this is where the magic happens and the formula is evaluated
        leaq -1(%rdi), %rdx
        leaq -2(%rdi), %rax
        mulxq %rax, %rax, %rcx
        shldq $63, %rax, %rcx
        leaq (%rcx,%rdi,2), %rax
        addq $-1, %rax
        retq
L32:
        xorl %eax, %eax
        retq
        nopw %cs:(%rax,%rax)

```

```julia
julia> @code_native g(10)
... # much longer output, without any `mul`, but with `call`

```

---

<div class="post-metadata">

**Author:** ![e3c6](https://avatars.discourse-cdn.com/v4/letter/e/e79b87/32.png) [@e3c6](https://discourse.julialang.org/u/e3c6)\
**Post date:** [April 28, 2019, 10:16pm UTC](https://discourse.julialang.org/t/why-summing-a-generator-is-slightly-slower/23629/5 "2019-04-28T22:16:35Z")

</div>

> [@ffevotte](#):
>
> looking at the output of `@code_native` for both variants, it looks like one of the function calls in the generator version has not been inlined

Is that okay, or a bug in the Julia compiler?

---

<div class="post-metadata">

**Author:** ![ffevotte](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ffevotte/32/6587_2.png) [@ffevotte](https://discourse.julialang.org/u/ffevotte)\
**Post date:** [April 28, 2019, 10:24pm UTC](https://discourse.julialang.org/t/why-summing-a-generator-is-slightly-slower/23629/6 "2019-04-28T22:24:44Z")

</div>

I would say it is OK: the function still has to perform a few tests in order to detect whether we are in the n==0 specific case (and these tests are probably a bit more complicated than in the case of the `for` loop, since they involve the iterator interface implemented by the generator). In light of this, the compiler might very well have decided that inlining the next function call did not present too much of a benefit.

In the general case (and this test case is far from being representative of a real reduction over a collection), I would expect this to have a significant impact only for very small collections (let’s say less than 10 elements).

---

<div class="post-metadata">

**Author:** ![e3c6](https://avatars.discourse-cdn.com/v4/letter/e/e79b87/32.png) [@e3c6](https://discourse.julialang.org/u/e3c6)\
**Post date:** [April 28, 2019, 10:26pm UTC](https://discourse.julialang.org/t/why-summing-a-generator-is-slightly-slower/23629/7 "2019-04-28T22:26:54Z")

</div>

@ffevotte Thanks so much for your answers.

---

<div class="post-metadata">

**Author:** ![ffevotte](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ffevotte/32/6587_2.png) [@ffevotte](https://discourse.julialang.org/u/ffevotte)\
**Post date:** [April 29, 2019, 9:55am UTC](https://discourse.julialang.org/t/why-summing-a-generator-is-slightly-slower/23629/8 "2019-04-29T09:55:44Z")

</div>

> [@e3c6](#):
>
> Wow… I had no idea the compiler could be so clever.

A colleague of mine just sent me the following link, which is relevant here:

> **[How LLVM optimizes power sums](https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geometric-sums.html)**
>
> LLVM optimizes power sums, such as int sum(int count) { int result = 0; for (int j = 0; j \< count; ++j) result += j\*j; return...