aliens needs multithreading :/

[hypertrax99]

Hi,

after i researched artillery range my fps drops from 60 to 6 :O,
i play with enemy base frequency & size max, enemy max expansion distance 2

i have a big map (savegame 90mb), 5 min later i have around 13 fps, now i have to wait until all death, hmm

my kills after i researched artillery range, but not all death, with 6 fps it needs time ^^

20190504161959_1.jpg (629.05 KiB) Viewed 8660 times

[TheTom]

Not so much biters (though the higher strategy there and pathfinding also needs, agree) as Radars and artillery. Basically every cannon should have targets identified in a separate job which gets distributed to the thread pool. Possibly this can happen in parallel (!) with other isolated phases (i.e. fluid or belt movement) so that high core count processors use them.

Simple as it is.

[PunkSkeleton]

It's the biters not artillery. FPS go up when biters die not when cannons stop shooting.

[FrodoOf9Fingers]

I would think that its the combination of the two: determining whether a biter is range of an artillery station is generally the same algorithm as collision detection. Since artillery has a very large range, I would assume whatever algorithm they use has to calculate many more distances. The more biter bases or the more artillery, the longer it'll take

[hypertrax99]

its not the artillery, just the biters

after i finished the research i see the artillery fire and i have still 60fps, but when they destroy the targets its over, fps goes down
to much biters who search a path maybe, its annoying

factorio uses just ~13% CPU at this moment, 1 core nearly 100%, rest nearly nothing (have 8 cores)

they must find a way to uses more cores for the aliens, its useless at this point, how long should i wait until the aliens goes down...with 6 fps 1min ingame needs 10min in real life? -.-
unplayable at this moment, just can load the game in background and do other things, that can't be a solution

[Ormy]

I have a similar experience. All map generation biter-related settings are at default however I'm using some biter mods: Rampant, Schall Endgame Evolution and Swarmageddon. I have increased the spawn rate using Rampant settings.

My factory is at around 300-400 SPM and I've launched 300-400 rockets (around 500k-600k entities total), the game runs at solid 60 fps/ups for a while (can be anything from 30 mins to two hours) then gradually fps/ups starts to slowly drop to around 35-40, then I use a console command to kill all biters and the fps/ups jumps back to 60 for a few hours.

You can use a debug option (forget the name) to show what mods or scripts are using compute time, really helpful to diagnose causes of slowdowns.

[Hannu]

they must find a way to uses more cores for the aliens, its useless at this point, how long should i wait until the aliens goes down...with 6 fps 1min ingame needs 10min in real life? -.-

Parallel processing of entities have problems with determinism which is needed in multiplayer. They can be solved but it is hard and takes significant amount of speed benefit. I would not expect devs to put such an effort. They have tested parallel processing but decided to reject it. I personally would give multiplayer game away to get maximum performance but I think at least 90 % players disagree.

unplayable at this moment, just can load the game in background and do other things, that can't be a solution

You have broken the game with huge area and extreme settings. There are always limits, whatever devs do, and current game can handle exceptionally massive factories. I would use commands to clear biters.

[TheTom]

Sorry, that is ignorant.

Parallel processing has NO issues with determinism when there is no dependency.

i.e. all Artillery could scan the areas for posible targets at the same time, add them to a list whiech then is combined and multiple removed, single threaded, possibly at the same time, i.e. as fluid runs. Whether a specific coordinate is a posible target is not depending on other artillery.

The main point is actually sitting down and using intelligence to determine where determinism is irrelevant.

They do that already in the new fluid simulation, i.e., which is actually using multiple threads as every fluid system is 100% independent of any other fluid system. You can do that a LOT more and still maintain full determinism.

The example they DID try was - sorry - not smart to start with. There would be no problem (except bandwidth obviously for multiplayer) using multiple threads to handle entities in multiple "clusters". At least when you go large base and use trains you get a lot of non-deterministic clusters anyway - every mining outpost I ever did is one, and in my case actually every facbrication "cell" would be one too (as it is far enuogh from other cells and all goods are moved by train only).

The fact that their initial try did only yield 20% gain is an immense sign that the people doing it later (i.e. the new fluid simulation) knew a lot more what they are doing. Sorry

Obviously network tuns into a bottleneck fast, but that is just a multiplayer scalability issue, one that can not be avoided.

[ratchetfreak]

You example isn't complete, the order of targets in the final list matters, so that needs to be deterministic which you can do by sorting. However then you end up with a super-linear complexity operation on the main thread that cannot be parallelized.

It is quite likely that the main-thread overhead of all that (don't forget the communication between threads is not free) is greater than just scanning in the main thread.

Blindly paralellizing is nearly always a bad thing.

[FrodoOf9Fingers]

You example isn't complete, the order of targets in the final list matters, so that needs to be deterministic which you can do by sorting. However then you end up with a super-linear complexity operation on the main thread that cannot be parallelized.

Are you saying that aorting cannot be threaded? I'm not 100% certain about quicksort (as it uses several sorts ubderneath that i forget), but merge sort certainly does well being threaded.

But it shouldn't be much of an issur anyways, consider the order that robota build things. I think it is by chuck, upper left to bottom right, the same could be true for selecting targets for artillery as reducing function allowing for deterministic results from threading the target for the nect artillery shot.

[ratchetfreak]

You example isn't complete, the order of targets in the final list matters, so that needs to be deterministic which you can do by sorting. However then you end up with a super-linear complexity operation on the main thread that cannot be parallelized.

Are you saying that aorting cannot be threaded? I'm not 100% certain about quicksort (as it uses several sorts ubderneath that i forget), but merge sort certainly does well being threaded.

But it shouldn't be much of an issur anyways, consider the order that robota build things. I think it is by chuck, upper left to bottom right, the same could be true for selecting targets for artillery as reducing function allowing for deterministic results from threading the target for the nect artillery shot.

you are underestimating the overhead of inter-thread communication.

At the very least each job requires that it is pushed into a thread safe queue, then popped from the job thread, then executed, then result pushed into result queue, then popped by the main thread, main thread then needs to concatenate and sort and then handle the valid targets.

Yes the concat and sort can be a n-way merge. But that is still super linear.

And between the job push and the last pop no modification of the map is allowed which limits what the main thread can do

For a lot less compute power the main thread do the query itself fully deterministically and in O(n) time.

[mrvn]

You example isn't complete, the order of targets in the final list matters, so that needs to be deterministic which you can do by sorting. However then you end up with a super-linear complexity operation on the main thread that cannot be parallelized.

Are you saying that aorting cannot be threaded? I'm not 100% certain about quicksort (as it uses several sorts ubderneath that i forget), but merge sort certainly does well being threaded.

But it shouldn't be much of an issur anyways, consider the order that robota build things. I think it is by chuck, upper left to bottom right, the same could be true for selecting targets for artillery as reducing function allowing for deterministic results from threading the target for the nect artillery shot.

There is a sorting algorithm for parallel sorting that is something like O(log n * log log n). It's defined recursively and starts with: For problems < 1000000 sort with your preferred sorting algorithm. It then describes how to parallelize larger problems by splitting them into iirc sqrt(n) parts. The whole thing is so complex that anything below a million entries is considered a trivial chunk. Think about that.

[Rseding91]

i.e. all Artillery could scan the areas for posible targets at the same time, add them to a list whiech then is combined and multiple removed, single threaded, possibly at the same time, i.e. as fluid runs. Whether a specific coordinate is a posible target is not depending on other artillery.

You are in fact wrong. What a given artillery is targeting does effect what the next artillery can target. It's what prevents artillery from over-shooting at any given set of targets.

... The fact that their initial try did only yield 20% gain is an immense sign that the people doing it later (i.e. the new fluid simulation) knew a lot more what they are doing. Sorry

Now that's just ignorant. You know nothing of how Factorio works internally.

Entities that need to update have a ton of state they potentially mutate each tick. Pipes do not.

Pipes have distinct connections which don't change during the pipe update and as such for any given set of connected pipes they never touch any other connected set of pipes. That's called a https://en.wikipedia.org/wiki/Embarrassingly_parallel workload where you can split the work over multiple cores in O(1) time.

Try to answer this for me: how many different shared data sets do you think a single biter can touch during its ::update() function? A minimum and maximum.

For example for "fish" you could say "the chunk - since they move".

[mrvn]

i.e. all Artillery could scan the areas for posible targets at the same time, add them to a list whiech then is combined and multiple removed, single threaded, possibly at the same time, i.e. as fluid runs. Whether a specific coordinate is a posible target is not depending on other artillery.

You are in fact wrong. What a given artillery is targeting does effect what the next artillery can target. It's what prevents artillery from over-shooting at any given set of targets.

... The fact that their initial try did only yield 20% gain is an immense sign that the people doing it later (i.e. the new fluid simulation) knew a lot more what they are doing. Sorry

Now that's just ignorant. You know nothing of how Factorio works internally.

Entities that need to update have a ton of state they potentially mutate each tick. Pipes do not.

Pipes have distinct connections which don't change during the pipe update and as such for any given set of connected pipes they never touch any other connected set of pipes. That's called a https://en.wikipedia.org/wiki/Embarrassingly_parallel workload where you can split the work over multiple cores in O(1) time.

Try to answer this for me: how many different shared data sets do you think a single biter can touch during its ::update() function? A minimum and maximum.

For example for "fish" you could say "the chunk - since they move".

Unless the fish is at the edge of a chunk and then it can touch the next chunk too. Make it a corner and you have 4 chunks. Shared (mutating) data structures are a pain for multithreading.

But there is a difference between only reading shared data, reading shared data while some writes it and writing shared data. Taking the example of fish: Aren't they https://en.wikipedia.org/wiki/Embarrassingly_parallel since each simply swims around in brownian motion? Do fish even collide with each other or swim through each other?

For the aliens the most expensive operation is path finding, right? To me path finding falls into the "only reading shared data" category that is a https://en.wikipedia.org/wiki/Embarrassingly_parallel workload. At least once you merged aliens into groups that act independently. Or not?

[Rseding91]

I'll give you a detailed answer for both fish and biters but I first want someone to try to answer this:

How many different shared (mutable) data sets do you think the fish or biter can touch during its ::update() function? List them + a minimum and maximum.

[ratchetfreak]

I'll give you a detailed answer for both fish and biters but I first want someone to try to answer this:

How many different shared (mutable) data sets do you think the fish or biter can touch during its ::update() function? List them + a minimum and maximum.

The fish would be itself and the map chunk its in (being technically mutable even though only landfill is a factor for that) and neighbours for collision detection

The biters would need itself, the mapchunk and other entities close by for player/turret agro and collision detection. Once triggered for behavior (strike force/expansion force) the path its been assigned with again close-by entities for collision avoidance.

The trigger for strikeforce and expansion would need to touch a lot of data to select the proper target but that doesn't need to run every frame especially not for every biter every frame.

[mrvn]

I'll give you a detailed answer for both fish and biters but I first want someone to try to answer this:

How many different shared (mutable) data sets do you think the fish or biter can touch during its ::update() function? List them + a minimum and maximum.

Do you mean any data set it touches that may mutate over time. Or data sets that mutate during the "process all fish" phase. Because I think the fish should only modify itself and maybe the chunk when it crosses from one to the other. Things like the tile being landfilled won't happen while the fish calculates how to move so that isn't mutable at that stage of the process.

With collision detection I would do fish in two phases:

1) decide where to move.
2) update position.

First phase doesn't mutate anything but fish internal data no other fish may access so its trivially multithreaded. Phase 2 needs to lock the chunks involved when a fish moved from one chunk to another. Most fish won't cross chunk boundaries and those that do are unlikely to be in the same chunks. A simple lock on the chunk should have little congestion when updating the position multithreaded.

As for aliens. I have no idea what all the aliens do in ::update(). But I'm dead certain that could be split into different phases where some are trivial to multithread.


Problem is you (devs) mentioned that factorio is bottlenecked by the ram throughput. Accessing every fish twice might be slower even if 16 cores do that in parallel. What would greatly help is to group fish (say 1024 fish each) together into an array and process each group on one core. That way the memory access would be linear. That would require using custom allocators for factorio entities. A lot of work to retroactively add them but so many entities would benefit from grouping them together in memory and processing them in batches.

[draknor]

With collision detection I would do fish in two phases:

1) decide where to move.
2) update position.

First phase doesn't mutate anything but fish internal data no other fish may access so its trivially multithreaded. Phase 2 needs to lock the chunks involved when a fish moved from one chunk to another. Most fish won't cross chunk boundaries and those that do are unlikely to be in the same chunks. A simple lock on the chunk should have little congestion when updating the position multithreaded.
<snip>

But when you are doing phase 1 - how can you ensure that no other fish decides to move the same position as the fish you are processing? If Fish A and Fish B are both within range of the same tile, they could both decide to move to that tile - so what happens in phase 2 when Fish A moves to tile X, but now Fish B's movement is illegal? Do you recalculate phase 1 again for Fish B?

What happens when you have dozens or hundreds of fish, all moving this tick? And then adding the next layer of complexity - what if these fish have goals or objectives? So it's not just random movement, but now both Fish (Biter) A and Fish (Biter) B want to get close to the water pump (turret)? High likelihood of collisions in this scenario!

[Zavian]

Also if fish movement is random, then if you parallelize the fish choosing where to move next, then each fish (or group of fish) needs its own random number generator/seed, so that fish stay deterministic for multiplayer.

[mrvn]

With collision detection I would do fish in two phases:

1) decide where to move.
2) update position.

First phase doesn't mutate anything but fish internal data no other fish may access so its trivially multithreaded. Phase 2 needs to lock the chunks involved when a fish moved from one chunk to another. Most fish won't cross chunk boundaries and those that do are unlikely to be in the same chunks. A simple lock on the chunk should have little congestion when updating the position multithreaded.
<snip>

But when you are doing phase 1 - how can you ensure that no other fish decides to move the same position as the fish you are processing? If Fish A and Fish B are both within range of the same tile, they could both decide to move to that tile - so what happens in phase 2 when Fish A moves to tile X, but now Fish B's movement is illegal? Do you recalculate phase 1 again for Fish B?

What happens when you have dozens or hundreds of fish, all moving this tick? And then adding the next layer of complexity - what if these fish have goals or objectives? So it's not just random movement, but now both Fish (Biter) A and Fish (Biter) B want to get close to the water pump (turret)? High likelihood of collisions in this scenario!

First by moving away from other fished that are near now. You can read the other fishes current position and avoid all tiles reachable by other fishes. Sometimes that will mean a fish won't move because it is surrounded by fish but that is ok.

Second you don't need a random number generator per fish. When you split up the fish for multiple threads you need to do this deterministically and fork a random number generator for each group. So don't split the fish into <number of cores> chunk as that would differ on every system. Instead split them into groups of say 1024 fish and fork a RNG for it. Then distribute those groups across cores. No matter the order the groups are done or how many cores are used the result will be the same.