Skip to content

Optimise _remove_agent in Continuous Space#3491

Merged
quaquel merged 3 commits intomesa:mainfrom
codebreaker32:refactor/continuous_space
Mar 11, 2026
Merged

Optimise _remove_agent in Continuous Space#3491
quaquel merged 3 commits intomesa:mainfrom
codebreaker32:refactor/continuous_space

Conversation

@codebreaker32
Copy link
Copy Markdown
Collaborator

@codebreaker32 codebreaker32 commented Mar 9, 2026 •
edited
Loading

Summary

This PR optimizes the internal agent removal process in ContinuousSpace by replacing the $O(N)$ array shifting logic with an $O(1)$ "swap-with-last" algorithm. This eliminates costly for loops and NumPy array slice shifting, drastically improving performance for models with high agent churn.

Motive

See #3490

Implementation

This PR aligns ContinuousSpace with the performance standards recently established in Mesa's data collection modules. It implements the exact same "swap-with-last" logic used by NumpyAgentDataSet.

Additional Notes

As Mesa 4.0 moves toward the "Stacked Spaces" architecture (where Continuous Agents may have primary role), optimizing base operations can be seen as prerequisites effort before we start introducing major changes

Closes #3490

@github-actions
Copy link
Copy Markdown

github-actions bot commented Mar 9, 2026

Performance benchmarks:

Model Size Init time [95% CI] Run time [95% CI]
BoltzmannWealth small 🔵 +0.5% [+0.2%, +0.8%] 🔵 -0.0% [-0.2%, +0.1%]
BoltzmannWealth large 🔵 +1.0% [+0.8%, +1.2%] 🔵 +0.7% [+0.5%, +0.9%]
Schelling small 🔵 +0.5% [+0.2%, +0.7%] 🔵 +0.2% [+0.0%, +0.3%]
Schelling large 🔵 +0.6% [+0.0%, +1.2%] 🔵 -0.5% [-1.8%, +0.5%]
WolfSheep small 🔵 +0.8% [+0.5%, +1.1%] 🔵 +0.3% [+0.1%, +0.5%]
WolfSheep large 🔵 +2.4% [+1.5%, +3.3%] 🔵 +2.2% [+1.3%, +3.2%]
SugarscapeG1mt small 🔵 +1.3% [+0.8%, +1.8%] 🔵 -0.7% [-0.9%, -0.6%]
SugarscapeG1mt large 🔵 +1.3% [+0.5%, +2.2%] 🔵 -1.2% [-1.5%, -0.9%]
BoidFlockers small 🔵 -0.1% [-0.4%, +0.4%] 🔵 -2.9% [-3.1%, -2.7%]
BoidFlockers large 🔵 +0.1% [-0.5%, +0.8%] 🔵 -1.9% [-2.0%, -1.8%]

@quaquel quaquel added the performance Release notes label label Mar 10, 2026
quaquel
quaquel reviewed Mar 11, 2026
View reviewed changes
mesa/experimental/continuous_space/continuous_space.py

# Pop the last elements
self.active_agents.pop()
self._index_to_agent.pop(last_index, None)
Copy link
Copy Markdown
Member

@quaquel quaquel Mar 11, 2026

Choose a reason for hiding this comment

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

I am fine with this change, but I wonder whether a further improvement might not be possible.

At the moment, on every access of agent.position, the agent has to look up its index. This seems wasteful. In principle, an agent can be assigned an index when added to a space and just keep this index for its lifetime. This does mean that on the space side, the indexing becomes a bit more difficult because we need to maintain a numpy array with the currently active indices. But it might offer speedups. Thoughts are welcome.

Copy link
Copy Markdown
Collaborator Author

@codebreaker32 codebreaker32 Mar 11, 2026

Choose a reason for hiding this comment

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

we need to maintain a numpy array with the currently active indices

How about using _mesa_index? I noticed we haven't using it actively. Any specific reason? Also see my latest commit.

Copy link
Copy Markdown
Member

@quaquel quaquel Mar 11, 2026

Choose a reason for hiding this comment

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

My hunch is that this index was added at some point while developing the code, but was not used in the final merged PR.

@codebreaker32 codebreaker32 force-pushed the refactor/continuous_space branch from 156cc27 to 3b82e0f Compare March 11, 2026 13:22
@quaquel quaquel added the trigger-benchmarks Special label that triggers the benchmarking CI label Mar 11, 2026
@github-actions
Copy link
Copy Markdown

github-actions bot commented Mar 11, 2026

Performance benchmarks:

Model Size Init time [95% CI] Run time [95% CI]
BoltzmannWealth small 🔵 +0.5% [+0.0%, +0.9%] 🔵 -0.8% [-1.0%, -0.7%]
BoltzmannWealth large 🔵 +0.7% [-0.1%, +1.4%] 🔵 -2.9% [-5.8%, -0.4%]
Schelling small 🔵 +1.6% [+1.3%, +2.0%] 🔵 +0.5% [+0.4%, +0.7%]
Schelling large 🔵 -1.6% [-2.1%, -1.1%] 🔵 -1.2% [-2.2%, -0.2%]
WolfSheep small 🔵 +0.0% [-0.3%, +0.3%] 🔵 -0.8% [-1.0%, -0.6%]
WolfSheep large 🔵 +1.5% [+0.1%, +3.3%] 🔵 +1.5% [-0.2%, +3.4%]
SugarscapeG1mt small 🔵 +0.4% [+0.0%, +0.8%] 🔵 -0.3% [-0.5%, -0.1%]
SugarscapeG1mt large 🔵 +0.5% [-1.0%, +1.8%] 🔵 -0.6% [-0.9%, -0.2%]
BoidFlockers small 🔵 -0.6% [-0.8%, -0.3%] 🔵 -2.6% [-2.7%, -2.4%]
BoidFlockers large 🔵 -0.4% [-0.9%, +0.0%] 🔵 -2.6% [-2.8%, -2.5%]

@quaquel quaquel merged commit 4140369 into mesa:main Mar 11, 2026
15 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@quaquel quaquel quaquel approved these changes

Assignees

No one assigned

Labels

performance Release notes label trigger-benchmarks Special label that triggers the benchmarking CI

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Optimise _remove_agent in Continuous Space

2 participants

@codebreaker32 @quaquel