Optimizing Hundreds of Thousands of Calculations

Unity Engine
, , , ,
1

Im working on a simulations where hundreds of thousands of pops have to grow each timestep. Each pop is its own class with a population growth function that grows the pop according to its size, birth rate, and death rate. The pops are told to grow by the tile manager which has all 725k (50 pops per tile, 14.4k tiles) pops in a list. Updating all these pops causes the game to run at 20 fps, however I cant have only some pops grow to preserve balance in the simulation. Is there anyway to optimize this without ripping apart the whole system?

// Pop class
public class Pop
{
    // Population
    public int population;
    //int dependents;
    //int workers;
    public const float baseBirthRate = 0.04f;
    public const float baseDeathRate = 0.037f;

    // Stats
    public Tile tile;
    public State state;
    public Culture culture;

    public void GrowPopulation(){
        float birthRate = 0f;

        if (population > 1){
            birthRate = baseBirthRate;
            if (population > tile.GetMaxPopulation()){
                birthRate *= 0.75f;
            }
        }

        float deathRate = baseDeathRate;
        float natutalGrowthRate = (birthRate - deathRate) / 12;

        int totalGrowth = Mathf.RoundToInt(population * natutalGrowthRate);

        if (Random.Range(0f,1f) < (population * Mathf.Abs(natutalGrowthRate)) - Mathf.FloorToInt(population * Mathf.Abs(natutalGrowthRate))){
            totalGrowth += (int) Mathf.Sign(natutalGrowthRate);
        }

        ChangePopulation(totalGrowth);
    }

    public void SetTile(Tile newTile){
        if (tile != null){
            tile.pops.Remove(this);
            tile.population -= population;
        }

        tile = newTile;

        if (tile != null){
            tile.population += population;
            tile.pops.Add(this);       

            SetState(tile.state);
        }  
    }

    public void SetState(State newState){
        if (state != null){
            //state.pops.Remove(this);
            state.population -= population;
        }

        state = newState;

        if (state != null){
            state.population += population;
            /*
            if (!state.pops.Contains(this)){
                state.pops.Add(this);        
            }
            */
        }  
    }

    public void SetPopulation(int amount){
        if (tile != null){
            tile.population -= population;
            if (state != null){
                state.population -= population;
            }
        }

        population = amount;

        if (tile != null){
            tile.population += population;
            if (state != null){
                state.population += population;
            }
        }
    }
    public void ChangePopulation(int amount){
        int totalChange = amount;

        // Changes population
        if (population + amount < 1){
            DeletePop();
        } else {
            population += amount;
        }

        // Updates statistics
        if (tile != null){
            tile.ChangePopulation(totalChange);
        }
        
    }

    public void DeletePop(){
        if (tile != null){
            tile.pops.Remove(this);
            tile.ChangePopulation(-population);
        }
        population = 0;
        tile = null;
        state = null;
    }

    public static void MergePops(Pop pop1, Pop pop2){
        if (pop1.culture == pop2.culture && pop1.tile == pop2.tile){
            pop1.ChangePopulation(pop2.population);
            pop2.DeletePop();
        }
    }
}

// Tile class
public class Tile
{
    public TileManager tm;
    public TileTerrain terrain;    public State state = null;
    public Vector3Int tilePos;
    public bool border;
    public bool frontier;
    public bool nationalBorder;
    public bool coastal = false;
    public bool anarchy = false;
    public int carryingCapacity {get; private set;}
    public List<State> borderingStates = new List<State>();

    // Population
    public int population;
    public List<Pop> pops = new List<Pop>();
    public const int maxPops = 25;
    public const float baseBirthRate = 0.04f;
    public const float baseDeathRate = 0.037f;

    public int GetMaxPopulation(){
        return Mathf.RoundToInt(10000 * terrain.biome.fertility);
    }

    public void GrowPopulation(){
        Pop[] popsArray = pops.ToArray();
        foreach (Pop pop in popsArray){
            pop.GrowPopulation();
        }
    }

    public void ChangePopulation(int amount){
        int totalChange = amount;
        if (population + amount < 1){
            totalChange = population * -1;
            population = 0;

        } else {
            population += amount;
        }
        if (state != null){
            state.population += totalChange;
        }
    }
}

// Function to update pops
void tickTiles(){
        foreach (Pop pop in pops.ToArray()){
            if (pop.population < 1){
                pops.Remove(pop);
                pop.DeletePop();
            }
            pop.GrowPopulation();
        }
        /*
        foreach (var entry in tiles){
            Tile tile = entry.Value;
            if (tile.population > 0){
                tile.GrowPopulation();
            }
        }
        */
    }

Sorry if this post is bad, I’m new around here and I’m happy to provide more information if needed!

2

What I would do, I hope it is possible, is to generate several ‘types’ of pops (what is a pop?), even one hundred or one thousand different types, then each pop will only have a ‘type’ and you only have to calculate for each type, that will mean a hundred or a thousand calculations and not several hundred thousands of calculations.

3

Because of the cyclical nature of your populations it may be easier to just make the whole thing statistical and calculate a population only when viewed, using perlin noise and Time.time. To visualize it imagine an image with all the pixels set using perlin noise and glowing over time. You could also use a shader to improve performance further.

4

A pop represents a unit of a population, so basically all of the people with the same tile, religion, and culture constitute a pop. However, every pop needs to grow, optimally at the same time to preserve balance

5

At the scale you are talking about the most efficient way would be zulo’s suggestion of making it into a statistical formula. Something where you can call a function with a time parameter and return the current population at that time. Nice side-effect of this approach is you can project future growth or do some sort of rewind time system.

The other option would be to use a parallel Job which is usually more efficient for this type of scale. Right now this is running on the main thread, with a job it could be running on multiple threads at the same time while the main thread does other stuff.

6

Could you walk me through how to use the jobs system? I actually tried to but I couldn’t figure out how. As for zulo’s suggestion, a lot of things reference an immediate population value rather than a value at some point in time, but perhaps making the sim keep track of its timestep could work in that area.

However there are also a lot of pops per tile so the tile would still need to iterate through them to get the total amount of pop change

7

I have only used jobs with systems and entities (ECS) so far so I am not certain what the structure would be for this. It will probably need to use managed data (structs instead of classes, native arrays/lists instead of arrays/lists, etc…).

This would probably be a good place to start Unity - Scripting API: IJob

8

what does Deep Profiler view of that code look like?

9

Are there limitations to using structs? And how much would I need to rewrite?

10

image
image1249×219 14.4 KB

11

There are a lot of moving parts in your classes that I don’t exactly know where they come into play. At a basic level you would need to move all the tile and pop functions into the job and make them both structs that just hold the data. The job then just changes the data every tick.

There might be simpler solution to improve performance of your current system. Use batching in tickTiles() so that it only updates a some of the tiles per tick. Once every tile has been updated it loops around and starts again. This will cause some latency, but it shouldn’t be noticeable or affect the simulation. Not sure this example is functional (might have an off by 1 error), but the general structure is taken from a batched system I have.

var batchSize = 1000;
var batchIndex = 0;

// Function to update pops
void tickTiles(){
    var totalBatches = (int)(tiles.Length + batchSize - 1) / batchSize; //The total number of batches
    batchIndex = (batchIndex + 1) % totalBatches; //The next batch to process
    var batchStartIndex = batchIndex * batchSize; //Current batch start index
    var batchEndIndex = (int)Mathf.Min(batchStartIndex + batchSize, tiles.Length); //Current batch end index
    for(int i = batchStartIndex; i < batchEndIndex; i++)
        {
            Tile tile = tiles[i];
            if (tile.population > 0)
            {
                tile.GrowPopulation();
            }
        }     
    }

With this you can decrease the batch size to get more performance at the cost of more latency, or vice-versa.

12

Do you have any examples of converting a project like this into a job system?

13

Not really, the jobs I have made were purpose built for pure ECS projects and would be more confusing than helpful. I threw your code at ChatGPT and it seems to have given pretty solid foundation to convert it to use a IJobParallelFor.

Instead of me posting GPTs response, try this prompt and include the same code you put in your original post
I have some Unity scripts and I want to improve the performance by making the tickTiles into a parallel job without using ECS. {code}

14

First you can use job with managed data (classes, reference types), however you have to use a 3rd party wrapper such as:

Second you can have both Job and Burst if you can rewrite your code with blittable data instead. Burst is really, really fast, it would blow your mind. So it’s best to consider the blittable data approach first. You should only fall back to the managed job at worst.

Either way, you have to rework your code to fit into the Job model. I think the most crucial part is having a clear separation between data and logic. Either structs or classes they should not contains any method that will be a part of the main logic. The logic in return should be designed as utility (or static) APIs.

For example, instead of pop.GrowPopulation(), you should have var x = PopAPI.GrowPopulation(pop, ...).

The 2 might look alike but they are not. The latter requires you to think of the logic as a transformation:

function
function215×212 3.49 KB

For the Pop.GrowPopulation method, you should analyse the input and output data it needs, then look for a way to model them separately. Also, any reference contained in Pop class and used in GrowPopulation should be broken into some kind of data as well. With structs you generally have no reference, only copies of a value. There are some ways to get reference to structs but that will come later when you understand the basis.

The input and output then become the fields of the job, the logic of “grow population” becomes the Job.Execute method (just think of it as static method). Superficially the job would look like this:

public struct GrowPopulationJob : IJob
{
    // public input data 1
    // public input data 2
    // ...
    
    // public output data
    
    public void Execute()
    {
        // transform input into output
    }
}

Note that, input data can be passed by value into the job because you only read their values. But to receive output data when the job is done, you must store the output in some kind of container. For example: NativeReference (array of length 1), NativeArray, etc.

There are differences between them. You should read this comparison:

There is 1 correction: since C# 10, structs can have default constructor. C# 10 is partially available in Unity 2022 and newer but have to be enabled via csc.rsp.