Bug 1073 http://bugs.introversion.co.uk/view.php?id=1073 was registered 2013-03-24 14:58 in Alpha 8
There has been 25 alpha releases since, and sure some of them have actually helped performance wise but none of the videos Introversion has made has even stated that they are thinking about multi-threading or that they won't do it because it's not feasible or too hard.
Multi-threading work should also be good for the Tablets-releases since most of our phones and tablets today are also multi-core.
The performance mother bug (http://bugs.introversion.co.uk/view.php?id=5315) is also listed as new with a severity of minor?
It would be nice for Introversion to at least acknowledge these bugs in their next Alpha video and make it a priority after summer holidays (if any) to iron these out before the release this autumn.
Why aren't we talking about 1073?
Moderator: NBJeff
Re: Why aren't we talking about 1073?
I agree, though I think this is very difficult so it may be a while. On the other hand you do have a point.
Re: Why aren't we talking about 1073?
Grrr... multithreading solves all problems! Rarg!
...
The major computational bottleneck in the game is pathfinding. Pathfinding is O(n^2) in complexity, where n is the number of nodes in the graph that must be searched for a path, which is essentially the number of cells on the map (so, 80^2 for a small map, i.e. very computationally intensive). Yes, it could be multithreaded, but the complexity of the pathfinding problem increases much, much faster than the improvement offered by splitting the problem into multiple threads, and so it is likely that you would run into the same poor performance relatively quickly (one land expansion would likely wipe out the benefits of adding a second core, and then some).
As has been noted every other time that this has appeared on the forums, there are probably other optimizations that could be made to the pathfinding routing that would help---for instance, the prisoners don't need to find an optimal path, which allows for some shortcuts; some kind of waypointing could be implemented; the AI could be smarter prioritizing nearby tasks; etc. Further multithreading is almost certainly *not* going to fix the problem. I highly recommend that you read the linked bug report in detail, particularly those comments left by RFC3514, which are fairly easy to grok even if you don't have a lot of computer science background.
xander
...
The major computational bottleneck in the game is pathfinding. Pathfinding is O(n^2) in complexity, where n is the number of nodes in the graph that must be searched for a path, which is essentially the number of cells on the map (so, 80^2 for a small map, i.e. very computationally intensive). Yes, it could be multithreaded, but the complexity of the pathfinding problem increases much, much faster than the improvement offered by splitting the problem into multiple threads, and so it is likely that you would run into the same poor performance relatively quickly (one land expansion would likely wipe out the benefits of adding a second core, and then some).
As has been noted every other time that this has appeared on the forums, there are probably other optimizations that could be made to the pathfinding routing that would help---for instance, the prisoners don't need to find an optimal path, which allows for some shortcuts; some kind of waypointing could be implemented; the AI could be smarter prioritizing nearby tasks; etc. Further multithreading is almost certainly *not* going to fix the problem. I highly recommend that you read the linked bug report in detail, particularly those comments left by RFC3514, which are fairly easy to grok even if you don't have a lot of computer science background.
xander
Re: Why aren't we talking about 1073?
xander wrote:Grrr... multithreading solves all problems! Rarg!
...
The major computational bottleneck in the game is pathfinding. Pathfinding is O(n^2) in complexity, where n is the number of nodes in the graph that must be searched for a path, which is essentially the number of cells on the map (so, 80^2 for a small map, i.e. very computationally intensive). Yes, it could be multithreaded, but the complexity of the pathfinding problem increases much, much faster than the improvement offered by splitting the problem into multiple threads, and so it is likely that you would run into the same poor performance relatively quickly (one land expansion would likely wipe out the benefits of adding a second core, and then some).
As has been noted every other time that this has appeared on the forums, there are probably other optimizations that could be made to the pathfinding routing that would help---for instance, the prisoners don't need to find an optimal path, which allows for some shortcuts; some kind of waypointing could be implemented; the AI could be smarter prioritizing nearby tasks; etc. Further multithreading is almost certainly *not* going to fix the problem. I highly recommend that you read the linked bug report in detail, particularly those comments left by RFC3514, which are fairly easy to grok even if you don't have a lot of computer science background.
xander
I do have a CS background, I've read the comments for the last 2 years as they come in. I really don't care if the solution is multithreading or not. What I want is for Introversion to acknowledge the performance problem and tell us what or if they are going to do something about it.
If pathing wouldn't gain much, don't multithread the pathfinding then.
What I want is a discussion about what to optimise and how.
For example, why not try Flow Fields?
It worked extremely well for Supreme Commander with massive amount of units.
Re: Why aren't we talking about 1073?
IV have repeatedly acknowledge that performance becomes an issue, and have even released at least one major update to address performance issues (that was alpha 12 or 13, maybe?---it's been a while). The fact that it is listed as a "minor" issue has nothing to do with IV and everything to do with the person that constructed the "Performance Issues" mother bug (priority is set by the reporter, unless IV decides to change it). That being said, performance is, generally speaking, something that is addressed near the end of development, once a game is feature complete. Since IV are pushing to get the game out this year, it seems likely that it will be addressed soon.
xander
xander
Re: Why aren't we talking about 1073?
I agree with both of your points. No offense to the devs, but during their Alpha videos, they talk a lot about nonsense but in over at least 10 - 15 Alpha videos, they have not addressed or even mentioned anything about this major issue and how/if/when/what they plan to do with it. Its an issue thats listed twice on the 10 Highest-Supported All Projects Issues, one of them thats listed the second highest supported issue out of all. To me personally it just seems like the devs feel if they ignore the problem long enough it'll go away.
I don't know if they will be fixing it, I dont know if they gave up on it. I would just like them to acknowledge the issue thats been the elephant in the room and advise whether or not they will be fixing it and maybe even a rough estimate of a date for when they plan to address it if they are. I don't believe that's too unrealistic of a request.
I don't know if they will be fixing it, I dont know if they gave up on it. I would just like them to acknowledge the issue thats been the elephant in the room and advise whether or not they will be fixing it and maybe even a rough estimate of a date for when they plan to address it if they are. I don't believe that's too unrealistic of a request.
Re: Why aren't we talking about 1073?
Sinnik wrote:I agree with both of your points. No offense to the devs, but during their Alpha videos, they talk a lot about nonsense but in over at least 10 - 15 Alpha videos, they have not addressed or even mentioned anything about this major issue and how/if/when/what they plan to do with it. Its an issue thats listed twice on the 10 Highest-Supported All Projects Issues, one of them thats listed the second highest supported issue out of all. To me personally it just seems like the devs feel if they ignore the problem long enough it'll go away.
I don't know if they will be fixing it, I dont know if they gave up on it. I would just like them to acknowledge the issue thats been the elephant in the room and advise whether or not they will be fixing it and maybe even a rough estimate of a date for when they plan to address it if they are. I don't believe that's too unrealistic of a request.
In the rule-set of software development is usually something like:
* If you want to do performance optimization, then do so when your full scope has been fixed; otherwise your new content is affecting your performance and you are going to do a lot of rework
In other words - IV have made some efforts already to keep the alphas playable, but as they have been adding content virtually every alpha iteration, they are probably waiting to do all the polishing until beta..
Re: Why aren't we talking about 1073?
I've been looking at 1073, and I can tell you one things:
'Game uses only one (or two) cores' is not a bug. This isn't even a symptom. At best it is a indication something is going wrong in concurrent code, at worse there is no concurrent code, and things simply work as intended. Either way, this is not something that can be fixed, or should be fixed.
'Game has massive lag', 'Game has low performance', 'Game has low fps', no matter how useless these reports might sound, are valid bugs. Bonus points if they have detailed information on how to hit these performance bottlenecks. 'Game is slow on huge prisons' is much less useful as 'Game is slow in this save file' or even better 'Game is slow with 200+ guards (see save file)'.
Now, adding multi-threading could very well be a solution to some performance issues. Then again, it probably isn't. In my experience in CS, adding multi-threading support to a program has very limited gains. If you go from 1 core to 8 cores, at best you get a 8x speedup, but more likely nothing more than 2-4x (see Amdahls law). While at the same time your program becomes massively more difficult to maintain.
While at the same time, if you slightly improve your algorithm, for example you go from n^3 to n^2, that's easily a 500x speed up (if n is large enough), and can be archived easily if your current algorithm is bogus and contains a bug that makes it more complex than required. And trust me, its really easy to make a small mistake that makes your algorithm 500x slower than it should be.
For example, I see people claim that path-finding is the biggest bottleneck. While this is probably true, the real problem is job assignment: Right now jobs get assigned in what seems to be a random way. Often a guard from the other side of the prisson has to make it all the way to the other side. Doing so takes a huge toll on the path-finding algorithm that has to cover a great distance. Imagine instead we assign jobs to guards close by, suddenly the algorithm has to cover 4x less distance, and is 16x faster.
Bottom line: Adding multi-threading is not a bug, or a feature, it is probably the wrong solution to a different underlying problem. If I worked at introversion, closing bug 1073 as INVALID of WORKSFORME would probably the first thing I'd do. Second thing would be optimizing the games algorithms.
'Game uses only one (or two) cores' is not a bug. This isn't even a symptom. At best it is a indication something is going wrong in concurrent code, at worse there is no concurrent code, and things simply work as intended. Either way, this is not something that can be fixed, or should be fixed.
'Game has massive lag', 'Game has low performance', 'Game has low fps', no matter how useless these reports might sound, are valid bugs. Bonus points if they have detailed information on how to hit these performance bottlenecks. 'Game is slow on huge prisons' is much less useful as 'Game is slow in this save file' or even better 'Game is slow with 200+ guards (see save file)'.
Now, adding multi-threading could very well be a solution to some performance issues. Then again, it probably isn't. In my experience in CS, adding multi-threading support to a program has very limited gains. If you go from 1 core to 8 cores, at best you get a 8x speedup, but more likely nothing more than 2-4x (see Amdahls law). While at the same time your program becomes massively more difficult to maintain.
While at the same time, if you slightly improve your algorithm, for example you go from n^3 to n^2, that's easily a 500x speed up (if n is large enough), and can be archived easily if your current algorithm is bogus and contains a bug that makes it more complex than required. And trust me, its really easy to make a small mistake that makes your algorithm 500x slower than it should be.
For example, I see people claim that path-finding is the biggest bottleneck. While this is probably true, the real problem is job assignment: Right now jobs get assigned in what seems to be a random way. Often a guard from the other side of the prisson has to make it all the way to the other side. Doing so takes a huge toll on the path-finding algorithm that has to cover a great distance. Imagine instead we assign jobs to guards close by, suddenly the algorithm has to cover 4x less distance, and is 16x faster.
Bottom line: Adding multi-threading is not a bug, or a feature, it is probably the wrong solution to a different underlying problem. If I worked at introversion, closing bug 1073 as INVALID of WORKSFORME would probably the first thing I'd do. Second thing would be optimizing the games algorithms.
Re: Why aren't we talking about 1073?
Honestly they have put out several performance related patches, usually shown off by loading a gargantuan prison and seeing it run fairly well. That said is it in this community or elsewhere that I heard about a method to kind of find and 'bake in' paths so that path finding does not need to be constantly figured out...
Re: Why aren't we talking about 1073?
i also posted a bug report, and made a video demonstrating the lag issues
https://www.youtube.com/watch?v=8-yJWGvxGR8
http://bugs.introversion.co.uk/view.php?id=9218
https://www.youtube.com/watch?v=8-yJWGvxGR8
http://bugs.introversion.co.uk/view.php?id=9218
Re: Why aren't we talking about 1073?
DreamRJ wrote:i also posted a bug report, and made a video demonstrating the lag issues
https://www.youtube.com/watch?v=8-yJWGvxGR8
http://bugs.introversion.co.uk/view.php?id=9218
I would suggest to add a save file
@lugaru: Yes, that's a interesting solution, there are tons of options to improve on stuff, there are probably already a fair number of optimizations in the code anyway. Shame only the devs really know what's going on and able to add to it
Re: Why aren't we talking about 1073?
Dorus wrote:DreamRJ wrote:i also posted a bug report, and made a video demonstrating the lag issues
https://www.youtube.com/watch?v=8-yJWGvxGR8
http://bugs.introversion.co.uk/view.php?id=9218
I would suggest to add a save file
@lugaru: Yes, that's a interesting solution, there are tons of options to improve on stuff, there are probably already a fair number of optimizations in the code anyway. Shame only the devs really know what's going on and able to add to it
yep true
-
SnowRaptor
- level0
- Posts: 1
- Joined: Sun Sep 13, 2015 7:27 pm
Re: Why aren't we talking about 1073?
The problem may be with pathfinding, may be with job assignment, whatever. The point is that the game works by having entities doing their things in parallel. If one worker has a job of getting a door from storage to install it, this worker, by itself, has to pathfind to the storage, and pathfind to the installation site and does not care about what others (workers, guards, prisoners) are doing. It only cares about closed jaildoors.
I don't see why assigning each pathfinding procedure to a thread* (that can be allocated to a "free" CPU core) would not be beneficial, even if the performance gain is strongly sublinear with the number of cores. If the gain is the sqrt of the core count, 4 cores would make the game 2x faster. Performance issues appear with 200, 400-inmate prisons. Doubling this, makes performance issues appear at 400, 800 inames. I don't recall seeing a prison larger than 600 inmates yet.
So yes, the effect may be less than what we would naively expect, but would be enough to push performance issues to larger prisons, giving the developers time to fix the job allocation part of the problem, for example.
* Or making sure that other cores are actually used most of the time.
I don't see why assigning each pathfinding procedure to a thread* (that can be allocated to a "free" CPU core) would not be beneficial, even if the performance gain is strongly sublinear with the number of cores. If the gain is the sqrt of the core count, 4 cores would make the game 2x faster. Performance issues appear with 200, 400-inmate prisons. Doubling this, makes performance issues appear at 400, 800 inames. I don't recall seeing a prison larger than 600 inmates yet.
So yes, the effect may be less than what we would naively expect, but would be enough to push performance issues to larger prisons, giving the developers time to fix the job allocation part of the problem, for example.
* Or making sure that other cores are actually used most of the time.
Re: Why aren't we talking about 1073?
Assuming that all cores are doing pathing (patently false) and that pathing can be done in parallel without any dependencies on data that needs synchronization (false again) you do get a N times performance boost by having each core path for a different entity. It may be difficult to parallelize the substeps of pathing, but it's no biggie to do it for each entity.
One thing I wonder about for the pathing is if it is hierarchal. That would allow precomputation of routing data on a coarse scale, massively reducing the search space for detailed computations.
One thing I wonder about for the pathing is if it is hierarchal. That would allow precomputation of routing data on a coarse scale, massively reducing the search space for detailed computations.
Who is online
Users browsing this forum: No registered users and 8 guests