Repository: projectmesa/mesa

Issue:
SingleGrid position_agent very slow for large grids
It's fine for square widths of around 20 cells, but when you 200 it slows right down.

It appears to be caused by the line `agent.random.choice(sorted(self.empties))` where it sorts the empties first. I guess it does this so you can replicate the results using random seed?

If you don't care about replication however, it's unreasonably slow and can be fixed by using `agent.random.choice(list(self.empties))` instead (speeding it enormously).

I'm not sure of the design decisions here, but maybe it's worth having two functions to make it clear or passing some sort of bool?

https://mesa.readthedocs.io/en/stable/mesa.html#mesa.space.SingleGrid.position_agent


Discussion:
rht: The next question is to whether remove the grid's `self.empties` attribute altogether. Currently, the remaining use of this attribute is that to check whether the grid is full in the function `position_agent`. Agents.jl doesn't do this. And I can see that instead of checking that the grid is full every time, we can do during the initializatio to check that the ratio between the number of agents and the grid area must not exceed 1. Thoughts?

This decision needs to be resolved before I can fix the tests.
tpike3: Sorry, it took me awhile to really think through this. I don't think we should get rid of self.empties as my sense is it will break a lot of models. 

On question in comments you say Agents.jl uses 0.998 as the cutoff score but say the number is different here. Not being familiar with how Julia stores numbers are you saying that although the numbers are the *same* the way they are stored is actually comparing a different value? 
rht: > I don't think we should get rid of self.empties as my sense is it will break a lot of models.

I have checked `self.empties` usage. It is only used in `move_to_empty` and `position_agent` (when x and y are 'random'). It shouldn't be a public attribute that Mesa users should use either.
rht: > On question in comments you say Agents.jl uses 0.998 as the cutoff score but say the number is different here. Not being familiar with how Julia stores numbers are you saying that although the numbers are the same the way they are stored is actually comparing a different value?

My code comment is certainly misleading. I currently hardcode the cutoff to be 0.998 (same as Agents.jl) because I haven't done the search for the optimum number for Mesa. I will probably have to use the exact same code @Libbum use (translated to Python from Julia) to get the number.

Just wanting to emphasize that the speedup is much, much higher when the grid size is 200 x 200 (i.e. the problem raised in #1052), it's just that it is taking too long on my laptop to measure. I'd consider 200x200 to be a common laptop-scale problem.
codecov[bot]: # [Codecov](https://codecov.io/gh/projectmesa/mesa/pull/1116?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa) Report
> Merging [#1116](https://codecov.io/gh/projectmesa/mesa/pull/1116?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa) (919a4cd) into [main](https://codecov.io/gh/projectmesa/mesa/commit/246c69d592a82e89c75d555c79736c3f619d434a?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa) (246c69d) will **decrease** coverage by `0.14%`.
> The diff coverage is `100.00%`.

[![Impacted file tree graph](https://codecov.io/gh/projectmesa/mesa/pull/1116/graphs/tree.svg?width=650&height=150&src=pr&token=OUHxz83iDi&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa)](https://codecov.io/gh/projectmesa/mesa/pull/1116?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa)

```diff
@@            Coverage Diff             @@
##             main    #1116      +/-   ##
==========================================
- Coverage   89.46%   89.32%   -0.15%     
==========================================
  Files          19       19              
  Lines        1253     1255       +2     
  Branches      256      253       -3     
==========================================
  Hits         1121     1121              
- Misses         97       98       +1     
- Partials       35       36       +1     
```


| [Impacted Files](https://codecov.io/gh/projectmesa/mesa/pull/1116?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa) | Coverage Δ | |
|---|---|---|
| [mesa/space.py](https://codecov.io/gh/projectmesa/mesa/pull/1116/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa#diff-bWVzYS9zcGFjZS5weQ==) | `96.04% <100.00%> (+0.13%)` | :arrow_up: |
| [mesa/visualization/UserParam.py](https://codecov.io/gh/projectmesa/mesa/pull/1116/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa#diff-bWVzYS92aXN1YWxpemF0aW9uL1VzZXJQYXJhbS5weQ==) | `86.00% <0.00%> (-0.80%)` | :arrow_down: |
| [mesa/batchrunner.py](https://codecov.io/gh/projectmesa/mesa/pull/1116/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa#diff-bWVzYS9iYXRjaHJ1bm5lci5weQ==) | `91.53% <0.00%> (-0.68%)` | :arrow_down: |
| [mesa/main.py](https://codecov.io/gh/projectmesa/mesa/pull/1116/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa#diff-bWVzYS9tYWluLnB5) | `96.00% <0.00%> (-0.43%)` | :arrow_down: |
| [mesa/visualization/ModularVisualization.py](https://codecov.io/gh/projectmesa/mesa/pull/1116/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa#diff-bWVzYS92aXN1YWxpemF0aW9uL01vZHVsYXJWaXN1YWxpemF0aW9uLnB5) | `75.20% <0.00%> (-0.41%)` | :arrow_down: |
| [mesa/datacollection.py](https://codecov.io/gh/projectmesa/mesa/pull/1116/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa#diff-bWVzYS9kYXRhY29sbGVjdGlvbi5weQ==) | `97.67% <0.00%> (-0.03%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/projectmesa/mesa/pull/1116?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/projectmesa/mesa/pull/1116?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa). Last update [246c69d...919a4cd](https://codecov.io/gh/projectmesa/mesa/pull/1116?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa).

rht: @tpike3 I have made sure that the logical diff of this PR is as small as possible, and so this PR is ready for review. This means that `self.empties` is still present. But this PR still improves the speed of `move_to_empty`.
See
![benchmark](https://user-images.githubusercontent.com/395821/149741064-ba077641-d78b-4f03-9f6a-ab6bfd8073dc.png)

rht: I had to modify the test because the `move_to_empty` requires the total number of agents in order to compute the threshold. This requires access to the `model` object. Some of the the mock agents don't have `model` object attached to them.

I checked Agents.jl's implementation, and it operates on the model directly (https://github.com/JuliaDynamics/Agents.jl/pull/541/files#diff-007fa315900dda19e79dff8b7fe546cd50232c4faf79c5551ca37fa9fc9d1f3bR85), and so a grid is never independent of a model.
rht: If we choose to always require a grid object to be tied to a model, this PR will become simpler.
The only drawback is that the grid & agents are no longer standalone, and so we sacrifice modularity.

I'm not aware of projects that use Mesa's grid & its `move_to_empty` without using Mesa's model and scheduler.
Thoughts?
tpike3: Boy, I had to really chew on this one. 

I agree I have never seen a model that uses Mesa's grid & its move_to_empty without using Mesa's model and scheduler. So I am confident with backwards compatibility we are fine there.

I am hesitant to reduce the modularity by always having a grid, the seminal zero intelligence traders does not need one and I have done SIR models just on a network. In general, I think being able to use a network abstraction without a physical location is a useful option. So, I am in favor of keeping it modular. 

So @jackiekazil thoughts?  This LGTM if you agree and want to merge.     
rht: There are 2 directions of dependency here:
- a grid that depends on a model.
- a model that depends on a grid. While I read that Agents.jl has the `random_empty` requiring a model (with a discrete space) as an argument, they can totally have a model without physical location, too.

Patch:
diff --git a/.github/workflows/python.yml b/.github/workflows/python.yml
index 6ed533ac..a5e9c8d5 100644
--- a/.github/workflows/python.yml
+++ b/.github/workflows/python.yml
@@ -42,8 +42,9 @@ jobs:
       run: pip install .[dev]
     - name: Test with pytest
       run: pytest --cov=mesa tests/ --cov-report=xml
-    - name: Codecov
-      uses: codecov/codecov-action@v1.0.15
+    - if: matrix.os == 'ubuntu'
+      name: Codecov
+      uses: codecov/codecov-action@v2
 
   lint-flake:
     runs-on: ubuntu-latest
diff --git a/.pre-commit-config.yaml b/.pre-commit-config.yaml
index 7a99e40a..9366459b 100644
--- a/.pre-commit-config.yaml
+++ b/.pre-commit-config.yaml
@@ -1,6 +1,6 @@
 repos:
 -   repo: https://github.com/ambv/black
-    rev: stable
+    rev: 21.12b0
     hooks:
     - id: black
       exclude: mesa/cookiecutter-mesa/*
diff --git a/README.rst b/README.rst
index dd2c581a..2dbc6604 100644
--- a/README.rst
+++ b/README.rst
@@ -54,7 +54,7 @@ Or any other (development) branch on this repo or your own fork:
 
 .. code-block:: bash
 
-    $ pip install -e git+https://github.com/YOUR_FORK/mesa@YOUR_BRANCH
+    $ pip install -e git+https://github.com/YOUR_FORK/mesa@YOUR_BRANCH#egg=mesa
 
 Take a look at the `examples <https://github.com/projectmesa/mesa/tree/main/examples>`_ folder for sample models demonstrating Mesa features.
 
diff --git a/docs/tutorials/intro_tutorial.ipynb b/docs/tutorials/intro_tutorial.ipynb
index ada51204..5e32142d 100644
--- a/docs/tutorials/intro_tutorial.ipynb
+++ b/docs/tutorials/intro_tutorial.ipynb
@@ -229,9 +229,7 @@
   },
   {
    "cell_type": "markdown",
-   "metadata": {
-    "collapsed": true
-   },
+   "metadata": {},
    "source": [
     "### Agent Step\n",
     "\n",
@@ -1046,11 +1044,11 @@
     "A dictionary containing all the parameters of the model class and desired values to use for the batch run as key-value pairs. Each value can either be fixed ( e.g. `{\"height\": 10, \"width\": 10}`) or an iterable (e.g. `{\"N\": range(10, 500, 10)}`). `batch_run` will then generate all possible parameter combinations based on this dictionary and run the model `iterations` times for each combination.\n",
     "<br/><br/>\n",
     "\n",
-    "* `nr_processes`\n",
+    "* `number_processes`\n",
     "<br/><br/>\n",
     "Number of processors used to run the sweep in parallel. Optional. If not specified, defaults to use all the available processors.\n",
     "<br/><br/>\n",
-    "Note: Multiprocessing does make debugging challenging. If your parameter sweeps are resulting in unexpected errors set `nr_processes = 1`.\n",
+    "Note: Multiprocessing does make debugging challenging. If your parameter sweeps are resulting in unexpected errors set `number_processes = 1`.\n",
     "<br/><br/>\n",
     "\n",
     "* `iterations`\n",
@@ -1117,7 +1115,7 @@
     "    parameters=params,\n",
     "    iterations=5,\n",
     "    max_steps=100,\n",
-    "    nr_processes=None,\n",
+    "    number_processes=None,\n",
     "    data_collection_period=1,\n",
     "    display_progress=True,\n",
     ")"
@@ -1328,7 +1326,7 @@
  "metadata": {
   "anaconda-cloud": {},
   "kernelspec": {
-   "display_name": "Python 3",
+   "display_name": "Python 3 (ipykernel)",
    "language": "python",
    "name": "python3"
   },
@@ -1342,7 +1340,7 @@
    "name": "python",
    "nbconvert_exporter": "python",
    "pygments_lexer": "ipython3",
-   "version": "3.7.12"
+   "version": "3.9.6"
   },
   "widgets": {
    "state": {},
@@ -1350,5 +1348,5 @@
   }
  },
  "nbformat": 4,
- "nbformat_minor": 1
+ "nbformat_minor": 4
 }
diff --git a/docs/tutorials/intro_tutorial.rst b/docs/tutorials/intro_tutorial.rst
index ca3cdf7b..967a0dd6 100644
--- a/docs/tutorials/intro_tutorial.rst
+++ b/docs/tutorials/intro_tutorial.rst
@@ -919,13 +919,13 @@ We call ``batch_run`` with the following arguments:
   will then generate all possible parameter combinations based on this
   dictionary and run the model ``iterations`` times for each combination.
 
-* ``nr_processes``
+* ``number_processes``
 
   Number of processors used to run the sweep in parallel. Optional.
   If not specified, defaults to use all the available processors.
 
   Note: Multiprocessing does make debugging challenging. If your
-  parameter sweeps are resulting in unexpected errors set ``nr_processes = 1``.
+  parameter sweeps are resulting in unexpected errors set ``number_processes = 1``.
 
 * ``iterations``
 
@@ -980,7 +980,7 @@ iteration).
         parameters=params,
         iterations=5,
         max_steps=100,
-        nr_processes=None,
+        number_processes=None,
         data_collection_period=1,
         display_progress=True,
     )
diff --git a/mesa/batchrunner.py b/mesa/batchrunner.py
index 9178f0d1..4b19c47e 100644
--- a/mesa/batchrunner.py
+++ b/mesa/batchrunner.py
@@ -12,6 +12,7 @@ from collections import OrderedDict
 from functools import partial
 from itertools import count, product
 from multiprocessing import Pool, cpu_count
+from warnings import warn
 from typing import (
     Any,
     Counter,
@@ -34,7 +35,7 @@ from mesa.model import Model
 def batch_run(
     model_cls: Type[Model],
     parameters: Mapping[str, Union[Any, Iterable[Any]]],
-    nr_processes: Optional[int] = None,
+    number_processes: Optional[int] = None,
     iterations: int = 1,
     data_collection_period: int = -1,
     max_steps: int = 1000,
@@ -48,7 +49,7 @@ def batch_run(
         The model class to batch-run
     parameters : Mapping[str, Union[Any, Iterable[Any]]],
         Dictionary with model parameters over which to run the model. You can either pass single values or iterables.
-    nr_processes : int, optional
+    number_processes : int, optional
         Number of processes used. Set to None (default) to use all available processors
     iterations : int, optional
         Number of iterations for each parameter combination, by default 1
@@ -79,7 +80,7 @@ def batch_run(
     results: List[Dict[str, Any]] = []
 
     with tqdm(total_iterations, disable=not display_progress) as pbar:
-        if nr_processes == 1:
+        if number_processes == 1:
             for iteration in range(iterations):
                 for kwargs in kwargs_list:
                     _, rawdata = process_func(kwargs)
@@ -94,7 +95,7 @@ def batch_run(
 
         else:
             iteration_counter: Counter[Tuple[Any, ...]] = Counter()
-            with Pool(nr_processes) as p:
+            with Pool(number_processes) as p:
                 for paramValues, rawdata in p.imap_unordered(process_func, kwargs_list):
                     iteration_counter[paramValues] += 1
                     iteration = iteration_counter[paramValues]
@@ -525,7 +526,8 @@ class ParameterSampler:
 
 
 class BatchRunner(FixedBatchRunner):
-    """This class is instantiated with a model class, and model parameters
+    """DEPRECATION WARNING: BatchRunner Class has been replaced batch_run function
+    This class is instantiated with a model class, and model parameters
     associated with one or more values. It is also instantiated with model and
     agent-level reporters, dictionaries mapping a variable name to a function
     which collects some data from the model or its agents at the end of the run
@@ -579,6 +581,11 @@ class BatchRunner(FixedBatchRunner):
             display_progress: Display progress bar with time estimation?
 
         """
+        warn(
+            "BatchRunner class has been replaced by batch_run function. Please see documentation.",
+            DeprecationWarning,
+            2,
+        )
         if variable_parameters is None:
             super().__init__(
                 model_cls,
@@ -604,7 +611,8 @@ class BatchRunner(FixedBatchRunner):
 
 
 class BatchRunnerMP(BatchRunner):
-    """Child class of BatchRunner, extended with multiprocessing support."""
+    """DEPRECATION WARNING: BatchRunner class has been replaced by batch_run
+    Child class of BatchRunner, extended with multiprocessing support."""
 
     def __init__(self, model_cls, nr_processes=None, **kwargs):
         """Create a new BatchRunnerMP for a given model with the given
@@ -616,6 +624,11 @@ class BatchRunnerMP(BatchRunner):
                       should start, all running in parallel.
         kwargs: the kwargs required for the parent BatchRunner class
         """
+        warn(
+            "BatchRunnerMP class has been replaced by batch_run function. Please see documentation.",
+            DeprecationWarning,
+            2,
+        )
         if nr_processes is None:
             # identify the number of processors available on users machine
             available_processors = cpu_count()
diff --git a/mesa/space.py b/mesa/space.py
index 873fa4cc..249904c2 100644
--- a/mesa/space.py
+++ b/mesa/space.py
@@ -39,6 +39,12 @@ GridContent = Union[Optional[Agent], Set[Agent]]
 FloatCoordinate = Union[Tuple[float, float], np.ndarray]
 
 
+def clamp(x: float, lowest: float, highest: float) -> float:
+    # This should be faster than np.clip for a scalar x.
+    # TODO: measure how much faster this function is.
+    return max(lowest, min(x, highest))
+
+
 def accept_tuple_argument(wrapped_function):
     """Decorator to allow grid methods that take a list of (x, y) coord tuples
     to also handle a single position, by automatically wrapping tuple in
@@ -410,12 +416,46 @@ class Grid:
         x, y = pos
         return self.grid[x][y] == self.default_val()
 
-    def move_to_empty(self, agent: Agent) -> None:
+    def move_to_empty(
+        self, agent: Agent, cutoff: float = 0.998, num_agents: Optional[int] = None
+    ) -> None:
         """Moves agent to a random empty cell, vacating agent's old cell."""
         pos = agent.pos
         if len(self.empties) == 0:
             raise Exception("ERROR: No empty cells")
-        new_pos = agent.random.choice(sorted(self.empties))
+        if num_agents is None:
+            try:
+                num_agents = agent.model.schedule.get_agent_count()
+            except AttributeError:
+                raise Exception(
+                    "Your agent is not attached to a model, and so Mesa is unable\n"
+                    "to figure out the total number of agents you have created.\n"
+                    "This number is required in order to calculate the threshold\n"
+                    "for using a much faster algorithm to find an empty cell.\n"
+                    "In this case, you must specify `num_agents`."
+                )
+        new_pos = (0, 0)  # Initialize it with a starting value.
+        # This method is based on Agents.jl's random_empty() implementation.
+        # See https://github.com/JuliaDynamics/Agents.jl/pull/541.
+        # For the discussion, see
+        # https://github.com/projectmesa/mesa/issues/1052.
+        # This switch assumes the worst case (for this algorithm) of one
+        # agent per position, which is not true in general but is appropriate
+        # here.
+        if clamp(num_agents / (self.width * self.height), 0.0, 1.0) < cutoff:
+            # The default cutoff value provided is the break-even comparison
+            # with the time taken in the else branching point.
+            # The number is measured to be 0.998 in Agents.jl, but since Mesa
+            # run under different environment, the number is different here.
+            while True:
+                new_pos = (
+                    agent.random.randrange(self.width),
+                    agent.random.randrange(self.height),
+                )
+                if self.is_cell_empty(new_pos):
+                    break
+        else:
+            new_pos = agent.random.choice(sorted(self.empties))
         self._place_agent(new_pos, agent)
         agent.pos = new_pos
         self._remove_agent(pos, agent)


Test patch:
diff --git a/tests/test_batch_run.py b/tests/test_batch_run.py
index 7d24e88f..072b1dae 100644
--- a/tests/test_batch_run.py
+++ b/tests/test_batch_run.py
@@ -141,4 +141,4 @@ def test_batch_run_no_agent_reporters():
 
 
 def test_batch_run_single_core():
-    batch_run(MockModel, {}, nr_processes=1, iterations=10)
+    batch_run(MockModel, {}, number_processes=1, iterations=10)
diff --git a/tests/test_grid.py b/tests/test_grid.py
index 636281f1..91bdf4b3 100644
--- a/tests/test_grid.py
+++ b/tests/test_grid.py
@@ -229,6 +229,7 @@ class TestSingleGrid(unittest.TestCase):
                 a = MockAgent(counter, None)
                 self.agents.append(a)
                 self.grid.place_agent(a, (x, y))
+        self.num_agents = len(self.agents)
 
     def test_enforcement(self):
         """
@@ -242,11 +243,14 @@ class TestSingleGrid(unittest.TestCase):
 
         # Place the agent in an empty cell
         self.grid.position_agent(a)
+        self.num_agents += 1
         # Test whether after placing, the empty cells are reduced by 1
         assert a.pos not in self.grid.empties
         assert len(self.grid.empties) == 8
         for i in range(10):
-            self.grid.move_to_empty(a)
+            # Since the agents and the grid are not associated with a model, we
+            # must explicitly tell move_to_empty the number of agents.
+            self.grid.move_to_empty(a, num_agents=self.num_agents)
         assert len(self.grid.empties) == 8
 
         # Place agents until the grid is full
@@ -254,13 +258,14 @@ class TestSingleGrid(unittest.TestCase):
         for i in range(empty_cells):
             a = MockAgent(101 + i, None)
             self.grid.position_agent(a)
+            self.num_agents += 1
         assert len(self.grid.empties) == 0
 
         a = MockAgent(110, None)
         with self.assertRaises(Exception):
             self.grid.position_agent(a)
         with self.assertRaises(Exception):
-            self.move_to_empty(self.agents[0])
+            self.move_to_empty(self.agents[0], num_agents=self.num_agents)
 
 
 # Number of agents at each position for testing