Repository: projectmesa/mesa
Pull request #1517 (2022-11-08 12:37:03)

Fix bug in Grid.get_neighborhood
One (hopefully last) bug was left unnoticed before merging, if a dimension is even and the radius is the maximum one possible, then we introduce duplicates in the list, consider the case of the width dimension equal to 4, and the user passes a value of 2 of radius and a x pos equal to 2 then we have a range(0, 5) but this means that we have two times the 0 position (0 % 4 and 4 % 4) . 

The way it is written now is not so good, hope to find a better way (a function for all the initial range conditions in the torus case?).

codecov[bot]: # [Codecov](https://codecov.io/gh/projectmesa/mesa/pull/1517?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa) Report
Base: **91.29**% // Head: **91.31**% // Increases project coverage by **`+0.01%`** :tada:
> Coverage data is based on head [(`636bd80`)](https://codecov.io/gh/projectmesa/mesa/pull/1517?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa) compared to base [(`b0bc381`)](https://codecov.io/gh/projectmesa/mesa/commit/b0bc381a64ea7fcf437f16a4f0a60d83e78862db?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa).
> Patch coverage: 100.00% of modified lines in pull request are covered.

<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff             @@
##             main    #1517      +/-   ##
==========================================
+ Coverage   91.29%   91.31%   +0.01%     
==========================================
  Files          15       15              
  Lines        1310     1312       +2     
  Branches      227      223       -4     
==========================================
+ Hits         1196     1198       +2     
  Misses         80       80              
  Partials       34       34              
```


| [Impacted Files](https://codecov.io/gh/projectmesa/mesa/pull/1517?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/1517/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa#diff-bWVzYS9zcGFjZS5weQ==) | `95.82% <100.00%> (+0.03%)` | :arrow_up: |
| [mesa/visualization/ModularVisualization.py](https://codecov.io/gh/projectmesa/mesa/pull/1517/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa#diff-bWVzYS92aXN1YWxpemF0aW9uL01vZHVsYXJWaXN1YWxpemF0aW9uLnB5) | `78.75% <0.00%> (-0.14%)` | :arrow_down: |

Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa)

</details>

[:umbrella: View full report at Codecov](https://codecov.io/gh/projectmesa/mesa/pull/1517?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa).   
:loudspeaker: Do you have feedback about the report comment? [Let us know in this issue](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa).

Tortar: this was left unnotices because the grid tested have only odd dimensions :-)
Tortar: It is a minimum probability situation (why does it exist?! :D) but we need to account for it
Tortar: @rht if the difference will be so minimal I will be with you, will do some testing, I feel like using lists is preferable also because of the advantages of conversion of the algorithm in other forms (Numba, Cython, (I think that lists are also more optimized in pypy)) as you already pointed out many times :-)
Tortar: Results:

- no difference for cpython
- pypy likes more lists: from 2.5 to 10 times faster than the other with dictionary with radius 10


Tortar: Added a comment explaining why it's needed to do that and modified and added tests so that also the edge case is covered
rht: > @rht if the difference will be so minimal I will be with you, will do some testing, I feel like using lists is preferable also because of the advantages of conversion of the algorithm in other forms (Numba, Cython, (I think that lists are also more optimized in pypy)) as you already pointed out many times :-)

That's true. I think we should document https://github.com/projectmesa/mesa/pull/1476#issuecomment-1304540328 in the code, and the Numba/Cython/PyPy optimization.
Tortar: I added the story about Cython/Numba/Pypy (maybe it's a bit verbose) . The comment doesn't really apply with the code we have right now. But I could link to the PR discussion maybe?
Tortar: I think that qouting https://github.com/projectmesa/mesa/pull/1476#issuecomment-1306220403 is better maybe
Corvince: Just out of interest, is the assertion that using a list will be faster rooted in some actual observations? I am really doubtful that it will be useful for mesa (the framework). 

Again, this is more for my curiosity, I think in this PR/setting it is the better choice anyways.
Corvince: But I think it is super annoying that we need this bug fix for such a corner case ;)
Tortar: My own non-authoritative observation is that arrays/vectors are easier data structures than hashmaps in C/C++, which I think has an impact on Cython and the others. For example, I compared the two algos with PyPy and it liked more the list alternative. It's difficult to find comparisons on the Internet for Cython or Numba because usually they are used for different purposes. From the point of view to the benefits to Mesa, I'm not sure actually too but anyway I like more this one than the alternative because it exploits better the topology.  But yes, surely rather annoying that we need to deal with such a special case :D
Tortar: Actually also in the faster Cpython 3.11 which I just downloaded now it is slightly favoured the way with lists (a step in the right direction? :D)
Tortar: Indeed adding 3.11 to the build Github actions I think could be good
rht: > Indeed adding 3.11 to the build Github actions I think could be good

I made #1519, but we don't have performance testing framework yet.
Corvince: Oops, sorry, I was confused by your answers and now realised that my previous comment was saying something completely different than what I had in mind.

I didn't want to discuss lists vs dicts. As you point out they serve different purposes (and in that sense the code comments notion that "lists are more optimized in PyPy than in Cpython" should maybe be removed). 

But the question I had in mind was about numba/cython providing speed-ups for mesa. I have my doubts that it does. I used numba years ago and for some calculations it provided extreme speedups, but I doubt we have many (or any) functions where it helps. But this is purely a gut feeling of mine, so I was interested if there are actual observations. I only found the small tests in https://github.com/projectmesa/mesa/pull/1492 but there numba seemed slower
Tortar: From what I observed, Numba has more overhead for function calls, which means that with small inputs can become slower than pure python, while Cython suffers less by this so it can be the optimal solution if someone has the courage to go that way :D
Tortar: I will try to come up with some small inputs benchmarks for Cython in the future
Tortar: Can I ask you @Corvince an evaluation of https://github.com/projectmesa/mesa/discussions/1513#discussioncomment-4069436, because I'd like to implement it if others are ok with it
rht: Numba/Cython can provide speedup to Mesa space module, if `Grid` internal is a blackbox without Python objects that is accessed by occasional API calls. `get_neighborhood` definitely will get a speedup with `nopython` and `nogil` (while `dict` requires GIL). `get_neighbors` should only return a list of agent IDs, because the `Grid.grid` has to be a typed array. An array of Python objects likely requires GIL. The part might be slower is if `__getitem__` is accessed multiple times from Python.
Corvince: > Numba/Cython can provide speedup to Mesa space module, if `Grid` internal is a blackbox without Python objects that is accessed by occasional API calls. `get_neighborhood` definitely will get a speedup with `nopython` and `nogil` (while `dict` requires GIL). 

See, these are those assertions I am talking about. How do you know that? I am not saying this is wrong, but is there any proof or at least indication for that?
rht: If the computation happens without GIL, and with explicit types, of course it will be fast.

Patch:
diff --git a/mesa/space.py b/mesa/space.py
index e895ba54..a0586a45 100644
--- a/mesa/space.py
+++ b/mesa/space.py
@@ -255,22 +255,37 @@ class Grid:
         if neighborhood is not None:
             return neighborhood
 
+        # We use a list instead of a dict for the neighborhood because it would
+        # be easier to port the code to Cython or Numba (for performance
+        # purpose), with minimal changes. To better understand how the
+        # algorithm was conceived, look at
+        # https://github.com/projectmesa/mesa/pull/1476#issuecomment-1306220403
+        # and the discussion in that PR in general.
         neighborhood = []
 
         x, y = pos
         if self.torus:
-            x_radius = min(radius, self.width // 2)
-            y_radius = min(radius, self.height // 2)
-
-            for dx in range(-x_radius, x_radius + 1):
-                for dy in range(-y_radius, y_radius + 1):
+            x_max_radius, y_max_radius = self.width // 2, self.height // 2
+            x_radius, y_radius = min(radius, x_max_radius), min(radius, y_max_radius)
+
+            # For each dimension, in the edge case where the radius is as big as
+            # possible and the dimension is even, we need to shrink by one the range
+            # of values, to avoid duplicates in neighborhood. For example, if
+            # the width is 4, while x, x_radius, and x_max_radius are 2, then
+            # (x + dx) has a value from 0 to 4 (inclusive), but this means that
+            # the 0 position is repeated since 0 % 4 and 4 % 4 are both 0.
+            xdim_even, ydim_even = (self.width + 1) % 2, (self.height + 1) % 2
+            kx = int(x_radius == x_max_radius and xdim_even)
+            ky = int(y_radius == y_max_radius and ydim_even)
+
+            for dx in range(-x_radius, x_radius + 1 - kx):
+                for dy in range(-y_radius, y_radius + 1 - ky):
 
                     if not moore and abs(dx) + abs(dy) > radius:
                         continue
 
                     nx, ny = (x + dx) % self.width, (y + dy) % self.height
                     neighborhood.append((nx, ny))
-
         else:
             x_range = range(max(0, x - radius), min(self.width, x + radius + 1))
             y_range = range(max(0, y - radius), min(self.height, y + radius + 1))
@@ -582,10 +597,10 @@ class MultiGrid(Grid):
     def place_agent(self, agent: Agent, pos: Coordinate) -> None:
         """Place the agent at the specified location, and set its pos variable."""
         x, y = pos
-        if agent not in self.grid[x][y]:
+        if agent.pos is None or agent not in self.grid[x][y]:
             self.grid[x][y].append(agent)
-        self.empties.discard(pos)
-        agent.pos = pos
+            agent.pos = pos
+            self.empties.discard(pos)
 
     def remove_agent(self, agent: Agent) -> None:
         """Remove the agent from the given location and set its pos attribute to None."""


Test patch:
diff --git a/tests/test_grid.py b/tests/test_grid.py
index 7a706198..007aa6c4 100644
--- a/tests/test_grid.py
+++ b/tests/test_grid.py
@@ -15,7 +15,7 @@ from mesa.space import Grid, SingleGrid, MultiGrid, HexGrid
 #   1 0 1
 #   0 0 1
 # -------------------
-TEST_GRID = [[0, 1, 0, 1, 0], [0, 0, 1, 1, 0], [1, 1, 0, 0, 0]]
+TEST_GRID = [[0, 1, 0, 1, 0, 0], [0, 0, 1, 1, 0, 1], [1, 1, 0, 0, 0, 1]]
 
 
 class MockAgent:
@@ -40,8 +40,9 @@ class TestBaseGrid(unittest.TestCase):
         """
         Create a test non-toroidal grid and populate it with Mock Agents
         """
+        # The height needs to be even to test the edge case described in PR #1517
+        height = 6  # height of grid
         width = 3  # width of grid
-        height = 5  # height of grid
         self.grid = Grid(width, height, self.torus)
         self.agents = []
         counter = 0
@@ -109,10 +110,10 @@ class TestBaseGrid(unittest.TestCase):
         assert len(neighborhood) == 8
 
         neighborhood = self.grid.get_neighborhood((1, 4), moore=False)
-        assert len(neighborhood) == 3
+        assert len(neighborhood) == 4
 
         neighborhood = self.grid.get_neighborhood((1, 4), moore=True)
-        assert len(neighborhood) == 5
+        assert len(neighborhood) == 8
 
         neighborhood = self.grid.get_neighborhood((0, 0), moore=False)
         assert len(neighborhood) == 2
@@ -127,7 +128,7 @@ class TestBaseGrid(unittest.TestCase):
         assert len(neighbors) == 3
 
         neighbors = self.grid.get_neighbors((1, 3), moore=False, radius=2)
-        assert len(neighbors) == 2
+        assert len(neighbors) == 3
 
     def test_coord_iter(self):
         ci = self.grid.coord_iter()
@@ -221,17 +222,25 @@ class TestBaseGridTorus(TestBaseGrid):
         neighborhood = self.grid.get_neighborhood((0, 0), moore=False)
         assert len(neighborhood) == 4
 
+        # here we test the edge case described in PR #1517 using a radius
+        # measuring half of the grid height
+        neighborhood = self.grid.get_neighborhood((0, 0), moore=True, radius=3)
+        assert len(neighborhood) == 17
+
+        neighborhood = self.grid.get_neighborhood((1, 1), moore=False, radius=3)
+        assert len(neighborhood) == 15
+
         neighbors = self.grid.get_neighbors((1, 4), moore=False)
-        assert len(neighbors) == 1
+        assert len(neighbors) == 2
 
         neighbors = self.grid.get_neighbors((1, 4), moore=True)
-        assert len(neighbors) == 3
+        assert len(neighbors) == 4
 
         neighbors = self.grid.get_neighbors((1, 1), moore=False, include_center=True)
         assert len(neighbors) == 3
 
         neighbors = self.grid.get_neighbors((1, 3), moore=False, radius=2)
-        assert len(neighbors) == 2
+        assert len(neighbors) == 3
 
 
 class TestSingleGrid(unittest.TestCase):