In game programming, it is very common to perform a lot of complicated calculations over and over, often many times per frame. There's nothing inherently wrong with that, but sometimes some of those calculations only need to be performed once - e.g. if, given the same parameters, you'd get exactly the same results. In cases like that, you may be served well by caching the result of the calculations rather than performing them again.
With that said, there's a lot more to caching than simply storing the results of performance-intensive calculations - it'd be a mistake (and one I've made frequently) simply to cache everything that looks like it might benefit from being cached.
So, when deciding what to cache there are two main questions to ask:
Can the code actually be cached?
Is it worth adding the overhead of populating and maintaining a cache?
When I code in Unity, I generally use two types of cache:
GetComponent<>() or Find() calls.
In Unity, it's very common to have components that reference other components - but the methods that are used to get references to them are often quite expensive performance-wise, so you don't really want to call them over and over.
As such, it's best to store the references the first time you get them, and then, in future, use the stored reference rather than calling GetComponent<>() or whatever method you used to get it.
Take, for example, the following very simple example component, which, when attached to any Unity UI GameObject, will fade it in and out repeatedly:
using UnityEngine;
public class FadeInOut : MonoBehaviour
{
private bool forwards = false;
private float index = 0;
private void Update()
{
// Get a reference to the CanvasGroup (or add one, if we don't find it)
var canvasGroup = GetComponent<CanvasGroup>();
if (canvasGroup == null) canvasGroup = gameObject.AddComponent<CanvasGroup>();
// Increment the index for lerping
index += Time.deltaTime;
// If we haven't reached the end of the 'animation'
if (index <= 1)
{
if (forwards)
{
// fade in
canvasGroup.alpha = Mathf.Lerp(0, 1, index);
}
else
{
// fade out
canvasGroup.alpha = Mathf.Lerp(1, 0, index);
}
}
else
{
// we've reached the end of the animation; change direction and reset the index
forwards = !forwards;
index = 0;
}
}
}This code works by obtaining a reference to the 'CanvasGroup' component (and adding it if we don't find one), and then lerping its 'alpha' value between 0 and 1, alternating directions as we reach the end of either value (0 or 1).
It's fairly easy to see the mistake here: GetComponent<> is an expensive call, and there's no need for this component to call it every frame. There are several ways to correct this - the easiest is to make canvasGroup a class member and then move the code that populates it into Start(), Awake(), or OnEnable() (whichever seems most appropriate, bearing in mind when each is called).
using UnityEngine;
public class FadeInOut : MonoBehaviour
{
private bool forwards = false;
private float index = 0;
private CanvasGroup canvasGroup = null;
private void Start()
{
canvasGroup = gameObject.AddComponent<CanvasGroup>();
}
private void Update()
{
// Increment the index for lerping
index += Time.deltaTime;
// If we haven't reached the end of the 'animation'
if (index <= 1)
{
if (forwards)
{
// fade in
canvasGroup.alpha = Mathf.Lerp(0, 1, index);
}
else
{
// fade out
canvasGroup.alpha = Mathf.Lerp(1, 0, index);
}
}
else
{
// we've reached the end of the animation; change direction and reset the index
forwards = !forwards;
index = 0;
}
}
}And there we go - almost exactly the same, but now GetComponent is only called once, rather than once every frame. It's a relatively minor performance improvement, but small improvements like these add up over time.
An alternative approach that I often use is a bit more complicated, but is a bit more encapsulated (i.e. self-contained) is to create a property which handles the GetComponent call internally, if necessary, like so:
private CanvasGroup m_canvasGroup = null;
private CanvasGroup canvasGroup
{
get
{
if (m_canvasGroup == null) m_canvasGroup = gameObject.AddComponent<CanvasGroup>();
return m_canvasGroup;
}
}This is very similar to the code in which we populated canvasGroup in Start(), except that in this case, the member is populated automatically the first time it is called. I tend to prefer this to the Start() approach, as it keeps all of the code needed for the property to work in one place.
It does, however, have a minor downside - the null check will be called every time the property is used, which does have a very minor (almost non-existent) performance hit. Ultimately, you'll have to decide what works best for you.
So, first things first - if you're looking to cache the return value from a method, for example, it:
Should be called frequently - there's little point in caching something that's only called every now and then (unless it's very, very complex).
E.g. a method that's called many times in each frame is ideal, whereas a method that's only called a few times over the course of your application is not.
Should, when given the same arguments, always return the same result.
If the method could return different values, then caching it would most likely break your application logic. You can sometimes get around this by invalidating the cache when things change that would affect its return values - but you do have to be careful with that; after all the idea of the cache is to reduce complexity, not increase it.
It probably goes without saying, but if the method doesn't return anything, then well, there's probably nothing to cache (that doesn't mean it can't benefit from some internal caching, however).
Arguments for the method should preferably be something you can easily use as a lookup for your cache
Basic data types like strings and integers are often good, but complex data types are usually not the best unless you have a way of quickly comparing them to one another (more on this later).
In my last post I shared some code where I'd mistakenly cached a method where it was actually faster to perform the calculation again than to get the stored result from the cache. Whoops!
Here's another method from my simulation code:
public List GetSurroundingCells(Cell cell, int distance = 1)
{
List cellList = new List| ((((distance * 2) + 1) * ((distance * 2) + 1)) - 1);
var minX = Math.Max(0, cell.X - distance);
var maxX = Math.Min(MaxGridIndex, cell.X + distance);
var minY = Math.Max(0, cell.Y - distance);
var maxY = Math.Min(MaxGridIndex, cell.Y + distance);
for (int x = minX; x < maxX; x++)
{
for(int y = minY; y < maxY; y++)
{
if (x == cell.X && y == cell.Y) continue;
cellList.Add(cells[x, y]);
}
}
return cellList;
} | | | This method returns all cells around a particular cell, using the optional distance argument to include cells that are further away. This is primarily used by the creatures in my simulation to locate things around them.
As you can imagine, this gets called quite a lot (every time the creature moves), which can happen multiple times per frame. It's also a fairly complicated operation, involving creating a new list of Cells with hundreds of entries (by default, each creature can see 7 cells in any given direction, which works out to 195 [14x14 - 1] cells - and through random mutations, this sense range can be increased even further).
Fortunately, the cells never move, and as such, any cells 'surrounding' another cell at up to a particular distance will never change - so this method is a prime candidate for caching.
Adding the cache code is in this case turned out to be fairly complicated - in my first iteration, I added a class called 'SurroundingCellData' which referenced the cell, the distance, and finally, the list of cells. I then added a list of these to store the cached data. When the method was called, the code would first check in the list to see if there was a matching entry, and if it found one, it would return it rather than executing the calculation. If the calculation was necessary, it would store the result in the cache.
In theory, that should have worked rather well, but I soon hit on a snag - after just a few minutes of execution, there were thousands upon thousands of entries in the cache. Pretty soon it was taking longer to look up results in the cache than it was to perform the calculations in the first place. Yikes.
After thinking it through, I realised that the number of entries in the cache was a huge problem - if there are so many entries that it takes a long time to find results, then the cache actually makes things worse.
So, what I ended up doing was switching from a List to a Dictionary, using the cell as the key - that way, the number of top-level entries in the cache is never higher than the number of cells on the grid, which is much lower. Each entry in the dictionary then has its own list of 'SurroundingCellData' entries which are fairly short - many only having a single item at first, and gaining more over time as creatures gain or lose sense range. The number of entries in them however is usually less than ten, far fewer than the thousands upon thousands I had been seeing in the top-level flat cache, and the lookups are now lightning-fast.
private class SurroundingCellData
{
public int distance;
public List<Cell> cellList;
}
private Dictionary<Cell, List<SurroundingCellData>> surroundingCellCache = new Dictionary<Cell, List<SurroundingCellData>>();
public List<Cell> GetSurroundingCells(Cell cell, int distance = 1)
{
if (!surroundingCellCache.ContainsKey(cell))
{
// if this cell has no entry, add one
surroundingCellCache.Add(cell, new List<SurroundingCellData>());
}
else
{
// Locate the first entry of this cell that matches the specified distance
// (if one exists)
for (int i = 0; i < surroundingCellCache[cell].Count; i++)
{
if (surroundingCellCache[cell][i].distance == distance)
{
return surroundingCellCache[cell][i].cellList;
}
}
}
// otherwise, perform the calculation and then store the result
List<Cell> cellList = new List<Cell>((((distance * 2) + 1) * ((distance * 2) + 1)) - 1);
var minX = Math.Max(0, cell.X - distance);
var maxX = Math.Min(MaxGridIndex, cell.X + distance);
var minY = Math.Max(0, cell.Y - distance);
var maxY = Math.Min(MaxGridIndex, cell.Y + distance);
for (int x = minX; x < maxX; x++)
{
for(int y = minY; y < maxY; y++)
{
if (x == cell.X && y == cell.Y) continue;
cellList.Add(cells[x, y]);
}
}
// store the result in the cache
surroundingCellCache[cell].Add(new SurroundingCellData { distance = distance, cellList = cellList });
return cellList;
}One thing I neglected to mention here is that I was also able to improve the lookup time by changing the way in which the Cell instances are compared (seeing as they are being used as keys for a dictionary).
By default, C# uses the object.Equals(object other) method to compare any two objects - this is generally fairly efficient, but it is also generalized - you can often make it more efficient by overriding the Equals method in your code.
In this case, two cells are equal if a) they are both of type Cell, and b) they have matching X and Y values.
So, this logic is fairly easy to implement into the Cell class:
public override bool Equals(object other)
{
if (other == null || !(other is Cell)) return false;
var otherCell = (Cell)other;
return otherCell.X == this.X && otherCell.Y == this.Y;
}However, if you override the Equals method, C# will also expect you to override the GetHashCode method. GetHashCode returns an integer value which can also be used for comparison. The reason it also needs to be implemented is that GetHashCode is actually used before Equals is called in order to group items together before directly testing them for equality when they are used as keys in, for example, a dictionary - like we've done here.
As such, it is extremely important that comparing the result of GetHashCode between two objects (in this case, cells) would also return the same result as comparing them with Equals.
Here is the implementation for GetHashCode that I've chosen to use here:
public override int GetHashCode()
{
unchecked
{
int hash = 17;
hash = hash * 23 + X.GetHashCode();
hash = hash * 23 + Y.GetHashCode();
return hash;
}
}The numbers in the calculation are not particularly relevant - so long as they never change (so that the hash code for any particular object never changes during that objects lifetime). Note that it uses both the cells X and Y properties - we can safely use these properties because the X and Y coordinates of each cell will never change (if they did, then we could not use them in GetHashCode as changing them would change the hash code of the object). The random-seeming nature of these numbers is to reduce the possibility of getting the same result when comparing different objects.
The unchecked keyword is uses here to disable overflow checking for the calculation, which is not necessary here. Essentially, this improves performance, albeit very slightly (remembering that this code is called a great many times per frame). If there was a danger of overflow (numbers too big to fit in an int), then we'd need to change the code anyway as our logic would be incorrect.