Parrallel processing in games & applications

Post all other topics which do not belong to any other category.
User avatar
boskid
Factorio Staff
Factorio Staff
Posts: 2964
Joined: Thu Dec 14, 2017 6:56 pm
Contact:

Re: Parrallel processing in games & applications

Post by boskid »

blazespinnaker wrote: Sat May 07, 2022 8:45 pmWube limits it to user input for reasons that they have never made clear.
I am feeling like being trolled by responding to this but i will answer anyway to have something to link to in the future.

Determinism in context of factorio is basically a property that when you have game state S at tick t (lets call this S_{t}) and set of input actions to be applied in that tick (lets call those I_{t}), a result of the game update function Update is same for all players:

Code: Select all

S_{t+1} = Update(S_{t}, I_{t})
When a player joins the game, server saves the game to a save file (which is basically entire S_{t}), sends it to another player so both players have the same starting point. If server and client also have the same input actions, under assumption of determinism they will get exactly the same state in the next tick S_{t+1}. Similar to mathematical induction, since the base case holds (due to save transfer) and induction step holds (due to input action broadcasting and deterministic update), client and server will stay in sync for entire duration of client connection to a server as long as all the I_{t+x} are guaranteed to be the same. That means when you want to get a data from a game state, there is no need to transfer anything through a network because server and every client has those values and they are equal.

You can read slightly more about "part of game state" in my other post in this topic

Since there is literally no good reason sending anything being "part of game state" through a network (it would not be carrying any new information as every client already knows about those), only reason to send an input action is literally to introduce data available only one of the machines (which means those are not part of game state) and which are supposed to affect state of the game.

Player interactions are the most obvious source of the input actions, but those are not the only ones.

All server console commands issued through RCON are also broadcasted through InputActions to all clients because if such command changes game state, scripts on all clients have to apply exactly same changes. If a server command says "add 100 iron plates to entity X because they are being sent from another clusterio node", all clients that are already connected need to know that the amount of items in a given inventory is to be changed and this cannot be deduced from game state in previous tick alone - those are broadcasted as input actions.

There is also third source of input actions, it is really subtle but it is one which is under mods control: it is a LuaPlayer::request_translation call. As it is implemented, all game instances not related to the given player are simply ignoring those LuaPlayer::request_translation calls, but the one instance which is of related player does the translation of LocalisedString into a regular string and then this string is sent through an InputAction so all other script instances will get the same value. In theory it should be relatively easy to abuse this mechanism by requesting translation of complex localised string with the data to be broadcasted and simply ignoring the translation result: in that case instance of a mod running on one client, even when being in a desync state (having some state differences to other clients) could properly introduce those data to other clients.

Now when all the important technical bits were explained, i can give you 2 reasons why we do not allow mods to send input actions:

1/ Throughput of internet connections and scaling. If your mod would need to send 100 bytes of input actions every tick for every client, that is basically a 100 * 60 * N bytes of data incoming to the server every second. Since the server is doing a broadcast of those input actions to all connected players, now server has to send a total stream of 100 * 60 * N * N bytes every second. Lets assume N = 100 players (even when i saw games where N was going up to 500). That gives 60MB of data to send by the server every second. Its basically 480Mbps of upload from the server side and its only 100 bytes every tick. This is not acceptable, by having N in square it becomes large really fast. Because of that we try to send as few data through input actions as possible and only in reaction to some reasonable events and when events are going more often (even player moving cursor from one entity to another is sent through an input action as a selection changed input action) they can take down to 3 bytes (where 1 is input action type, 1 is player index and 1 is encoded position in a coarse grid around last selection position).

2/ Design of scripting support assumes scripts should not have anything in their state that is not part of game state. That means we never expose anything not part of game state through a Lua-API and as such we never give any reasons for mods to need to send an InputAction. It is a lot easier to write a correct mod that is only based on a data which are part of game state compared to what it would be if you would have access to non game state data. In case of access to non game state data, literally every Lua-API read/write/call would also need to have sets of remarks which would be only useful for advanced mod developers and incorrect usage of them would almost always mean a super hard to understand or reproduce desync event.
Those remarks would need to touch details such as:
- remark if given access is causing game state changes - there are even some places where a read operation is causing game state changes.
- remark if given variable is part of game state - usage of values which are not part of game state to make a direct game state change would immedaitely cause a desync as they violate our assumption of deterministic update (mod script update is part of the update). Those values would need to be sent through input actions to be correctly introduced for every script instance.
- remark if given variable is accessible at all on every instance - for example a headless server will not have any local players.

I am aware it would be powerful to write scripts which would be aware of local player and doing some computation only on one instance (first example i could think of is a helmod which could find a solution using CPU power of the player requesting the computation and then sending the results through input actions - that would make other players with slower CPU not be punished by other player using this tool), or they could access some data that were previously not accessible (like local clock or last tick time measurements), or even interact with latency state (absurdly non realistic, that would be a separate API to maintain which we do not want to go into). I am simply not sure if it makes sense to introduce scripting API which would be hard to correctly use, hard to debug and having only a tiny benefits (maybe there are some with huge benefits).
blazespinnaker
Filter Inserter
Filter Inserter
Posts: 665
Joined: Wed Sep 16, 2020 12:45 pm
Contact:

Re: Parrallel processing in games & applications

Post by blazespinnaker »

Thanks, great clarity there. Nothing but respect.

"add 100 iron plates to entity X because they are being sent from another clusterio node"

fwiw, this was precisely what I described above. And now looks to me that it is fully supported via lua comms. sigh.

I think there is some arbitrary json serdes going with clusterio rather than basic rcon, I can imagine different approaches to supporting that.
OptimaUPS Mod, pm for info.
-Holo-
Burner Inserter
Burner Inserter
Posts: 15
Joined: Thu Feb 04, 2021 7:26 pm
Contact:

Re: Parrallel processing in games & applications

Post by -Holo- »

It feels like it's long overdue to get more use of cores from gaming.
In Factorio's case I'd guess Bot pathing, Biter AI and Train pathing should probably be beneficial to have their own threads to live in.

Train network and Biter AI are the two things that get massive framedrops when they change in my current game (also running dangerously close to not being able to catching up when joining)
(Server Ryzen 5600G, PC Ryzen 5600X)
azesmbog
Filter Inserter
Filter Inserter
Posts: 254
Joined: Mon Jan 28, 2019 12:05 pm
Contact:

Re: Parrallel processing in games & applications

Post by azesmbog »

-Holo- wrote: Wed Aug 03, 2022 7:41 pm It feels like it's long overdue to get more use of cores from gaming.
(Server Ryzen 5600G, PC Ryzen 5600X)
Everything is exactly the opposite.
The fewer cores, the faster Factorio works :)
16core.jpg
16core.jpg (59.31 KiB) Viewed 5467 times
Results with factoriobox, if that.
-Holo-
Burner Inserter
Burner Inserter
Posts: 15
Joined: Thu Feb 04, 2021 7:26 pm
Contact:

Re: Parrallel processing in games & applications

Post by -Holo- »

azesmbog wrote: Wed Aug 03, 2022 8:29 pm
-Holo- wrote: Wed Aug 03, 2022 7:41 pm It feels like it's long overdue to get more use of cores from gaming.
(Server Ryzen 5600G, PC Ryzen 5600X)
Everything is exactly the opposite.
The fewer cores, the faster Factorio works :)
16core.jpg
Results with factoriobox, if that.
Exactly the point, A multithreaded system with good threaded support should run circles around an old core2duo.
Rseding91
Factorio Staff
Factorio Staff
Posts: 14247
Joined: Wed Jun 11, 2014 5:23 am
Contact:

Re: Parrallel processing in games & applications

Post by Rseding91 »

-Holo- wrote: Wed Aug 03, 2022 9:40 pm Exactly the point, A multithreaded system with good threaded support should run circles around an old core2duo.
I don't see any old core2duo in that CPU list; but I do see a CPU released within the last 6 months on the latest manufacturing process with amazing single core performance.
-Holo- wrote: Wed Aug 03, 2022 7:41 pm It feels like it's long overdue to get more use of cores from gaming.
In Factorio's case I'd guess Bot pathing, Biter AI and Train pathing should probably be beneficial to have their own threads to live in.

Train network and Biter AI are the two things that get massive framedrops when they change in my current game (also running dangerously close to not being able to catching up when joining)
(Server Ryzen 5600G, PC Ryzen 5600X)
Could you provide your save file? I can profile it and show where exactly the time is spent. Based off all of the profiling I've done over the years I doubt it's spent where you think it actually is.
If you want to get ahold of me I'm almost always on Discord.
-Holo-
Burner Inserter
Burner Inserter
Posts: 15
Joined: Thu Feb 04, 2021 7:26 pm
Contact:

Re: Parrallel processing in games & applications

Post by -Holo- »

Rseding91 wrote: Wed Aug 03, 2022 10:43 pm
-Holo- wrote: Wed Aug 03, 2022 9:40 pm Exactly the point, A multithreaded system with good threaded support should run circles around an old core2duo.
I don't see any old core2duo in that CPU list; but I do see a CPU released within the last 6 months on the latest manufacturing process with amazing single core performance.
-Holo- wrote: Wed Aug 03, 2022 7:41 pm It feels like it's long overdue to get more use of cores from gaming.
In Factorio's case I'd guess Bot pathing, Biter AI and Train pathing should probably be beneficial to have their own threads to live in.

Train network and Biter AI are the two things that get massive framedrops when they change in my current game (also running dangerously close to not being able to catching up when joining)
(Server Ryzen 5600G, PC Ryzen 5600X)
Could you provide your save file? I can profile it and show where exactly the time is spent. Based off all of the profiling I've done over the years I doubt it's spent where you think it actually is.
Sorry it was a Celeron, still same deal. Sure, I can try to remember to upload it to dropbox or something tomorrow.
FuryoftheStars
Smart Inserter
Smart Inserter
Posts: 2768
Joined: Tue Apr 25, 2017 2:01 pm
Contact:

Re: Parrallel processing in games & applications

Post by FuryoftheStars »

-Holo- wrote: Wed Aug 03, 2022 10:52 pm Sorry it was a Celeron, still same deal.
Rseding91 wrote: Wed Aug 03, 2022 10:43 pm I don't see any old […] but I do see a CPU released within the last 6 months on the latest manufacturing process with amazing single core performance.
Emphasis mine. Rseding91’s point is that it’s not old, not by a long shot. (edit: reduced image dimensions)
FFC19258-5E31-4203-99EB-340746ECD2A5.jpg
FFC19258-5E31-4203-99EB-340746ECD2A5.jpg (62.01 KiB) Viewed 5432 times
Edit:
I also find this interesting (added architects and release dates to the image from the earlier post):
comparison with architecture and release dates.png
comparison with architecture and release dates.png (302.42 KiB) Viewed 5414 times
Also, what are the 2 columns of numbers there? Average result of tests (if so, it's not accurate) and the individual results of tests? Why does the 8-core get five tests and the Celeron one?
(Oh, and that 8 core? Based on what I can find, it's 6.)

Finally, comparing AMD score to Intel score I feel like doesn't mean much, especially considering the differences between AMD and Intel and that the hardware is obviously going to be different between the two setups. Trying to show how much better a dual core is over an 8-core I feel would have more meaning if they were both from the same brand, using the same architecture and subsequent hardware in the PC, with the same tests performed the same number of times between both.

Just saying.
My Mods: Classic Factorio Basic Oil Processing | Sulfur Production from Oils | Wood to Oil Processing | Infinite Resources - Normal Yield | Tree Saplings (Redux) | Alien Biomes Tweaked | Restrictions on Artificial Tiles | New Gear Girl & HR Graphics
azesmbog
Filter Inserter
Filter Inserter
Posts: 254
Joined: Mon Jan 28, 2019 12:05 pm
Contact:

Re: Parrallel processing in games & applications

Post by azesmbog »

I'm sorry. I only messed up one number.
Here are much more revealing figures, on a heavier map
4core.jpg
4core.jpg (96.19 KiB) Viewed 5385 times
2-core celeron, Q4'15
https://ark.intel.com/content/www/ru/ru ... 0-ghz.html
4-core 6400 (non-K ) , Q3'15
https://ark.intel.com/content/www/ru/ru ... 0-ghz.html
Compare with the results of more modern and multi-core processors, there are many of them in this sample.
This is a very revealing map.
https://factoriobox.1au.us/results/cpus ... =1.0.0&vh=
And these are the correct results in Windows, I don’t consider the results in Linux valid for myself for some reason :)
upd:
AMD Ryzen 5 5600G 6-Core 12-Thread Unlocked
Yes, here I also slightly overestimated the cores / threads.
but even 12 modern streams against 2 old ones is somehow too much. Is not it?

And here is the correct result to the first table
https://factoriobox.1au.us/result/31b10 ... e3f67f1447
156 UPS
This is an even more shameful result for all the results from the first table, and even for that modern Celeron
gGeorg
Filter Inserter
Filter Inserter
Posts: 436
Joined: Wed Jun 19, 2019 8:06 pm
Contact:

Re: Parrallel processing in games & applications

Post by gGeorg »

boskid wrote: Sat May 07, 2022 10:54 pm I am feeling like being trolled by responding to this but i will answer anyway to have something to link to in the future.

Determinism in context of factorio is ...
Thank you for a Friday fact article. :-) For some reason it is satisfying to read a deep technical stuff, just to know that someone else think and work hard to offer me a well made game. Quality and chasing perfection quest is in current software world a very rare flower.
FuryoftheStars
Smart Inserter
Smart Inserter
Posts: 2768
Joined: Tue Apr 25, 2017 2:01 pm
Contact:

Re: Parrallel processing in games & applications

Post by FuryoftheStars »

azesmbog wrote: Thu Aug 04, 2022 7:00 am [...]
I'm sorry, but you gotta start looking at these better and noting the difference between some of the numbers you are citing.
(And before I go any further, disclaimer: I'm not debating the multi-threaded status of Factorio. I'm just trying to illustrate a point that if you're going to use this kind of method to "test" for the "multi-threaded status" of a game (which, btw, I think is highly error prone without knowing the code internals of the game), then you need to standardize as much as possible.)
azesmbog wrote: Thu Aug 04, 2022 7:00 am This is a very revealing map.
https://factoriobox.1au.us/results/cpus ... =1.0.0&vh=
So, first off, it says right at the top of that page:
Results vary depending on CPU clock, memory clock, memory timings, etc., so take these numbers with a grain of salt.
And this becomes more evident when you compare these 2:
azesmbog wrote: Thu Aug 04, 2022 7:00 am 2-core celeron, Q4'15
[...]
4-core 6400 (non-K ) , Q3'15
[...]
Several of the results recorded are using different RAM counts with different MHz. Considering how RAM heavy this game is compared to others, that makes a difference.

Further, if I'm reading that list correctly, the 4 core out performed the dual core anyway? As it should?

Finally, I want to hammer at this:
azesmbog wrote: Thu Aug 04, 2022 7:00 am And here is the correct result to the first table
https://factoriobox.1au.us/result/31b10 ... e3f67f1447
156 UPS
This is an even more shameful result for all the results from the first table, and even for that modern Celeron
You're bouncing between results from different test maps. If you want to compare numbers, pick one and stick with it, or at the very least make it especially clear in your post which maps the different results go to rather than depending on the reader to follow the link through and happen to notice that part at the top of the page is slightly different than on the others.
My Mods: Classic Factorio Basic Oil Processing | Sulfur Production from Oils | Wood to Oil Processing | Infinite Resources - Normal Yield | Tree Saplings (Redux) | Alien Biomes Tweaked | Restrictions on Artificial Tiles | New Gear Girl & HR Graphics
Koub
Global Moderator
Global Moderator
Posts: 7764
Joined: Fri May 30, 2014 8:54 am
Contact:

Re: Parrallel processing in games & applications

Post by Koub »

For people thinking Factorio doesn't make use of multicore/multithread, I guess one could use this method (or anything similar) and compare the performance on their own CPU if it does make a difference. I have never felt the urge to do it myself, so I can't tell if it works, never been able to stress my CPU enough to get under 60 UPS.
Koub - Please consider English is not my native language.
Xoriun
Long Handed Inserter
Long Handed Inserter
Posts: 69
Joined: Wed Apr 01, 2020 11:31 am
Contact:

Multithread the entity update phase

Post by Xoriun »

Would it be possible to somehow multithread the entity update phase of the game loop?
At least on the large bases I build, most of the update time (between ~12 ms at ~55 UPS) is spend on the entity phase, so any optimization there would be really nice.
I gave this some thought and would like to know your opinion on if this would be feasible to implement.

The map/factory would be divided into several groups of chunks, such that between chunks of different groups there are no connections that have to be processed within the entity phase. Then those groups could be processed in parallel.

As I understand it, this would still allow to have connections between those groups that consist of belts, rails, electric networks, circuit networks and fluid/heat pipes.
Entities that would combine chunks into groups would be inserters with pickup and drop-off location in different chunks, assemblers/chem plants/miners/pump-jacks/refineries/roboports/labs/silo/gun turrets on chunk borders and beacons with effect range over different chunks.
I don't know how biters and bots (networks) together with their pathfinding would impact this.
Did I miss(understand) anything?

The other part that I'm not sure about is how to efficiently split up a group into two when deconstructing an entity.

As said, I would just like to know your opinion on this.
Nidan
Filter Inserter
Filter Inserter
Posts: 267
Joined: Sat Nov 21, 2015 1:40 am
Contact:

Re: Multithread the entity update phase

Post by Nidan »

Do you mean similar to what was discussed in FFF 151? There's also a bit of an followup in FFF 176.
User avatar
Stringweasel
Filter Inserter
Filter Inserter
Posts: 411
Joined: Thu Apr 27, 2017 8:22 pm
Contact:

Re: Multithread the entity update phase

Post by Stringweasel »

Belts are multitheaded as also discussed in FFF-364. It's also mentioned in ALTF4-52 that there's an electric network thread, heat transfer thread, a few fluid calculation threads (assuming I understood the the person correctly).

It something isn't threaded at this point it's likely because the likely performance gain is debatable, or it would require too big of a rewrite. :D
Alt-F4 Author | Factorio Modder
My Mods: Hall of Fame | Better Victory Screen | Fluidic Power | Biter Power | Space Spidertron | Spidertron Dock | Weasel's Demolition Derby
Official Contributor to Space Exploration
Xoriun
Long Handed Inserter
Long Handed Inserter
Posts: 69
Joined: Wed Apr 01, 2020 11:31 am
Contact:

Re: Multithread the entity update phase

Post by Xoriun »

With entity phase I mean the part of the main loop which appears as "Entity update" in the debug option "show-time-usage".
Afaik, this is one single thread and contains production entities (assemblers, furnaces, etc.) and inserters. As stated in the first post, I'm not sure about where/when bots and biters are processed.

I know that other parts of the main loop already run in parallel or have their own phase of the main loop, such as belts, pipes, heat, electricity, circuits, trains.
These are not included in my idea.
Rseding91
Factorio Staff
Factorio Staff
Posts: 14247
Joined: Wed Jun 11, 2014 5:23 am
Contact:

Re: Multithread the entity update phase

Post by Rseding91 »

If you want to get ahold of me I'm almost always on Discord.
Xoriun
Long Handed Inserter
Long Handed Inserter
Posts: 69
Joined: Wed Apr 01, 2020 11:31 am
Contact:

Re: Multithread the entity update phase

Post by Xoriun »

Thank you, that was quite a read (though I only read the dev's replies). I didn't think to search in General discussion...

If I understood that thread correctly, that part that mostly affects my idea is viewtopic.php?p=479362#p479362, as in: multithreading the entities would not help since RAM latency is the real bottleneck in the entity update, right?
User avatar
ssilk
Global Moderator
Global Moderator
Posts: 12889
Joined: Tue Apr 16, 2013 10:35 pm
Contact:

Re: Multithread the entity update phase

Post by ssilk »

Yes. The actual bottleneck is the RAM, not CPU.
Cool suggestion: Eatable MOUSE-pointers.
Have you used the Advanced Search today?
Need help, question? FAQ - Wiki - Forum help
I still like small signatures...
Koub
Global Moderator
Global Moderator
Posts: 7764
Joined: Fri May 30, 2014 8:54 am
Contact:

Re: Parrallel processing in games & applications

Post by Koub »

[Koub] Merged into the main thread about multithreading.
Koub - Please consider English is not my native language.
Post Reply

Return to “General discussion”