Why aren't we talking about 1073?

(previously 'DEVELOPER') Private forum for registered community members. To register, please visit www.prison-architect.com/register.

Moderator: NBJeff

MaXMC
level0
Posts: 6
Joined: Tue Oct 12, 2010 11:48 am
Location: Luleå, Sweden

Why aren't we talking about 1073?

Postby MaXMC » Sat Jun 27, 2015 12:06 am

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.
crafcik
level0
Posts: 9
Joined: Wed Dec 19, 2012 1:20 am

Re: Why aren't we talking about 1073?

Postby crafcik » Sat Jun 27, 2015 12:12 am

I agree, though I think this is very difficult so it may be a while. On the other hand you do have a point.
User avatar
xander
level5
level5
Posts: 16869
Joined: Thu Oct 21, 2004 11:41 pm
Location: Highland, CA, USA
Contact:

Re: Why aren't we talking about 1073?

Postby xander » Sat Jun 27, 2015 4:49 am

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
MaXMC
level0
Posts: 6
Joined: Tue Oct 12, 2010 11:48 am
Location: Luleå, Sweden

Re: Why aren't we talking about 1073?

Postby MaXMC » Sat Jun 27, 2015 10:49 am

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.
User avatar
xander
level5
level5
Posts: 16869
Joined: Thu Oct 21, 2004 11:41 pm
Location: Highland, CA, USA
Contact:

Re: Why aren't we talking about 1073?

Postby xander » Sat Jun 27, 2015 3:07 pm

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
Sinnik
level0
Posts: 1
Joined: Fri May 01, 2015 8:34 pm

Re: Why aren't we talking about 1073?

Postby Sinnik » Sun Jun 28, 2015 12:56 pm

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.
Jailer
level2
level2
Posts: 173
Joined: Tue Mar 25, 2014 3:29 pm

Re: Why aren't we talking about 1073?

Postby Jailer » Mon Jun 29, 2015 9:55 am

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..
Dorus
level0
Posts: 2
Joined: Tue Sep 09, 2014 9:12 pm

Re: Why aren't we talking about 1073?

Postby Dorus » Mon Jun 29, 2015 6:22 pm

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.
lugaru
level3
level3
Posts: 288
Joined: Wed Feb 06, 2013 7:03 pm

Re: Why aren't we talking about 1073?

Postby lugaru » Mon Jun 29, 2015 8:03 pm

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...
DreamRJ
level0
Posts: 2
Joined: Thu Jun 25, 2015 2:53 pm

Re: Why aren't we talking about 1073?

Postby DreamRJ » Mon Jun 29, 2015 9:45 pm

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
Dorus
level0
Posts: 2
Joined: Tue Sep 09, 2014 9:12 pm

Re: Why aren't we talking about 1073?

Postby Dorus » Mon Jun 29, 2015 11:50 pm

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 :P
DreamRJ
level0
Posts: 2
Joined: Thu Jun 25, 2015 2:53 pm

Re: Why aren't we talking about 1073?

Postby DreamRJ » Tue Jun 30, 2015 12:48 pm

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 :P


yep true
SnowRaptor
level0
Posts: 1
Joined: Sun Sep 13, 2015 7:27 pm

Re: Why aren't we talking about 1073?

Postby SnowRaptor » Sun Sep 13, 2015 7:58 pm

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.
henke37
level2
level2
Posts: 156
Joined: Thu Jul 11, 2013 11:22 pm
Location: Sweden

Re: Why aren't we talking about 1073?

Postby henke37 » Mon Sep 14, 2015 9:58 am

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.

Return to “Community Members”

Who is online

Users browsing this forum: No registered users and 8 guests