# Rollsum/cumulative optimisation
**URL:** https://discourse.julialang.org/t/rollsum-cumulative-optimisation/99718
**Category:** Performance
**Tags:** question
**Created:** [June 1, 2023, 10:09am UTC](https://discourse.julialang.org/t/rollsum-cumulative-optimisation/99718 "2023-06-01T10:09:14Z")
**Posts on this page:** 13
**Page:** 1
### Author:  [@gitboy16](https://discourse.julialang.org/u/gitboy16)
#### Post date: [June 1, 2023, 10:09am UTC](https://discourse.julialang.org/t/rollsum-cumulative-optimisation/99718/1 "2023-06-01T10:09:15Z")
Hi,
I was wondering if someone can help me speed up the below function (roll\_sum) in anyway? (Multi-threading, better algorithm,…etc).
An easy way would be to remove the `copy` but I have added it so it is easy to benchmark. It is really the double for loop part that I am trying to optimize.
Thank you for your help.
```julia
import Random
Random.seed!(1234)
A = rand(0:100, 1_000_000, 8)
cvt(x::UInt64) = string(x, base = 10)
function roll_sum(
octs::Matrix{UInt64},
len::StepRange{Int64, Int64},
k::Int64,
)
cts = copy(octs)
rollSum = UInt64(0)
@inbounds for j in len
for i in 1:k
tmp = cts[j, i]
cts[j, i] = rollSum
rollSum += tmp
end
end
return cts
end
B = A .% UInt64
sz = size(B)
using BenchmarkTools
@btime roll_sum(B, 1:1:sz[1], sz[2]);
# to see the result in human readable format
roll_sum(B, 1:1:sz[1], sz[2]) .|> cvt
```
---
### Author:  [@screw\_dog](https://discourse.julialang.org/u/screw_dog)
#### Post date: [June 1, 2023, 2:27pm UTC](https://discourse.julialang.org/t/rollsum-cumulative-optimisation/99718/2 "2023-06-01T14:27:12Z")
Here’s a couple of alternatives:
```julia
function roll_sum2(octs, len, k)
cts = Matrix{UInt64}(undef, length(len), k)
rollsum = zero(UInt64)
@inbounds for j in len, i in 1:k
cts[j, i] = rollsum
rollsum += octs[j, i]
end
return cts
end
function roll_sum3(octs, len, k)
cts = permutedims(octs)
rollsum = zero(UInt64)
@inbounds for i in 1:k, j in len
tmp = cts[j, i]
cts[j, i] = rollsum
rollsum += tmp
end
return cts
end
```
The first avoids copying the data (ie using the `undef` initialiser), the second copies the data into column-major order which is more efficient for Julia (see [the docs](https://docs.julialang.org/en/v1/manual/performance-tips/#man-performance-column-major)). I get these results:
```julia-repl
50.147 ms (4 allocations: 61.04 MiB)
35.773 ms (4 allocations: 61.04 MiB)
41.850 ms (4 allocations: 61.04 MiB)
```
which suggests with this data a significant amount of time is spent copying. If you could arrange your data in column-major order (ie the rolling sum is computed down columns and then across rows) you’d get further speedup combining both these approaches.
---
### Author:  [@gitboy16](https://discourse.julialang.org/u/gitboy16)
#### Post date: [June 1, 2023, 2:32pm UTC](https://discourse.julialang.org/t/rollsum-cumulative-optimisation/99718/3 "2023-06-01T14:32:46Z")
Thank you but I have added the copy just to be able to benchmark it. But in reality I don’t need to copy it and can do everything inplace. I am more looking for improving the double for loop part by using a better algorithm, multi-threading or any other trick…
---
### Author:  [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)
#### Post date: [June 1, 2023, 4:03pm UTC](https://discourse.julialang.org/t/rollsum-cumulative-optimisation/99718/4 "2023-06-01T16:03:25Z")
If you can’t find anything better, this one fits the bill
```julia
reshape(cumsum(vec(B')),8,:)'
```
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [June 1, 2023, 4:04pm UTC](https://discourse.julialang.org/t/rollsum-cumulative-optimisation/99718/5 "2023-06-01T16:04:33Z")
Note that this algorithm discards the last element of the input array from the sum, is that what you want? (This is because the first element of the return value is 0 rather than the first element of the input, the latter being the way `cumsum` works.)
Have you considered just (a) storing `octs` in the opposite/transposed order so that you can skip the call to `permutedims`, and (b) then just calling something like:
```julia
roll_sum(A) = reshape(cumsum(vec(A)), size(A))
```
---
### Author:  [@gitboy16](https://discourse.julialang.org/u/gitboy16)
#### Post date: [June 1, 2023, 4:24pm UTC](https://discourse.julialang.org/t/rollsum-cumulative-optimisation/99718/6 "2023-06-01T16:24:16Z")
Yes it discard the last element and the first is 0. The answer of @rocco_sprmnt21 is close but does not return the correct result with regards to first and last element.
---
### Author:  [@gitboy16](https://discourse.julialang.org/u/gitboy16)
#### Post date: [June 1, 2023, 4:25pm UTC](https://discourse.julialang.org/t/rollsum-cumulative-optimisation/99718/7 "2023-06-01T16:25:08Z")
Thank you @stevengj , can you please provide an example? I am not sure to get what you mean. Thanks.
---
### Author:  [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)
#### Post date: [June 1, 2023, 4:45pm UTC](https://discourse.julialang.org/t/rollsum-cumulative-optimisation/99718/8 "2023-06-01T16:45:18Z")
using ShiftedArrays
```julia
reshape(cumsum(ShiftedArray(vec($B'),1,default=0x0)),8,:)'
```
but if you can do what @stevengj recommends you save part of the transformations
---
### Author:  [@gitboy16](https://discourse.julialang.org/u/gitboy16)
#### Post date: [June 2, 2023, 8:59am UTC](https://discourse.julialang.org/t/rollsum-cumulative-optimisation/99718/9 "2023-06-02T08:59:05Z")
Thank you @rocco_sprmnt21 for your help. I think I will keep searching for something faster.
---
### Author:  [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)
#### Post date: [June 2, 2023, 11:47am UTC](https://discourse.julialang.org/t/rollsum-cumulative-optimisation/99718/10 "2023-06-02T11:47:26Z")
check this expression
```julia
reshape(accumulate(+,ShiftedArray(vec(B),1,default=zero(UInt64)),init=0),8,:)'
```
---
### Author:  [@gitboy16](https://discourse.julialang.org/u/gitboy16)
#### Post date: [June 2, 2023, 1:19pm UTC](https://discourse.julialang.org/t/rollsum-cumulative-optimisation/99718/11 "2023-06-02T13:19:17Z")
Your previous answer is faster on my computer.
---
### Author:  [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)
#### Post date: [June 2, 2023, 2:11pm UTC](https://discourse.julialang.org/t/rollsum-cumulative-optimisation/99718/12 "2023-06-02T14:11:42Z")
I tried the expression inside a function in the following way.
Here the time I get in a clean REPL session
```julia
julia> using BenchmarkTools
julia> import Random
julia> Random.seed!(1234)
Random.TaskLocalRNG()
julia> A = rand(0:100, 1_000_000, 8);
julia> B = A .% UInt64
1000000×8 Matrix{UInt64}:
julia> using ShiftedArrays
julia> function roll_sum4(B)
vb=vec(B)
Out=similar(vb)
accumulate!(+,Out,ShiftedArray(vb,1,default=zero(UInt64)),init=0)
reshape(Out,8,:)'
end
roll_sum4 (generic function with 1 method)
julia> @btime reshape(accumulate(+,ShiftedArray(vec($B),1,default=zero(UInt64)),init=0),8,:)'
20.844 ms (9 allocations: 61.04 MiB)
julia> @btime roll_sum4($B)
18.623 ms (9 allocations: 61.04 MiB)
julia> @btime reshape(cumsum(ShiftedArray(vec($B'),1,default=0x0)),8,:)'
25.406 ms (4 allocations: 61.04 MiB)
1000000×8 adjoint(::Matrix{UInt64}) with eltype UInt64:
```
---
### Author:  [@gitboy16](https://discourse.julialang.org/u/gitboy16)
#### Post date: [June 5, 2023, 11:36am UTC](https://discourse.julialang.org/t/rollsum-cumulative-optimisation/99718/13 "2023-06-05T11:36:53Z")
I will mark this as the solution even if I am not excited about it. Thank you.