9e. Pre-Allocations

Initializing Vectors

Vector initialization refers to the process of creating a vector for subsequently filling it with values. The process typically involves two steps: reserving space in memory and populating that space with some initial values. An efficient approach to initializing a vector involves performing only the first step, keeping whatever content is held in the memory address at the moment of creation. Although Julia will display these contents as numerical values, note that they're essentially arbitrary and meaningless, explaining why they're referred to as undef (undefined).

There are two methods for initializing a vector with undef values. The first one is through a constructor, requiring the specification of length and element types. The second one is based on the function similar(y), which creates a vector with the same type and dimension as another existing vector y. This approach is particularly useful when your output matches the structure of an input.

Below, we compare the performance of approaches to initializing a vector. In particular, we establish that working with undef values is faster than populating the vector with specific values. To starkly show the differences in execution time, we repeat the process of vector creation 100,000 times.

x           = collect(1:100)
repetitions = 100_000                       # repetitions in a for-loop

function foo(x, repetitions)
    for _ in 1:repetitions
        Vector{Int64}(undef, length(x))
    end
end

  1.581 ms (100000 allocations: 85.45 MiB)

x           = collect(1:100)
repetitions = 100_000                       # repetitions in a for-loop

function foo(x, repetitions)
    for _ in 1:repetitions
        similar(x)
    end
end

  1.623 ms (100000 allocations: 85.45 MiB)

x           = collect(1:100)
repetitions = 100_000                       # repetitions in a for-loop

function foo(x, repetitions)
    for _ in 1:repetitions
        zeros(Int64, length(x))
    end
end

  7.530 ms (100000 allocations: 85.45 MiB)

x           = collect(1:100)
repetitions = 100_000                       # repetitions in a for-loop

function foo(x, repetitions)
    for _ in 1:repetitions
        ones(Int64, length(x))
    end
end

  4.674 ms (100000 allocations: 85.45 MiB)

x           = collect(1:100)
repetitions = 100_000                       # repetitions in a for-loop

function foo(x, repetitions)
    for _ in 1:repetitions
        fill(2, length(x))                  # vector filled with integer 2
    end
end

  4.877 ms (100000 allocations: 85.45 MiB)

Remark

Recall that _ is a convention adopted for dummy variables. These are variables with a value assigned, but without being used or referenced anywhere in the code. In the context of for-loops, the sole purpose of _ is to satisfy the syntax requirements, which expect a variable to iterate over. The symbol _ is purely a convention and any other symbol could be used instead.

Approaches to Initializing Vectors

We can initialize output by passing it to the function as a keyword argument. This enables the use of similar(x), where x is a previous function's argument. Given this, the following two implementations turn out to be equivalent.

function foo(x)
   output = similar(x) 
   # <some calculations using 'output'>
end

function foo(x; output = similar(x))

   # <some calculations using 'output'>
end

When multiple variables of the same type need to be initialized, array comprehensions offer a concise solution. A more efficient alternative is based on the so-called generators, which will be covered in a subsequent section. Although we haven't introduced generators yet, we present this approach because it's generally preferred: it avoids memory allocation and are therefore more performant. Moreover, the syntax for generators is identical to that of array comprehensions, with the only difference that square brackets [] are replaced by parentheses ().

x = [1,2,3]

function foo(x)
    a,b,c = [similar(x) for _ in 1:3]
    # <some calculations using a,b,c>
end

  49.848 ns (4 allocations: 320 bytes)

x = [1,2,3]

function foo(x)
    a,b,c = (similar(x) for _ in 1:3)
    # <some calculations using a,b,c>
end

  35.348 ns (3 allocations: 240 bytes)

Although the example uses similar(x), note that the same principle applies to other initialization methods such as Vector{Float64}(undef, length(x)).

Pre-Allocations for Intermediate Steps

So far, our discussion has centered around the benefits of pre-allocating vectors in nested for-loops. However, such benefits extend beyond that specific setting.

Broadly speaking, pre-allocating proves useful when: i) the vector serves an intermediate result that feeds into another operation, and ii) the intermediate result is computed inside a for-loop. When both conditions are met, reusing a pre-allocated vector consistently outperforms creating a new vector at each iteration.

To illustrate, consider a function foo that returns output, whose computation requires an intermediate variable temp. The key feature here is that, even though foo itself won't be called inside a nested for-loop, the computation of output is complex enough that it's convenient to split it into multiple steps.

If temp isn't pre-allocated, a new vector is created at each iteration as shown below.

x = rand(100)

function foo(x; output = similar(x))
    for i in eachindex(x)
        temp      = x .> x[i]
        output[i] = sum(temp)
    end

    return output
end

  14.700 μs (201 allocations: 11.81 KiB)

x = rand(100)

foo(x) = [sum(x .> x[i]) for i in eachindex(x)]

  14.600 μs (201 allocations: 11.81 KiB)

x = rand(100)

function foo(x) 
    temp   = [x .> x[i] for i in eachindex(x)]
    output = sum.(temp)
end

  15.100 μs (202 allocations: 12.69 KiB)

Next, we demonstrate different strategies that pre-allocate temp. The implementation of the pre-allocation differs in subtle but important ways from the nested-loop case.

First, because foo won't be eventually called in a for-loop, the pre-allocation of temp can be performed within the function itself. This means we don't need to define temp as an argument of foo. Second, since all iterations occur within a single for-loop, broadcasting becomes a particularly convenient option for updating temp.

Via a For-Loop or Broadcasting

The simplest strategy to avoid the allocations of temp is to pre-allocate it and update its values via broadcasting. By contrast, updating temp through a for-loop represents a more involved approach. The difference can be observed below.

x = rand(100)

function foo!(x; output = similar(x), temp = similar(x))
    for i in eachindex(x)        
        for j in eachindex(x)
            temp[j] = x[j] > x[i]
        end
        output[i] = sum(temp)
    end

    return output
end

  1.850 μs (2 allocations: 1.75 KiB)

x = rand(100)

function foo!(x; output = similar(x), temp = similar(x))
    for i in eachindex(x)
        temp     .= x .> x[i]
        output[i] = sum(temp)
    end

    return output
end

  1.660 μs (2 allocations: 1.75 KiB)

x = rand(100)

function foo!(x; output = similar(x), temp = similar(x))
    for i in eachindex(x)
        @. temp      = x > x[i]
           output[i] = sum(temp)
    end

    return output
end

  1.660 μs (2 allocations: 1.75 KiB)

Note that the two allocations observed are due to the creation of temp and output, which are unavoidable.

Via In-Place Function

Another way to avoid the memory allocations of temp is to pre-allocate it via an in-place function. We'll refer to this function as update_temp!, which is defined outside the for-loop and executed at each iteration. The advantage of this approach is modularity: by separating the update logic from the for-loop, we can focus on optimizing update_temp! independently if its performance becomes critical. This design also improves code readability and maintainability.

x = rand(100)

function update_temp!(x, temp, i)
    for j in eachindex(x)        
       temp[j] = x[j] > x[i]
    end    
end

function foo!(x; output = similar(x), temp = similar(x))
    for i in eachindex(x)
        update_temp!(x, temp, i)
        output[i] = sum(temp)
    end

    return output
end

  1.790 μs (2 allocations: 1.75 KiB)

x = rand(100)

update_temp!(x, temp, i) = (@. temp = x > x[i])

function foo!(x; output = similar(x), temp = similar(x))
    for i in eachindex(x)
           update_temp!(x, temp, i)
           output[i] = sum(temp)
    end

    return output
end

  1.680 μs (2 allocations: 1.75 KiB)

Adding a Nested For-Loop

Finally, let's study a scenario that combines the two situations discussed earlier: a function foo that requires an intermediate variable temp, and the repeated invocation of foo inside an outer for-loop. In this case, we're layering the complexity of intermediate pre-allocation with the demands of a nested loop structure.

In this combined setting, both output and temp must be initialized outside the function and passed in as arguments. This ensures that no vector is re-created at each iteration of the inner or outer for-loop. The following example illustrates an implementation that avoids unnecessary allocations by updating update_temp! via broadcasting.

x      = rand(100)



update_temp!(x, temp, i) = (@. temp = x > x[i])

function foo!(x; output = similar(x), temp = similar(x))
    for i in eachindex(x)
           update_temp!(x, temp, i)
           output[i] = sum(temp)
    end
    return output
end

calling_foo_in_a_loop(x) = [foo!(x) for _ in 1:1_000]

  1.734 ms (2001 allocations: 1.72 MiB)

x      = rand(100)
output = similar(x)
temp   = similar(x)

update_temp!(x, temp, i) = (@. temp = x > x[i])

function foo!(x, output, temp)    
    for i in eachindex(x)
           update_temp!(x, temp, i)
           output[i] = sum(temp)
    end
    return output
end

calling_foo_in_a_loop(x, output, temp) = [foo!(x, output, temp) for _ in 1:1_000]

  1.666 ms (1 allocation: 7.94 KiB)