BTW, does Python GC overhead only scale with the number of referenced objects since it uses reference counting? It do no scale with the memory consumption size?
Not sure what exactly you mean by “memory consumption” here but you are at most just seeing the time different it takes to free 1kB, 1MB or 1GB of memory.
Note that there are many different kinds of memory consumptions, total memory used, new allocation, new free, number of references (I don’t think number of references counts as memory concumption but I included it since you mentioned it) etc. Also, you are measuring the GC latency rather than the GC overhead in real code (throughput).
Yes. The overhead scales with the number of heap objects that need to be scanned, and this can make a linear time algorithm quadratic. Apart from “don’t write code like that”, I don’t know how to avoid this problem.
julia> using BenchmarkTools
julia> for N_ = [1,2,4,8,16]
N = N_ * 100_000
@show N
x = [rand(1:99,4) for i=1:N]; y=Set.(x);
GC.gc()
@time GC.gc()
@time broadcast!(Set, y, x)
@btime GC.gc()
@btime broadcast!(Set, $y, $x)
end;
N = 100000
0.086399 seconds (4 allocations: 160 bytes, 99.99% gc time)
0.108643 seconds (544.83 k allocations: 49.462 MiB, 37.66% gc time)
83.138 ms (0 allocations: 0 bytes)
57.079 ms (500000 allocations: 47.30 MiB)
N = 200000
0.153665 seconds (4 allocations: 160 bytes, 99.99% gc time)
0.163872 seconds (1.00 M allocations: 94.605 MiB, 46.82% gc time)
136.349 ms (0 allocations: 0 bytes)
156.661 ms (1000000 allocations: 94.60 MiB)
N = 400000
0.255492 seconds (4 allocations: 160 bytes, 100.00% gc time)
0.566196 seconds (2.00 M allocations: 189.209 MiB, 74.15% gc time)
244.466 ms (0 allocations: 0 bytes)
565.818 ms (2000000 allocations: 189.21 MiB)
N = 800000
0.545402 seconds (4 allocations: 160 bytes, 100.00% gc time)
2.156038 seconds (4.00 M allocations: 378.418 MiB, 87.63% gc time)
462.694 ms (0 allocations: 0 bytes)
2.165 s (4000000 allocations: 378.42 MiB)
N = 1600000
1.076869 seconds (4 allocations: 160 bytes, 100.00% gc time)
7.780642 seconds (8.00 M allocations: 756.836 MiB, 93.36% gc time)
898.342 ms (0 allocations: 0 bytes)
7.796 s (8000000 allocations: 756.84 MiB)
julia> @time GC.gc()
0.944954 seconds (4 allocations: 160 bytes, 100.00% gc time)
I am not sure why the heap fails to properly recover (make GC fast again) after the offending objects have been removed (bug?).
thanks, it seems that the GC overhead is not scaling with the array size.
for i in 1:9
println("GC time of array size ", 10^i, " byte")
a = Vector{UInt8}(undef, 10^i); @time GC.gc(); a = nothing; GC.gc()
end
output:
GC time of array size 10 byte
0.001955 seconds, 97.80% gc time
GC time of array size 100 byte
0.047600 seconds, 99.96% gc time
GC time of array size 1000 byte
0.042948 seconds, 99.97% gc time
GC time of array size 10000 byte
0.042336 seconds, 99.97% gc time
GC time of array size 100000 byte
0.042537 seconds, 99.97% gc time
GC time of array size 1000000 byte
0.042043 seconds, 99.96% gc time
GC time of array size 10000000 byte
0.042041 seconds, 99.96% gc time
GC time of array size 100000000 byte
0.078706 seconds, 99.98% gc time
GC time of array size 1000000000 byte
0.077601 seconds, 99.98% gc time
julia> for i in 1:8
println("GC time of array size ", 10^i, " byte")
a = fill("a", 10^i); @time GC.gc(); a = nothing; GC.gc()
end
GC time of array size 10 byte
0.110873 seconds, 100.00% gc time
GC time of array size 100 byte
0.062038 seconds, 100.00% gc time
GC time of array size 1000 byte
0.059134 seconds, 100.00% gc time
GC time of array size 10000 byte
0.062449 seconds, 100.00% gc time
GC time of array size 100000 byte
0.066105 seconds, 100.00% gc time
GC time of array size 1000000 byte
0.064020 seconds, 100.00% gc time
GC time of array size 10000000 byte
0.132790 seconds, 100.00% gc time
GC time of array size 100000000 byte
0.348486 seconds, 100.00% gc time
If your array is filled with actual objects this gets worse:
julia> for i in 1:7
println("GC time of array size ", 10^i, " byte")
a = [[] for i=1:10^i];
@time GC.gc(); a = nothing; GC.gc()
end
GC time of array size 10 byte
0.011026 seconds (2.04 k allocations: 113.338 KiB, 75.14% gc time)
GC time of array size 100 byte
0.061323 seconds (4 allocations: 160 bytes, 99.98% gc time)
GC time of array size 1000 byte
0.060049 seconds (4 allocations: 160 bytes, 99.98% gc time)
GC time of array size 10000 byte
0.061976 seconds (4 allocations: 160 bytes, 99.98% gc time)
GC time of array size 100000 byte
0.071098 seconds (4 allocations: 160 bytes, 99.98% gc time)
GC time of array size 1000000 byte
0.197971 seconds (4 allocations: 160 bytes, 99.99% gc time)
GC time of array size 10000000 byte
1.085488 seconds (4 allocations: 160 bytes, 100.00% gc time)
And if you force the gc to have bad memory access-patterns:
julia> using Random
julia> for i in 1:7
println("GC time of array size ", 10^i, " byte")
a = [[] for i=1:10^i];
shuffle!(a)
@time GC.gc(); a = nothing; GC.gc()
end
GC time of array size 10 byte
0.108458 seconds (4 allocations: 160 bytes, 99.99% gc time)
GC time of array size 100 byte
0.063253 seconds (4 allocations: 160 bytes, 99.99% gc time)
GC time of array size 1000 byte
0.061627 seconds (4 allocations: 160 bytes, 99.98% gc time)
GC time of array size 10000 byte
0.063966 seconds (4 allocations: 160 bytes, 99.99% gc time)
GC time of array size 100000 byte
0.082214 seconds (4 allocations: 160 bytes, 99.98% gc time)
GC time of array size 1000000 byte
0.327439 seconds (4 allocations: 160 bytes, 100.00% gc time)
GC time of array size 10000000 byte
3.483846 seconds (4 allocations: 160 bytes, 100.00% gc time)