New functions: random_id_in_position & random_agent_in_position

[Tortar]

These are the functions we need for WolfSheep in the benchmark repo. And they are also useful in general.

There is also another important change in this PR -> a new keyword alloc for all the filtered random searches: this makes it possible to choose between the best method for each case:

• allocation + evaluation of the filtering on just some members
• no allocation + evaluation of the filtering on all members

Notice that alloc is currently set to False (even if some benchmarks are needed to say if it is better to set it so), which means that the new methodology is currently being tested

This is still a rough PR, many things are a bit redundant or can be improved, docstrings are lacking, etc...

[codecov-commenter]

Codecov Report

Merging #842 (2ee4687) into main (3ac17b8) will increase coverage by 0.56%. The diff coverage is 98.21%.

@@            Coverage Diff             @@
##             main     #842      +/-   ##
==========================================
+ Coverage   70.18%   70.75%   +0.56%     
==========================================
  Files          42       42              
  Lines        2727     2773      +46     
==========================================
+ Hits         1914     1962      +48     
+ Misses        813      811       -2     

Files Changed	Coverage Δ
src/spaces/graph.jl	76.19% <ø> (+0.80%)	:arrow_up:
src/core/model_abstract.jl	90.76% <91.66%> (+4.76%)	:arrow_up:
src/core/space_interaction_API.jl	92.64% <100.00%> (+0.64%)	:arrow_up:
src/spaces/discrete.jl	97.61% <100.00%> (+0.84%)	:arrow_up:

:mega: We’re building smart automated test selection to slash your CI/CD build times. Learn more

[Tortar]

@Datseris if you want to take a look, this is ready for review, this can be used to close https://github.com/JuliaDynamics/ABM_Framework_Comparisons/issues/66

We should still run some benchmarks to see how this new version with alloc performs

[Tortar]

yes, this way is better (alloc = false) than the previous one as a default:

julia> using Agents, Random, BenchmarkTools

julia> mutable struct LabelledAgent <: AbstractAgent
           id::Int
           label::Bool
       end

julia> function create_model(ModelType, n_agents_with_condition, n_agents=10000)
           agents = [LabelledAgent(id, id<=n_agents_with_condition) for id in 1:n_agents]
           model = ModelType(LabelledAgent)
           for a in agents
               add_agent!(a, model)
           end
           return model
       end
create_model (generic function with 2 methods)

julia> cond(agent) = agent.label
cond (generic function with 1 method)

julia> # common condition

       # UnremovableABM
       @benchmark random_agent(model, $cond, optimistic=false, alloc=false) setup=(model=create_model(UnremovableABM, 2000))
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):   8.455 μs … 82.620 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     10.311 μs              ┊ GC (median):    0.00%
 Time  (mean ± σ):   10.461 μs ±  1.621 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

                             ▅█▅▅▂
  ▂▁▁▂▂▂▂▂▁▂▂▁▂▂▂▂▂▂▂▂▂▂▂▂▃▆████████▇▇▆▅▃▃▃▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂ ▃
  8.46 μs         Histogram: frequency by time        12.1 μs <

 Memory estimate: 0 bytes, allocs estimate: 0.

julia> @benchmark random_agent(model, $cond, optimistic=false, alloc=true) setup=(model=create_model(UnremovableABM, 2000))
BenchmarkTools.Trial: 10000 samples with 7 evaluations.
 Range (min … max):   4.624 μs … 235.504 μs  ┊ GC (min … max):  0.00% … 94.15%
 Time  (median):      6.080 μs               ┊ GC (median):     0.00%
 Time  (mean ± σ):   10.228 μs ±  24.123 μs  ┊ GC (mean ± σ):  38.44% ± 15.34%

  █▃                                                           ▁
  ███▆▆▇▄▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▅▇█▇▇▇▆ █
  4.62 μs       Histogram: log(frequency) by time       150 μs <

 Memory estimate: 78.17 KiB, allocs estimate: 2.

julia> # DictionaryABM
       @benchmark random_agent(model, $cond, optimistic=false, alloc=false) setup=(model=create_model(StandardABM, 2000))
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  49.614 μs … 445.393 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     52.001 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   53.021 μs ±   5.342 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

   ▁▃▅▆▇███▆▅▅▅▆▅▄▄▃▂▂▁▁▁▁▁▁▁▁                                 ▂
  ▆██████████████████████████████████▇███▇▇▆▅▆▆▄▆▄▅▆▆▅▄▂▄▅▅▅▅▆ █
  49.6 μs       Histogram: log(frequency) by time      66.8 μs <

 Memory estimate: 0 bytes, allocs estimate: 0.

julia> @benchmark random_agent(model, $cond, optimistic=false, alloc=true) setup=(model=create_model(StandardABM, 2000))

BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  41.191 μs …  1.718 ms  ┊ GC (min … max):  0.00% … 95.23%
 Time  (median):     43.470 μs              ┊ GC (median):     0.00%
 Time  (mean ± σ):   51.051 μs ± 96.665 μs  ┊ GC (mean ± σ):  12.29% ±  6.28%

  ▂▅▆█▇▆▆▆▄▂▂▂▂▁▁▁▁▁▁                                         ▂
  █████████████████████▇▇▇▆██▇▆▇▆▇▆▆▇▇▇▇▅▇▅▆▆▅▄▃▆▃▅▄▃▅▃▄▃▄▄▁▃ █
  41.2 μs      Histogram: log(frequency) by time      71.6 μs <

 Memory estimate: 78.17 KiB, allocs estimate: 2.

julia> # rare condition

       # UnremovableABM
       @benchmark random_agent(model, $cond, optimistic=false, alloc=false) setup=(model=create_model(UnremovableABM, 2))
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):   8.217 μs … 114.933 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     10.311 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   10.493 μs ±   2.668 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

                         ▂▇▇█▅▄▁
  ▂▁▁▂▁▂▂▂▂▂▂▂▂▂▂▂▂▂▂▃▄▇█████████▇▅▄▃▃▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▁▂ ▃
  8.22 μs         Histogram: frequency by time           13 μs <

 Memory estimate: 0 bytes, allocs estimate: 0.

julia> @benchmark random_agent(model, $cond, optimistic=false, alloc=true) setup=(model=create_model(UnremovableABM, 2))

BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):   4.906 μs …   1.574 ms  ┊ GC (min … max):  0.00% … 91.35%
 Time  (median):     29.230 μs               ┊ GC (median):     0.00%
 Time  (mean ± σ):   40.121 μs ± 107.777 μs  ┊ GC (mean ± σ):  19.43% ±  7.14%

   ▄▆██▇▇▅▅▇▅▄▅▄▅▄▂▄▄▃▂▂▃▂▂▁▂▁▁▁
  ▄██████████████████████████████▇█▇▇▆▆▆▆▅▆▅▄▄▄▃▃▃▂▂▂▂▁▁▁▁▁▁▁▁ ▅
  4.91 μs         Histogram: frequency by time         89.1 μs <

 Memory estimate: 78.17 KiB, allocs estimate: 2.

julia> # DictionaryABM
       @benchmark random_agent(model, $cond, optimistic=false, alloc=false) setup=(model=create_model(StandardABM, 2))
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  49.570 μs … 181.012 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     52.338 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   53.540 μs ±   4.754 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

    ▃▄▆▇██▇▅▅▅▅▅▄▃▃▂▂▁▂▂▂▁▂▁▁▁▁▁  ▁                            ▃
  ▅██████████████████████████████▇███▇▇▆▆▆▅▅▅▅▆▆▆▆▄▆▆▅▅▆▄▅▁▅▅▅ █
  49.6 μs       Histogram: log(frequency) by time      71.1 μs <

 Memory estimate: 0 bytes, allocs estimate: 0.

julia> @benchmark random_agent(model, $cond, optimistic=false, alloc=true) setup=(model=create_model(StandardABM, 2))
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):   42.938 μs …   2.115 ms  ┊ GC (min … max): 0.00% … 86.96%
 Time  (median):     101.398 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   115.503 μs ± 109.425 μs  ┊ GC (mean ± σ):  5.50% ±  5.95%

  ▄▇▇▇▇█▆▇▇▇█▇▆▆▆▅▄▅▅▄▄▄▃▃▄▃▃▂▂▁▁ ▁ ▁▁
  ████████████████████████████████████▇▆██▇▆▆▇▆▆▅▄▄▅▃▄▃▃▃▂▂▂▂▁▁ ▆
  42.9 μs          Histogram: frequency by time          231 μs <

 Memory estimate: 78.17 KiB, allocs estimate: 2.

for a common (simple) condition the mean time is almost equal to the previous one, for a rare (simple) condition is 4x in unremovableabm and 2x in standardabm in this setup

[Tortar]

the eat! method in WolfSheep now it's simpler and faster:

function eat!(wolf::Wolf, model)
    is_sheep(agent) = typeof(agent) == Sheep
    dinner = random_agent_in_position(wolf.pos, model, is_sheep)
    if !isnothing(dinner)
        remove_agent!(dinner, model)
        wolf.energy += wolf.Δenergy
    end
end

the wolfsheep model passed from 96 ms to 84 ms!

[Datseris]

i don't understand why these fnctions exist when one can use r=0 in the existing functions?

[Tortar]

I would say for mainly three reasons: we have ids_in_position and agents_in_position already (while you can have them with r = 0), writing r = 0 is strange (to me) and undocumented, using r = 0 without any change will have performance drawbacks since it creates an iterator while it is unnecessary and if we create a fastpath for r = 0 the function will become type-unstable in the returning value, which can possibly have some (albeit small) perf problems. While most of these problems are solvable with a different implementation of the change, I think It is a bit better to add these two functions.

[Datseris]

You should cross-refernce these funtions in ids_in_position and random_nearby... Then merge!