Skip to content

Empty positions performance boost#541

Merged
Libbum merged 7 commits intomasterfrom
rand_empty
Aug 23, 2021
Merged

Empty positions performance boost#541
Libbum merged 7 commits intomasterfrom
rand_empty

Conversation

@Libbum
Copy link
Copy Markdown
Member

@Libbum Libbum commented Aug 9, 2021

random_empty and kin require a full filter of the board each time they're called regardless of how sparse the agents are populating it. This PR provides us quite a noticeable performance enhancement using guesses, that we stop using once we start failing too much.

The core concept is a loop that gives us a random_position and returns it, otherwise tries again.

while true
    pos = random_position(model)
    isempty(pos, model) && return pos
end

Benchmarking on the maximum time of our current and this proposed solution, we can find the place where we guarantee chance will win out to filtering/collecting.

function rand_mt(model)
    has_empty_positions(model) || return nothing
    while true
        pos = random_position(model)
        if isempty(pos, model)
            return pos
        end
    end
end

julia> nagents(model)
249999

julia> prod(size(model.space))
250000

function run_test(model)
    while true
        println(nagents(model))
        curr = @benchmark random_empty($model)
        prop = @benchmark rand_mt($model)
        max_curr = maximum(curr.times)*1e-6 # ms
        max_prop = maximum(prop.times)*1e-6 # ms
        println("Current: $max_curr ms, Proposed: $max_prop ms")
        if max_prop < max_curr
            return nagents(model)/prod(size(model.space))
        end
        kill_agent!(random_agent(model), model)
    end
end

The changeover point is close to 0.999 (!) on this model, and as we go lower, as performance matters less, 0.998.. So we set our cutoff there and we can compare our standard Schelling benchmark (which needs random_empty):

Current (my machine): 13.783 ms
This PR (my machine): 2.771 ms

Speedup: 4.98x

Comparisons against other frameworks for Schelling (est, need to bump some changes here):
Mesa: 31.5x -> 156.9x
Netlogo: 8x -> 39.8x
MASON: 14.3x -> 71.1x

@Libbum Libbum requested a review from Datseris August 9, 2021 11:03
Datseris
Datseris reviewed Aug 9, 2021
View reviewed changes
Comment thread src/spaces/discrete.jl Outdated
@Datseris
Copy link
Copy Markdown
Member

Datseris commented Aug 9, 2021

hell yeah baby!!!!

@Datseris
Copy link
Copy Markdown
Member

Datseris commented Aug 9, 2021 •
edited
Loading

Sorry, test fail because of me. I've tried to improve the printing of the model for no space but failed to adjust the tests. Can you do it quickly (I don't have Agents deved atm)?

@Libbum
Copy link
Copy Markdown
Member Author

Libbum commented Aug 9, 2021

Yes, and yes - i'll fix both in a bit.

@Datseris
Copy link
Copy Markdown
Member

Datseris commented Aug 9, 2021

Perhaps we should also update the comparison table in this PR?

@Libbum
Copy link
Copy Markdown
Member Author

Libbum commented Aug 9, 2021

Yep. I need to update ABM_framework_comparison et al as well. About to go to get the second vaccine, so will get back to this later.

(Wanted to get this out before resubmit)

@codecov-commenter
Copy link
Copy Markdown

codecov-commenter commented Aug 12, 2021 •
edited
Loading

Codecov Report

Merging #541 (893f498) into master (5693d22) will increase coverage by 0.03%.
The diff coverage is 100.00%.

❗ Current head 893f498 differs from pull request most recent head 6926eb3. Consider uploading reports for the commit 6926eb3 to get more accurate results
Impacted file tree graph

@@            Coverage Diff             @@
##           master     #541      +/-   ##
==========================================
+ Coverage   94.35%   94.38%   +0.03%     
==========================================
  Files          24       24              
  Lines        1453     1461       +8     
==========================================
+ Hits         1371     1379       +8     
  Misses         82       82
Impacted Files Coverage Δ
src/spaces/discrete.jl 100.00% <100.00%> (ø)
src/submodules/pathfinding/astar.jl 93.24% <0.00%> (+0.28%) ⬆️

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update 5693d22...6926eb3. Read the comment docs.

rht
rht reviewed Aug 12, 2021
View reviewed changes
Comment thread src/spaces/discrete.jl
@Datseris
Copy link
Copy Markdown
Member

Datseris commented Aug 13, 2021

just to clarify: I shouldn't merge this, right?

@Libbum
Copy link
Copy Markdown
Member Author

Libbum commented Aug 13, 2021

Correct. It's not ready yet. Will let you know.

@Libbum
Copy link
Copy Markdown
Member Author

Libbum commented Aug 18, 2021

The cutoff looks like it scales pretty well for everything:

GraphSpace

g = complete_digraph(500)
model = ABM(Agent5, GraphSpace(g))
for _ in 1:500
    add_agent_single!(model, rand(model.rng))
end
kill_agent!(random_agent(model), model)

run_test(model)
499
Current: 0.023975974358974358 ms, Proposed: 0.010073555555555554 ms
0.998

For 5000

julia> run_test(model)
4999
Current: 0.046383 ms, Proposed: 0.40435699999999997 ms
4998
Current: 0.052060999999999996 ms, Proposed: 0.143565 ms
4997
Current: 0.048937999999999995 ms, Proposed: 0.15190599999999999 ms
4996
Current: 0.07264799999999999 ms, Proposed: 0.052907249999999996 ms
0.9992

For 50

julia> run_test(model)
49
Current: 0.037711253583241455 ms, Proposed: 0.0005155497326203208 ms
0.98

3D GridSpace

@agent Agent3D GridAgent{3} begin end
model = ABM(Agent3D, GridSpace((10,10,10)))
for _ in 1:prod(size(model.space.s))
    add_agent_single!(model)
end
kill_agent!(random_agent(model), model)

julia> run_test(model)
999
Current: 0.007721111111111111 ms, Proposed: 0.05982014285714285 ms
998
Current: 0.01596222222222222 ms, Proposed: 0.034263166666666664 ms
997
Current: 0.007904777777777776 ms, Proposed: 0.017391666666666666 ms
996
Current: 0.007268999999999999 ms, Proposed: 0.010618924242424242 ms
995
Current: 0.015423999999999998 ms, Proposed: 0.011567 ms
0.995

For 50^3

julia> run_test(model)
124999
Current: 1.212627 ms, Proposed: 35.20457 ms
124998
Current: 1.047918 ms, Proposed: 21.559383 ms
124997
Current: 1.0224309999999999 ms, Proposed: 12.160535 ms
...
124954
Current: 1.023584 ms, Proposed: 1.061899 ms
124953
Current: 1.080368 ms, Proposed: 1.014422 ms
0.999624

Of course you can micromanage this value but we have a good default at 0.998.

I'll run the benchmarks and update the docs soon.

@AayushSabharwal
Copy link
Copy Markdown
Collaborator

AayushSabharwal commented Aug 20, 2021

While cutoff is less than 1, the while true loop is guaranteed to terminate (since there are less agents than the positions they can fill)
However, this isn't guaranteed if cutoff >= 1. Should there be some sort of guard against this? Should values larger than 1 even be allowed?

@Libbum
Copy link
Copy Markdown
Member Author

Libbum commented Aug 20, 2021 •
edited
Loading

Good point. These tests assume that the number of agents are always less than the available spaces in the grid. The logic should be clamped to 1 (values above 1 should not be allowed). I'll fix that.

@Libbum Libbum merged commit c8ba2fa into master Aug 23, 2021
@Libbum Libbum deleted the rand_empty branch August 23, 2021 07:50
Datseris
Datseris reviewed Aug 23, 2021
View reviewed changes
Comment thread CHANGELOG.md
@rht rht mentioned this pull request Sep 8, 2021
Closed
@rht rht mentioned this pull request Dec 23, 2021
Merged
@rht rht mentioned this pull request Oct 30, 2022
Merged
@yassinekolsi yassinekolsi mentioned this pull request Mar 23, 2026
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@Datseris Datseris Datseris left review comments

+1 more reviewer

@rht rht rht left review comments

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

performance

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

5 participants

@Libbum @Datseris @codecov-commenter @AayushSabharwal @rht