Optimise select_random_empty_cell() in grid.py by codebreaker32 · Pull Request #3087 · mesa/mesa

codebreaker32 · 2026-01-07T19:14:41Z

Summary

This PR optimizes the fallback mechanism in Grid.select_random_empty_cell to use vectorized NumPy operations, replacing the slow O(N) Python iteration. It also fixes a critical bug in HasPropertyLayers.select_cells preventing the correct masking of empty cells.

Motive

1. Performance on Dense Grids:
The select_random_empty_cell method uses a fast random heuristic (O(1)). However, when the grid is nearly full (dense), this heuristic fails, and the code previously fell back to iterating over all cells:
return self.random.choice(list(self.empties))
This triggered the descriptor protocol for every single cell, causing a massive performance penalty. By switching to self.select_cells(only_empty=True), we bypass the Cell objects entirely and scan the underlying NumPy array directly.

2. Bug Fix:
The select_cells(only_empty=True) method in property_layer.py was previously broken. It attempted to apply a logical mask to the PropertyLayer object instead of its underlying .data array, causing operations to fail or return incorrect results.( I missed it in #3074 )

Implementation

mesa/discrete_space/grid.py:

Updated select_random_empty_cell to call self.select_cells(only_empty=True) in the fallback block.

mesa/discrete_space/property_layer.py:

Fixed select_cells: Changed self._mesa_property_layers["empty"] to self._mesa_property_layers["empty"].data.

Usage Examples

There is no change to the public API.

Additional Notes

Dependencies: This relies on the PropertyLayer architecture being present.

quaquel · 2026-01-07T19:21:04Z

mesa/discrete_space/grid.py

+        empty_coords = self.select_cells(only_empty=True)
+        random_coord = self.random.choice(empty_coords)
+        return self._cells[random_coord]


would it not be a lot faster to do something like

coords = np.argwhere(self.empty.data) random_coord = self.random.choice(empty_coords)

You are right.

but if that works, I am wondering whether its not just allways faster to do this instead of the random trying.

I know that there has been some research on this before (see. mesa.space for details). I am just not sure how those findings translate to the new discrete_space.

I looked into the existing mesa.space implementation(which led me to #1052), and it actually uses a specific cutoff formula (cutoff_empties) to switch between random sampling and list generation. However, I believe numpy definitely shifts the cutoff point so we might reduce the N

Yeah, my thinking exactly. I suppose some of the testing will need to be rerun to determine the cutoff in this case.

for more information, see https://pre-commit.ci

quaquel · 2026-01-07T20:12:47Z

So this crashed:

  return self._cells[random_coord]
           ~~~~~~~~~~~^^^^^^^^^^^^^^
TypeError: cannot use 'numpy.ndarray' as a dict key (unhashable type: 'numpy.ndarray')

Basically, the numpy array for the coordinates needs to be cast to a tuple I guess. Also, it highlights the need for test coverage.

update: I fixed it for you after confirming that it was indeed working. Main thing now is to add test coverage.

mesa/discrete_space/grid.py

github-actions · 2026-01-07T21:19:52Z

Performance benchmarks:

Model	Size	Init time [95% CI]	Run time [95% CI]
BoltzmannWealth	small	🔵 -0.9% [-2.0%, +0.3%]	🔵 -0.4% [-0.6%, -0.3%]
BoltzmannWealth	large	🔵 -1.5% [-2.1%, -0.9%]	🟢 -5.9% [-8.9%, -3.6%]
Schelling	small	🔵 +0.1% [-0.8%, +1.1%]	🔵 -0.7% [-1.2%, -0.1%]
Schelling	large	🔵 -0.0% [-0.3%, +0.2%]	🔵 -1.0% [-1.6%, -0.4%]
WolfSheep	small	🔵 +0.3% [+0.1%, +0.5%]	🔵 -0.1% [-0.4%, +0.1%]
WolfSheep	large	🔵 -0.5% [-2.7%, +1.1%]	🔵 -1.1% [-2.4%, +0.1%]
BoidFlockers	small	🔵 +2.4% [+2.2%, +2.7%]	🔵 +0.3% [+0.2%, +0.5%]
BoidFlockers	large	🔵 +1.8% [+1.3%, +2.4%]	🔵 -0.4% [-0.6%, -0.2%]

codebreaker32 · 2026-01-08T04:45:34Z

I will add tests for it today only.

codebreaker32 · 2026-01-08T05:42:16Z

Hi @quaquel
I also want to point out one minor inconsistency
ufunc.nargs counts both inputs and outputs (e.g., np.add has nargs=3) and ufunc.nin counts only input(np.add has nin=2)

def ufunc_requires_additional_input(ufunc):  # noqa: D103
    # NumPy ufuncs have a 'nargs' attribute indicating the number of input arguments
    # For binary ufuncs (like np.add), nargs is 2
    return ufunc.nargs > 1

Isn't it misleading then?

quaquel · 2026-01-08T06:41:22Z

Isn't it misleading then?

I guess so. I just copied this frommesa.space, but I guess it should be ufunc.nin > 1.

codebreaker32 · 2026-01-08T06:49:06Z

ufunc.nin resulted in a linting(codespell) error

ruff (legacy alias)......................................................Passed
ruff format..............................................................Passed
pyupgrade................................................................Passed
trim trailing whitespace.................................................Passed
check toml...............................................................Passed
check yaml...............................................................Passed
codespell................................................................Failed- hook id: codespell- exit code: 
65:mesa/discrete_space/property_layer.py:422: nin ==> inn, min, bin, nine
mesa/discrete_space/property_layer.py:423: nin ==> inn, min, bin, nine

quaquel · 2026-01-08T08:49:18Z

ufunc.nin resulted in a linting(codespell) error

What did you change exactly? I guess the problem triggers on the comment, not the actual code?

codebreaker32 · 2026-01-08T08:58:54Z

What did you change exactly? I guess the problem triggers on the comment, not the actual code?

Both i.e method and comments. Yes the problem was triggered by comment

Update: Replaced nargs with nin and updated pyproject.toml to add "nin" as ignored-word

for more information, see https://pre-commit.ci

mesa/discrete_space/property_layer.py

pyproject.toml

codebreaker32 · 2026-01-08T14:00:56Z

I think its ready to be merged now.

github-actions · 2026-01-09T10:35:56Z

Performance benchmarks:

Model	Size	Init time [95% CI]	Run time [95% CI]
BoltzmannWealth	small	🔵 +0.8% [+0.4%, +1.3%]	🔵 +0.5% [+0.2%, +0.8%]
BoltzmannWealth	large	🔵 +0.4% [+0.1%, +0.8%]	🔵 +0.8% [+0.1%, +1.5%]
Schelling	small	🔵 +0.4% [-0.5%, +1.4%]	🔵 -0.2% [-0.8%, +0.3%]
Schelling	large	🔵 -0.8% [-1.1%, -0.5%]	🔵 +1.1% [-0.2%, +2.3%]
WolfSheep	small	🔵 +0.7% [+0.4%, +1.0%]	🔵 +2.3% [+2.1%, +2.5%]
WolfSheep	large	🔵 -0.2% [-3.0%, +1.4%]	🔵 +3.0% [+1.6%, +4.6%]
BoidFlockers	small	🔵 +1.6% [+1.0%, +2.3%]	🔵 +2.4% [+2.2%, +2.7%]
BoidFlockers	large	🔵 +0.2% [-0.3%, +0.8%]	🔵 +1.6% [+1.4%, +1.8%]

Optimise select_random_empty_cell() in grid.py

f9ee651

quaquel reviewed Jan 7, 2026

View reviewed changes

This comment was marked as outdated.

Sign in to view

codebreaker32 and others added 2 commits January 7, 2026 19:28

Use np.argwhere instead of select_cells

a8bda78

[pre-commit.ci] auto fixes from pre-commit.com hooks

2d5f21b

for more information, see https://pre-commit.ci

quaquel added performance Release notes label trigger-benchmarks Special label that triggers the benchmarking CI labels Jan 7, 2026

quaquel reviewed Jan 7, 2026

View reviewed changes

mesa/discrete_space/grid.py Outdated Show resolved Hide resolved

quaquel added trigger-benchmarks Special label that triggers the benchmarking CI and removed trigger-benchmarks Special label that triggers the benchmarking CI labels Jan 7, 2026

Apply suggestion from @quaquel

f7b703b

codebreaker32 force-pushed the feat/optimise-random-empty-cell_in_grid branch 2 times, most recently from cd8d18c to 2b4581e Compare January 8, 2026 05:31

Add tests coverage

5d763d7

codebreaker32 force-pushed the feat/optimise-random-empty-cell_in_grid branch from ed76b23 to 5d763d7 Compare January 8, 2026 05:33

codebreaker32 force-pushed the feat/optimise-random-empty-cell_in_grid branch from 4e207e8 to 5d763d7 Compare January 8, 2026 09:13

Replaced with in property_layer.py

bc4cee8

codebreaker32 force-pushed the feat/optimise-random-empty-cell_in_grid branch from cf9ed0f to bc4cee8 Compare January 8, 2026 09:20

[pre-commit.ci] auto fixes from pre-commit.com hooks

083092f

for more information, see https://pre-commit.ci

quaquel reviewed Jan 8, 2026

View reviewed changes

mesa/discrete_space/property_layer.py Outdated Show resolved Hide resolved

quaquel reviewed Jan 8, 2026

View reviewed changes

pyproject.toml Outdated Show resolved Hide resolved

Fix linting errors and replaced nargs with nin

32d9bc3

codebreaker32 requested a review from quaquel January 8, 2026 14:01

quaquel approved these changes Jan 8, 2026

View reviewed changes

quaquel merged commit 37a3a20 into mesa:main Jan 8, 2026
14 checks passed

EwoutH added the enhancement Release notes label label Jan 9, 2026

codebreaker32 deleted the feat/optimise-random-empty-cell_in_grid branch January 10, 2026 13:13

Uh oh!

Conversation

codebreaker32 commented Jan 7, 2026

Summary

Motive

Implementation

Usage Examples

Additional Notes

Uh oh!

quaquel Jan 7, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

codebreaker32 Jan 7, 2026

Choose a reason for hiding this comment

Uh oh!

quaquel Jan 7, 2026

Choose a reason for hiding this comment

Uh oh!

codebreaker32 Jan 7, 2026

Choose a reason for hiding this comment

Uh oh!

quaquel Jan 7, 2026

Choose a reason for hiding this comment

Uh oh!

This comment was marked as outdated.

quaquel commented Jan 7, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

github-actions bot commented Jan 7, 2026

Uh oh!

codebreaker32 commented Jan 8, 2026

Uh oh!

codebreaker32 commented Jan 8, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

quaquel commented Jan 8, 2026

Uh oh!

codebreaker32 commented Jan 8, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

quaquel commented Jan 8, 2026

Uh oh!

codebreaker32 commented Jan 8, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

codebreaker32 commented Jan 8, 2026

Uh oh!

Uh oh!

github-actions bot commented Jan 9, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

quaquel Jan 7, 2026 •

edited

Loading

quaquel commented Jan 7, 2026 •

edited

Loading

codebreaker32 commented Jan 8, 2026 •

edited

Loading

codebreaker32 commented Jan 8, 2026 •

edited

Loading

codebreaker32 commented Jan 8, 2026 •

edited

Loading