# Allocations on threaded prefix algorithm

**URL:** <https://discourse.julialang.org/t/allocations-on-threaded-prefix-algorithm/33631>\
**Category:** Performance\
**Created:** [January 21, 2020, 6:10pm UTC](https://discourse.julialang.org/t/allocations-on-threaded-prefix-algorithm/33631 "2020-01-21T18:10:43Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![squirrel](https://avatars.discourse-cdn.com/v4/letter/s/96bed5/32.png) [@squirrel](https://discourse.julialang.org/u/squirrel)\
**Post date:** [January 21, 2020, 6:10pm UTC](https://discourse.julialang.org/t/allocations-on-threaded-prefix-algorithm/33631/1 "2020-01-21T18:10:43Z")

</div>

I’m going through the Parallel Computing course at [juliaacademy.com](http://juliaacademy.com). They give this example of a prefix code being rewritten in parallel. However, the video does not go through it, and when I run it on my own, I get a lot of memory allocations in the benchmark for `prefix_threads!` that I don’t know what it’s from.

Can anyone tell me why it’s doing so many allocations?

```julia
function prefix_serial!(y, ⊕)
    for i=2:length(y)
        y[i] = y[i-1] ⊕ y[i]
    end
    y
end

function prefix!(y, ⊕)
    l=length(y)
    k=ceil(Int, log2(l))
    @inbounds for j=1:k, i=2^j:2^j:min(l, 2^k) #"reduce"
        y[i] = y[i-2^(j-1)] ⊕ y[i]
    end
    @inbounds for j=(k-1):-1:1, i=3*2^(j-1):2^j:min(l, 2^k) #"expand"
        y[i] = y[i-2^(j-1)] ⊕ y[i]
    end
    y
end

using .Threads
function prefix_threads!(y, ⊕)
    l=length(y)
    k=ceil(Int, log2(l))
    for j=1:k
        @threads for i=2^j:2^j:min(l, 2^k) #"reduce"
            @inbounds y[i] = y[i-2^(j-1)] ⊕ y[i]
        end
    end
    for j=(k-1):-1:1
        @threads for i=3*2^(j-1):2^j:min(l, 2^k) #"expand"
            @inbounds y[i] = y[i-2^(j-1)] ⊕ y[i]
        end
    end
    return y
end

A = rand(500_000);

using BenchmarkTools
@btime prefix_serial!($(copy(A)), +);
@btime prefix!($(copy(A)), +);
@btime prefix_threads!($(copy(A)), +);

```

> 1.129 ms (0 allocations: 0 bytes)  
> 2.130 ms (0 allocations: 0 bytes)  
> 1.297 ms (1160 allocations: 126.78 KiB)