Trying to figure out how to do things faster with parallelism in nim - See https://en.wikipedia.org/wiki/Prefix_sum

prefix.nim

import times, sequtils, math, algorithm, strformat

proc ones(n: int): seq =
    ## Helper to make a sequence of ones
    result = newSeq[int](n)
    result.fill(1)

proc prefixSumWithPipes(p: seq): seq {.noInit.} =
    result = p
    var last = p
    var c = 0
    let
      t0 = cpuTime()
      n_vals = len(p)
      jobs = int(ceil(log2(float(n_vals))))
    
    # For each step that can be done in parallel
    for j in 1..jobs:

      # Previous number's index delta, as well as starint point
      let backpointer = 2^(j-1)

      # Store previous stage in last variable
      var last = result

      # Loop over
      for i in `||`(backpointer, n_vals - 1):
          let prev = i - backpointer
          result[i] = last[prev] + last[i]
          c += 1

    echo &"Pipes: \t{len(p)} \t{cpuTime() - t0} \t Added: {c}/{len(p)}"


proc naiveCumulativeSum(p: seq): seq {.noInit.} =
    let t0 = cpuTime()
    for i in 1..len(p)-1:
        result[i] += result[i-1]
    echo &"Naive: \t{len(p)} \t{cpuTime() - t0} \t Added {len(p)}/{len(p)}"
    

var data = ones(16) # should have added 49 units for the pipes, a span of 4
discard prefixSumWithPipes(data)
discard naiveCumulativeSum(data)

# Pipes:  16      6.400000000000069e-05    Added: 49/16
# Naive:  16      2.000000000000265e-06    Added 16/16

data = ones(10^6) 
discard prefixSumWithPipes(data)
discard naiveCumulativeSum(data)

# Pipes:  1000000         0.333885         Added: 18951425/1000000
# Naive:  1000000         0.01581899999999997      Added 1000000/1000000