Parrallel processing in games & applications

Post all other topics which do not belong to any other category.
Jap2.0
Smart Inserter
Smart Inserter
Posts: 2338
Joined: Tue Jun 20, 2017 12:02 am
Contact:

Re: Parrallel processing in games & applications

Post by Jap2.0 »

BlueTemplar wrote:
Thu Mar 10, 2022 10:45 am
The rendering isn't going to be a performance bottleneck anyway... (unless maybe on very low power integrated graphic chips ?)
And of course, as already mentioned, it's already fully multithreaded.
Render preparation is CPU, iirc. I don't think it's generally a major bottleneck, though.
There are 10 types of people: those who get this joke and those who don't.

NotoriousPyro
Manual Inserter
Manual Inserter
Posts: 2
Joined: Sun Feb 27, 2022 9:31 pm
Contact:

Re: Parrallel processing in games & applications

Post by NotoriousPyro »

BenSeidel wrote:
Sat Mar 05, 2022 6:21 am
I disagree. Asynchronous means non-sequential programming, of which multithreading is one type. Or to be more specific, multithreading is a sub-set, or implementation, of Asynchronous programming.
Asynchronous programs can run on one thread or they can run on multiple threads. Asynchronous code is not related to multi-threadedness. Both are a way to concurrently run code, but they both approach the task differently.

Async code allows tasks to switch cooperatively, where each task signals when it is complete and can 'yield' to another task. All these tasks can operate in the context of one thread, or multiple threads.

In contrast, multi-threaded programs can be interrupted at any time by other threads, so for example you can have a long running task interrupted many times by other threads causing a context switches and synch overhead: https://pybay.com/site_media/slides/ray ... s-vs-async

https://www.youtube.com/watch?v=9zinZmE3Ogk

This image used to be in Mozilla's HQ. I think this says enough about how complicated it is to get multi-threadedness right.

Image

User avatar
lovewyrm
Inserter
Inserter
Posts: 42
Joined: Sun Apr 15, 2018 10:04 am
Contact:

Re: Parrallel processing in games & applications

Post by lovewyrm »

>functional programming
>haskell
There is no functional programming for computers. It's all imperative, not a single exception.
It cannot be escaped. Only coated over to an extent.

Somewhere, somehow, there is always the important core of having things in a specific order, in a specific way, for a specific goal.
Don't know if I should accept the notion that parralellism is easy on that front, then...

blazespinnaker
Filter Inserter
Filter Inserter
Posts: 532
Joined: Wed Sep 16, 2020 12:45 pm
Contact:

Re: Parrallel processing in games & applications

Post by blazespinnaker »

There's an fff link somewhere, the big gap was processing chunks in parallel. It seems pretty doable, hopefully it will get addressed in the dlc upgrade, though as mentioned the already threaded belt logic is a bit of a memory bottleneck, but in theory you can minimize your belts to get around that. Dunno if wube will priortize that use case tho
OptimaUPS Mod, pm for info.

Rseding91
Factorio Staff
Factorio Staff
Posts: 12209
Joined: Wed Jun 11, 2014 5:23 am
Contact:

Re: Parrallel processing in games & applications

Post by Rseding91 »

blazespinnaker wrote:
Sat Apr 30, 2022 8:06 pm
... It seems pretty doable ...
It's not.
If you want to get ahold of me I'm almost always on Discord.

BenSeidel
Filter Inserter
Filter Inserter
Posts: 581
Joined: Tue Jun 28, 2016 1:44 am
Contact:

Re: Parrallel processing in games & applications

Post by BenSeidel »

Rseding91 wrote:
Sat Apr 30, 2022 8:28 pm
It's not.
To expand on this a bit (it's also explained elsewhere). It's not [easy to parallelise on chunk boundaries] because the factory behaviour can't be affected by the chunk boundaries (ie, blueprint translational symmetry).

Rseding (and the team) has spent quite a lot of time fixing bugs where builds don't work in one location when compared to another because chunk boundaries affected the order that entities were processed. If this wasn't the case we wouldn't have the awesome blueprints we have because they would only work in one rotation or at specific chunk boundaries. A fact that we should be eternally grateful to him and the rest of the team for doing.

Unfortunately, there is no way to process each chunk independently with the above constraint.

blazespinnaker
Filter Inserter
Filter Inserter
Posts: 532
Joined: Wed Sep 16, 2020 12:45 pm
Contact:

Re: Parrallel processing in games & applications

Post by blazespinnaker »

Well, you could probably define meta-chunks, eg, 16x16 chunks or something. Or maybe one thread per surface at a minimum, though maybe it's already like that I guess. Certainly the per surface approach opens up a lot of potential for the dlc if it leverages that. Maybe they could even fix the per surface production tracking while they are at it :)

Reading back, it seems that it's not one thread per surface. That seems like a shame, tbh. It'd be interesting to see what the benchmark blueprints look like and how much belting you need to do before it saturates the cache.

Direct insert can be quite elegant at times.


Part of the problem (but also a boon) is that wube has gone all in on unit testing. Hard to change things without breaking those tests and rewriting them can be challenging, depending on how they're done. But it's not all bad, the stability of factorio is one of its greatest selling points I think. Speedrunning itself is so compelling because there are so few if any exploits.

I suppose the lack of multithreading also contributes to the stability. So there is that.
OptimaUPS Mod, pm for info.

robot256
Filter Inserter
Filter Inserter
Posts: 428
Joined: Sun Mar 17, 2019 1:52 am
Contact:

Re: Parrallel processing in games & applications

Post by robot256 »

Different surfaces aren't really separate. There are cross-surface effects (like linked chests, electric networks, teleport commands, and mod scripts in general) that would become difficult edge cases if it were split up that way.

Rseding91
Factorio Staff
Factorio Staff
Posts: 12209
Joined: Wed Jun 11, 2014 5:23 am
Contact:

Re: Parrallel processing in games & applications

Post by Rseding91 »

blazespinnaker wrote:
Sun May 01, 2022 2:39 am

Part of the problem (but also a boon) is that wube has gone all in on unit testing. Hard to change things without breaking those tests and rewriting them can be challenging, depending on how they're done. But it's not all bad, the stability of factorio is one of its greatest selling points I think. Speedrunning itself is so compelling because there are so few if any exploits.
This depends on how people define "unit test". To me a unit test is a test that in-isolation tests that 1 exact piece of code/class/function to do exactly what it thinks it should be doing. The other definition in my head is "integration test" which sets up some state, performs some operation, and checks that the result it expected happened. How that result was processed didn't really matter just that the expected state was the result.

Using this definition; 95%+ of Factorio's tests are "integration tests." We can re-factor and re-work code largely without needing to go back and "fix" tests afterword because they don't care how the in-between-update happened just that the end result of the test logic running was that the condition was fulfilled. For example: an entity being deconstructed by robots has its items removed first and the result storage chest ends up with all the expected items and the item to place the entity. If that happened in threads or not the test doesn't really mind.
If you want to get ahold of me I'm almost always on Discord.

Rseding91
Factorio Staff
Factorio Staff
Posts: 12209
Joined: Wed Jun 11, 2014 5:23 am
Contact:

Re: Parrallel processing in games & applications

Post by Rseding91 »

blazespinnaker wrote:
Sun May 01, 2022 2:39 am
Well, you could probably define meta-chunks, eg, 16x16 chunks or something. Or maybe one thread per surface at a minimum, though maybe it's already like that I guess. Certainly the per surface approach opens up a lot of potential for the dlc if it leverages that. Maybe they could even fix the per surface production tracking while they are at it :)

Reading back, it seems that it's not one thread per surface. That seems like a shame, tbh. It'd be interesting to see what the benchmark blueprints look like and how much belting you need to do before it saturates the cache.
This is another common misconception that because there are multiple surfaces some how there aren't shared state between them. The most common and main one I go to is Lua events: lua has global access to literally everything the API exposes during virtually all events and virtually all events happen instantly as the trigger condition happens (for example: entity-destroyed has to happen right before it's actually destroyed because once it's deleted you can't use a deleted object; it's gone).

The "splitting" of things across surfaces is largely just for gameplay purposes and not actual code/logic splitting/separation.

To see a true "no shared state" you'd need to do something like: run 2 instances of the game. Then those share no state and can utilize multiple threads to run concurrently. But obviously then there is no shared state. You can't move between games, mods can't know anything about the other game and so on. You'd have to re-introduce shared state to make any of it communicate and then you have to decide where that sharing happens, when, and what data can be shared. It stops being threaded at that point and everything gets blocked while the sharing happens.
If you want to get ahold of me I'm almost always on Discord.

blazespinnaker
Filter Inserter
Filter Inserter
Posts: 532
Joined: Wed Sep 16, 2020 12:45 pm
Contact:

Re: Parrallel processing in games & applications

Post by blazespinnaker »

Rseding91 wrote:
Sun May 01, 2022 2:54 pm
This depends on how people define "unit test". To me a unit test is a test that in-isolation tests that 1 exact piece of code/class/function to do exactly what it thinks it should be doing. The other definition in my head is "integration test" which sets up some state, performs some operation, and checks that the result it expected happened. How that result was processed didn't really matter just that the expected state was the result.

Using this definition; 95%+ of Factorio's tests are "integration tests." We can re-factor and re-work code largely without needing to go back and "fix" tests afterword because they don't care how the in-between-update happened just that the end result of the test logic running was that the condition was fulfilled. For example: an entity being deconstructed by robots has its items removed first and the result storage chest ends up with all the expected items and the item to place the entity. If that happened in threads or not the test doesn't really mind.
A well defined group taxonomy and accurate tagging of tests is vital. It is very important to make distinctions as your testing harness becomes immensely more effective and efficient when you can run it contextually - ie, how much have I changed, what am I trying to verify. Developer productivity is a big deal and these tests are what allow for agile scrum where anyone can change anything.

Unfortunately the message rarely gets across except a smattering of 'oh yeah, you're right' and then just crickets. And to be honest, until I see high coverage numbers it's not the highest priority, which I think is probably why the message is never well recieved (rare to see high coverage numbers).

Measuring contention based coverage is tricky, as it's no longer just a matter of executing a line of code, it's also a matter of measuring different timing sequences. This is probably the most solid argument against multithreading.
run 2 instances of the game
This is an interesting suggestion, but like you said, the juice probably isn't worth the squeeze.

Though, hmm. If there is a quick and easy way to add it (rather, enhance it), that would improve the multicore issue. Also, it could allow for a bigger scale multi-player, ie: grid hopping. Something like roblox/second life/RPO. In truth this already exists with Factorio, right, though maybe it could be done more seamlessly and with immersion.

The biggest issues become science levels, mods and inventory. Science levels could be separate, but mods (rather, modset) I think should be defined for the grid. This would allow for inventory transfers, which is what makes it a grid. Obv grid management (inclusion, kicking, policy, etc) required.

Griefing of course is always the biggest deal, but the nice thing about the grid approach is it can be tackled from a single source. Right now griefers can move around with a degree of impunity. At the very minimum, hopefully something can be done on this point, as it is a serious issue that plagues online multi player currently.

Cross instance communication can be added after the fact via network message into queues. With SE, cross surface circuit networks were not absolutely necessary, but it is good to have.
OptimaUPS Mod, pm for info.

Nidan
Long Handed Inserter
Long Handed Inserter
Posts: 96
Joined: Sat Nov 21, 2015 1:40 am
Contact:

Re: Parrallel processing in games & applications

Post by Nidan »

blazespinnaker wrote:
Sun May 01, 2022 2:39 am
Well, you could probably define meta-chunks, eg, 16x16 chunks or something. Or maybe one thread per surface at a minimum, though maybe it's already like that I guess. Certainly the per surface approach opens up a lot of potential for the dlc if it leverages that. Maybe they could even fix the per surface production tracking while they are at it :)

Reading back, it seems that it's not one thread per surface. That seems like a shame, tbh. It'd be interesting to see what the benchmark blueprints look like and how much belting you need to do before it saturates the cache.

Direct insert can be quite elegant at times.
Rseding91 already wrote why this won't work, but here's a bit of additional context: Wube already tried grouping chunks, see FFF 151 (section Multithreaded update) for their approach. The issues mentioned in the post all seem manageable, but mods being able to change any state arbitrarily is probably what killed it in the end. And since then we also got various linked entities, which also pose a problem in their approach.

blazespinnaker
Filter Inserter
Filter Inserter
Posts: 532
Joined: Wed Sep 16, 2020 12:45 pm
Contact:

Re: Parrallel processing in games & applications

Post by blazespinnaker »

Well, anything will work. Contention can be managed by semaphores and queues. The problem is risk and effort versus reward.

And I have to say, Rseding's suggestion about multiple instances is very compelling. To me at least, that's the answer. In fact, maybe the question isn't so much about enabling multi-threading, but rather - disabling it! This is so one instance doesn't starve the multi-core node of resources. There are ways I believe to restrict applications to specific cores, which might be required because of such things as the belt multi-threading.

And while it might be a bit niche for Wube, hopefully at least they could enable this via mod API. The question is what interfaces are we missing to make this possible? Instance traversal would be infrequent, but obv required. Some way of transfering inventory between instances (say via file or network) would be necessary. Note that maybe this is already doable today and we have everything required.

https://wiki.factorio.com/Application_d ... _directory exists, but can that be shared between multiple instances? A separate proxy app could deal with that problem though, as well as support multi-node / grid style.

Also, what would game play be like? Ie, why do we care about parrallel processing?

Given that resource scarcity is a core game mechanic, you can extrapolate that out to interesting multiplayer scenarios.

Assuming for a moment you can get over the hurdle of trusted instances, one interesting take on game theory here might be having a resource which is deeply scarce (call it X resource) which players battle over as it's required to climb the tech tree. OR it could be cooperative in which new players might join and are educated in how to climb the tech tree and contribute their small amount of X resource to the group effort.

Moving between instances could be approximated via something like the SE mod. When you land, your inventory is saved and you get logged out of instance A and logged into instance B. Your inventory is read in and given to you and your spaceship. APIs exist for setting inventory, but I don't believe there are APIs around logging a user out / in that I'm aware of.
OptimaUPS Mod, pm for info.

Rseding91
Factorio Staff
Factorio Staff
Posts: 12209
Joined: Wed Jun 11, 2014 5:23 am
Contact:

Re: Parrallel processing in games & applications

Post by Rseding91 »

There are already setups out there doing what I described. We even added an API for mods to do it: https://lua-api.factorio.com/latest/Lua ... _to_server
If you want to get ahold of me I'm almost always on Discord.

blazespinnaker
Filter Inserter
Filter Inserter
Posts: 532
Joined: Wed Sep 16, 2020 12:45 pm
Contact:

Re: Parrallel processing in games & applications

Post by blazespinnaker »

Very cool. Looks like the answer, imho.

One question above - you mentioned "You can't move between games, mods can't know anything about the other game and so on". This isn't strictly true than, right?
OptimaUPS Mod, pm for info.

Rseding91
Factorio Staff
Factorio Staff
Posts: 12209
Joined: Wed Jun 11, 2014 5:23 am
Contact:

Re: Parrallel processing in games & applications

Post by Rseding91 »

blazespinnaker wrote:
Mon May 02, 2022 10:20 pm
Very cool. Looks like the answer, imho.

One question above - you mentioned "You can't move between games, mods can't know anything about the other game and so on". This isn't strictly true than, right?
All that API does is disconnect you from the current game and request connect to the other. It doesn't move anything between them and from the games perspective you just disconnect from server A and connect to server B.
If you want to get ahold of me I'm almost always on Discord.

robot256
Filter Inserter
Filter Inserter
Posts: 428
Joined: Sun Mar 17, 2019 1:52 am
Contact:

Re: Parrallel processing in games & applications

Post by robot256 »

The two games on the two servers are completely separate, and any communication between them (I assume) is done asynchronously through external software that emulates player input. The relationship between the two servers is not deterministic and will be affected by network latency. Once that input is received, within each server the execution is deterministic. Normal mod code running on one server has no access to the game state of the other server.

blazespinnaker
Filter Inserter
Filter Inserter
Posts: 532
Joined: Wed Sep 16, 2020 12:45 pm
Contact:

Re: Parrallel processing in games & applications

Post by blazespinnaker »

Well, if you are running on linux, symbolic links can manage state via write_file.

"Determinism" is a generally bad argument. User input, for example, is not deterministic. Should that be disabled as well?
OptimaUPS Mod, pm for info.

robot256
Filter Inserter
Filter Inserter
Posts: 428
Joined: Sun Mar 17, 2019 1:52 am
Contact:

Re: Parrallel processing in games & applications

Post by robot256 »

blazespinnaker wrote:
Wed May 04, 2022 4:42 pm
"Determinism" is a generally bad argument. User input, for example, is not deterministic. Should that be disabled as well?
Another thing that you can read more about in the Alt-F4 blog archive to know why it is important. Factorio keeps the entire game state in memory on the server and in every client. They all receive the "canonical" timestamped user input stream so they can update their own copies of the game state in an identical, deterministic manner (based only on previous state and new input) and remain synchronized.

There are other ways of solving the problem, but then you would have a different game and not Factorio.

blazespinnaker
Filter Inserter
Filter Inserter
Posts: 532
Joined: Wed Sep 16, 2020 12:45 pm
Contact:

Re: Parrallel processing in games & applications

Post by blazespinnaker »

"canonical" timestamped user input stream

Mods are canonical by definition, joining a multi player server enforces that, right?

Your broadcasted "stream" can be anything, Wube limits it to user input for reasons that they have never made clear.

Performance, maybe. Not "determinism", tho

Maybe security, though you have to solve that anyways.

Adding a hook into the broadcast for judicious usage could allow for interesting behavior. Sadly the only way to do it is via problematic hacks


https://github.com/clusterio/clusterio/ ... /index.jsx

Not sure how this works
OptimaUPS Mod, pm for info.

Post Reply

Return to “General discussion”