Parallel killing of agents results in error

[Datseris]

Describe the bug
When killing agents from a model using Threads.@thread, we get an error.

Minimal Working Example
Notice that the example breaks even if I don't add agents.

# julia --threads=4

using Agents

mutable struct Ag <: AbstractAgent
  id::Int
end

function initialize(;d=0.2, b=0.2)
  model = ABM(Ag, nothing, properties=(b=b, d=d))
  for i in 1:1000
    add_agent!(model)
  end
  return model
end

function model_step!(model::ABM)
  Threads.@threads for ag in collect(allagents(model))
    if rand() < model.b
      add_agent!(model)
    end
    if rand() < model.d
      kill_agent!(ag, model)
    end
  end
end

model = initialize()
step!(model, dummystep, model_step!, 1)

ERROR: TaskFailedException
Stacktrace:
 [1] wait
   @ .\task.jl:334 [inlined]
 [2] threading_run(func::Function)
   @ Base.Threads .\threadingconstructs.jl:38
 [3] macro expansion
   @ .\threadingconstructs.jl:97 [inlined]
 [4] model_step!(model::AgentBasedModel{Nothing, Ag, typeof(Agents.Schedulers.fastest), NamedTuple{(:b, :d), Tuple{Float64, Float64}}, Random.TaskLocalRNG})
   @ Main .\REPL[6]:2
 [5] step!(model::AgentBasedModel{Nothing, Ag, typeof(Agents.Schedulers.fastest), NamedTuple{(:b, :d), Tuple{Float64, Float64}}, Random.TaskLocalRNG}, agent_step!::typeof(dummystep), model_step!::typeof(model_step!), n::Int64, agents_first::Bool)
   @ Agents C:\Users\arvka\.julia\packages\Agents\yf6MH\src\simulations\step.jl:58
 [6] step!(model::AgentBasedModel{Nothing, Ag, typeof(Agents.Schedulers.fastest), NamedTuple{(:b, :d), Tuple{Float64, Float64}}, Random.TaskLocalRNG}, agent_step!::Function, model_step!::Function, n::Int64)
   @ Agents C:\Users\arvka\.julia\packages\Agents\yf6MH\src\simulations\step.jl:48
 [7] top-level scope
   @ REPL[12]:1

    nested task error: UndefRefError: access to undefined reference
    Stacktrace:
     [1] getindex
       @ .\array.jl:861 [inlined]
     [2] (::var"#7#threadsfor_fun#2"{AgentBasedModel{Nothing, Ag, typeof(Agents.Schedulers.fastest), NamedTuple{(:b, :d), Tuple{Float64, Float64}}, Random.TaskLocalRNG}, Vector{Ag}})(onethread::Bool)
       @ Main .\threadingconstructs.jl:84
     [3] (::var"#7#threadsfor_fun#2"{AgentBasedModel{Nothing, Ag, typeof(Agents.Schedulers.fastest), NamedTuple{(:b, :d), Tuple{Float64, Float64}}, Random.TaskLocalRNG}, Vector{Ag}})()
       @ Main .\threadingconstructs.jl:52

Agents.jl version
Version doesn't matter here, anything 5+. Julia 1.7+.

[Datseris]

As @kavir1698 reported, this is not an issue of julia dictionaries (see #596 (comment))

this works:

dd = Dict(i => rand() for i in 1:2000)

function model_step2!(dd)
  Threads.@threads for k in collect(keys(dd))
    if rand() < 0.2
      dd[maximum(keys(dd))+1] = rand()
    end
    if rand() < 0.2
      delete!(dd, k)
    end
  end
end

for i in 1:100
  model_step2!(dd)
end

[Datseris]

That is very interesting and shows pretty clearly that this is a bug in Agents.jl. At first I thought it could be because of the usage of Ref for the maximum id container. But you said the example breaks even when not adding agents, so this excludes that.

[fbanning]

I was unable to always reconstruct this bug with the following MWE:

julia> using Agents
[ Info: Precompiling Agents [46ada45e-f475-11e8-01d0-f70cc89e6671]

julia> mutable struct Ag <: AbstractAgent
         id::Int
       end

julia> function initialize()
         model = ABM(Ag, nothing)
         for i in 1:100
           add_agent!(model)
         end
         return model
       end
initialize (generic function with 1 method)

julia> function model_step!(model::ABM)
         Threads.@threads for ag in collect(allagents(model))
           if rand() < 0.2
             kill_agent!(ag, model)
           end
         end
       end
model_step! (generic function with 1 method)

julia> model = initialize()
AgentBasedModel with 100 agents of type Ag
 space: nothing (no spatial structure)
 scheduler: fastest

julia> step!(model, dummystep, model_step!, 1)

Note that I've simplified your MWE a bit and excluded model properties.

It doesn't always work though, if I step the model multiple times in a row, at some seemingly random point it throws the TaskFailedException that you've also encountered:

Stacktrace

ERROR: TaskFailedException
Stacktrace:
 [1] wait
   @ ./task.jl:345 [inlined]
 [2] threading_run(fun::var"#23#threadsfor_fun#5"{var"#23#threadsfor_fun#4#6"{AgentBasedModel{Nothing, Ag, typeof(Agents.Schedulers.fastest), Nothing, Random.TaskLocalRNG}, Vector{Ag}}}, static::Bool)
   @ Base.Threads ./threadingconstructs.jl:38
 [3] macro expansion
   @ ./threadingconstructs.jl:89 [inlined]
 [4] model_step!
   @ ./REPL[7]:2 [inlined]
 [5] step!(model::AgentBasedModel{Nothing, Ag, typeof(Agents.Schedulers.fastest), Nothing, Random.TaskLocalRNG}, agent_step!::typeof(dummystep), model_step!::typeof(model_step!), n::Int64, agents_first::Bool)
   @ Agents ~/.julia/packages/Agents/QtIUJ/src/simulations/step.jl:58
 [6] step!(model::AgentBasedModel{Nothing, Ag, typeof(Agents.Schedulers.fastest), Nothing, Random.TaskLocalRNG}, agent_step!::Function, model_step!::Function, n::Int64)
   @ Agents ~/.julia/packages/Agents/QtIUJ/src/simulations/step.jl:48
 [7] top-level scope
   @ REPL[30]:1

    nested task error: UndefRefError: access to undefined reference
    Stacktrace:
     [1] getindex
       @ ./array.jl:924 [inlined]
     [2] (::var"#23#threadsfor_fun#5"{var"#23#threadsfor_fun#4#6"{AgentBasedModel{Nothing, Ag, typeof(Agents.Schedulers.fastest), Nothing, Random.TaskLocalRNG}, Vector{Ag}}})(tid::Int64; onethread::Bool)
       @ Main ./threadingconstructs.jl:83
     [3] #23#threadsfor_fun
       @ ./threadingconstructs.jl:51 [inlined]
     [4] (::Base.Threads.var"#1#2"{var"#23#threadsfor_fun#5"{var"#23#threadsfor_fun#4#6"{AgentBasedModel{Nothing, Ag, typeof(Agents.Schedulers.fastest), Nothing, Random.TaskLocalRNG}, Vector{Ag}}}, Int64})()
       @ Base.Threads ./threadingconstructs.jl:30

Could this be some kind of data race such that two threads pick the same agent to remove from the model? I think that's the case because you run collect at the beginning of the loop, resulting in a fixed set of agents at that time.

Logging the removed agent ids and using allids instead of allagents lets us test this hypothesis. And indeed, it yields a different task error:

julia> function model_step!(model::ABM)
         Threads.@threads for ag in collect(allids(model))
           if rand() < 0.2
             print("-$(ag), ")
             kill_agent!(ag, model)
           end
         end
         println("=> $(nagents(model))")
       end
model_step! (generic function with 1 method)

julia> model = initialize()
AgentBasedModel with 100 agents of type Ag
 space: nothing (no spatial structure)
 scheduler: fastest

julia> step!(model, dummystep, model_step!, 10)
-56, -41, -10, -11, -17, -30, -98, -27, -89, -45, -63, -48, -85, -100, -65, -66, -16, -75, -49, -2, -61, => 82
-60, -76, -9, -47, -32, -59, -74, -14, -93, -86, -78, -80, -72, -33, -0, ERROR: TaskFailedException
Stacktrace:
 [1] wait
   @ ./task.jl:345 [inlined]
 [2] threading_run(fun::var"#98#threadsfor_fun#20"{var"#98#threadsfor_fun#19#21"{AgentBasedModel{Nothing, Ag, typeof(Agents.Schedulers.fastest), Nothing, Random.TaskLocalRNG}, Vector{Int64}}}, static::Bool)
   @ Base.Threads ./threadingconstructs.jl:38
 [3] macro expansion
   @ ./threadingconstructs.jl:89 [inlined]
 [4] model_step!
   @ ./REPL[20]:2 [inlined]
 [5] step!(model::AgentBasedModel{Nothing, Ag, typeof(Agents.Schedulers.fastest), Nothing, Random.TaskLocalRNG}, agent_step!::typeof(dummystep), model_step!::typeof(model_step!), n::Int64, agents_first::Bool)
   @ Agents ~/.julia/packages/Agents/QtIUJ/src/simulations/step.jl:58
 [6] step!(model::AgentBasedModel{Nothing, Ag, typeof(Agents.Schedulers.fastest), Nothing, Random.TaskLocalRNG}, agent_step!::Function, model_step!::Function, n::Int64)
   @ Agents ~/.julia/packages/Agents/QtIUJ/src/simulations/step.jl:48
 [7] top-level scope
   @ REPL[22]:1

    nested task error: KeyError: key 0 not found
    Stacktrace:
     [1] getindex
       @ ./dict.jl:498 [inlined]
     [2] getindex
       @ ~/.julia/packages/Agents/QtIUJ/src/core/model.jl:113 [inlined]
     [3] kill_agent!
       @ ~/.julia/packages/Agents/QtIUJ/src/core/space_interaction_API.jl:150 [inlined]
     [4] macro expansion
       @ ./REPL[20]:5 [inlined]
     [5] (::var"#98#threadsfor_fun#20"{var"#98#threadsfor_fun#19#21"{AgentBasedModel{Nothing, Ag, typeof(Agents.Schedulers.fastest), Nothing, Random.TaskLocalRNG}, Vector{Int64}}})(tid::Int64; onethread::Bool)
       @ Main ./threadingconstructs.jl:84
     [6] #98#threadsfor_fun
       @ ./threadingconstructs.jl:51 [inlined]
     [7] (::Base.Threads.var"#1#2"{var"#98#threadsfor_fun#20"{var"#98#threadsfor_fun#19#21"{AgentBasedModel{Nothing, Ag, typeof(Agents.Schedulers.fastest), Nothing, Random.TaskLocalRNG}, Vector{Int64}}}, Int64})()
       @ Base.Threads ./threadingconstructs.jl:30

No idea why it's doing this though. The KeyError differs from run to run, so I experienced anything from 0 to 139879233089544. And of course those are not valid ids in the first place. 🤔

[Tortar]

Investigated the problem. I was not finding any bug in the implementation of related things in Agents.jl, and so I was a bit surprised by the behaviour, but the matter is simple in the end : Dicts are not thread-safe!

The problem with the test of dicts of @Datseris is that using delete! doesn't show up the problem with a simple dictionary with ints as keys and floats as values, since delete! actually doesn't require that the key exists when you delete it. The reason why it shows up in our code instead is that undefined behaviours when there is no thread-safety are tricky, they are a bit unpredictable, probably using structs instead of floats as values creates a different undefined behaviour which overcomes the fact that delete! doesn't require keys to be present, to see this run this code instead using julia --threads=4

dd = Dict(i => rand() for i in 1:2000)

function model_step2!(dd)
  Threads.@threads for k in collect(keys(dd))
    if rand() < 0.2
      pop!(dd, k)
    end
  end
  println(dd)
end

for i in 1:100
  model_step2!(dd)
end

and it will fail with something like

Stacktrace:
 [1] wait
   @ ./task.jl:345 [inlined]
 [2] threading_run(fun::var"#22#threadsfor_fun#9"{var"#22#threadsfor_fun#8#10"{Dict{Int64, Float64}, Vector{Int64}}}, static::Bool)
   @ Base.Threads ./threadingconstructs.jl:38
 [3] macro expansion
   @ ./threadingconstructs.jl:89 [inlined]
 [4] model_step2!(dd::Dict{Int64, Float64})
   @ Main ./REPL[5]:2
 [5] top-level scope
   @ ./REPL[6]:2

    nested task error: KeyError: key 27477424 not found
    Stacktrace:
     [1] pop!(h::Dict{Int64, Float64}, key::Int64)
       @ Base ./dict.jl:604
     [2] macro expansion
       @ ./REPL[5]:4 [inlined]
     [3] (::var"#22#threadsfor_fun#9"{var"#22#threadsfor_fun#8#10"{Dict{Int64, Float64}, Vector{Int64}}})(tid::Int64; onethread::Bool)
       @ Main ./threadingconstructs.jl:84
     [4] #22#threadsfor_fun
       @ ./threadingconstructs.jl:51 [inlined]
     [5] (::Base.Threads.var"#1#2"{var"#22#threadsfor_fun#9"{var"#22#threadsfor_fun#8#10"{Dict{Int64, Float64}, Vector{Int64}}}, Int64})()
       @ Base.Threads ./threadingconstructs.jl:30

But it should work if dicts were thread-safe, but they are not, this is also confirmed in https://discourse.julialang.org/t/can-dicts-be-threadsafe/27172/5 where Stefan Karpinsky says that basic data structures will never be thread-safe for performance reasons.

[Tortar]

Another way to see it is to just copy-paste the code of @Datseris adding a print of the keys after every step

dd = Dict(i => rand() for i in 1:2000)

function model_step2!(dd)
         Threads.@threads for k in collect(keys(dd))
           if rand() < 0.2
             dd[maximum(keys(dd))+1] = rand()
           end
           if rand() < 0.2
             delete!(dd, k)
           end
         end
       println(collect(keys(dd)))
       end

for i in 1:100
  model_step2!(dd)
end

in the 100th step it printed on my last run

[4109, 4098, 4101, 4105, 3995, 4066, 4095, 4106, 4097, 4049, 4064, 4091, 4068, 4036, 4096, 4087, 4102, 4103, 4107, 4104, 4093, 4110, 4108, 4099, 4084, 4074, 4094, 4073, 139821093559568, 139821093559632, 139821093537872, 139821093537920, 139821093537968, 139821093559696, 139821093559760, 139821093559824, 139821093559888, 13, 12, 2, 1, 0, 0]

which is a bit absurd :D

[Tortar]

I added the parallelism label to #596, I think that since this is not a bug in Agents.jl we can close this issue, if nobody has anything to say about this I will close it

[Datseris]

I think we should add a note about this in the performance documentation. That in generally kiling or adding agents is not thread safe. I'm not sure what else isn't thread safe but these two certainly arent :D

then, we can close this

[Tortar]

looked into the docs and they are already quite good:

Julia provides several tools for parallelization and distributed computing. Notice that we cannot help you with parallelizing the actual model evolution via the agent- and model-stepping functions. This is something you must do manually, as depending on the model, parallelization might not be possible at all due to e.g. the access and overwrite of the same memory location (writing on same agent in different threads or killing/creating agents). If your model evolution satisfies the criteria allowing parallelism, the simplest way to do it is using Julia's @threads or @spawn macros.

It is also already mentioned that killing/creating agents is not thread safe actually :D