Multithreaded game update loop

[tux_mark_5]

Based on developer blog post (https://www.factorio.com/blog/post/fff-70) it seems that currently all game update logic happens in a single thread. And the maximum performance of this lone thread is the main thing that limits overall factory size. Considering that multicore CPUs are becoming more widespread, it would make sense for game logic update loop to in parallel, possibly in unlimited number of threads.

Are there any plans to implement multithreaded game update loop?

[SHiRKiT]

I bet there are plans, but know this: making a multithreaded game loop is NO easy thing. Too much assumptions needs to be made, very specific optimizations and a LOT of concerns regarding multiple threads. It's the hardest thing to be done in a game, followed by networking below it.

[tux_mark_5]

I agree that it is not an easy thing. If factorio logic is divided nicely to process one chunk at a time, then it would be more or less a matter of processing multiple chunks at a time. The problem with this approach would possibly be chunk boundary processing.

[hoho]

Main problem is that actions done within a game tick can change how other actions need to be processed in that same tick. Figuring out what depends on what is a monumentally complex task that (mathematically speaking) is still unsolved in computer science.

Though, obviously, that doesn't stop people from writing multithreaded code. It simply means it's hard to manage and extremely hard to make it scale half-decently with added computational power.

[ssilk]

Some answers:
https://forums.factorio.com/forum/vie ... ads#p37918
https://forums.factorio.com/forum/vie ... ads#p61351

[SHiRKiT]

I agree that it is not an easy thing. If factorio logic is divided nicely to process one chunk at a time, then it would be more or less a matter of processing multiple chunks at a time. The problem with this approach would possibly be chunk boundary processing.

Not that easy. It's really really complicated to do this, even this way, since chunk boarders will mess things up. The game runs pretty well IMO as it is.

[tux_mark_5]

I agree that it is not an easy thing. If factorio logic is divided nicely to process one chunk at a time, then it would be more or less a matter of processing multiple chunks at a time. The problem with this approach would possibly be chunk boundary processing.

Not that easy. It's really really complicated to do this, even this way, since chunk boarders will mess things up. The game runs pretty well IMO as it is.

I would still like for the game update to run in parallel. This would make Factorio's performance future-proof. Imagine running Factorio on one of those rumored Intel Xeons with 18 cores. Even with 50% scalability, you could have 9 times larger factories. Now that would be cool

The ultimate dream for me is however to extend this parallel behavior to multiplayer: if Factorio was both per-chunk deterministic and could run updates in parallel, then there would be no reason for all players to completely sync-up their worlds. Each player could 'own' some of map chunks. If there were no other players nearby, then only the owner would run updates on their active chunks. If another player came close to other's players chunks, then the guest player could download these chunks from the owner and keep them in-sync as long as the guest is nearby. Basically, with this model factory size in multiplayer would linearly scale with player count. In addition, you could have distributed servers with pretty much unlimited factory size (as long as you have enough hardware to support it).

The current Factorio's multiplayer model seems kind of flawed for me, because game's update speed in multiplayer is limited by the slowest player, which is really kinda backwards. And because of that I doubt we will ever see well-performing and stable multiplayer with more than 20 people (assuming that the current multiplayer model is kept). This is why I am so curious/excited about splitting game updates to work on chunk-by-chunk basis.

[SHiRKiT]

I agree that it is not an easy thing. If factorio logic is divided nicely to process one chunk at a time, then it would be more or less a matter of processing multiple chunks at a time. The problem with this approach would possibly be chunk boundary processing.

Not that easy. It's really really complicated to do this, even this way, since chunk boarders will mess things up. The game runs pretty well IMO as it is.

I would still like for the game update to run in parallel. This would make Factorio's performance future-proof. Imagine running Factorio on one of those rumored Intel Xeons with 18 cores. Even with 50% scalability, you could have 9 times larger factories. Now that would be cool

The ultimate dream for me is however to extend this parallel behavior to multiplayer: if Factorio was both per-chunk deterministic and could run updates in parallel, then there would be no reason for all players to completely sync-up their worlds. Each player could 'own' some of map chunks. If there were no other players nearby, then only the owner would run updates on their active chunks. If another player came close to other's players chunks, then the guest player could download these chunks from the owner and keep them in-sync as long as the guest is nearby. Basically, with this model factory size in multiplayer would linearly scale with player count. In addition, you could have distributed servers with pretty much unlimited factory size (as long as you have enough hardware to support it).

The current Factorio's multiplayer model seems kind of flawed for me, because game's update speed in multiplayer is limited by the slowest player, which is really kinda backwards. And because of that I doubt we will ever see well-performing and stable multiplayer with more than 20 people (assuming that the current multiplayer model is kept). This is why I am so curious/excited about splitting game updates to work on chunk-by-chunk basis.

The current structure makes it possible to be programmed by 2 guys. That's the whole point

[hoho]

I would still like for the game update to run in parallel. This would make Factorio's performance future-proof. Imagine running Factorio on one of those rumored Intel Xeons with 18 cores. Even with 50% scalability, you could have 9 times larger factories. Now that would be cool

Too bad there is this thing we call "real world"
http://en.wikipedia.org/wiki/Amdahl%27s_law

There *will* be parts of game that simply can't be parallelized and at certain point combining the work of all the parallel threads gets bigger than the time saved from parallelizing them in the first place.

[kovarex]

I would still like for the game update to run in parallel. This would make Factorio's performance future-proof. Imagine running Factorio on one of those rumored Intel Xeons with 18 cores. Even with 50% scalability, you could have 9 times larger factories. Now that would be cool

Too bad there is this thing we call "real world"
http://en.wikipedia.org/wiki/Amdahl%27s_law

There *will* be parts of game that simply can't be parallelized and at certain point combining the work of all the parallel threads gets bigger than the time saved from parallelizing them in the first place.

Yes, this is our dream as well, ofcourse. But nothing makes more sense, than to optimise the core performance on one core, mainly when I see huge area for improvement.

The task is extra difficult mainly because of the need for strict determinism.

[Marconos]

Not sure if this would make things better or worse, would definitely help with lag in multiplayer.

Go with a true server model. The server does nothing with the screen and just handles the determinism and states of objects, movement etc. The client systems handle graphical updates and syncing with the server.

I believe, from reading other posts of yours, that you already have this pretty well split out in the engine currently. To me this makes the most sense as you can isolate one players lag from the rest. That person on the slower connection just gets fewer updates etc. I'm just really concerned about the lag in multiplayer. It is great that you are working on optimizations, I just believe splitting out the logic entirely one from the other and designing in the server portion earlier rather than later will save tons of work.

[ssilk]

TL;DR
Sectors of limited size and complexity, that are connected over some transfer-interface (like a tunnel, it takes some time for the transfert to reach the other end and in the tunnel nothing can happen with the transfer) would enable to calculate the whole Factorio world into different CPUs and/or even on different hosts! In other words: Instead of threading calculation chunk-wise, which will create big problems, we calculate sector-wise.

In long
I think we can have both. I think a single factory should always be able to run on one CPU. And indeed, there is a lot of potential left for increasing.

But my thoughts into that direction always have been going around the problem, how the world could be updated in different threads chunk-wise. I thought into another direction.

With the new "space/orbit-stuff", that will come into the game, it might be possible to run the space part on a different CPU. Why? The space is not directly connected to the planet surface. We can say always something like "A transport-rocket is comming in 300 ticks, it has loaded this and that." Or in other words: There is a moment, between the launch of the rocket and the arriving in orbit, which are guaranteed, that the rocket cannot be interacted. Or collide. Or anything. It's like a tunnel or an interface. There will be stuff happening in some seconds, the rocket will be removed from the surface and arrives in space.

The "space-CPU-thread" has then time enough to prepare for the incoming rocket. No break in determinismn, no problems to solve. Just a fixed schedule. It should work perfectly on two different CPUs, cause the world is then not ONE world, it's two worlds with an interface between them.

And not only that! For multiplayer it is possible then, that not all parts of the world run on all connected hosts. If one player says, I go into space and the other keeps on surface, then only one host needs to calculate both parts.

Let's call the parts just sectors to make that more clear: A world contains sector A and B. If player 1 has a weak computer, the game can decide to run both sectors only on player 2 computers, on player 1 computer only his current sector is running. If he wants to switch, he might need a bit time to switch back and forward, but that is much better, then that every player needs to wait, that player 1's computer calculates all updates.

When I think further into that direction, I come to a point, when it suddenly is logical to split also areas on ground.

This is a little bit complex thought. I need to get a bit off topic. Let's say we split the planet surface into sectors. One sector is quite big, I think to 3000-10000 tiles in diameter. More than enough (about factor 10-50 time more) space to build a factory, than needed. I'm sure more is useless and it will also look quite unnatural, if you fill such a sector with constructions. I mean you can fill it, but See this statement for example: https://forums.factorio.com/forum/sea ... sf=msgonly
I think this is what factorio distincts from so many other games: It's the huge space you have. You need not to compress, because you don't have enough space (there are other reasons to build compressed, but not that!). You can look for the best place to extend your factory.

I always come back to thinking this is OpenTTD or Railroad Tycoon or whatever, but the zoom doesn't end at 50 meters, it ends at one meter.

About two months ago I drawed a pic to illustrate me that (it was mainly to illustrate, how I think a ropeway conveyor would work together with other stuff):

Photo on 16.Feb.15 at 18.45.jpg (172.8 KiB) Viewed 12941 times

Look at this pic, close you eyes a bit and think, this is a map from your favourite train-game. One caro is about 50 tiles in factorio. You see the structures, landscape...
Well, I think I explain it a bit more.
A - your factory, see some structures, a big train station a wall; B - the sector area, reaching from the lake in the north to the mountains in the south and limited by a river in the east. Originally many natives settled here. C - are mountains. Nothing can go through. This is a border of a sector! D - mining outpost with ropeway conveyors (lilac); E - mines. Ropeway brings the ores to the outpost; F - A (place for a) brigde. You have (naturally) only some points where you can cross the sector borders, in this c ase some rocks at both sides. See C that shows a tunnel, that's also only some places, where you can dig such tunnels. G - a new outpost in the middle of the aliens; H - Some lost structure, ready to overtake I - a river; J - a big lake; K - other side of the mountains

I need to underline, that I drawed the sectors too small! It's some weeks ago. Meanwhile I think (see above), that one sector should be about 4-10 times bigger, than drawed here. I was inspired by this pic: http://media.openttd.org/images/screens ... _vries.png
Need also to say, that the scale of OpenTTD is not 1:50 it's more like 1:20, compared with Factorio. See also this pic: http://www.openttd.org/en/screenshot/1. ... lo_pereira
This is about 50x50 tiles in OpenTTD and I think in Factorio it could be built within 200x200 tiles.
Ok, this was just a short off-off-topic to scales in games. This short introduction into the scales of Factorio is important. Cause the scales could be so gigantic (for a game).

I the pic you see the limitations: I used lakes (already in), rivers, mountains or rocks. There is potentially unlimited ideas and possibilities to generate borders of a sector, that have some minimum width, are unbuildable land, cannot be crossed or used in any way.

What I want to say is, that at the time, when a train goes onto the bridge, it can be calculated, how much time it takes to go to the other side. Or when the train goes into the tunnel, the game knows exactly at which time it will come out at the other end. The same situation as with the space, when you send a rocket into orbit!

And because of the pure size of the sections, the borders and the limited transition points (of course much more than drawed) won't hurt; I tested this in the last 2 month very carefully: If someone keeps crying, he must be really crazy like me.

So you can say of course, that a Factory with that size doesn't need to spread out into other sections. There are 2 points against it:

A) It might be, that the distribution of resources is really like shown on the picture: Some resources in the starting zone (already depleted), some anywhere in the landscape, but the really big resources can be found here at the mountains only. There are always some resources, but they are not worth the afford to mine, what you are really searching for are really big resource fields. I assume here, that the rocket defence is not the end of the game and we need to increase prodution to factor 5 or 10 over the current "standard". Whatever this means.
B) You will not gain all resources in one sector. Or only, if you are really really lucky. For example uranium: https://forums.factorio.com/forum/vie ... ium#p69028
This would be also a good Multiplayer game: Sector 1 and 2 have two players, both can work against or together and if they work together, we can send material over the bridge which are not available on the other side.
C) There are potentially unlimited ideas, that make use of such sectors, which are connected only by some kind of very defined interface to enable a computation on different CPUs.

It can be also say, that you can make the Factory so big into one sector, that no CPU can calculate that. I have also a simple argument against: Every factorio-machine needs power and using power means in Factorio to pollute. What if, we have something, which hard-limits the pollution?
For exapmle:
- if the pollution goes over a certain level, the natives will get really, really angry and will come in such masses, that you don't have any more chances than to reduce pollution. Less pollution, less power, less work, less CPU.
- if you need too much electricity you emit a magnetic field, which attracts some flying native birds and when the come to sit on the poles ... brrrrzzzzzzz ... and you lost an Gigajoule or so.
- there are also potentially unlimited ideas to limit the size of one factory part.

This will force the player to built parts of his Factory into different sectors. This is also the point H in the pic above: You found some pre-built area. For example a nearly finished oil refinery with more than 40 refineries, 200 oil tanks and so on. A really big oil-refinery. You would need some hours to built up such a big oil refinery, but you recive it as gift. You need just to bring oil and more products to there, power it, fix up some broken parts and it will work and can produce oil in amounts you never dreamed for! The game changes then also it's scale. And changing the scale in the end-game by factor 10 or 100 is in my opinion a good idea.

@Marconos: We already had that discussion. It would help nothing to change to a client-server model. How will you tell the client, how many items are laying on a belt? In which order and distance? How will you tell a client, which of your 2000 robots took now an item from what chest and will move it to what other chest? And so on, and so on. There is no such client/server model possible for Factorio, or if you will come immediately to a point, where you need to calculate the actions on all belts, inserters, assemblies etc. in the client itself.

[tux_mark_5]

Actually, per-sector parallelism is a pretty neat compromise that IMO shouldn't be too hard to implement. Each sector could have a fixed size. Sectors logically can be laid out in a grid. To travel between sectors one could use a special building (say, a tunnel) that can only built on sector's edge. Also it is important (at least for me) that trains could travel between sectors. This could be implemented by simply destroying train in one sector and spawning an identical copy of that train in the destination sector. And since each sector could run independently of all the others in it's own thread, then even if some sectors were lagging, it would not impact other sectors, ultimately leading to a more lag-free multiplayer experience.

It also would allow new game mechanics. For example, different sectors could be generated using different map generation parameters. This would also balance late-game difficulty pretty nicely: starting sector could have less resources and less enemies, while sectors with more resources could contain more dangerous enemies. Different sectors could use different tilesets. By adding more methods to travel between sectors, one could have underground sectors, or in space-sectors (for example, mining an asteroid). Basically, this would open-up so many possibilities while simultaneously making the game infinitely scalable. Basically, some ideas could be borrowed from Starbound.

[ssilk]

Different map generators: https://forums.factorio.com/forum/vie ... 2&start=10
See also the first page!

But I wouldn't like a fixed grid for the sectors. I think it should be possible to have quite different sized (50 to 50000 tiles), different shaped sectors, but in practical usage they need to fit together with the next sector. This is complex.

I know there are algorithms, that can generate worlds like so. But indeed: programming a world generator working like so will be a brainfuck.

[hoho]

But nothing makes more sense, than to optimise the core performance on one core, mainly when I see huge area for improvement.

This an infinite times over.

Trying to parallelize stuff only makes sense when optimizations on single-thread are already near maximum that is possible. Improving algorithms is pretty much always far more efficient and more scaleable than bruteforce parallelization. Going from O(n) to O(log(n)) will speed things up far more in the general case than going from single thread to a dozen.

Even in ideal, perfect world parallelization can only give linear increase in speed. It essentially just moves the performance ceiling up somewhat but whenever there are some stuff limited by something that is more complex than algorithm with linear complexity the difference is neglible.

[tux_mark_5]

While I agree that optimizing the current game update loop is the way to go, parallelisation shouldn't be dismissed.

Even in ideal, perfect world parallelization can only give linear increase in speed. It essentially just moves the performance ceiling up somewhat but whenever there are some stuff limited by something that is more complex than algorithm with linear complexity the difference is neglible.

I completely disagree. This 'neglible' and 'only linear' increase in speed may double or quadruple world size on most machines (considering that 2-core and 4-core CPUs are most popular and ignoring the fact that other threads may be busy doing something else and eating up available resources). Factorio already supports quite vast factories. With further optimizations that size may double (just guessing). With splitting the world into independent sectors/maps/whatever, factory size may double or quadruple again. So no, even with further optimizations, parallelisation should still be at least considered.

Plus, other optimizations most likely won't solve multiplayer problems when you have 20+ people in the same game. Keeping the whole world in-sync between all clients when each client is apart from another seems just like a waste of resources.

[kovarex]

There is no need to split the map into some parts, we have chunks already, and the most time consuming tasks can be divided into chunks, but it will have to do A LOT of special logic for proper synchronising of any action that can affect global state.

Not impossible, but hard, and yes optimising the core loop is much better now. Most of the stuff the engine is computing now can be simplified/avoided.

[tux_mark_5]

I believe in you, kovarex

Thank you for the wonderful game. I really wanted something like this for quite a long time.

[Nova]

I think you should still take a look at better parallelization. Maybe not now, maybe not with high priority, but parallelization is the way to go to get better perfomance as soon as the "normal ways" have been exhausted.

[casey]

While I agree that optimizing the current game update loop is the way to go, parallelisation shouldn't be dismissed.

Even in ideal, perfect world parallelization can only give linear increase in speed. It essentially just moves the performance ceiling up somewhat but whenever there are some stuff limited by something that is more complex than algorithm with linear complexity the difference is neglible.

I completely disagree. This 'neglible' and 'only linear' increase in speed may double or quadruple world size on most machines (considering that 2-core and 4-core CPUs are most popular and ignoring the fact that other threads may be busy doing something else and eating up available resources). Factorio already supports quite vast factories. With further optimizations that size may double (just guessing). With splitting the world into independent sectors/maps/whatever, factory size may double or quadruple again. So no, even with further optimizations, parallelisation should still be at least considered.

Plus, other optimizations most likely won't solve multiplayer problems when you have 20+ people in the same game. Keeping the whole world in-sync between all clients when each client is apart from another seems just like a waste of resources.

You certainly have enthusiasm, but its clouding your view of the reality of multi-core computing. Even a linear increase in speed requires what we call an "embarrassingly parallel" problem that lends itself to problems that are more IO bound than CPU bound (my experience here is writing Fortran that runs on hundreds or thousands of cores at once). The game loop likely does not qualify as embarrassingly parallel and can except to see much less than linear scaling across multiple cores.

Secondly, consider your goal of bigger factories. If you have a factory that is 50x50 (just for arguments sake) and want to double its dimensions to 100x100, that is 4 times as much area and could be as much as four times more processing power to solve. Throwing cores at this problem is going to hit diminishing returns very quickly.

Lastly, parallelisation isn't a matter of just spawning more threads. It takes careful design to do right and when done wrong can actually hurt performance and create lots of hard to find bugs. Properly distributing load across threads and proper synchronization are vital and the algorithms in use must be designed with this in mind. How are you going to share data between threads? Is your solution going to impact cache locality (performance killer)? As mentioned by another poster, it is better to spend the time now squeezing all of the performance available out of the serial thread and fixing its bugs.