search

andyferris / Dictionaries.jl

An alternative interface for dictionaries in Julia, for improved productivity and performance
Other
278 stars 28 forks source link

Garbage collection of deleted keys #57

Open jekyllstein opened 2 years ago

jekyllstein commented 2 years ago

I ran into this issue a while ago trying to add/remove keys from a dictionary and having the memory build up despite the dictionary itself not growing in size. I was curious how the behavior might be different with Dictionaries.jl but I'm running into the same difference in behavior from Windows to Linux that I experienced here.

For the following code I have it saved in a file called dict_vs_Dictionaries_allocation_test.jl. I have it in an environment with BenchmarkTools and Dictionaries installed

using Pkg
Pkg.activate(@__DIR__)

using Dictionaries
using BenchmarkTools
using InteractiveUtils

versioninfo()

function test(use_dict)
    use_dict ? println("Using Base dict") : println("Using Dictionaries.jl")
    totmem = Int64(Sys.total_memory())

    getfreemem() = Int64(Sys.free_memory())

    # println()
    # if isempty(ARGS)
    #   println("Testing in global space")
    # else
    #   println("Testing inside a function")
    # end
    # println()

    function create_test_dict(totmem)
        testdict = Dict{Int64, Matrix{Float64}}()
        #insert 100k elements
        for i in 1:100000
            push!(testdict, i => ones(Float64, 100, 100))
        end
        freemem = totmem - getfreemem()

        #delete the first 50k elements
        for i in 1:50000
            delete!(testdict, i)
        end
        return freemem, testdict
    end

    function create_test_dictionary(totmem)
        testdict = Dictionary{Int64, Matrix{Float64}}()
        #insert 100k elements
        for i in 1:100000
            insert!(testdict, i, ones(Float64, 100, 100))
        end
        freemem = totmem - getfreemem()

        #delete the first 50k elements
        for i in 1:50000
            delete!(testdict, i)
        end
        return freemem, testdict
    end

    initialfreemem = totmem - getfreemem()

    mem2, testdict = if use_dict
        @time create_test_dict(totmem)
    else
        @time create_test_dictionary(totmem)
    end

    #try to garbage collect parts of dictionary now that it is no longer needed
    GC.gc()

    post_gc_mem = totmem - getfreemem()

    println("Memory added from dictionary is $((mem2 - initialfreemem)/(10^9)) gigabytes")
    println("Memory freed from clearing half of dictionary is $((mem2 - post_gc_mem)/(10^9)) gigabytes")
    println("Final memory usage as a percent of allocated is $(100*(post_gc_mem - initialfreemem)/(mem2 - initialfreemem))% (ideally would be 50%)")
    #verify that testdict is missing the first 50k indicies
    try 
        testdict[1]
    catch
        println("Could not access index 1 as expected")
    end
    println("Waiting 10 seconds to see if gc occurs")
    1 + 1 #random code execution to see if it affects gc
    sleep(10)
    println("Final memory usage as a percent of allocated is $(100*((totmem - getfreemem()) - initialfreemem)/(mem2 - initialfreemem))% (ideally would be 50%)")
    println("_____________________________________________________________________________")
end

#toggle to use dict or Dictionaries.jl
use_dict = isempty(ARGS) ? true : false
test(use_dict)

Project.toml

[deps]
BenchmarkTools = "6e4b80f9-dd63-53aa-95a3-0cdb28fa8baf"
Dictionaries = "85a47980-9c8c-11e8-2b9f-f7ca1fa99fb4"

Manifest.toml

# This file is machine-generated - editing it directly is not advised

[[BenchmarkTools]]
deps = ["JSON", "Logging", "Printf", "Statistics", "UUIDs"]
git-tree-sha1 = "c31ebabde28d102b602bada60ce8922c266d205b"
uuid = "6e4b80f9-dd63-53aa-95a3-0cdb28fa8baf"
version = "1.1.1"

[[Dates]]
deps = ["Printf"]
uuid = "ade2ca70-3891-5945-98fb-dc099432e06a"

[[Dictionaries]]
deps = ["Indexing", "Random"]
git-tree-sha1 = "011d10589449681ad631c0f866a2ce72771648c6"
uuid = "85a47980-9c8c-11e8-2b9f-f7ca1fa99fb4"
version = "0.3.10"

[[Indexing]]
git-tree-sha1 = "ce1566720fd6b19ff3411404d4b977acd4814f9f"
uuid = "313cdc1a-70c2-5d6a-ae34-0150d3930a38"
version = "1.1.1"

[[JSON]]
deps = ["Dates", "Mmap", "Parsers", "Unicode"]
git-tree-sha1 = "81690084b6198a2e1da36fcfda16eeca9f9f24e4"
uuid = "682c06a0-de6a-54ab-a142-c8b1cf79cde6"
version = "0.21.1"

[[Libdl]]
uuid = "8f399da3-3557-5675-b5ff-fb832c97cbdb"

[[LinearAlgebra]]
deps = ["Libdl"]
uuid = "37e2e46d-f89d-539d-b4ee-838fcccc9c8e"

[[Logging]]
uuid = "56ddb016-857b-54e1-b83d-db4d58db5568"

[[Mmap]]
uuid = "a63ad114-7e13-5084-954f-fe012c677804"

[[Parsers]]
deps = ["Dates"]
git-tree-sha1 = "94bf17e83a0e4b20c8d77f6af8ffe8cc3b386c0a"
uuid = "69de0a69-1ddd-5017-9359-2bf0b02dc9f0"
version = "1.1.1"

[[Printf]]
deps = ["Unicode"]
uuid = "de0858da-6303-5e67-8744-51eddeeeb8d7"

[[Random]]
deps = ["Serialization"]
uuid = "9a3f8284-a2c9-5f02-9a11-845980a1fd5c"

[[SHA]]
uuid = "ea8e919c-243c-51af-8825-aaa63cd721ce"

[[Serialization]]
uuid = "9e88b42a-f829-5b0c-bbe9-9e923198166b"

[[SparseArrays]]
deps = ["LinearAlgebra", "Random"]
uuid = "2f01184e-e22b-5df5-ae63-d93ebab69eaf"

[[Statistics]]
deps = ["LinearAlgebra", "SparseArrays"]
uuid = "10745b16-79ce-11e8-11f9-7d13ad32a3b2"

[[UUIDs]]
deps = ["Random", "SHA"]
uuid = "cf7118a7-6976-5b1a-9a39-7adc72f591a4"

[[Unicode]]
uuid = "4ec0a83e-493e-50e2-b9ac-8f72acf5a8f5"

These are the results of running the script in both Windows and Linux (I used WSL but experienced the same problem in native Linux).

$ julia-1.6 dict_vs_Dictionaries_alloaction_test.jl true
  Activating environment at `E:\Dropbox (Personal)\Misc. Programs\Julia Code Testing\DictionaryTesting\Project.toml`
Julia Version 1.6.0
Commit f9720dc2eb (2021-03-24 12:55 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: Intel(R) Xeon(R) Gold 6230 CPU @ 2.10GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, cascadelake)
Using Dictionaries.jl
  3.976637 seconds (519.21 k allocations: 7.478 GiB, 19.32% gc time, 2.74% compilation time)
Memory added from dictionary is 8.004358144 gigabytes
Memory freed from clearing half of dictionary is 3.968114688 gigabytes
Final memory usage as a percent of allocated is 50.42557296146892% (ideally would be 50%)
Could not access index 1 as expected
Waiting 10 seconds to see if gc occurs
Final memory usage as a percent of allocated is 50.33003460770683% (ideally would be 50%)
_____________________________________________________________________________

$ julia-1.6 dict_vs_Dictionaries_alloaction_test.jl
  Activating environment at `E:\Dropbox (Personal)\Misc. Programs\Julia Code Testing\DictionaryTesting\Project.toml`
Julia Version 1.6.0
Commit f9720dc2eb (2021-03-24 12:55 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: Intel(R) Xeon(R) Gold 6230 CPU @ 2.10GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, cascadelake)
Using Base dict
  4.037212 seconds (544.58 k allocations: 7.478 GiB, 20.08% gc time, 2.76% compilation time)
Memory added from dictionary is 8.015466496 gigabytes
Memory freed from clearing half of dictionary is 3.960201216 gigabytes
Final memory usage as a percent of allocated is 50.593003938369904% (ideally would be 50%)
Could not access index 1 as expected
Waiting 10 seconds to see if gc occurs
Final memory usage as a percent of allocated is 50.54691065107535% (ideally would be 50%)
_____________________________________________________________________________

$ julia-1.6 dict_vs_Dictionaries_alloaction_test.jl
  Activating environment at `/mnt/e/Dropbox (Personal)/Misc. Programs/Julia Code Testing/DictionaryTesting/Project.toml`
Julia Version 1.6.0
Commit f9720dc2eb (2021-03-24 12:55 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: Intel(R) Xeon(R) Gold 6230 CPU @ 2.10GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, cascadelake)
Using Base dict
  5.088407 seconds (547.23 k allocations: 7.478 GiB, 21.41% gc time, 2.21% compilation time)
Memory added from dictionary is 8.02164736 gigabytes
Memory freed from clearing half of dictionary is -0.001548288 gigabytes
Final memory usage as a percent of allocated is 100.01930137203139
Could not access index 1
Waiting 10 seconds to see if gc occurs
Final memory usage as a percent of allocated is 100.01930137203139
_____________________________________________________________________________

$ julia-1.6 dict_vs_Dictionaries_alloaction_test.jl true
  Activating environment at `/mnt/e/Dropbox (Personal)/Misc. Programs/Julia Code Testing/DictionaryTesting/Project.toml`
Julia Version 1.6.0
Commit f9720dc2eb (2021-03-24 12:55 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: Intel(R) Xeon(R) Gold 6230 CPU @ 2.10GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, cascadelake)
Using Dictionaries.jl
  5.269116 seconds (519.20 k allocations: 7.478 GiB, 20.45% gc time, 2.21% compilation time)
Memory added from dictionary is 8.024260608 gigabytes
Memory freed from clearing half of dictionary is -0.001032192 gigabytes
Final memory usage as a percent of allocated is 100.01286339078982
Could not access index 1 as expected
Waiting 10 seconds to see if gc occurs
Final memory usage as a percent of allocated is 100.01929508618471 (ideally would be 50%)
_____________________________________________________________________________

In Linux the memory is not being freed and this occurs with removing the entire dictionary as well which was the previous discourse test case. Also I'm interested in hearing if for this type of use case there is a more efficient way to implement it with Dictionaries.jl

andyferris commented 2 years ago

Hmm I wonder if Julia ever reduces the size of the buffer behind Vector? What happens if you push! to create a large array and then pop! it until it is small again?

If it’s a Vector issue we could recreate the vectors when they shrink. Will be a bit of an issue for Dictionary as it is an immutable struct. Perhaps there’s a C function that could help us out, though.

jekyllstein commented 2 years ago

I'll try making a similar test with vectors instead. You see in this example how I'm actually pushing in a matrix into each spot. Do you want me to try it pushing matrices into a vector of matrices or just having a vector of a primitive type like Float64? Are you gonna be around on discord during the hackathon in case I wanna ask more questions or we can bring someone else in for help?

jekyllstein commented 2 years ago

Ran a similar test with vectors of matrices and got the same results.

using InteractiveUtils

versioninfo()

function test()
    totmem = Int64(Sys.total_memory())
    getfreemem() = Int64(Sys.free_memory())

    # println()
    # if isempty(ARGS)
    #   println("Testing in global space")
    # else
    #   println("Testing inside a function")
    # end
    # println()

    function create_test_vector(totmem)
        testvect = Vector{Matrix{Float64}}()
        #insert 100k elements
        for i in 1:100000
            push!(testvect, ones(Float64, 100, 100))
        end
        freemem = totmem - getfreemem()

        #delete the first 50k elements
        for i in 1:50000
            pop!(testvect)
        end
        return freemem, testvect
    end

    initialfreemem = totmem - getfreemem()

    @time mem2, testvect = create_test_vector(totmem)

    #try to garbage collect parts of dictionary now that it is no longer needed
    GC.gc()

    post_gc_mem = totmem - getfreemem()

    println("Memory added from vector is $((mem2 - initialfreemem)/(10^9)) gigabytes")
    println("Memory freed from clearing half of vector is $((mem2 - post_gc_mem)/(10^9)) gigabytes")
    println("Final memory usage as a percent of allocated is $(100*(post_gc_mem - initialfreemem)/(mem2 - initialfreemem))% (ideally would be 50%)")
    #verify that vector is only 50k long
    @assert length(testvect) == 50000
    println("Waiting 10 seconds to see if gc occurs")
    1 + 1 #random code execution to see if it affects gc
    sleep(10)
    println("Final memory usage as a percent of allocated is $(100*((totmem - getfreemem()) - initialfreemem)/(mem2 - initialfreemem))% (ideally would be 50%)")
    println("_____________________________________________________________________________")
end

test()

$ julia-1.6 vector_alloaction_test.jl Julia Version 1.6.0 Commit f9720dc2eb (2021-03-24 12:55 UTC) Platform Info: OS: Windows (x86_64-w64-mingw32) CPU: Intel(R) Xeon(R) Gold 6230 CPU @ 2.10GHz WORD_SIZE: 64 LIBM: libopenlibm LLVM: libLLVM-11.0.1 (ORCJIT, cascadelake) 3.871681 seconds (216.78 k allocations: 7.461 GiB, 18.74% gc time, 0.35% compilation time) Memory added from vector is 7.960039424 gigabytes Memory freed from clearing half of vector is 3.962011648 gigabytes Final memory usage as a percent of allocated is 50.22623083933108% (ideally would be 50%) Waiting 10 seconds to see if gc occurs Final memory usage as a percent of allocated is 50.15110357322773% (ideally would be 50%)

$ julia-1.6 vector_alloaction_test.jl Julia Version 1.6.0 Commit f9720dc2eb (2021-03-24 12:55 UTC) Platform Info: OS: Linux (x86_64-linux-gnu) CPU: Intel(R) Xeon(R) Gold 6230 CPU @ 2.10GHz WORD_SIZE: 64 LIBM: libopenlibm LLVM: libLLVM-11.0.1 (ORCJIT, cascadelake) 7.095680 seconds (216.78 k allocations: 7.461 GiB, 14.34% gc time, 0.20% compilation time) Memory added from vector is 8.023228416 gigabytes Memory freed from clearing half of vector is 0.000516096 gigabytes Final memory usage as a percent of allocated is 99.99356747716455% (ideally would be 50%) Waiting 10 seconds to see if gc occurs Final memory usage as a percent of allocated is 99.99678373858227% (ideally would be 50%)

jekyllstein commented 2 years ago

What is super interesting though is I modified the test to just be a plain vector of Float64 and the gc fails to free the memory for both Windows and Linux this time so the problem actually got worse with a simpler vector.

using InteractiveUtils

versioninfo()

function test()
    totmem = Int64(Sys.total_memory())
    getfreemem() = Int64(Sys.free_memory())

    # println()
    # if isempty(ARGS)
    #   println("Testing in global space")
    # else
    #   println("Testing inside a function")
    # end
    # println()

    function create_test_vector(totmem)
        # testvect = Vector{Float64}()
        # #insert 100k elements
        # for i in 1:1e9
        #   push!(testvect, 1.0)
        # end

        testvect = ones(Float64, round(Int64, 1e9))
        freemem = totmem - getfreemem()

        #delete the first 50k elements
        for i in 1:5e8
            pop!(testvect)
        end
        return freemem, testvect
    end

    initialfreemem = totmem - getfreemem()

    @time mem2, testvect = create_test_vector(totmem)

    #try to garbage collect parts of dictionary now that it is no longer needed
    GC.gc()

    post_gc_mem = totmem - getfreemem()

    println("Memory added from vector is $((mem2 - initialfreemem)/(10^9)) gigabytes")
    println("Memory freed from clearing half of vector is $((mem2 - post_gc_mem)/(10^9)) gigabytes")
    println("Final memory usage as a percent of allocated is $(100*(post_gc_mem - initialfreemem)/(mem2 - initialfreemem))% (ideally would be 50%)")
    #verify that vector is only 50k long
    @assert length(testvect) == 5e8
    println("Waiting 10 seconds to see if gc occurs")
    1 + 1 #random code execution to see if it affects gc
    sleep(10)
    println("Final memory usage as a percent of allocated is $(100*((totmem - getfreemem()) - initialfreemem)/(mem2 - initialfreemem))% (ideally would be 50%)")
    println("_____________________________________________________________________________")
end

test()
$ julia-1.6 vector_alloaction_test2.jl
Julia Version 1.6.0
Commit f9720dc2eb (2021-03-24 12:55 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: Intel(R) Xeon(R) Gold 6230 CPU @ 2.10GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, cascadelake)
 14.858286 seconds (500.01 M allocations: 14.902 GiB, 1.57% gc time, 0.05% compilation time)
Memory added from vector is 7.991279616 gigabytes
Memory freed from clearing half of vector is 0.019038208 gigabytes
Final memory usage as a percent of allocated is 99.76176270991841% (ideally would be 50%)
Waiting 10 seconds to see if gc occurs
Final memory usage as a percent of allocated is 99.81388993109161% (ideally would be 50%)
_____________________________________________________________________________

$ julia-1.6 vector_alloaction_test2.jl
Julia Version 1.6.0
Commit f9720dc2eb (2021-03-24 12:55 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: Intel(R) Xeon(R) Gold 6230 CPU @ 2.10GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, cascadelake)
 15.436591 seconds (500.01 M allocations: 14.902 GiB, 2.16% gc time, 0.05% compilation time)
Memory added from vector is 8.015568896 gigabytes
Memory freed from clearing half of vector is -0.002097152 gigabytes
Final memory usage as a percent of allocated is 100.0261634829319% (ideally would be 50%)
Waiting 10 seconds to see if gc occurs
Final memory usage as a percent of allocated is 100.0261634829319% (ideally would be 50%)
_____________________________________________________________________________
guimarqu commented 2 years ago

Hi, did you try to use sizehint!(vec, len)? It frees memory on my computer.

If you look at the C code called by sizehint!, you'll see that this method may call the garbage collector if you delete more than 1 out of 8 elements and depending on the allocation style of the array (https://github.com/JuliaLang/julia/blob/8ece8655da44895864c9bb02d32f023be6382c44/src/julia.h#L162).

C jl_array_shrink called by C jlarray_sizehint called by Julia sizehint! : https://github.com/JuliaLang/julia/blob/2e06a016fdad70736dd6c25c5a5286809e442b35/src/array.c#L1007 (see the methods prefixed by jl_gc).

At first sight, there are no such calls for pop! or even resize!. I don't know enough about the C code and the julia GC to give more information.

andyferris commented 2 years ago

Great detective work @guimarqu!

It seems like we should try adding sizehint! calls in this code block: https://github.com/andyferris/Dictionaries.jl/blob/master/src/Indices.jl#L238-L242 and see what happens. If anyone is up for preparing a PR that would be appreciated :)

jekyllstein commented 2 years ago

Hi, did you try to use sizehint!(vec, len)? It frees memory on my computer.

If you look at the C code called by sizehint!, you'll see that this method may call the garbage collector if you delete more than 1 out of 8 elements and depending on the allocation style of the array (https://github.com/JuliaLang/julia/blob/8ece8655da44895864c9bb02d32f023be6382c44/src/julia.h#L162).

C jl_array_shrink called by C jlarray_sizehint called by Julia sizehint! : https://github.com/JuliaLang/julia/blob/2e06a016fdad70736dd6c25c5a5286809e442b35/src/array.c#L1007 (see the methods prefixed by jl_gc).

At first sight, there are no such calls for pop! or even resize!. I don't know enough about the C code and the julia GC to give more information.

Thanks for the tip. So are you suggesting that once I remove half the elements I call sizehint! and suggest the updated smaller length? Also how would you use this for the case of a vector/dictionary being defined inside a function, not being returned but being in memory still. Because in that case you cannot refer to the vector b/c it isn't in the namespace.

andyferris commented 2 years ago

So are you suggesting that once I remove half the elements I call sizehint! and suggest the updated smaller length?

I think the best way is if we just call it every time we rehash!. EDIT: this get's called in deletetoken! whenever a large fraction of elements are deleted.

. Because in that case you cannot refer to the vector b/c it isn't in the namespace.

If it's truly unreachable, the GC will remove it entirely (eventually).

jekyllstein commented 2 years ago

Tried using sizehint!(vec, len) but in Ubuntu dind't make any change to the gc behavior

using InteractiveUtils

versioninfo()

function test()
    totmem = Int64(Sys.total_memory())
    getfreemem() = Int64(Sys.free_memory())

    function create_test_vector(totmem)
        testvect = Vector{Matrix{Float64}}()
        #insert 100k elements
        for i in 1:100000
            push!(testvect, ones(Float64, 100, 100))
        end
        freemem = totmem - getfreemem()

        #delete the first 50k elements
        for i in 1:50000
            pop!(testvect)
        end
        sizehint!(testvect, 50000)
        return freemem, testvect
    end

    initialfreemem = totmem - getfreemem()

    @time mem2, testvect = create_test_vector(totmem)

    #try to garbage collect parts of dictionary now that it is no longer needed
    GC.gc()

    post_gc_mem = totmem - getfreemem()

    println("Memory added from vector is $((mem2 - initialfreemem)/(10^9)) gigabytes")
    println("Memory freed from clearing half of vector is $((mem2 - post_gc_mem)/(10^9)) gigabytes")
    println("Final memory usage as a percent of allocated is $(100*(post_gc_mem - initialfreemem)/(mem2 - initialfreemem))% (ideally would be 50%)")
    #verify that vector is only 50k long
    @assert length(testvect) == 50000
    println("Waiting 10 seconds to see if gc occurs")
    1 + 1 #random code execution to see if it affects gc
    sleep(10)
    println("Final memory usage as a percent of allocated is $(100*((totmem - getfreemem()) - initialfreemem)/(mem2 - initialfreemem))% (ideally would be 50%)")
    println("_____________________________________________________________________________")
end

test()
$ julia-1.6 vector_alloaction_test3.jl
Julia Version 1.6.0
Commit f9720dc2eb (2021-03-24 12:55 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: Intel(R) Xeon(R) Gold 6230 CPU @ 2.10GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, cascadelake)
  5.046759 seconds (218.29 k allocations: 7.461 GiB, 19.37% gc time, 0.38% compilation time)
Memory added from vector is 8.029421568 gigabytes
Memory freed from clearing half of vector is 0.001032192 gigabytes
Final memory usage as a percent of allocated is 99.98714487723358% (ideally would be 50%)
Waiting 10 seconds to see if gc occurs
Final memory usage as a percent of allocated is 100.00683566051865% (ideally would be 50%)
andyferris commented 2 years ago

Interesting. Hmm. I wonder if GC.gc() works better than sleep? Have you tried reducing the vector much further (perhaps even empty)?

jekyllstein commented 2 years ago

So I made a new test, I call GC.gc() right after clearing the keys as before and once again after the sleep call. This time the entire vector is cleared and I verify that it is empty in the Main space. I also use sizehint! within the function after clearing the vector to suggest a size of 0. The behavior on linux is the same however with virtually none of the memory being freed. See code and execution below.

using InteractiveUtils

versioninfo()

function test()
    totmem = Int64(Sys.total_memory())
    getfreemem() = Int64(Sys.free_memory())

    function create_test_vector(totmem)
        testvect = Vector{Matrix{Float64}}()
        #insert 100k elements
        for i in 1:100000
            push!(testvect, ones(Float64, 100, 100))
        end
        freemem = totmem - getfreemem()

        #delete all the elements
        for i in 1:100000
            pop!(testvect)
        end
        sizehint!(testvect, 0)
        return freemem, testvect
    end

    initialfreemem = totmem - getfreemem()

    @time mem2, testvect = create_test_vector(totmem)

    #try to garbage collect parts of dictionary now that it is no longer needed
    GC.gc()

    post_gc_mem = totmem - getfreemem()

    println("Memory added from vector is $((mem2 - initialfreemem)/(10^9)) gigabytes")
    println("Memory freed from clearing vector is $((mem2 - post_gc_mem)/(10^9)) gigabytes")
    println("Final memory usage as a percent of allocated is $(100*(post_gc_mem - initialfreemem)/(mem2 - initialfreemem))% (ideally would be 50%)")
    #verify that vector is empty
    @assert length(testvect) == 0
    println("Waiting 10 seconds to see if gc occurs")
    1 + 1 #random code execution to see if it affects gc
    sleep(10)
    GC.gc()
    println("Final memory usage as a percent of allocated is $(100*((totmem - getfreemem()) - initialfreemem)/(mem2 - initialfreemem))% (ideally would be 0%)")
    println("_____________________________________________________________________________")
end

test()

$ julia-1.6 vector_alloaction_test4.jl Julia Version 1.6.0 Commit f9720dc2eb (2021-03-24 12:55 UTC) Platform Info: OS: Linux (x86_64-linux-gnu) CPU: Intel(R) Xeon(R) Gold 6230 CPU @ 2.10GHz WORD_SIZE: 64 LIBM: libopenlibm LLVM: libLLVM-11.0.1 (ORCJIT, cascadelake) 5.085217 seconds (218.29 k allocations: 7.461 GiB, 19.17% gc time, 0.34% compilation time) Memory added from vector is 8.02271232 gigabytes Memory freed from clearing vector is 0.001032192 gigabytes Final memory usage as a percent of allocated is 99.98713412672885% (ideally would be 0%) Waiting 10 seconds to see if gc occurs Final memory usage as a percent of allocated is 99.98713412672885% (ideally would be 0%)

andyferris commented 2 years ago

Okay, interesting. It really seemed like that C code should be reallocating... @c42f sorry to bother you but I was wondering if you had any insights?

(Also, in general, I'm not sure if we can be expected to manage memory "better" than Base.Array - should we escalate this before trying workarounds?)

c42f commented 2 years ago

Not sure I have time to dig into this deeply, but a couple of thoughts -

First, Sys.free_memory() may be misleading on linux — it's a common problem that actual free memory can be hard (or confusing) to measure on linux because linux is happy to fill your physical memory up completely with things like cached file data, but which can be trivially evicted to make room for new programs. Looking at free_memory(), it calls uv_get_free_memory() which seems to just use /proc/meminfo and the FreeMem field which is not very useful at all! Instead you could use something like filter(startswith("MemAvailable"), readlines("/proc/meminfo")) to get a more accurate assessment.

If you're seeing GC problems with plain Vector and Matrix (or Dict) you should certainly report this upstream at the julialang bug tracker.

jekyllstein commented 2 years ago

This was an issue I originally brought up on discourse not connected to any specific package. Back then we didn't make much progress but I do want to retry the test on linux with the other method of testing free memory. Do you know if that same method works on macOS? Also in windows, is free_memory() okay to use or is there another more accurate version you'd suggest?

c42f commented 2 years ago

Do you know if that same method works on macOS? Also in windows, is free_memory() okay to use or is there another more accurate version you'd suggest?

/proc is a linux-specific filesystem, so it won't work elsewhere. On windows libuv does this:

https://github.com/libuv/libuv/blob/04289fa326b790c1a4abb236d1f9d913bacfc8c6/src/win/util.c#L328-L337

which seems reasonable enough from reading the docs at https://docs.microsoft.com/en-us/windows/win32/api/sysinfoapi/ns-sysinfoapi-memorystatusex, but I've not got firsthand knowledge about this.

No idea about macos, it's easy to see how libuv implements it but the underlying OS library call is surprisingly poorly documented. You may be better off searching for a reliable command line way to measure memory on macos and just calling run() with that command (can be compared with free_memory).

It would also be better to measure memory usage for the current process rather than measure the free memory. It looks like you can use Base.gc_live_bytes() for a snapshot of the amount of memory which the Julia GC has provided to the user program and not yet reclaimed. (Note that the total memory used by the process will be somewhat higher than this.)

andyferris commented 2 years ago

Thanks Chris - gc_live_bytes sounds pretty useful!

jekyllstein commented 2 years ago

Using Base.gc_live_bytes() did seem to show the memory was freed up in most of the earlier tests, however I saw in some cases that using vs not using sizehint!() made a big difference. I'm still not sure what to make of this case with a simple vector of Float64.

using InteractiveUtils

versioninfo()

const l = 100000000
const initialmem = Base.gc_live_bytes()
function test(prct)
    getusedmem() = Base.gc_live_bytes() - initialmem

    function create_test_vector()
        testvect = Vector{Float64}()

        #insert l elements
        for i in 1:l
            push!(testvect, rand())
        end
        usedmem = getusedmem()

        #delete all the elements
        for i in 1:round(Int64, l*prct)
            pop!(testvect)
        end
        # sizehint!(testvect, 0)
        usedmem2 = getusedmem()
        return usedmem, usedmem2, testvect
    end

    @time mem2, mem3, testvect = create_test_vector()

    #try to garbage collect parts of dictionary now that it is no longer needed
    GC.gc()

    post_gc_mem =  getusedmem()

    println("Memory added from vector is $((mem2)/(10^6)) megabytes (should be $(l*64/8/(10^6)) megabytes)")
    println("Memory freed (pre GC) from clearing $(prct*100)% of vector is $((mem2 - mem3)/(10^6)) megabytes")
    println("Memory freed (postGC) from clearing $(prct*100)% of vector is $((mem2 - post_gc_mem)/(10^6)) megabytes")
    println("Final memory usage as a percent of allocated is $(100*(post_gc_mem)/(mem2))% (ideally would be $((1.0-prct)*100)%)")
    #verify that vector is empty
    @assert length(testvect) == l - (round(Int64, l*prct))
    println("Waiting 10 seconds to see if gc occurs")
    1 + 1 #random code execution to see if it affects gc
    sleep(10)
    GC.gc()
    println("Final memory usage as a percent of allocated is $(100*((getusedmem()))/(mem2))% (ideally would be $((1.0-prct)*100)%)")
    println("_____________________________________________________________________________")
end

prct = if isempty(ARGS)
    1.0
else
    parse(Float64, ARGS[1])
end

test(prct)

When I ran it with the sizehint!() line commented out, it seemed to over allocate memory for the vector and then free some of it but not enough to even be lower than the theoretical size of the original vector.

$ julia-1.6 vector_alloaction_test6.jl
Julia Version 1.6.0
Commit f9720dc2eb (2021-03-24 12:55 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: Intel(R) Xeon(R) Gold 6230 CPU @ 2.10GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, cascadelake)
  8.298152 seconds (200.01 M allocations: 3.982 GiB, 12.18% gc time, 0.15% compilation time)
Memory added from vector is 1566.43908 megabytes (should be 800.0 megabytes)
Memory freed (pre GC) from clearing 100.0% of vector is 202.624899 megabytes
Memory freed (postGC) from clearing 100.0% of vector is 526.254285 megabytes
Final memory usage is 1040.184795 megabytes or 66.40442059195816% of allocated (ideally would be 0.0%)
Waiting 10 seconds to see if gc occurs
Final memory usage is 1040.184859 megabytes, or 66.40442467765807% of allocated (ideally would be 0.0%)

When I ran the same code with sizehint!(testvect, 0) it initially frees much more memory and basically removes all of it by the end.

$ julia-1.6 vector_alloaction_test6.jl
Julia Version 1.6.0
Commit f9720dc2eb (2021-03-24 12:55 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: Intel(R) Xeon(R) Gold 6230 CPU @ 2.10GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, cascadelake)
  8.634766 seconds (200.01 M allocations: 3.982 GiB, 12.37% gc time, 0.19% compilation time)
Memory added from vector is 1566.437568 megabytes (should be 800.0 megabytes)
Memory freed (pre GC) from clearing 100.0% of vector is 1276.28314 megabytes
Memory freed (postGC) from clearing 100.0% of vector is 1599.995374 megabytes
Final memory usage is -33.557806 megabytes or -2.14230089251792% of allocated (ideally would be 0.0%)
Waiting 10 seconds to see if gc occurs
Final memory usage is -33.557726 megabytes, or -2.142291699684261% of allocated (ideally would be 0.0%)
c42f commented 2 years ago

Vector has an exponential resizing strategy where the vector's capacity (allocated size rather than logical size) is increased according to a multiple of the current number of elements when growing with push!. This avoids the severe performance penalty of reallocating and copying elements which you would get if Vector always used the exact amount of memory you'd expect from calling length(). The tradeoff is some memory overhead, which is likely what you're seeing here.

Note also that