Notes on in Radius - NetLogo/NetLogo GitHub Wiki

This page has been updated to describe early-2018 improvements to in-radius and in-cone at a high level.

This page also contains some mid-2017 notes, starting here, on how we might optimize in-radius. Most of the details on here also apply to in-cone, but in slightly modified form.

We implemented an improvement that gets patches via System.arraycopy instead of the relatively slow getPatchAtOffsets. In order for System.arraycopy to work, it needs to know which contiguous blocks of patches to copy. Therefore a key part of this implementation was to implement getRegion in Topology, which organizes the patches' indices in a concise contiguous manner. To streamline this implementation, InRadiusOrCone was also converted to scala. A significant improvement was also implemented within in-cone, by filtering out (sometimes many) world offsets with a single check.

getRegion's task is to group patch indices as ranges for System.arraycopy to use. It does this by considering four cases for each row:

1. the row of patches is contiguous -> it does not wrap.
2. the row of patches wraps in both directions -> the entire row must be included.
3. the row of patches wraps in the negative direction -> there are two contiguous pieces with the wrapped piece second.
4. the row of patches wraps in the positive direction -> there are two contiguous pieces, with the wrapped piece first.

These conditions are taken and ranges of indices are created for each case. As they are created, they are added to a list of all ranges. If an added range is adjacent/contiguous with the previous range added, they can be merged with the previous range. Ranges are stored as a (Int, Int), where the first Int represents the starting index, and the second Int represents the last index plus one. To further show how getRegion works, an example follows. Note that patches are stored in a 2D arrangement where the top left patch has the indices (0,0).

State:

resize-world 0 4 0 4
__change-topology true true

Call:

getRegion(initialX = 0, initialY = 0, initialR = 1)

Result:

■ ■ □ □ ■  
■ ■ □ □ ■  
□ □ □ □ □  
□ □ □ □ □    
■ ■ □ □ ■  

where the boxes are patches, and the black boxes are the patches that need to be retrieved. In this case, getRegion starts by identifying that this is case 3 for the columns, and case 3 for each row, and creates a list of ranges, merging on any add if necessary:

| Row Processed |                  Result                  |  
|:-------------:|:----------------------------------------:|  
|       0       | [(0,2), (4,5)]                           |  
|       1       | [(0,2), (4,7), (9,10)]                   |  <-- (5,7) gets merged with (4,5) when it is added.
|       4       | [(0,2), (4,7), (9,10), (20,22), (24,25)] |   

The final returned list [(0,2), (4,7), (9,10), (20,22), (24,25)] is as contiguous as possible.

Recall that inCone works by calculating if agents are within a cone. It takes into account wrapping by creating "world offsets" and checking if agents in the offset worlds are within the cone. Previously, all world offsets within a given radius were tried. Now, a simple filter is applied that checks if any part of a world offset is within the radius. If no part of a world offset is within the radius, then there is no point in checking if an agent in that world offset is within the cone. This can be done trivially by checking if the nearest point on the edge of the world offset is within the radius. closestPointIsInRadius performs this check and is now used in inCone to filter out world offsets. Below is a quick illustration.

Previously, given the world marked with X and a radius of 1, there are 8 world offsets around the world that are tested:

 ___ ___ ___
|   |   |   |
 --- --- ---
|   | X |   |
 --- --- ---
|   |   |   |
 ¯¯¯ ¯¯¯ ¯¯¯

Now, the points marked with • determine whether the world offset they are a part of can be filtered out based on whether that point is within the radius of the original agent:

 ___ ___ ___
|   |   |   |
 ---•-•-•---
|   • X •   |
 ---•-•-•---
|   |   |   |
 ¯¯¯ ¯¯¯ ¯¯¯

For example, if the original agent is very close to the top-right corner of world X, it is likely that the left and bottom • points are not within its radius, and many world offsets can be filtered out (F represents world offsets that are filtered out):

 ___ ___ ___
| F |   |   |
 ---•-•-•---
| F • X •   |
 ---•-•-•---
| F | F | F |
 ¯¯¯ ¯¯¯ ¯¯¯

This results in significant computational savings in most cases.

Using getRegion and System.arraycopy achieved significant improvements in the case of larger radii (r > 2), but left smaller radii cases slightly slower than previous implementations due to the overhead introduced by getRegion. We managed to improve these cases by special casing radius 1 and 2 by taking advantage of getNeighbors caching. See setPatches1 and setPatches2. These functions never call getRegion, so the implementation discussed previously that uses System.arraycopy is not used for these small radii.

The following preliminary NetLogo benchmark was used to compare performance between the old and new implementations:

extensions [ profiler cf ]
globals [ profiler-agent-set profiler-reporter profiler-result]
turtles-own [ near-me ]

to setup
  random-seed 0
  clear-all
  create-turtles 100 [ setxy random-xcor random-ycor ]
  reset-ticks
end

to go
  move-turtles
  tick
end

to move-turtles
  ask turtles [
    right (count turtles in-cone ((random (max-pxcor - min-pxcor)) + 1) ((random 360) + 1)) * 25
    forward (count turtles in-radius (random (max-pxcor - min-pxcor)) + 1)
  ]
end

to profile-basic
  setup
  repeat 200 [ go ]
  profiler:start
  repeat 1000 [ go ]
  profiler:stop
  print profiler:report
  profiler:reset
end

to profile-go [ agents ]
  ask agents [ set near-me (run-result profiler-reporter radius-size) ]
end

to profile
  random-seed 0
  clear-all
  reset-ticks

  set profiler-agent-set
  cf:select
  cf:case [agent = "patch"] [patches]
  cf:else [turtles]

  let radius-reporter [ [x] -> profiler-agent-set in-radius x ]
  let cone-reporter [ [x] -> profiler-agent-set in-cone x 60 ]

  set profiler-reporter
  cf:select
  cf:case [ function = "radius" ] [ radius-reporter ]
  cf:else [ cone-reporter ]

  let nturtles
  cf:select
  cf:case [ turtle-density = "sparse" ] [ count patches / 3 ]
  cf:case [ turtle-density = "average" ] [ count patches ]
  cf:else [ count patches * 4 ]

  create-turtles nturtles [ setxy random-xcor random-ycor ]

  let agents (n-of (count patches / 10) turtles)
  repeat 200 [ profile-go agents ]
  profiler:start
  repeat 1000 [ profile-go agents ]
  profiler:stop
  set profiler-result (profiler:inclusive-time "profile-go") / (profiler:calls "profile-go")
  profiler:reset
  stop

end

This was run as a BehaviorSpace Experiment with the following parameters:

Variables:

["turtle-density" "sparse" "average" "dense"]
["radius-size" 1 2 3 4 5]
["function" "radius" "cone"]
["agent" "patch" "turtle"]

Repetitions: 5
Run combinations in sequential order: Unchecked
Measure runs using these reporters: profiler-result
Measure runs at every step: Checked
Setup commands: profile
Go commands: None
Stop condition: true
Time limit: 0

The results on hexy (6.0.2) were:

|   hexy   | "radius"    |             |             | "cone"      |             |             |
|          | "average"   | "dense"     | "sparse"    | "average"   | "dense"     | "sparse"    |
|----------|-------------|-------------|-------------|-------------|-------------|-------------|
| "patch"  |             |             |             |             |             |             |
| 1        | 0.42356578  | 0.415211964 | 0.447924489 | 0.643343218 | 0.653342778 | 0.658662075 |
| 2        | 0.765174188 | 0.755083149 | 0.798701274 | 1.619584988 | 1.609069376 | 1.63029553  |
| 3        | 1.349323757 | 1.423747792 | 1.431566501 | 3.048253953 | 3.087273826 | 3.073600844 |
| 4        | 2.099994937 | 2.147415704 | 2.209340976 | 5.088709769 | 5.070102749 | 5.04299285  |
| 5        | 3.144040517 | 3.175777021 | 3.12565473  | 7.597543335 | 7.628076702 | 7.540777485 |
| "turtle" |             |             |             |             |             |             |
| 1        | 0.479421554 | 0.935529033 | 0.369713571 | 0.794886621 | 2.381225315 | 0.464317636 |
| 2        | 1.073975247 | 2.392927506 | 0.740152201 | 1.962893479 | 6.410227509 | 0.971958586 |
| 3        | 2.044676106 | 4.894963461 | 1.32739544  | 3.715223945 | 12.40143037 | 1.722480897 |
| 4        | 3.231826062 | 7.521266154 | 2.149901187 | 5.753639775 | 18.72294019 | 2.668533445 |
| 5        | 4.694879076 | 10.86470665 | 3.121346507 | 8.304177011 | 26.87364897 | 3.948171305 |

And for our new InRadiusOrCone.scala implementation:

|   New    | "radius"    |             |             | "cone"      |             |             |
|          | "average"   | "dense"     | "sparse"    | "average"   | "dense"     | "sparse"    |
|----------|-------------|-------------|-------------|-------------|-------------|-------------|
| "patch"  |             |             |             |             |             |             |
| 1        | 0.289079671 | 0.275225819 | 0.276215298 | 0.274820714 | 0.313149421 | 0.281473333 |
| 2        | 0.545929921 | 0.544369947 | 0.653777005 | 0.811499492 | 0.783968303 | 0.770931155 |
| 3        | 1.230538925 | 1.238099073 | 1.258571036 | 1.583966713 | 1.584773997 | 1.59336633  |
| 4        | 1.752392825 | 1.802672396 | 1.775644464 | 2.419219188 | 2.448583919 | 2.546160449 |
| 5        | 2.450282659 | 2.396128118 | 2.393427568 | 3.669244181 | 3.703793228 | 3.704711838 |
| "turtle" |             |             |             |             |             |             |
| 1        | 0.281424219 | 0.678918119 | 0.201757588 | 0.393713016 | 1.009525492 | 0.291293826 |
| 2        | 0.707423928 | 1.952373726 | 0.430213617 | 1.114570949 | 2.988804263 | 0.620638501 |
| 3        | 1.377638427 | 3.979828554 | 0.802219568 | 1.949493884 | 5.896653957 | 1.04611047  |
| 4        | 2.064942684 | 5.98387757  | 1.173704629 | 3.050284819 | 9.233598343 | 1.575043888 |
| 5        | 2.925055705 | 7.868025705 | 1.566913489 | 4.365741384 | 13.35471968 | 2.181650227 |

Finally, a table with the percent increase in speed from old to new (-(new-old)/old):

|% increase| "radius"  |         |          | "cone"    |         |          |
|          | "average" | "dense" | "sparse" | "average" | "dense" | "sparse" |
|----------|-----------|---------|----------|-----------|---------|----------|
| "patch"  |           |         |          |           |         |          |
| 1        | 31.75%    | 33.71%  | 38.33%   | 57.28%    | 52.07%  | 57.27%   |
| 2        | 28.65%    | 27.91%  | 18.14%   | 49.89%    | 51.28%  | 52.71%   |
| 3        | 8.80%     | 13.04%  | 12.08%   | 48.04%    | 48.67%  | 48.16%   |
| 4        | 16.55%    | 16.05%  | 19.63%   | 52.46%    | 51.71%  | 49.51%   |
| 5        | 22.07%    | 24.55%  | 23.43%   | 51.70%    | 51.45%  | 50.87%   |
| "turtle" |           |         |          |           |         |          |
| 1        | 41.30%    | 27.43%  | 45.43%   | 50.47%    | 57.60%  | 37.26%   |
| 2        | 34.13%    | 18.41%  | 41.87%   | 43.22%    | 53.37%  | 36.15%   |
| 3        | 32.62%    | 18.70%  | 39.56%   | 47.53%    | 52.45%  | 39.27%   |
| 4        | 36.11%    | 20.44%  | 45.41%   | 46.99%    | 50.68%  | 40.98%   |
| 5        | 37.70%    | 27.58%  | 49.80%   | 47.43%    | 50.31%  | 44.74%   |

As the radius increases past 5, the speed improvements increase exponentially for in-radius.

Ignoring details about world-wrapping, the in-radius algorithm follows roughly the following outline

def agentset inRadius(startX, startY, sourceSet, radius) =
  LET resultSet be an empty agentset
  FOR each column of patches with x > radius - startX AND x < radius + startX
    FOR each patch in column with y > radius - startY AND y < radius + startY
      IF sourceSet is patch set
        IF patch is within distance radius of startX and startY AND (sourceSet is set of all patches OR sourceSet contains patch)
          ADD patch to resultSet
        END IF
      ELSE
        FOR each turtle on patch
          IF turtle is within distance radius of startX and startY AND (
            sourceSet is set of all turtles OR
            sourceSet is a breeded set and equal to the breed of turtle OR
            sourceSet contains turtle)
            ADD turtle to resultSet
          END IF
        END FOR 
      END IF
    END FOR
  END FOR
  RETURN resultSet

Prior to 6.0.1, the check sourceSet contains patch/turtle were implemented by looking through each agent in sourceSet to determine whether it contained patch/turtle. This was obviously inefficient. Starting with 6.0.1 this check was replaced by computing a hash set of the agent IDs of all agents in sourceSet and comparing that to the id of each patch/turtle as it was checked, turning a linear-time check into a constant-time check.

For the below formulae, the following are used as variables:

• r - radius
• #s - count of all agents in the source set
• #t - count of all turtles within radius

The following are treated as constants:

• D - the time taken to compute the distance from the center of the in-radius to a given agent
• P - the time to fetch a single patch
• I - the cost to insert an agent ID into a hash set
• C - the cost to determine whether an agent ID is in the hash set
• Z - the average cost per-agent of iterating through a set to determine whether it contains a specific agent, assuming that an agent has an equal chance of being included or not included.

We can express the speed of in-radius with the following

• in-radius of all patches: (2r)^2*(P + D)
• in-radius of all turtles: (2r)^2*P + #t*D
• in-radius of a breeded turtleset is approximately the same as in-radius of all turtles
• in-radius of a non-breeded patchset (6.0.1): #s*I + (2r)^2*(P + D + C)
• in-radius of a non-breeded turtleset (6.0.1): #s*I + (2r)^2*P + #t*(D + C)
• in-radius of a non-breeded patcheset (6.0 and earlier): (2r)^2*(P + D + #s*Z)
• in-radius of a non-breeded turtleset (6.0 and earlier): (2r)^2*P + #t*(D + #s*Z)

The following are relative measures of the constants circa the 6.0.1 release. Note that these reflect living code and it is possible (even likely) that they will change as the code evolves. These are not absolute terms and should only be used for comparison with each other.

Patch retrieval is extremely slow in the current implementation - it takes more time to retrieve a patch from the world than it does to compute the distance between said patch and the starting point. This is because patch retrieval is done using relative offsets and the topology is forced to recompute the location for each patch retrieval. Theoretically, it should be possible to retrieve patches using only radius + 2 array-copies from the world's patch array. Even if we can't hit the theoretical maximum, we could compute the total set of patches from the topology only once and then retrieve all of them in a single go instead of repeatedly recomputing. Optimizing this is the subject of #1318. This could be done in a minor release.

One alternative to the current implementation is simply to perform the radius calculation on each agent in the sourceSet. This tends to be faster in many cases, especially when the world is densely packed and the sourceSet is small compared to the total number of turtles. This fix was considered for 6.0.1 but later dropped because it would affect the random order that agents are returned in on later operations (we try to preserve this order between minor releases and only break it in major releases).