# Sum of doubles

**URL:** <https://discourse.julialang.org/t/sum-of-doubles/68747>\
**Category:** Performance\
**Created:** [September 25, 2021, 11:27am UTC](https://discourse.julialang.org/t/sum-of-doubles/68747 "2021-09-25T11:27:18Z")\
**Posts on this page:** 17\
**Page:** 1

<div class="post-metadata">

**Author:** ![HexxCube](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hexxcube/32/24995_2.png) [@HexxCube](https://discourse.julialang.org/u/HexxCube)\
**Post date:** [September 25, 2021, 11:27am UTC](https://discourse.julialang.org/t/sum-of-doubles/68747/1 "2021-09-25T11:27:18Z")

</div>

I am trying to speed up my solution to the following exercise:

Given a Array of int values (from 1 to p), return the sum of doubles. If one of the values occurs only once, it does not count towards the sum.

- loneSum([1, 2, 3]) → 0
- loneSum([3, 2, 3]) → 6
- loneSum([3, 3, 3]) → 9

The current solution:

```julia
using BenchmarkTools
function sumofdoubles(values, p)
    sum = 0
    counts = zeros(UInt16, p)

    @inbounds for value in values
        counts[value] += 1
    end

    @inbounds for (i, v) in enumerate(counts)
        (v > 1) && (sum += i * v)
    end

    sum
end

p = 10^4
x = rand(1:p, 10^8)

@btime sumofdoubles($x, $p) #68.616 ms (2 allocations: 19.64 KiB)

```

Does anyone have an idea how to make it even faster?

---

<div class="post-metadata">

**Author:** ![Bardo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bardo/32/21601_2.png) [@Bardo](https://discourse.julialang.org/u/Bardo)\
**Post date:** [September 25, 2021, 11:57am UTC](https://discourse.julialang.org/t/sum-of-doubles/68747/2 "2021-09-25T11:57:53Z")

</div>

Do you have the original task description? There are quite some question marks:

> Given a Array of int values (from 1 to p), return the sum of doubles.

There are no doubles in 1:p, so probably you meant (of length p)

The loneSum examples work on a single array, your sumofdoubles(values, p) has two inputs

If the second parameter is just to pass the length (could be inferred from values), then your actual running example is not consistent 10^4 vs. 10^8.

I would go for building up a **set** (not dict), check for membership and add up.  
But wait, your solution is better, you just count and multiply later, instead of (more costly) adding values.

---

<div class="post-metadata">

**Author:** ![HexxCube](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hexxcube/32/24995_2.png) [@HexxCube](https://discourse.julialang.org/u/HexxCube)\
**Post date:** [September 25, 2021, 12:22pm UTC](https://discourse.julialang.org/t/sum-of-doubles/68747/3 "2021-09-25T12:22:54Z")

</div>

Sorry my post was not very clear. This is only a toy exercise, but still fun to see how far one can go with performance. I expanded on the original task description:

Given a Array of int values (all between 0 and 9), return the sum of doubles. If one of the values occurs only once, it does not count towards the sum.

- loneSum([1, 2, 3]) → 0
- loneSum([3, 2, 3]) → 6
- loneSum([3, 3, 3]) → 9

I wanted to expand on the original question. In my case there are 10^8 array elements (instead of 3) where each element is a random integer between 1 and 10^4 (instead of 0 to 9).

If i didn’t pass p as an argument it would already take 54 ms to find the maximum number (which is 10^4) in the array.

Thank you for your suggestion, but I can’t see a way how a solution using a dict could be faster.

---

<div class="post-metadata">

**Author:** ![LaurentPlagne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laurentplagne/32/10103_2.png) [@LaurentPlagne](https://discourse.julialang.org/u/LaurentPlagne)\
**Post date:** [September 25, 2021, 12:26pm UTC](https://discourse.julialang.org/t/sum-of-doubles/68747/4 "2021-09-25T12:26:21Z")

</div>

The effective bandwidth is

```julia
julia> GBpS=(8*10^8)/(68.61*10^6)
11.660107855997667

```

if I only take into account the big array reads.

With one thread, It may be close to the max Read From RAM bandwidth of your computer… How long does it takes to simply read `values` array ?

---

<div class="post-metadata">

**Author:** ![cjdoris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cjdoris/32/213133_2.png) [@cjdoris](https://discourse.julialang.org/u/cjdoris)\
**Post date:** [September 25, 2021, 5:15pm UTC](https://discourse.julialang.org/t/sum-of-doubles/68747/5 "2021-09-25T17:15:46Z")

</div>

You could eliminate all the multiplications by summing all the values and then subtracting the values which only occur once.

---

<div class="post-metadata">

**Author:** ![LaurentPlagne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laurentplagne/32/10103_2.png) [@LaurentPlagne](https://discourse.julialang.org/u/LaurentPlagne)\
**Post date:** [September 25, 2021, 6:24pm UTC](https://discourse.julialang.org/t/sum-of-doubles/68747/6 "2021-09-25T18:24:20Z")

</div>

The second loop cost almost nothing. All the time is spent in the count array definition.

---

<div class="post-metadata">

**Author:** ![ParadaCarleton](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/paradacarleton/32/20005_2.png) [@ParadaCarleton](https://discourse.julialang.org/u/ParadaCarleton)\
**Post date:** [September 25, 2021, 6:58pm UTC](https://discourse.julialang.org/t/sum-of-doubles/68747/7 "2021-09-25T18:58:29Z")

</div>

You could use LoopVectorization.jl – replace `@inbounds` with `@turbo` from LoopVectorization.jl and it should go much faster.

---

<div class="post-metadata">

**Author:** ![HexxCube](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hexxcube/32/24995_2.png) [@HexxCube](https://discourse.julialang.org/u/HexxCube)\
**Post date:** [September 25, 2021, 9:40pm UTC](https://discourse.julialang.org/t/sum-of-doubles/68747/8 "2021-09-25T21:40:48Z")

</div>

That could be it. How can this be tested without it getting optimized away by the compiler?  
When I profile the code most of the time is spent on `getindex`.

---

<div class="post-metadata">

**Author:** ![HexxCube](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hexxcube/32/24995_2.png) [@HexxCube](https://discourse.julialang.org/u/HexxCube)\
**Post date:** [September 25, 2021, 9:43pm UTC](https://discourse.julialang.org/t/sum-of-doubles/68747/9 "2021-09-25T21:43:05Z")

</div>

I just tried that and when i simply replace `@indbounds` with `@turbo` i get the following error:

```julia
LoadError: MethodError: no method matching canonicalize_range(::Vector{Int64})

```

Would there no be a problem with a race condition anyway?

---

<div class="post-metadata">

**Author:** ![LaurentPlagne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laurentplagne/32/10103_2.png) [@LaurentPlagne](https://discourse.julialang.org/u/LaurentPlagne)\
**Post date:** [September 25, 2021, 9:47pm UTC](https://discourse.julialang.org/t/sum-of-doubles/68747/10 "2021-09-25T21:47:51Z")

</div>

I guess that a linear sum of array’s elements (maybe not the Julia’s Base.sum based on reduce) time is mostly dominated by the read bandwidth for arrays larger that L3 cache. This should gives you an upper bound for your algorithm performance.

Another way to see it is to use a smaller array (\<1.e6 elts) and you should see a large performance (per elt) bump because BenchmarkTools will keep a hot cache.

---

<div class="post-metadata">

**Author:** ![HexxCube](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hexxcube/32/24995_2.png) [@HexxCube](https://discourse.julialang.org/u/HexxCube)\
**Post date:** [September 25, 2021, 9:58pm UTC](https://discourse.julialang.org/t/sum-of-doubles/68747/11 "2021-09-25T21:58:15Z")

</div>

That must be the limiting factor. A simple `sum(x)` already takes 53.779 ms.  
Thank you for helping me understand the bottleneck.

---

<div class="post-metadata">

**Author:** ![LaurentPlagne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laurentplagne/32/10103_2.png) [@LaurentPlagne](https://discourse.julialang.org/u/LaurentPlagne)\
**Post date:** [September 25, 2021, 10:01pm UTC](https://discourse.julialang.org/t/sum-of-doubles/68747/12 "2021-09-25T22:01:12Z")

</div>

You may have some acceleration with threads (x2 on dual channels or 4x on quad channels) but you must replicate the counters to avoid data races.  
Another way is to reduce the size of your Integers : try it with values of type Vector{Int32}

---

<div class="post-metadata">

**Author:** ![HexxCube](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hexxcube/32/24995_2.png) [@HexxCube](https://discourse.julialang.org/u/HexxCube)\
**Post date:** [September 25, 2021, 10:12pm UTC](https://discourse.julialang.org/t/sum-of-doubles/68747/13 "2021-09-25T22:12:44Z")

</div>

Let’s leave at this. My friend who used Java with the same parameters had a time of 134 ms. I just wanted to flex on him with Julia.

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [September 26, 2021, 4:56am UTC](https://discourse.julialang.org/t/sum-of-doubles/68747/14 "2021-09-26T04:56:14Z")

</div>

> [@HexxCube](#):
>
> I just tried that and when i simply replace `@indbounds` with `@turbo` i get the following error:
> 
> ```julia
> LoadError: MethodError: no method matching canonicalize_range(::Vector{Int64})
> 
> ```

You’d need something like:

```julia
function sumofdoubles(values, p)
    sum = 0
    counts = zeros(UInt16, p)

    @turbo for i in eachindex(values)
        value = values[i]
        counts[value] += 1
    end

    @inbounds for (i, v) in enumerate(counts)
        (v > 1) && (sum += i * v)
    end

    sum
end

```

Or, alternatively, `counts[values[i]] += 1`.  
[Here](https://github.com/JuliaSIMD/LoopVectorization.jl/issues/334) is the associated issue.

> [@HexxCube](#):
>
> Would there no be a problem with a race condition anyway?

Yes, the above would get an incorrect answer if multiple of the same `value` occur close enough together.  
It also requires very slow memory operations, so it’s unlikely to really be faster anyway: you can’t really speed up non-consecutive memory operations with SIMD, unless they have particular patterns allowing you to use consecutive memory accesses + shuffles.  
If the rest of the computation is expensive enough, SIMD can still help.  
Here, the rest of the computation (`+=1`) is not expensive.

And unlike threads, SIMD can’t help with memory bottlenecks.

---

<div class="post-metadata">

**Author:** ![SteffenPL](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/steffenpl/32/206270_2.png) [@SteffenPL](https://discourse.julialang.org/u/SteffenPL)\
**Post date:** [September 26, 2021, 6:32am UTC](https://discourse.julialang.org/t/sum-of-doubles/68747/15 "2021-09-26T06:32:46Z")

</div>

I was just trying to do it differently, (without success!)  
Anyway, creating two `BitVector`s to figure out if an array already occurred once or twice needs less memory, but is slower on my computer.

```julia
using BenchmarkTools
function sumofdoubles_bitarray(values, p)
    s = 0
    first_val = trues(p)
    second_val = trues(p)

    @inbounds for (i, v) in enumerate(values)
        if first_val[v]
            first_val[v] = false
        else
            if second_val[v]
                s += 2*v
                second_val[v] = false
            else
                s += v
            end
        end
    end

    s
end

p = 10^4
x = rand(1:p, 10^8)

@btime sumofdoubles_bitarray($x, $p) # 173.226 ms (4 allocations: 2.72 KiB)
# for comparison
@btime sumofdoubles($x, $p) # 102.769 ms (2 allocations: 19.64 KiB)

```

---

<div class="post-metadata">

**Author:** ![LaurentPlagne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laurentplagne/32/10103_2.png) [@LaurentPlagne](https://discourse.julialang.org/u/LaurentPlagne)\
**Post date:** [September 26, 2021, 7:08am UTC](https://discourse.julialang.org/t/sum-of-doubles/68747/16 "2021-09-26T07:08:40Z")

</div>

Again the second loop consumes little time and the performance is memory bound.  
The following code (marginally improved ) performance gives the following results on my laptop:

```julia
t_with_Int64 = 0.079648421
t_with_Int32 = 0.056981823
t_1_loop_with_Int32 = 0.067936515

```

```julia
using BenchmarkTools
using Random

Random.seed!(1234)

function sumofdoubles(values, p)
    sum = 0
    counts = zeros(UInt16,p)
    _1 = one(UInt16) # this seems to give a small accelaration

    @inbounds for value in values
        counts[value] += _1
    end

    for (i, v) in enumerate(counts)
        (v > 1) && (sum += i * v)
    end

    sum
end

function only_counts(values, p)
    sum = 0
    counts = zeros(UInt16,p)
    _1 = one(UInt16)

    @inbounds for value in values
        counts[value] += _1
    end

    sum+=Int(counts[1])
end

p = 10^4
x = rand(1:p, 10^8)

t_with_Int64=@belapsed sumofdoubles($x, $p)

x32 = Vector{Int32}(x)
t_with_Int32=@belapsed sumofdoubles($x32, $p)

x32 = Vector{Int32}(x)
t_1_loop_with_Int32=@belapsed only_counts($x32, $p)
@show t_with_Int64
@show t_with_Int32
@show t_1_loop_with_Int32

```

---

<div class="post-metadata">

**Author:** ![pjentsch0](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pjentsch0/32/15148_2.png) [@pjentsch0](https://discourse.julialang.org/u/pjentsch0)\
**Post date:** [September 26, 2021, 9:02pm UTC](https://discourse.julialang.org/t/sum-of-doubles/68747/17 "2021-09-26T21:02:55Z")

</div>

Nice idea. I wonder why it is slower given it uses so much less memory.

You can use slightly less memory by going with a `DiBitVector` from DataStructures.jl but the performance is the same.