The goal of this PR is primarily to optimize the LayeredSpatialMap.GetItemsAt method. Currently, it uses nested foreach loops (the inner IEnumerable potentially being implemented with yield return, which results in a good bit of allocation overhead.
This is not ideal because spatial map functions such as this are often used very frequently; the primary purpose of a spatial map is to be able to quickly retrieve the objects at a specific location. This makes a large amount of allocation particularly harmful for these functions.
This PR aims to change that by implementing a custom enumerator which can function with any IReadOnlyLayeredSpatialMap optimization. It provides better performance in the following ways:
It is a struct, so when returned directly from a function and used in a foreach loop, it won't entail any boxing and won't create memory the GC has to worry about reference counting
It takes advantage of the concept that, primarily, MultiSpatialMap and SpatialMap are the types used for the layers of a layered spatial map. Both of these types now provide custom GetItemsAt functions that are much faster than using IEnumerable, and spatial map guarantees only one item at max could exist at a location so an iterator isn't even necessary.
The enumerator code is somewhat complex due to the second point. All of the iterators for all spatial maps implement IEnumerator<T>, so we could just record an IEnumerator for the current layer in our iterator; but that is slower than it needs to be since storing it as an interface would box the iterator. Therefore, this implementation elects to have one field for each potential iterator type. Only if the type of the layer isn't MultiSpatialMap or SpatialMap will it resort to using IEnumerator.
This optimization is noticable; the benchmarks contain GetItemsAtCustomEnumeratorInterface, which is identical to the custom iterator GetItemsAt now uses except for it stores the enumerator for the current layer as IEnumerable, and the difference can be noticed as non-trivial in the results.
The PR also adds a custom iterator for SpatialMap which would be used whenever a user iterates over a spatial map stored as a reference of type SpatialMap or AdvancedSpatialMap. If a user knows they have one of those two types, they will likely just want to use GetItem or one of its variants; however, this still provides some benefit to the generic-case IReadOnlySpatialMap.GetItemsAt, since the custom enumerator is a bit better than yield return.
Changes
LayeredSpatialMap.GetItemsAt now uses a custom enumerator (completes #122)
SpatialMap.GetItemsAt now uses custom iterator
Benchmarks
The following benchmarks the new LayeredSpatialMap.GetItemsAt implementation against some other possible implementations:
Method
NumEntities
NumLayers
Mean
Error
StdDev
GetItemsAt
1
1
53.98 ns
0.598 ns
0.559 ns
GetItemsAtCustomEnumerator
1
1
53.36 ns
0.761 ns
0.675 ns
GetItemsAtCustomEnumeratorInterface
1
1
53.13 ns
0.928 ns
0.823 ns
GetItemsAtYieldReturn
1
1
69.09 ns
1.399 ns
2.827 ns
GetItemsAt
1
2
77.85 ns
1.589 ns
2.227 ns
GetItemsAtCustomEnumerator
1
2
76.81 ns
0.825 ns
0.731 ns
GetItemsAtCustomEnumeratorInterface
1
2
85.08 ns
1.570 ns
1.311 ns
GetItemsAtYieldReturn
1
2
94.78 ns
1.372 ns
1.283 ns
GetItemsAt
1
3
104.27 ns
2.117 ns
3.707 ns
GetItemsAtCustomEnumerator
1
3
95.78 ns
0.658 ns
0.646 ns
GetItemsAtCustomEnumeratorInterface
1
3
112.61 ns
2.251 ns
2.927 ns
GetItemsAtYieldReturn
1
3
124.17 ns
1.431 ns
1.195 ns
GetItemsAt
10
1
52.63 ns
0.379 ns
0.316 ns
GetItemsAtCustomEnumerator
10
1
53.15 ns
0.682 ns
0.605 ns
GetItemsAtCustomEnumeratorInterface
10
1
57.16 ns
1.166 ns
1.247 ns
GetItemsAtYieldReturn
10
1
67.21 ns
1.371 ns
2.213 ns
GetItemsAt
10
2
78.27 ns
1.202 ns
1.124 ns
GetItemsAtCustomEnumerator
10
2
75.82 ns
0.670 ns
0.594 ns
GetItemsAtCustomEnumeratorInterface
10
2
93.82 ns
1.891 ns
3.777 ns
GetItemsAtYieldReturn
10
2
97.95 ns
1.925 ns
1.801 ns
GetItemsAt
10
3
102.07 ns
0.654 ns
0.510 ns
GetItemsAtCustomEnumerator
10
3
99.33 ns
0.740 ns
0.656 ns
GetItemsAtCustomEnumeratorInterface
10
3
115.42 ns
1.891 ns
1.676 ns
GetItemsAtYieldReturn
10
3
128.82 ns
2.341 ns
2.076 ns
GetItemsAt
50
1
60.23 ns
0.545 ns
0.455 ns
GetItemsAtCustomEnumerator
50
1
60.75 ns
0.133 ns
0.111 ns
GetItemsAtCustomEnumeratorInterface
50
1
62.98 ns
0.301 ns
0.252 ns
GetItemsAtYieldReturn
50
1
73.93 ns
0.982 ns
0.871 ns
GetItemsAt
50
2
88.98 ns
0.448 ns
0.397 ns
GetItemsAtCustomEnumerator
50
2
85.91 ns
0.339 ns
0.265 ns
GetItemsAtCustomEnumeratorInterface
50
2
101.05 ns
1.221 ns
0.954 ns
GetItemsAtYieldReturn
50
2
118.33 ns
1.845 ns
1.726 ns
GetItemsAt
50
3
115.74 ns
0.597 ns
0.558 ns
GetItemsAtCustomEnumerator
50
3
113.39 ns
0.629 ns
0.589 ns
GetItemsAtCustomEnumeratorInterface
50
3
144.37 ns
1.435 ns
1.342 ns
GetItemsAtYieldReturn
50
3
163.52 ns
0.533 ns
0.416 ns
GetItemsAt
100
1
60.15 ns
0.303 ns
0.253 ns
GetItemsAtCustomEnumerator
100
1
60.63 ns
0.528 ns
0.468 ns
GetItemsAtCustomEnumeratorInterface
100
1
63.63 ns
0.386 ns
0.322 ns
GetItemsAtYieldReturn
100
1
73.57 ns
1.014 ns
0.899 ns
GetItemsAt
100
2
88.62 ns
0.821 ns
0.728 ns
GetItemsAtCustomEnumerator
100
2
87.57 ns
0.715 ns
0.669 ns
GetItemsAtCustomEnumeratorInterface
100
2
106.69 ns
0.225 ns
0.200 ns
GetItemsAtYieldReturn
100
2
119.44 ns
2.421 ns
2.377 ns
GetItemsAt
100
3
114.59 ns
0.768 ns
0.681 ns
GetItemsAtCustomEnumerator
100
3
113.57 ns
0.435 ns
0.385 ns
GetItemsAtCustomEnumeratorInterface
100
3
143.12 ns
0.891 ns
0.834 ns
GetItemsAtYieldReturn
100
3
164.85 ns
1.043 ns
0.871 ns
GetItemsAt is the current implementation of the spatial map function which returns a custom enumerator. GetItemsAtCustomEnumerator is the same thing as GetItemsAt, but implemented via the extension method we use to provide custom methods for testing (just to baseline to validate there isn't much difference).
GetItemsAtYieldReturn represents the old method of implementing GetItemsAt; the new method is clearly notably faster. More importantly, it allocates less memory, which should help avoid creating GC issues.
GetItemsAtCustomEnumeratorInterface is a custom enumerator that is implemented slightly differently (by using a single field of type IEnumerator<T>, rather than specific fields for each spatial map type. These are slower (particularly on the upper end of sizes), which shows the benefit of the cast-and-check method.
Overview
The goal of this PR is primarily to optimize the
LayeredSpatialMap.GetItemsAtmethod. Currently, it uses nested foreach loops (the innerIEnumerablepotentially being implemented withyield return, which results in a good bit of allocation overhead.This is not ideal because spatial map functions such as this are often used very frequently; the primary purpose of a spatial map is to be able to quickly retrieve the objects at a specific location. This makes a large amount of allocation particularly harmful for these functions.
This PR aims to change that by implementing a custom enumerator which can function with any
IReadOnlyLayeredSpatialMapoptimization. It provides better performance in the following ways:MultiSpatialMapandSpatialMapare the types used for the layers of a layered spatial map. Both of these types now provide customGetItemsAtfunctions that are much faster than usingIEnumerable, and spatial map guarantees only one item at max could exist at a location so an iterator isn't even necessary.The enumerator code is somewhat complex due to the second point. All of the iterators for all spatial maps implement
IEnumerator<T>, so we could just record anIEnumeratorfor the current layer in our iterator; but that is slower than it needs to be since storing it as an interface would box the iterator. Therefore, this implementation elects to have one field for each potential iterator type. Only if the type of the layer isn'tMultiSpatialMaporSpatialMapwill it resort to usingIEnumerator.This optimization is noticable; the benchmarks contain
GetItemsAtCustomEnumeratorInterface, which is identical to the custom iteratorGetItemsAtnow uses except for it stores the enumerator for the current layer asIEnumerable, and the difference can be noticed as non-trivial in the results.The PR also adds a custom iterator for
SpatialMapwhich would be used whenever a user iterates over a spatial map stored as a reference of typeSpatialMaporAdvancedSpatialMap. If a user knows they have one of those two types, they will likely just want to useGetItemor one of its variants; however, this still provides some benefit to the generic-caseIReadOnlySpatialMap.GetItemsAt, since the custom enumerator is a bit better thanyield return.Changes
LayeredSpatialMap.GetItemsAtnow uses a custom enumerator (completes #122)SpatialMap.GetItemsAtnow uses custom iteratorBenchmarks
LayeredSpatialMap.GetItemsAtimplementation against some other possible implementations:GetItemsAtis the current implementation of the spatial map function which returns a custom enumerator.GetItemsAtCustomEnumeratoris the same thing asGetItemsAt, but implemented via the extension method we use to provide custom methods for testing (just to baseline to validate there isn't much difference).GetItemsAtYieldReturnrepresents the old method of implementingGetItemsAt; the new method is clearly notably faster. More importantly, it allocates less memory, which should help avoid creating GC issues.GetItemsAtCustomEnumeratorInterfaceis a custom enumerator that is implemented slightly differently (by using a single field of typeIEnumerator<T>, rather than specific fields for each spatial map type. These are slower (particularly on the upper end of sizes), which shows the benefit of the cast-and-check method.