Insert value with fixed size/gc time

General Usage Performance
1

I am a julia beginner. I am working on a large structural (economic) model. But, the problem is that one iteration of the entire model takes 395 seconds, and its 42.84% consists of gc time. My suspicion is that the following code causes such high gc time, but I am not 100% sure.

using BenchmarkTools

function insert_value2!(array_val, array_b, array_l, array_τ, current_val, b_pol, l_pol, τ_pol)
    if current_val > first(array_val)
        ii = searchsortedlast(array_val, current_val)
        if ii!= 1
            copyto!(array_val, [@view array_val[2:ii]; current_val]) 
            copyto!(array_b, [@view array_b[2:ii]; b_pol])
            copyto!(array_l, [@view array_l[2:ii]; l_pol])
            copyto!(array_τ, [@view array_τ[2:ii]; τ_pol])          
        else
            array_val[1] = current_val
            array_b[1] = b_pol
            array_l[1] = l_pol
            array_τ[1] = τ_pol    
        end
    end
end

array_val = [1.0, 2.0, 3.0, 4.0, 5.0];
array_b = [1, 2, 3, 4, 5];
array_l = [1, 2, 3, 4, 5];
array_τ = [1, 2, 3, 4, 5];
current_val = 2.5;
b_pol = 2;
l_pol = 2;
τ_pol = 2; 

@btime insert_value2!(array_val, array_b, array_l, array_τ, current_val, b_pol, l_pol, τ_pol);

I got some hint from here when I wrote down this code. In the actual code, the size of each array is 200, and this function is inside of multiple loops (approximately, 81 \times 51 \times 21 \times 81). Thus, the efficiency is essential. The feature of this code is that the rearrangement is initiated by current_val. Also, each array is weakly increasing. Except array_val, all arrays are weakly increasing integer array. Is this causing high gc time? Is there a better way to speed up? Thanks!

2

I do not want to comment on your code here, I leave that to others. But did you start Julia with these or similar parameters?

julia --gcthreads=8,1

The first number should be the number of your fast CPU cores.

This might speed up your code and reduce the GC time.

2 Likes
3

This pattern allocates the array [@view array_val ...; current_val] before it fills it in and copies it to array_val. If you instead write it as a loop there will be no allocations

for i in 2:ii
   array_val[i-i] = array_val[i]
end
array_val[ii] = current_val

And copyto! is not safe for shifting an array in this way, it says in the docs: “Behavior can be unexpected when any mutated argument shares memory with any other argument.”

2 Likes
4

There is however a possibly faster method. You can shift the array explicitly with memmove from Libc. It will work correctly on overlapping memory areas, but you’ll need to be careful. Its third argument is the number of bytes to copy, which you need to compute from the element size of your array.

Libc.memmove(pointer(array_val), pointer(array_val,2), (ii-1)*sizeof(eltype(array_val)))
array_val[ii] = current_val

The memmove might be faster than a loop because it typically will utilize any form of vectorized copy available in your system, whereas the loop may or may not do such things. (copyto! currently uses memmove under the hood, but you’re not guaranteed that).

5

Thanks. Now, gc time is reduced to 1 percent.

2 Likes
6

There is the minor wrinkle that memmove is afaiu only safe with bitstypes. If you have a small bits union, then you also need to set the types. If you have managed object references, then the failure mode is more insiduous: There is a write-barrier when you mutate an old object to point to a young one. Memmove tramples over the write barrier, with potential use-after-free.

1 Like