Skip to content

Speedup of Agentset.shuffle#2010

Merged
rht merged 29 commits intomesa:mainfrom
quaquel:agentset_speed
Jan 27, 2024
Merged

Speedup of Agentset.shuffle#2010
rht merged 29 commits intomesa:mainfrom
quaquel:agentset_speed

Conversation

@quaquel
Copy link
Copy Markdown
Member

@quaquel quaquel commented Jan 27, 2024

This speeds up shuffle by shuffling the actual weakrefs, rather than first turning them back into hard refs, shuffling them, and turning them back into weakness (which is what the old code did).

One probably controversial choice is that I have shifted to default inplace shuffle. Feel free to let me know what you think. I am fine either way but inplace is quite a bit faster (and the default behavior of random.shuffle).

quaquel and others added 26 commits January 15, 2024 11:23
commit c0de4a1
Author: Ewout ter Hoeven <[email protected]>
Date:   Sun Jan 21 14:43:08 2024 +0100

    Add CI workflow for performance benchmarks (mesa#1983)

    This commit introduces a new GitHub Actions workflow for performance benchmarking. The workflow is triggered on `pull_request_target` events and can be triggered with a "/rerun-benchmarks" comment in the PR. It should be compatible with PRs from both forks and the main repository. It includes steps for setting up the environment, checking out the PR and main branches, installing dependencies, and running benchmarks on both branches. The results are then compared, encoded, and posted as a comment on the PR.
@EwoutH EwoutH added performance Release notes label enhancement Release notes label labels Jan 27, 2024
@quaquel
Copy link
Copy Markdown
Member Author

quaquel commented Jan 27, 2024

How can I trigger the benchmark stuff?

@github-actions
Copy link
Copy Markdown

Performance benchmarks:

Model Size Init time [95% CI] Run time [95% CI]
Schelling small 🔵 +0.2% [-0.1%, +0.6%] 🟢 -11.1% [-11.2%, -11.0%]
Schelling large 🔴 +93.7% [+46.5%, +141.0%] 🟢 -14.7% [-15.7%, -13.7%]
WolfSheep small 🔵 +0.6% [+0.1%, +1.0%] 🟢 -18.1% [-18.2%, -18.0%]
WolfSheep large 🔴 +32.7% [+4.0%, +65.2%] 🟢 -20.1% [-21.6%, -18.3%]
BoidFlockers small 🔵 +1.0% [+0.4%, +1.6%] 🔵 +0.6% [-0.0%, +1.3%]
BoidFlockers large 🔵 -0.2% [-1.0%, +0.7%] 🔵 +0.7% [+0.2%, +1.1%]

@quaquel
Copy link
Copy Markdown
Member Author

quaquel commented Jan 27, 2024

The benchmark init numbers make little sense to me. My changes only relate to shuffle and do, neither of which is touched by the model initialization.

@EwoutH
Copy link
Copy Markdown
Member

EwoutH commented Jan 27, 2024

Can you replicate them locally? Maybe with some more replications/seeds (modify benchmarks/configurations.py)?

@quaquel
Copy link
Copy Markdown
Member Author

quaquel commented Jan 27, 2024

Can you replicate them locally? Maybe with some more replications/seeds (modify benchmarks/configurations.py)?

I'll try.

One possible solution, more generally, is to ensure the same seeds are used in both benchmarks. I'll look at the code and open a separate PR if needed.

@EwoutH
Copy link
Copy Markdown
Member

EwoutH commented Jan 27, 2024

One possible solution, more generally, is to ensure the same seeds are used in both benchmarks.

Should already be happening:
https://github.com/projectmesa/mesa/blob/6a4ea54d6dade48591db512d3f7ada18ec4d42ff/benchmarks/global_benchmark.py#L38
So if "seeds" in the config say 25, it will use seed 1 to 25. It then does use the paired samples to compare it.

But if you see room for improvement, please do! Also check: #1983 (comment)

@quaquel
Copy link
Copy Markdown
Member Author

quaquel commented Jan 27, 2024

Can you replicate them locally? Maybe with some more replications/seeds (modify benchmarks/configurations.py)?

I ran it locally with the default settings. The results are more in line with what I would expect. It seems the init is particularly noisy. Not really surprising but good to know.

Model Size Init time [95% CI] Run time [95% CI]
Schelling small 🔵 -0.2% [-0.7%, +0.2%] 🟢 -9.5% [-9.7%, -9.4%]
Schelling large 🔵 -1.6% [-3.5%, +0.4%] 🟢 -25.0% [-29.1%, -20.9%]
WolfSheep small 🔵 -3.8% [-4.6%, -2.9%] 🟢 -20.5% [-21.2%, -19.7%]
WolfSheep large 🔵 -11.0% [-24.2%, -1.5%] 🟢 -24.4% [-28.0%, -20.7%]
BoidFlockers small 🔵 -3.2% [-5.6%, -0.6%] 🔵 -2.9% [-4.1%, -1.9%]
BoidFlockers large 🟢 -7.1% [-8.1%, -6.2%] 🟢 -5.0% [-6.8%, -3.2%]

@quaquel
Copy link
Copy Markdown
Member Author

quaquel commented Jan 27, 2024

This is ready for review and merging. When merging, please squash and merge.

Copy link
Copy Markdown
Contributor

@Corvince Corvince left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I am wondering if a similar logic could be applied to there other methods or in place of the current _update method. I would think similar performance improvements might be possible?

@quaquel
Copy link
Copy Markdown
Member Author

quaquel commented Jan 27, 2024

I am wondering if a similar logic could be applied to there other methods or in place of the current _update method. I would think similar performance improvements might be possible?

It's a bit tricky. Both select and sort typically need the actual agent object and thus cannot operate only on the weakrefs as is possible with shuffle.

@EwoutH
Copy link
Copy Markdown
Member

EwoutH commented Jan 27, 2024

This PR is starting to look ready to me. How good is the test coverage of this part of the code?

@EwoutH EwoutH added trigger-benchmarks Special label that triggers the benchmarking CI and removed trigger-benchmarks Special label that triggers the benchmarking CI labels Jan 27, 2024
@github-actions
Copy link
Copy Markdown

Performance benchmarks:

Model Size Init time [95% CI] Run time [95% CI]
Schelling small 🔵 +0.6% [+0.1%, +1.1%] 🟢 -11.4% [-11.6%, -11.3%]
Schelling large 🔴 +96.2% [+47.7%, +142.9%] 🟢 -14.2% [-15.7%, -12.4%]
WolfSheep small 🔵 +1.1% [+0.6%, +1.7%] 🟢 -18.1% [-18.3%, -18.0%]
WolfSheep large 🔵 +39.6% [+2.1%, +80.7%] 🟢 -13.1% [-15.0%, -11.2%]
BoidFlockers small 🔵 +3.3% [+2.8%, +3.8%] 🔵 +0.7% [+0.0%, +1.4%]
BoidFlockers large 🔵 +2.7% [+1.7%, +3.8%] 🔵 +1.0% [+0.4%, +1.6%]

@EwoutH
Copy link
Copy Markdown
Member

EwoutH commented Jan 27, 2024

Do we have any idea why this could slow down the shelling large init? It happened on both CI runs, with remarkable consistency.

@quaquel
Copy link
Copy Markdown
Member Author

quaquel commented Jan 27, 2024

This PR is starting to look ready to me. How good is the test coverage of this part of the code?

We added testcode as part of #2007. This already covers inplace=True and inplace=False.

Do we have any idea why this could slow down the shelling large init? It happened on both CI runs, with remarkable consistency.

Yes, but not on my machine. Moreover, the init code is unrelated to this change. Shuffle is not called in model.__init__. Remember, the init is very short so tiny changes result in large percentages quickly.

@rht
Copy link
Copy Markdown
Contributor

rht commented Jan 27, 2024

@rht rht merged commit 449d230 into mesa:main Jan 27, 2024
@rht
Copy link
Copy Markdown
Contributor

rht commented Jan 27, 2024

Squashed and merged with the commit message perf: Speed up Agentset.shuffle (#2010).

self.random.shuffle(weakrefs)

if inplace:
self._agents.data = {entry: None for entry in weakrefs}
Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

How come in this line there is no need for (agent := ref()) is not None), but it is needed in L204?

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

When you create a new AgentSet, it has its own internal WeakkeyDict. Each WeakkeyDict creates its own weakrefs.

As can be seen in the docs, weakref.ref takes an optional callback. In the case of WeakkeyDict, this callback is a method on the dict itself (i.e., self.remove). So, when not shuffling in place, I have to unpack the weakrefs to ensure the new WeakkeyDict behaves correctly.

Moreover, AgentSet takes an iteratable of agents as an argument. Not an iterable of weakref. ref instances.

Hope this clarifies.

@quaquel quaquel deleted the agentset_speed branch October 7, 2024 07:06
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

enhancement Release notes label performance Release notes label

Projects

None yet

Development

Successfully merging this pull request may close these issues.

4 participants