Unstable results with high standard error in Julia

General Usage Performance
1

Has anyone encountered unstable results from Julia, specifically issues with large variance? For example, when I repeat the following experiment 100 times and record the time taken for each run, I find that there are always a few instances where the time is significantly higher than the average. Does anyone know the reason for this? How can I reduce the variance?

n=10^6;
rlevel = [[0;1;2;3;4;5;6;7;8;9] .//10; [99//100, 999//1000]];
klevel = [[1; 10; 100; 500] .// 10^4; [1;2;3;4;5;6;7;8;9] .// 10]

res = zeros(100,2);
Random.seed!(n)
for i in 1:100
    x0 = rand(Float64, n);
    x0sort = sort(x0, rev=true);
    k = Int64(ceil(n * klevel[1])) # 10
    tks = sum(x0sort[1:k]);
    r = tks * float(rlevel[1]); # 1

    res[i,1] = @elapsed begin
        tol::Float64 = 1e-8 # stopping criteria
        uL::Float64 = -Inf
        diffL::Float64 = vlengthL::Float64 = uR::Float64 = +Inf
        l_fold = unew::Float64 = r/k;
        uold = max_a::Float64 = maximum(x0);
        Ite_init::Integer = 0;
        sum_a_r1_old = 0.0;
        m_old = 0;
        l_fnew = 0.0;
        flag = -2;
      while true
        r1 = x0 .> unew
        m = sum(r1)
        sum_a_r1 = sum(x0[r1])
        l_fnew = (r - sum_a_r1 + m*unew)/k
    
        if unew - l_fnew < tol
            flag = 0;
            break
        end
  
        if m == k
          flag = -1;
          break
        end
        
        if m > k
          break
        end
        
        Ite_init += 1;
        uold = unew;
        l_fold = l_fnew
        m_old = m;
        sum_a_r1_old = sum_a_r1
        
        unew = (uold*m - k*l_fold)/(m-k);

      end
    end

    res[i, 2] = @elapsed begin
        r3 = x0.>l_fold
        compare_result = (r-k*l_fold) - (sum(x0[r3]) - sum(r3)*l_fold) + k*(uold - l_fold)
        flag = -1;
    end
end
mean(res, dims=1)
std(res, dims=1)
2

1
11188Γ—786 38.3 KB

2
21170Γ—786 47.3 KB

I get the following results. Some experiments are not stable, and they need a lot of time.

3

Without having looked at the code: garbage collector pauses?

If that’s the issue, then you want to reduce memory allocations in hot loops. See Performance Tips Β· The Julia Language, in particular the section Measure performance with @time and pay attention to memory allocation

2 Likes
4

the primary thing you need to do is put your code in functions

6 Likes
5

Without following the basic performance tips, your benchmarks will not be very valuable. Right now your code is working on global variables and is therefore probably very type unstable.

Start with reading this, and then test again.

Nevertheless, you will most likely see performance variability. Julia is not yet well suited for hard realtime workloads.

Additionally, you can use BenchmarkTools.jl instead of making your own benchmarking boilerplate.

1 Like
6

I had put the code in the functions before. However, the results are still unstable.

7

I put the code (the body in res[i, 1] = @elapsed begin ... end) into the function and I apply benchmark for this function. The results are as follows:

julia> @benchmark part1(x0, r, k)
BenchmarkTools.Trial: 2252 samples with 1 evaluation.
 Range (min … max):  1.744 ms …   9.512 ms  β”Š GC (min … max): 0.00% … 77.20%
 Time  (median):     2.056 ms               β”Š GC (median):    0.00%
 Time  (mean Β± Οƒ):   2.219 ms Β± 810.661 ΞΌs  β”Š GC (mean Β± Οƒ):  6.37% Β± 11.83%

     β–ˆβ–†β–„β–‚                                                      
  β–†β–ƒβ–ˆβ–ˆβ–ˆβ–ˆβ–ˆβ–ˆβ–‡β–…β–…β–ƒβ–β–β–β–β–ƒβ–β–β–β–β–β–β–β–β–β–β–β–β–β–β–β–β–β–β–ƒβ–β–β–β–β–β–β–β–β–β–β–β–β–β–β–ƒβ–ƒβ–ƒβ–…β–†β–‡β–‡β–…β–† β–ˆ
  1.74 ms      Histogram: log(frequency) by time       6.6 ms <

 Memory estimate: 7.75 MiB, allocs estimate: 6.

I am confused about there exists some extreme cases, leading to high standard error. I have use @code_warntype to check this function and it seems all right. In addition, the while loop in the function runs only once and then exits. The running time should be stable I think.

Furthermore, maybe I cannot use benchmark in the experiments, because I want to do many independent experiments with different inputs x0.

8

Your profile is telling you that Garbage Collection is the cause. Most of the iterations don’t stop for garbage collection, but some do, and when it does that dominates the time taken for the calculation.

1 Like
9

Thanks for your reply.

Can you please give me some advice how to solve this Garbage Collection issue?