Multithreaded game update loop

[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 11766 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.

[tux_mark_5]

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.

By doubling the factory size, I mean exactly that. Not quadrupling. Factories are essentially made of various entities. Double the size == double the entity count. How these entities are distributed in a map shouldn't matter.

As kovarex has already mentioned, game is already organized by chunks. Without knowing exact implementation details I can guess that each chunk also contains a list of entities that exist in that chunk. Basically, entire map is divided to chunks. In a hypothetical situation, where one chunk cannot affect another, parallel update is trivial - you only need a thread pool that processes a job list, where each job is meant to update a single active chunk. This is why I agreed with ssilk's idea to divide map into sectors and to update those (rather than chunks) in parallel instead - because for the most part sectors could be completely independent.

I know for a fact that game can run in parallel quite well without running into IO bottlenecks or cache locality problems: I can easily run 4 instances of factorio on my 6-core CPU at the same time. All 4 instances are running the same save that contains a fairly large factory that takes 12ms to update. When running 4 instances, this time increases to 15ms. So the game logic is obviously not IO dependent. If only 1 instance was rendering instead of all 4, I'm sure I could have increased factorio instance count to 6.

If the game had a deterministic Lua bindings API for IPC or some other form of communication between instances (like unix sockets), I could implement a crude version sector parallelism as a mod myself by running several instances of the game at the same time and teleporting items between instances. I would be more or less okay with something similar like that.

However, as kovarex mentioned in his latest post, the most intense game update parts can be easily split into separate threads. Also, he believes that per-chunk parallelism can be implemented without dividing map further into sectors.

So there you have it. The game is capable of parallel scalability. The game can be made to run parallel in two ways - either by processing chunks or sectors. Both methods gameplay-wise are suitable for me. If you don't want to run into various multithreading issues, the easy way is to handle game on sector-by-sector basis. But if the developers believe that they can implement even better version of parallelism (chunk-by-chunk), I'm definitely not going to argue.

[keyboardhack]

However, as kovarex mentioned in his latest post, the most intense game update parts can be easily split into separate threads

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.

Hard = easily?

If the game had a deterministic Lua bindings API for IPC or some other form of communication between instances (like unix sockets), I could implement a crude version sector parallelism as a mod myself by running several instances of the game at the same time and teleporting items between instances. I would be more or less okay with something similar like that.

Say i want to run my factory on 4 cores with your mod. I now need to run 4 independent factorios with their own ram requirements. My world takes 4gb(5gb is not excessive because you want multithreading to work on big maps) of memory so i would need over 16gb of ram to run factorio on 4 cores. I highly doubt that a lot of people has enough ram for that.

Multithreading would be cool, but we shouldn't push for it to happen sooner, when it's better to optimize factorio for a single thread. If that's not what this thread is about atm then i don't know what it's for.

[tux_mark_5]

By 'easily' I referred to 'the most time consuming tasks can be divided into chunks' bit.

When I tested 4 instances of factorio, they consumed less than 8 GB of ram combined, which is a reasonable amount of RAM for any descent machine. Also, it is unclear how much of that memory is textures, sounds and other data than can be shared across instances. And in the end, if player's pc is a wooden toaster, then you shouldn't expect great performance with vast maps anyways.

And I am not pushing for it to happen sooner. Guys, please read the previous posts first before making assumptions.

It's almost like you don't want a better factorio and are arguing just for the sake of it.

[SHiRKiT]

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.

The general rule of thumb is this. Normally, optimizing the core logic is better than to parallize it. And since parallel computation brings so much bugs, and the Factorio team loves spending hours and hours fixing them, I still agree that's just not worthwise.

[cpy]

I guess if you can thread everything it will take a lot of time and effort. But maybe one day we'll see it happen?
When big factory is not big enough! Damn this determinism.

[hoho]

By doubling the factory size, I mean exactly that. Not quadrupling. Factories are essentially made of various entities. Double the size == double the entity count. How these entities are distributed in a map shouldn't matter.

No, usually doubling the size of a factory consumes more than twice the amount of computing power and especially memory bandwidth as it likely won't fit to cache any more. I'm simplifying here but increasing the amount of entities also increases the amount of entities that have to be searched to find the right one to perform actions with. With naive algorithms it means doubling the amount quadruples the amount of lookup operations made.

I know for a fact that game can run in parallel quite well without running into IO bottlenecks or cache locality problems: I can easily run 4 instances of factorio on my 6-core CPU at the same time

You aren't hitting *any* cache locality problems with that sort of "test". You had literally zero data sharing between the game instances even if they were in same multiplayer world.

In best-case scenario modern CPUs can move a couple of tens of GBs of data per second from core to core *when that data is streamed*. When you need to update a few bytes here and there and flush cache lines to get it propagated to other cores it drops down to just a tiny fraction of that and it *will* cause extra cache misses that require very expensive trips to either L3 or RAM (not much of a difference in terms of latency for AMD stuff, somewhat better on Intel). A cache miss means several hundred cycles of the CPU just idling doing nothing and with parallel programming you (well, the compiler, actually) often need to force those cache misses to be able to get your data to other threads/cores.

Then there is the other "problem" of the game running at 60Hz update time or around 17ms per tick. I'm not sure how it is with windows 8 and up but before that when one allowed the OS to manage the threads it could easily mean they'd be put to sleep for 10ms. In linux it varies from 1-10ms depending on kernel settings. If the OS decides it's a good idea to throw your computing thread off the core it'll mean the cache gets trashed by whatever other thing gets put there. Not to mention it has to copy off the state of registers too.

[tux_mark_5]

You aren't hitting *any* cache locality problems with that sort of "test". You had literally zero data sharing between the game instances even if they were in same multiplayer world.

Since I love repeating myself, I'll state this: one of the main points I made in my previous posts that a variant of parallelism can be implemented that requires little to no data sharing across threads, thus making your argument irrelevant. Also, factories can be laid out in a map in such a way that respective chunks would be independent (different electrical grids, no roboport overlaps, etc) achieving the same effect. And my test was mostly intended to disprove the notion that factories are IO bound and implementing any kind of parallelism is futile.

Edit:

A cache miss means several hundred cycles of the CPU just idling doing nothing and with parallel programming you (well, the compiler, actually) often need to force those cache misses to be able to get your data to other threads/cores.

You are wrong there. Compiler has no notion of threads beyond atomic operations (and even those are probably implemented using inline assembly). It does nothing to force cache-misses and so on.

Then there is the other "problem" of the game running at 60Hz update time or around 17ms per tick. I'm not sure how it is with windows 8 and up but before that when one allowed the OS to manage the threads it could easily mean they'd be put to sleep for 10ms. In linux it varies from 1-10ms depending on kernel settings. If the OS decides it's a good idea to throw your computing thread off the core it'll mean the cache gets trashed by whatever other thing gets put there.

Even if every update cycle is performed on a different core compared to the previous update, I doubt it would affect overall performance much. Factorio's working set is already larger than that of even most high-end CPU caches, thus it can be safe to assume, that all or most data involved in single update is transferred from RAM every update cycle.

Not to mention it has to copy off the state of registers too.

Really? That almost feels like gripping on straws. Register preservation has such a negligible performance impact that can be easily ignored.

[Alekthefirst]

so this ended up being the "shit-throwing-thread"....

[mike_smit]

Since kovarex has stated that he will optimize single core performance it is best that you use this graph when buying your next CPU. Many people have a multicore CPU but a cheap crappy model

Use this to buy your next
http://www.cpubenchmark.net/singleThread.html

[tux_mark_5]

so this ended up being the "shit-throwing-thread"....

Sorry