JacksonDunstan.com

using System.Collections.Generic;
using System.Reflection;
using System.Runtime;
 
using UnityEngine;
 
public class TestScript : MonoBehaviour
{
	private string report;
 
	void Start()
	{
		GCSettings.LatencyMode = GCLatencyMode.LowLatency;
		report = string.Join(
			"\n",
			new string[]{
				"Test,Array Time,List Time,LinkedList Time,FastList Time",
				Test(1000000),
				Test(2000000),
				Test(3000000),
				Test(4000000),
				Test(5000000),
				Test(6000000),
				Test(7000000),
				Test(8000000),
				Test(9000000),
				Test(10000000)
			}
		);
	}
 
	string Test(int length)
	{
		var stopwatch = new System.Diagnostics.Stopwatch();
		var array = new int[length];
		var list = new List<int>();
		var linkedList = new LinkedList<int>();
		var fastList = new FastList<int>();
		for (var i = 0; i < length; ++i)
		{
			array[i] = i;
			list.Add(i);
			linkedList.AddLast(i);
			fastList.Add(i);
		}
 
		int sum;
 
		stopwatch.Reset();
		stopwatch.Start();
		sum = 0;
		foreach (var i in array)
		{
			sum += i;
		}
		var arrayTime = stopwatch.ElapsedMilliseconds;
 
		stopwatch.Reset();
		stopwatch.Start();
		sum = 0;
		foreach (var i in list)
		{
			sum += i;
		}
		var listTime = stopwatch.ElapsedMilliseconds;
 
		stopwatch.Reset();
		stopwatch.Start();
		sum = 0;
		foreach (var i in linkedList)
		{
			sum += i;
		}
		var linkedListTime = stopwatch.ElapsedMilliseconds;
 
		stopwatch.Reset();
		stopwatch.Start();
		sum = 0;
		foreach (var i in fastList)
		{
			sum += i;
		}
		var fastListTime = stopwatch.ElapsedMilliseconds;
 
		return string.Join(
			",",
			new string[] {
				length.ToString(),
				arrayTime.ToString(),
				listTime.ToString(),
				linkedListTime.ToString(),
				fastListTime.ToString()
			}
		);
	}
 
	void OnGUI()
	{
		GUI.TextArea(new Rect(0, 0, Screen.width, Screen.height), report);
	}
}

Comments

• #1 by Kristián on March 7th, 2016 · Reply

  And what if I use simply just for loops when working with List ?? .. is there any garbage created, too ?? ..

  • #2 by jackson on March 7th, 2016 · Reply

    Nope, only foreach loops which call GetEnumerator create any garbage. They’re also faster than foreach, just not as nice to use or as flexible (e.g. for working with IEnumerable instead of plain arrays).

• #3 by focus on April 23rd, 2016 · Reply

  Thanks for looking into FastList, Jackson! =)

• #4 by Yuri Tikhomirov on April 23rd, 2016 · Reply

  Hey Jackson!

  According to your performance test, I see now “FastList” is not the best name for that kind of implementation =)

  But overall the purpose was to rapidly make a list that won’t produce garbage when it is being enumerated using IEnumerator (foreach, but not passing this list as IEnumerable since it actually does not overrides GetEnumerator() method).

  So it have very limited usage as described in the very first lines of comments there.

  Also I’d like to specify the following:

  1. This list is totally not thread safe, it could not be used without care in multithreaded environment. It’s actually made for Unity to work within main thread. Enumerating this list using foreach loop in different threads will probably lead to major failures since different threads could possibly retain control over the same instance of CustomEnumerator.

  2. I’m not sure I understand this term correctly, but as for me, producing garbage is not the same as allocating object. When you make screenshots from Unity Profiler, you could see the column is named “GC Alloc”, this means, it show how many bytes of memory is allocated during this frame. And it tells nothing about garbage collection. So, what I want to say, you are not producing garbage when allocating objects – until this objects are ‘alive’, they are not supposed to be treated as garbage =) But when you ‘release’ all the references to that object, that’s the point from which the garbage collection may occur and when you actually ‘producing garbage’.

  So, as from my point, it’s totally ok when Start() methods allocates objects (‘GC Alloc’), but it is total failure when each Update() allocates any object of any size – of course except the transitions from state to state. (I mean in most cases Update() should strongly not be designed such ways that it makes GC alloc every frame, like Update() { scoreText = playerScore.ToString(); })

  Now let’s get back to that FastList. It’s a really rapid solution that was made to avoid multiple GC allocations on each frame where foreach is used over number of lists. It is built over a standart list and it inherits all it’s problems you mentioned in this and previous articles. But as for me, until your scripts is not a real bottleneck (let’s say, all your Updates takes 1ms, but rendering takes 10ms), it is okay to use that kind of FastList in a purposes to keep some objects that is being ‘touched’ each frame using foreach.

  Anyway, thanks for your article. It actually tells me again that naming of entities is very important in programming =)

  • #5 by jackson on April 23rd, 2016 · Reply

    Hey Yuri!

    Thanks for adding these points. It’s definitely important to mention that FastList isn’t thread-safe and that’s not something I mentioned in the article.

    As for “GC Alloc”, you’re right that the GC only needs to collect when you’ve released all references to an object that was allocated. For example, this will have 200 KB of “GC Alloc” even though the string isn’t ever garbage-collected:

    public class TestScript : MonoBehaviour
    {
    	private string str;
     
    	void Start()
    	{
    		str = new string('*', 1024 * 100);
    	}
    }

    The point is more that the allocation has occurred and eventually the garbage will need to be collected. For temporary operations such as a foreach loop, “eventually” is “right after the loop”. FastList has the advantage over List here because it doesn’t release the enumerator right after the list for garbage collection. We can see this in the second test run (i.e. TestScript.SecondTest) where FastList has no “GC Alloc” but List does.

    Thanks again for posting such a thorough comment! Let me know if you have any followups to FastList or other experiments that I can check out.