Multithreading Solutions

[NathanWarden1]

This post isn’t a complaining thread, but instead is a solution thread.

I’ve read several posts of people complaining about how there are many places where Unity isn’t multi-threaded.

The following are places where I’ve found that multi-threading can be safely used in Unity. Feel free to add ideas and uses to this thread

Real-time Mesh Manipulation

1. Store the Vector3 array of the mesh’s verts property into an array in your script.
2. Start a thread (or threads at N indexes) that manipulate the Vector3 data
3. If the data needs to be 100% accurate, set a flag or do a Thread.Sleep in the main thread (such as Unity’s Update function or whatever) until the data has been updated. In most cases I suspect the data doesn’t need to be 100% accurate, but can be arbitrarily assigned back to the mesh.verts property
4. In the main thread assign the Vector3 array back to the mesh’s verts property.

NOTE: This method would be beneficial for a single time mesh manipulation, but would need to be a large mesh to offset the cost of starting the threads.

Image processing

1. In the main thread, grab the Color[ ] data using the Texture2D.GetPixels function
2. Start the thread/threads to manipulate the Color data
3. Wait in main thread until the threads have completed
4. assign the manipulated color data to the texture in the main thread using the Texture2D.SetPixels function

NOTE: This is only beneficial on large images such as 512x512 or greater to offset the cost of starting the threads.

Pathfinding

If you have several characters you can store the nav mesh into thread safe data such as the Vector3 class and calculate each pathfinding actor into their own thread, or all in a single thread depending on your needs.

Calculating Distances of Vector3’s

If you have a ton of objects (maybe a few hundred or more) you can store the positions into a Vector3 array every N frames and calculate the distances between them in another thread.

Why? Because 3D distance calculations use the Pythagorean theorem which use a square root. This could possibly alleviate hundreds or thousands of square root calculations per check. You may not want to be pushing data around every frame however, because reading/writing data can be more expensive than the square root calculation itself. You definitely will need to do testing to see if it does more harm or good.

NOTE: this wouldn’t make much difference and may make your app slower if there are only a few distances to calculate.

Sorting

NOTE 1: This would be pretty rare since to balance the cost of starting the threads necessary you’d need a lot of data to sort.

NOTE 2: I’m not writing a psuedo algorithm since it depends on the algorithm you use, however it’s possible to use pretty much any algorithm to sort data. I recommend the merge sort for data that must be compared. I’ve written multi-threaded code for the Bubble sort that has sped the sorting up by 20x or more with a dual core CPU, but, this is still slower than sorting with the merge sort in the main thread.

Again, please feel free to add to this thread as I’m curious where others use multi-threading in Unity

Thanks,
Nathan

[Eric5h5]

See here for an example of using multi-threading for image processing. Fractscape uses multi-threading for the terrain calculations (useful for when you jack the resolution way up and it takes a little while to compute).

–Eric

[NathanWarden1]

Thanks Eric,

I hadn’t really thought about doing that with terrains, makes sense though. Are you using it for painting?

For those interested in having an example of multithreaded code, here’s my multithreaded merge sort:

using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using System.Threading;

public class MergeSort : MonoBehaviour {
	float[] values = new float[5000000];

	float singleThreadedTime = -1.0f;
	float multiThreadedTime = -1.0f;

	private int threadCount {
		get {
			if ( tCount == -1 )
				tCount = System.Environment.ProcessorCount;

			return tCount;
		}
	}
	private int tCount = -1;


	void Update() {
		if ( Input.GetKeyDown(KeyCode.S) ) {
			DoSorts();
		}
	}

	
	void DoSorts() {
		// Single threaded sort
		InitValues();
		DoSingleThreadMergeSort();

		// Multi threaded sort
		InitValues();
		StartMultiThreadedSort(threadCount);
	}


	/* ****** Inits the array with unsorted values ******* */

	void InitValues() {
		for ( int i = 0; i < values.Length; i++ )
			values[i] = (Random.value * 1000.0f) + ((float)i / (float)values.Length);
	}


	/* ****** Single threaded Sort ******* */

	void DoSingleThreadMergeSort() {
		float startTime = Time.realtimeSinceStartup;

		if ( values.Length > 1 ) {
			// Split the list in half
			MergeSorter(0, values.Length-1);
		}

		singleThreadedTime = Time.realtimeSinceStartup - startTime;
	}


	void MergeSorter(int fIndex, int lIndex) {
		// range will be greater than 1 if there are more than 2 elements in this split
		if ( lIndex-fIndex > 0 ) {
			int firstIndexR = 0;
			int lastIndexR = 0;
			int firstIndexL = 0;
			int lastIndexL = 0;

			GetArrayHalf(fIndex, lIndex, out firstIndexL, out lastIndexL, true);
			GetArrayHalf(fIndex, lIndex, out firstIndexR, out lastIndexR, false);

			MergeSorter(firstIndexL, lastIndexL);
			MergeSorter(firstIndexR, lastIndexR);

			MergeArrays(firstIndexL, lastIndexL, firstIndexR, lastIndexR);
		}
	}


	void MergeArrays(int firstIndexL, int lastIndexL, int firstIndexR, int lastIndexR) {
		int leftSize = (lastIndexL-firstIndexL)+1;
		int rightSize = (lastIndexR-firstIndexR)+1;
		int dataSize = leftSize + rightSize;
		float[] results = new float[dataSize];
		int leftIndex = 0;
		int rightIndex = 0;

		for ( int i = 0; i < dataSize; i++ ) {
			if ( leftIndex >= leftSize ) {
				results[i] = values[firstIndexR+rightIndex++];
			}
			else if ( rightIndex >= rightSize ) {
				results[i] = values[firstIndexL+leftIndex++];
			}
			else if ( values[firstIndexL+leftIndex] < values[firstIndexR+rightIndex] ) {
				results[i] = values[firstIndexL+leftIndex++];
			}
			else {
				results[i] = values[firstIndexR+rightIndex++];
			}
		}

		for ( int i = 0; i < dataSize; i++ ) {
			values[firstIndexL+i] = results[i];
		}
	}


	/* ****** Multithreaded Sort ******* */

	void StartMultiThreadedSort(int numThreads) {
		float startTime = Time.realtimeSinceStartup;

		// Sort on multiple threads (sorts every X elements where X == threadCount)
		HandleThreads(0, numThreads);

		multiThreadedTime = Time.realtimeSinceStartup - startTime;
	}


	void HandleThreads(int additionalThreads, int threadTotal) {
		int threads = threadTotal + additionalThreads;
		SortParameters[] sortParameters = new SortParameters[threads];
		bool done = true;

		if ( threads > values.Length ) {
			threads = values.Length;
			sortParameters = new SortParameters[threads];
		}

		// Start the threads
		for ( int i = 0; i < threads; i++ ) {
			float valuesPerThread = (float)values.Length/(float)threads;
			int firstIndex = (int)Mathf.Round((float)i*valuesPerThread);
			int lastIndex = (int)(Mathf.Round((float)(i+1.0f) * valuesPerThread)-1.0f);

			sortParameters[i] = new SortParameters();
			sortParameters[i].threadNum = i;
			sortParameters[i].threadCount = threadTotal;
			sortParameters[i].firstIndex = firstIndex;
			sortParameters[i].lastIndex = lastIndex;

			ThreadPool.QueueUserWorkItem(SortingThread, sortParameters[i]);
		}

		// Wait for threads to finish
		do {
			done = true;

			for ( int i = 0; i < sortParameters.Length; i++ ) {
				if ( !sortParameters[i].isDone ) {
					done = false;
					break;
				}
			}

			Thread.Sleep(10);
		}
		while ( !done );

		for ( int i = 0; i < sortParameters.Length-1; i++ ) {
			SortParameters sp1 = sortParameters[i];
			SortParameters sp2 = sortParameters[i+1];

			MergeArrays(sp1.firstIndex, sp1.lastIndex,sp2.firstIndex, sp2.lastIndex);
		}
	}


	// Here's were the thread does its' work
	void SortingThread(object parameters) {
		SortParameters sp = parameters as SortParameters;

		MergeSorter(sp.firstIndex, sp.lastIndex);

		sp.isDone = true;
	}


	class SortParameters {
		public int threadNum = 0;
		public int threadCount = 1;
		public bool isDone = false;
		public int firstIndex = 0;
		public int lastIndex = 0;
	}


	/* ****** Grabs the indexes for half of an array ******* */

	void GetArrayHalf(int fIndex, int lIndex, out int leftIndex, out int rightIndex, bool left) {
		int halfPoint = (int)Mathf.Lerp(fIndex, lIndex, 0.5f);

		if ( left ) {
			leftIndex = fIndex;
			rightIndex = halfPoint;
		}
		else {
			leftIndex = halfPoint+1;
			rightIndex = lIndex;
		}
	}


	void OnGUI() {
		bool showSingleThreaded = singleThreadedTime >= 0.0f;
		bool showMultiThreaded = multiThreadedTime >= 0.0f;

		if ( showSingleThreaded )
			GUILayout.TextField("Single thread time: " + singleThreadedTime.ToString());

		if ( showMultiThreaded )
			GUILayout.TextField("Multithreaded time: " + multiThreadedTime.ToString() + " (sec) on " + threadCount + " threads.");

		if ( showSingleThreaded  showMultiThreaded ) {
			if ( multiThreadedTime < singleThreadedTime )
				GUILayout.TextField("Multithreaded was " + singleThreadedTime/multiThreadedTime + " times faster!");
			else
				GUILayout.TextField("Single threaded was " + multiThreadedTime/singleThreadedTime + " times faster!");
		}

		if ( GUILayout.Button("Update ('s')") ) {
			DoSorts();
		}
	}
}

[Eric5h5]

@NathanWarden_1

I hadn’t really thought about doing that with terrains, makes sense though. Are you using it for painting?

It’s for the fractal terrain calculations, and auto-texturing.

–Eric

[Marrrk]

Great idea this thread.

Not long ago I created some thread utilities to help me with threading in unity:
http://forum.unity3d.com/threads/90128-Unity-Threading-Helper

[NathanWarden1]

Cool, nice tools Mark. Looks like you’ve put a lot of work into them.

Okay, here’s a code example of how to manipulate a meshes on threads. If you want to compare the difference between multithreaded and single, just check/uncheck the isMultithreaded checkbox on the AllMeshes object and the setting will propogate to the sub objects.

My machine gets about a 10 fps increase. 18-19 for single threaded and 25-28 for multi.

589057–20953–$MeshRipples.unitypackage (6.53 KB)

[Nick-Wiggill]

EDIT (after erasing the rest of my post): I see, System.Threading.ThreadPool is being used. A thread pool has no thread spawn and kill overhead. Thanks for sharing your code, Nathan. So is that what all of Unity uses? Mono thread pools? If so, that’s a major win IMO since that’s the design pattern I’d favour any day for MT.

[NathanWarden1]

Hi Nick, the Unity Engine itself uses C++ at it’s core, so the ThreadPool you’d use for your code would be a different pool than what they’re using, which shouldn’t be a big deal. But, the thread pool is definitely worth using. There is a slight overhead when you use the first few threads since it spawns them as you need them, but once they’re spawned they’re super fast to reuse.

Here’s what I was posting based on your original post and may be stuff you already know, but I hope it’s helpful in some way:

They don’t need to release the functions every cycle, they can simply sleep the threads at the end of each frame and start them up again once it needs to be drawn again. Certainly there is a slight overhead for this, but, if you need to run multi-threaded code per frame you can only benefit from Unity having their code threaded as well since it’ll take less time to draw a frame, leaving you with more time between frames to do more stuff. This is actually a fundamental rule of parallelism (IE. Amdahl’s Law)

Amdahl’s Law in a very tight nutshell says that as you add cores a system cannot go any faster beyond it’s sequential parts. So if most of the time is spent rendering a frame (which is usually the case) and if the rendering code and core engine code is not parallel you have a serious performance problem. For instance, if 50% of the time is spent in the engine and 50% of the time is in your code and if the engine code is all sequential and all of your code is all parallel, even if you have a trillion cores running your program it will never go faster than a 2x speedup.

Here’s a reference,

Amdahl's law

Hope this helps you in some way,
Nathan

[Nick-Wiggill]

Thanks for your reply Nathan.

I didn’t know about Amdahl’s law, but yes, it seems to formalise the limits of parallelisation. It’s a lot like parallelising raytracing, for instance: while you can break it down to the pixel level, each ray you cast through those pixels from the near plane, and out into space, has to do sequential raymarch processing for pixel composition and early ray termination. In the Ahmdahl example, the difference is that one component becomes the bottleneck, rather than all of them.

Re the initial overheads, yep, normal for threadpools and very acceptable considering the alternatives to threadpooling! I am actually very happy to have discovered threadpools here, and to know I don’t have to write my own implementation.