Skip to content

Micro optimization of grid.select_random_empty_cell#3214

Merged
quaquel merged 1 commit intomesa:mainfrom
quaquel:select_random_empty_cell
Jan 27, 2026
Merged

Micro optimization of grid.select_random_empty_cell#3214
quaquel merged 1 commit intomesa:mainfrom
quaquel:select_random_empty_cell

Conversation

@quaquel
Copy link
Copy Markdown
Member

@quaquel quaquel commented Jan 27, 2026 •
edited
Loading

This is a micro optimization of grid.select_random_empty_cell. Currently, this calls cellcollection.select_random_cell, which in turn does random.choice(cells). This indirection can be avoided by just having a _celllist inside grid and using random.choice directly on it. Then, to top it off, we assign self.random and self._celllist to local variables in the method to further improve performance. This trick avoids the Python calling overhead of attribute lookup. Since this for loop runs 50 times in the worst case, this micro stuff adds up a lot.

@quaquel quaquel added performance Release notes label trigger-benchmarks Special label that triggers the benchmarking CI labels Jan 27, 2026
@github-actions
Copy link
Copy Markdown

github-actions bot commented Jan 27, 2026

Performance benchmarks:

Model Size Init time [95% CI] Run time [95% CI]
BoltzmannWealth small 🔵 -0.6% [-1.1%, -0.2%] 🟢 -4.7% [-4.8%, -4.5%]
BoltzmannWealth large 🔵 +0.6% [-0.8%, +1.9%] 🔵 +4.9% [-3.4%, +12.1%]
Schelling small 🔵 -1.3% [-1.6%, -0.9%] 🔵 -1.7% [-2.1%, -1.4%]
Schelling large 🔵 -2.5% [-3.0%, -2.0%] 🟢 -19.2% [-23.2%, -14.4%]
WolfSheep small 🔵 -1.2% [-1.4%, -1.0%] 🔵 -0.5% [-0.6%, -0.3%]
WolfSheep large 🔵 -2.5% [-3.3%, -1.7%] 🔵 -3.2% [-5.0%, -1.5%]
BoidFlockers small 🔵 -2.5% [-2.8%, -2.2%] 🔵 -0.3% [-0.4%, -0.3%]
BoidFlockers large 🔵 -0.9% [-1.4%, -0.5%] 🔵 -0.4% [-0.6%, -0.2%]

@github-actions

This comment was marked as outdated.

Sign in to view
@quaquel
Copy link
Copy Markdown
Member Author

quaquel commented Jan 27, 2026

If I use timeit with Schelling, on a 50X50 grid, a fixed seed, and a density of 0.9, the results are for just grid.select_random_empty_cell.

3.4.2: 3.12 μs ± 64 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
with this PR merged: 2.42 μs ± 21.6 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

EwoutH
EwoutH approved these changes Jan 27, 2026
View reviewed changes
Copy link
Copy Markdown
Member

@EwoutH EwoutH left a comment

Choose a reason for hiding this comment

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

Looks clean, and I like the green!

@quaquel
Copy link
Copy Markdown
Member Author

quaquel commented Jan 27, 2026

It was a no-brainer that I came across while microbenchmarking stuff for mesa-rust.

@quaquel quaquel merged commit f85328a into mesa:main Jan 27, 2026
17 checks passed
@EwoutH
Copy link
Copy Markdown
Member

EwoutH commented Jan 27, 2026

20% in Schelling is quite a lot

@quaquel
Copy link
Copy Markdown
Member Author

quaquel commented Jan 27, 2026

Large schelling is in essence just a test for how fast get_random_empty_cell is. Which is what I figured out while working on the mesa-rust stuff.

@EwoutH EwoutH added the enhancement Release notes label label Feb 11, 2026
@github-actions
Copy link
Copy Markdown

github-actions bot commented Feb 11, 2026

Performance benchmarks:

Model Size Init time [95% CI] Run time [95% CI]
BoltzmannWealth small 🔵 -2.4% [-2.9%, -1.7%] 🔵 -1.7% [-1.9%, -1.6%]
BoltzmannWealth large 🔵 +1.2% [+0.5%, +1.9%] 🔵 +5.0% [+1.9%, +8.2%]
Schelling small 🔵 +1.0% [+0.7%, +1.3%] 🔵 +0.3% [+0.1%, +0.4%]
Schelling large 🔵 +0.1% [-0.6%, +0.8%] 🔴 +5.1% [+3.9%, +6.2%]
WolfSheep small 🟢 -7.9% [-8.2%, -7.7%] 🔵 -1.0% [-1.2%, -0.9%]
WolfSheep large 🟢 -8.6% [-9.8%, -7.5%] 🔵 +0.3% [-1.1%, +1.5%]
BoidFlockers small 🟢 -7.0% [-7.3%, -6.7%] 🔵 -0.7% [-0.8%, -0.6%]
BoidFlockers large 🟢 -7.6% [-8.0%, -7.2%] 🔵 -0.6% [-0.8%, -0.5%]

@quaquel quaquel deleted the select_random_empty_cell branch February 16, 2026 15:11
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@EwoutH EwoutH EwoutH approved these changes

Assignees

No one assigned

Labels

enhancement Release notes label 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.

2 participants

@quaquel @EwoutH