Multi-threading performance

Unity Engine
1

I’ve got a HUGE generic list that a particular function uses. It takes quite a bit of time for the function to go through every item in the list. Because every item is independent from one another (aka: the value of one item doesn’t affect the computation of the other), I thought it’d be a neat idea to use multiple CPU threads to compute that list.

I figured that this is the ideal case for using multiple threads.

So in my for loop:

For (int i = startingPoint; i < endPoint; i++) {
}

I have it set up so that the startingPoint and the endPoint are of the appropriate values so that the total amount of items in the list gets divided and computed by different threads.

0, 1000
1000, 2000
2000, 3000
etc.

1 thread, 2 threads, 3 threads, etc. The code seems to work great and I can see in my computer’s activity monitor that my cores are being used. No errors, no crash.

Here’s the thing, though. CPU load never seem to go above 50% of a particular thread (so, for 3 threads, each of them stay at around 50%). I figured that’d be pretty standard/reasonable behaviour so, as much as I would want to use 100% of my threads, I can shrug that off.

Where it gets odd is that, the more threads I use, it seems to take my computer progressively more time to complete the task. It’s almost as if using 1 or 2 threads is faster than using all 8 on my computer. I can understand the initial step of starting each thread could take some time however, I got a Debug.Log time stamp and they all seem to start at a relatively short time from one another… they just seem to go through the function a lot slower.

Is there something I’m missing? Is this normal? I thought maybe there was a bottleneck with memory but I don’t see it either with my computer’s activity monitor nor with Unity’s Profiler (either that or I apparently don’t know how to read it).

Any thoughts or clarifications would be great as I’m kind of new to the whole multi-threaded thing. Thanks.

2

Are you accessing some common resource in those threads? Like an array? In that case, the processors are having to wait for each other to access it, which will be a problem.

1 Like
3

Thread scheduling can also become a bottle neck. The OS has to decide which thread to run, and where. But I would have thought this use case would have been a straight forward win.

The main use I’ve had for threading in the past has been about making long tasks non blocking. I’ve never really looked at it from an absolute performance perspective.

1 Like
4

They’re all accessing different items in the same generic list; I guess that’s the catch.

Like BoredMormon, I had the impression that this was most straight forward use case.

So I guess the advantages of using multiple-threads is to compute completely unrelated resources… like AI.

5

You can split the list up in a bunch of different lists before you start the threaded job, and then combine them again when you’re finished.

Or, if this is lists of reference types (ie. objects, not structs or numbers), you don’t even have to combine the different lists again, as the objects in the smaller lists are the same as the ones in the larger one.

1 Like
6

There is typically an overhead cost that must be paid for using threads and when the number of threads used creates more overhead than concurrency gains you will start to see an increase in processing time instead of a decrease.

However, most of the overhead happens at certain thresholds such as moving from 1 thread to 2, or when moving from the number of resources available to your computer to the number of resources + 1.

I thought there were a few things in your OP that seemed a bit strange.

What do you mean by this?

You can think of threads like workers, but they can’t do any without a processor to work on. CPU load is typically measured by processor, or “core”, not by thread.

Each time you add a thread to your application, it will get in queue to use system resources. Your logical processors are one of those resources, so if this is the only resource needed by the thread, you should see your CPU load increase by a set percentage. I have 8 processors on my system, so if I create a new thread that is very busy, my CPU load will increase by 100%/8 = 12.5%. I can do this all the way to 100% CPU load.

It doesn’t always work this way though, if there is some other resource which the threads are waiting on, they will not take a CPU processor and the CPU load may not increase after all. However, unless you are using a specially crafted collection, there will be no synchronization between the threads, so it’s unlikely they are waiting for access to the collection of items.

Without seeing more code, it is difficult for us to speculate on why adding threads may be slowing down the operation. It could very well be that the function is simple enough that the overhead of thread scheduling is more expensive than the gains of using multiple processors. Or, it could be that you are trying to use more threads than there are processors, which would cause extra context swaps. Finding the ideal number of “workers” on a system is pretty complex and is one of the best arguments for abstracting the concepts of “what work to do” from “how to do it”.

I’ve heard mostly good results from people making use of the Task Parallel Library from within Unity. I really like this framework because it allows the programmer to describe chunks of work and pass it off to the system to decide how many workers would be ideal to complete it. The TPL was introduced in .net 4 but some very smart people have done an excellent job of back-porting it to .net 3.5, so you can use (most of) it in Unity too. Unfortunately, it’s a Windows binary, so taking on this dependency might tie your hands in terms of target platforms. I don’t have any experience here…

3 Likes
7

It would be pretty nice for Unity to roll out something similar to the most excellent (free) thread ninja in asset store. I don’t know if anyone’s used it but it makes threading super simple in a game-like format. So if your main thread is bloating out, just split the logic above and below the thread ninja yield.

Any thoughts on that? I’m a noob at threading so I thought I’d throw in my 2p.

1 Like
8

I’ve never used Thread Ninja but if the screenshots are to be believed, the interface is really smart! It looks almost like the fancy async stuff Microsoft has done but way simpler. I’d be curious to know how it handles communication/memory sharing between the threads but it seems very useful if it works…

9

I think that pot of noodles in your avatar (if that’s what it is) is far more interesting than any of this threading nonsense. You have a very compelling avatar.

10

Thanks for taking the time to respond. What I mean is that if I were to use my computer’s Activity Monitor (on Windows it’s the… um… “Task Manager”, I think?) I can see that my CPU is divided into 8 cores who’s load is represented by different bars and, by creating a new thread, I can see a bar of a particular core go up.

If I were to use 3 threads, I see 3 cores of 8 being used. Overall CPU load is increased by, per core/thread, I never see the bars of each core go over the 50% mark. I would spend minutes waiting for the process to complete and, while I’m waiting for the kettle to boil, I’m noticing that it doesn’t seem to be using the CPU’s full potential.

So if you say the CPU load is increased by: 100%/8 = 12.5%, I’m saying I’m noticing that it’s more like (100%/8)/2 = 6.25%

The overhead cost that you’re referring to (and I guess that’s what BoredMormon is talking about as well) is probably what I’m experiencing as adding 1 or 2 extra threads seems to help.

I’m definitely taking Baste’s thoughts into consideration, though, despite the fact that splitting my list prior to computation seem counter-productive. I’m dealing with really large lists (100000 items being a relatively small number).

11

Thanks! Yes, some “threading” problems are more interesting (delicious) than others…
Actually, I’m always jealous of @Kiwasi 's avatars; I never have any damn idea what’s going on.

I’m guessing that’s Apple for Task Manager… Which will make this more difficult because I don’t know much about them.

That’s quite interesting, could be a design decision by Apple to never allow a single process to use more than 50% of a processors cycles, or it could be the effect of some other hardware “feature” like hyper-threading.

Keep in mind that the ideal number of threads will probably change based on your target device’s hardware. This becomes especially troublesome when targeting many devices, which is why I like the TPL framework. While I was looking for backports that would be compatible with the Mac, I found this on the Asset Store. Could be useful!

I don’t usually do this (mostly because of that damn grin), but I will disagree with Baste. I don’t believe the generic list will be blocking your threads because the built in simple collection types do not have any synchronization features built into them. In other words, its a free-for-all in terms of accessing the data. There should not be any blocking.

12

Really? This one is fairly straight forward. I’m the guy in blue. I am attempting to kill the guy in chain mail. Behind me is a lake. On the other side of the lake is a variety of fallen soldiers, healers and guards.

I don’t remember the specific details of the fight. But lets just assume I won?

2 Likes
13

And songs are still sung of your heroism!

This thread makes me want to added my always planned threading option to RadicalCoroutine… going to do that now.

2 Likes
14

// TODO: Have a bard write a song about my heroic sacrifice in battle. Last night I managed to draw the generals elite guard away from their posts. By the time they had killed me my squad mates had killed the general, winning the war.

1 Like
15

Sweet, that actually came out pretty nicely.

Some mods to RadicalCoroutine had to be made:

I even borrowed the ‘jumpto’ tokens from ninja, though really it’s just sugar as really it just replaces the token with a RadicalTask object.

I went with the inverse of ninja in that you can start a coroutine async, or you can turn async from an already operating coroutine, because the task is a yieldinstruction itself. If you yield ANYTHING you immediately return to the main thread (ths JumpToUnityThread really is no different from yielding null… it’s merely there to again allow syntax that reads nicely).

using UnityEngine;
using System.Threading;

using com.spacepuppy;
using com.spacepuppy.Async;
using com.spacepuppy.Utils;

public class zTestScript : MonoBehaviour {

    void Start()
    {
        this.StartRadicalCoroutine(this.SomeRoutine()); //is an extension method
        //this.StartRadicalCoroutineAsync(this.SomeRoutine()); //alternatively, start async
    }


    System.Collections.IEnumerator SomeRoutine()
    {

        Debug.Log("MAIN: " + Thread.CurrentThread.ManagedThreadId);

        yield return WaitForDuration.Seconds(1f);

        Debug.Log("MAIN: " + Thread.CurrentThread.ManagedThreadId);

        yield return RadicalTask.JumpToAsync;

        Debug.Log("OTHER: " + Thread.CurrentThread.ManagedThreadId);

        Thread.Sleep(1000);

        Debug.Log("OTHER: " + Thread.CurrentThread.ManagedThreadId);

        yield return RadicalTask.JumpToUnityThread;

        Debug.Log("MAIN: " + Thread.CurrentThread.ManagedThreadId);

        yield return WaitForDuration.Seconds(1f);

        Debug.Log("MAIN: " + Thread.CurrentThread.ManagedThreadId);

    }
 
}

…

Sorry if this is hijacking the thread…

5 Likes
16

Nice!

17

I’ve done some further reading on the matter and I’m a bit at a loss. The primary bottleneck that I had (when I wrote my OP) was that, per thread, I was writing into a variable… frequently. Reading suffers no noticeable performance loss.

Okay. So I rewrote my code taking this into consideration. The idea is to, per thread, build temporary data and then, at the end only write once on the “main” variable.

Here’s a simplified version of the I’m using (filtering out everything that’s irrelevant):

private List<Things> listOfThings = new List<Things>();
private List<Stuff> theRealList = new List<Stuff>();
private int startedThreads = 0;

void MainFunction()
{
    for (int i = 0; i < numOfThreads; i++) {
        new Thread (Work).Start();
    }
}

void Work()
{
    //////////
    // divide the work

    in split = Mathf.CeilToInt(listOfThings.Count / System.Environment.ProcessorCount) +1; //+1 to avoid missing items to compute due to float value of a division

    int startPoint = startedThreads * split;
    int amount = startPoint + splitCount;
    if (startThreads+1 == numOfThreads && amount > listOfThings.Count) { //since I added a +1 to the split,  I have to make sure that I don't go beyond the listOfThings.Count;
        amount = listOfThings.Count;
    }

    /////////
    // start the work
    List<Stuff> theStuff = new List<Stuff>(amount); // <-- hoping that this is isolated to the thread
    Dictionary<Vector3, int> hashStuff = new Dictionary<Vector3, int>(amount);// <-- hoping that this is isolated to the thread

    startedThreads++; // <-- this writes to all threads
    for (int i = startPoint; i < amount; i++) {
        Vector3 coords = new Vector3( X, Y, Z ); // <— X, Y, Z are generated by more code, I removed it for simplicity’s sake.  Besides, this isn't where the bottleneck is.

        AddStuff(theStuff, hashStuff, coords);
    }

    //eventually write code here that'll add the items from "theStuff" into "theRealList"
}

void AddStuff(List<Stuff> theTheStuff, Dictionary<Vector3, int> theHashStuff, vector3 theCoords)
{
    if (!hashStuff.ContainsKey( theCoords )) { //prevent Vector3 from existing twice.
        hashStuff.Add( theCoords, theTheStuff.Counter );

        Stuff newStuff = new Stuff();
        theTheStuff.Add( newStuff );  // <-- this is where it's slowing down.
    }
}

Just to give you guys an idea, the average time to compute this script with 8 threads is roughly 3minutes. With a single thread, the average is 50 seconds. 50 seconds isn’t that bad but the entire purpose for me to use multi-threading was to, hopefully, trim that time down, not increase it.

Maybe I’m not doing it right but I have a feeling that, when I add an item in hashStuff and theTheStuff (line# 44 and 47), it’s slowing down all the other threads as if they’re all using the same variable… or are they? If so, how I isolate the variable so that each thread can write in peace?

EDIT: Hang on a sec… should I make a new class for Work() ?
EDIT EDIT: Nope… that makes it WAY worse; practically doubling the process time.

The average amount of items listOfThings has is around 50,000 items.

Thanks

(I’m currently reading lordofduct’s “radical” stuff.)

18

I see a couple of problems right away. I’ll try to fit in some time to look more closely later. I’ll put an * in front of my comments. Here’s what I noticed from a quick scan:

//* You hardly use this list at all (reading the count value is not going to cause slow downs)
private List<Things> listOfThings = new List<Things>();
//* Nor this list. You seem to have simplified the problem too much in your post, you are not using these shared resources.
private List<Stuff> theRealList = new List<Stuff>();
private int startedThreads = 0;

void MainFunction()
{
    for (int i = 0; i < numOfThreads; i++) {
        new Thread (Work).Start();
    }
}

void Work()
{
    //////////
    // divide the work

    //* This could be done in the main thread and passed as a parameter
    int split = Mathf.CeilToInt(listOfThings.Count / System.Environment.ProcessorCount) +1; //+1 to avoid missing items to compute due to float value of a division

    //* There is a race condition here -- startedThreads is going to be zero until much later.
    int startPoint = startedThreads * split;
    int amount = startPoint + splitCount;
    if (startThreads+1 == numOfThreads && amount > listOfThings.Count) { //since I added a +1 to the split,  I have to make sure that I don't go beyond the listOfThings.Count;
        amount = listOfThings.Count;
    }

    /////////
    // start the work
    //* Since this is a local variable, each thread will have their own copy so it is, as you say, "isolated to the thread"..
    List<Stuff> theStuff = new List<Stuff>(amount); // <-- hoping that this is isolated to the thread
    Dictionary<Vector3, int> hashStuff = new Dictionary<Vector3, int>(amount);// <-- hoping that this is isolated to the thread

    //* Here is the other half of your race condition .. Answer this question: What happens if a thread yields just before this line executes and another of your threads takes over from the top?
    startedThreads++; // <-- this writes to all threads
    for (int i = startPoint; i < amount; i++) {
        Vector3 coords = new Vector3( X, Y, Z ); // <— X, Y, Z are generated by more code, I removed it for simplicity’s sake.  Besides, this isn't where the bottleneck is.

        AddStuff(theStuff, hashStuff, coords);
    }

    //eventually write code here that'll add the items from "theStuff" into "theRealList"
}

void AddStuff(List<Stuff> theTheStuff, Dictionary<Vector3, int> theHashStuff, vector3 theCoords)
{
    if (!hashStuff.ContainsKey( theCoords )) { //prevent Vector3 from existing twice.
        hashStuff.Add( theCoords, theTheStuff.Counter );

        Stuff newStuff = new Stuff();
        //* Doesn't make sense that this would be slowing down. As you say, theTheStuff is "isolated" to each thread. That is, each thread has their own copy. Even if there was synchronizing locks in a regular Dictionary, which there isn't, there is no concurrency happening here anyways.
        theTheStuff.Add( newStuff );  // <-- this is where it's slowing down.
    }
}
2 Likes
19

GixG17, I’ll be honest, it was pretty difficult to decipher what your program is intended to do since you removed so many details. Anyways, I “read between the lines” a bit to compile this program in Visual Studio. I don’t have Unity on this computer, so I needed to tweak things a bit anyways. Honestly, I wouldn’t process things this way (I prefer Tasks) but I wanted to show you that it is possible to improve your processing time using similar thinking to your original code.

This code is pretty crude but it demonstrates that your idea is plausible.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading;

namespace ConsoleApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            var watch = new Stopwatch();
            watch.Reset();

            Console.WriteLine($"Starting timer for {numOfThreads} threads");
            watch.Start();

            var p = new Program();
            p.MainFunction();

            watch.Stop();
            Console.Write($"Processing completed in {watch.ElapsedMilliseconds}ms.");

            Console.ReadLine();
        }
      
        private int numberOfThings = 1000000;
        private int startedThreads = 0;
        const int numOfThreads = 8;

        void MainFunction()
        {
            Thread[] workers = new Thread[numOfThreads];
            for (int i = 0; i < numOfThreads; i++)
            {
                workers[i] = new Thread(Work);
                workers[i].Start();
            }

            for (int i = 0; i < workers.Length; i++)
                workers[i].Join();
        }

        void Work()
        {
            //////////
            // divide the work

            int split = (int)Math.Ceiling((double)(numberOfThings / numOfThreads));

            //* Determine this thread's #
            int threadNumber = Interlocked.Increment(ref startedThreads) - 1;
            int startPoint = threadNumber * split;
            int endPoint = startPoint + split;

            if (threadNumber + 1 == numOfThreads)
                endPoint = numberOfThings;

            int amount = endPoint - startPoint;

            /////////
            // start the work

            List<Vector3> theStuff = new List<Vector3>(amount);
            Dictionary<Vector3, int> hashStuff = new Dictionary<Vector3, int>(amount);
          
            for (int i = startPoint; i < endPoint; i++)
            {
                Vector3 coords = Vector3.CalculateNext(12345 + threadNumber);

                AddStuff(theStuff, hashStuff, coords);
            }

            Console.WriteLine($"Thread {threadNumber} is done processing items {startPoint} through {endPoint}. Created {hashStuff.Count} unique items");

            //eventually write code here that'll add the items from "theStuff" into "theRealList"
        }

        void AddStuff(List<Vector3> theTheStuff, Dictionary<Vector3, int> theHashStuff, Vector3 theCoords)
        {
            if (!theHashStuff.ContainsKey(theCoords))
            { //prevent Vector3 from existing twice.
                theHashStuff.Add(theCoords, theTheStuff.Count);

                Vector3 newStuff = new Vector3();
                theTheStuff.Add(newStuff);
            }
        }
    }

    internal struct Vector3
    {
        public long x, y, z;

        public static Vector3 CalculateNext(long salt)
        {
            Random r = new Random();
            Vector3 newVector = new Vector3();

            newVector.x = r.Next();
            newVector.y = r.Next() << 16;
            newVector.z = r.Next() << 32;

            for (long i = 0; i < salt; i ++)
            {
                newVector.x = newVector.x ^ newVector.y ^ newVector.z;
                newVector.y = newVector.y ^ newVector.z ^ newVector.x;
                newVector.z = newVector.z ^ newVector.x ^ newVector.y;
            }

            return newVector;
        }


    }
}

I changed the numOfThreads constant to give an idea how multi threading can have an effect. Here are some results run on my machine

Starting timer for 1 threads
Thread 0 is done processing items 0 through 1000000. Created 3624 unique items
Processing completed in 56611ms.

Starting timer for 2 threads
Thread 1 is done processing items 500000 through 1000000. Created 1861 unique items
Thread 0 is done processing items 0 through 500000. Created 1864 unique items
Processing completed in 29122ms.

Starting timer for 8 threads
Thread 2 is done processing items 250000 through 375000. Created 730 unique items
Thread 7 is done processing items 875000 through 1000000. Created 739 unique item
Thread 5 is done processing items 625000 through 750000. Created 745 unique items
Thread 4 is done processing items 500000 through 625000. Created 743 unique items
Thread 1 is done processing items 125000 through 250000. Created 742 unique items
Thread 3 is done processing items 375000 through 500000. Created 750 unique items
Thread 6 is done processing items 750000 through 875000. Created 748 unique items
Thread 0 is done processing items 0 through 125000. Created 749 unique items
Processing completed in 12061ms.

4 Likes
20

Just wanted to say I think your contributions are both intelligent and a breath of fresh air in the community, eisenpony! Thanks!

1 Like