Walk and CPU usage

ID:1838509
 
Apr 22 2015, 2:58 am
BYOND Version:507
Operating System:Windows Vista Business 64-bit
Web Browser:Chrome 42.0.2311.90
Applies to:Dream Seeker
Status: Open
Issue hasn't been assigned a status value.
Descriptive Problem Summary:

If you have a lot of objects walking (walk, walk_rand, walk_to and walk_towards) in the same location CPU usage massively increases.
This only occurs if the objects are at the exact same location as they move, if they're all at different locations, there is no issue. So it's likely somehow related to collision checking (these objects are not dense, nor am I making any use of bump/cross/crossed).

Numbered Steps to Reproduce Problem:

Create 100 objects at the same location. Have them all walk in the same direction. Watch as CPU usage sky rockets.

Code Snippet (if applicable) to Reproduce Problem:
mob/verb/movetst()
    var/i=100
    while(i)
        var/obj/O=new(locate(50,50,1))
        walk(O,SOUTH)
        i--


Expected Results:

CPU usage is not so high.

Actual Results:

Here are the results of tests I did

10 FPS
100 objs using walk (south): 15-16 CPU
100 objs using walk_rand: 2-12 CPU
100 objs using walk_towards: 27-29 CPU
100 objs using walk_to: 85-90 CPU

30 FPS
100 objs using walk (south): 47 CPU
100 objs using walk_rand: 6-36 CPU
100 objs using walk_towards: 86-90 CPU
100 objs using walk_to: ??? CPU (basically resulted in a freeze, saw a spike of 250 CPU usage once)

60 FPS
100 objs using walk (south): 95-96 CPU
100 objs using walk_rand: 12-48 CPU
100 objs using walk_towards: ??? CPU (freeze, saw 180 CPU before it froze)
100 objs using walk_to: ??? CPU (freeze so bad I couldn't see sort of reading)

As you can see, walk_rand has the lowest CPU usage because the mobs walk in different directions and not as many are stacked on top of each other.

Does the problem occur:
Every time? Or how often? Everytime
In other games? N/A
In other user accounts? N/A
On other computers? N/A

When does the problem NOT occur?

If objects aren't stacked in the same location it's not an issue.

Did the problem NOT occur in any earlier versions? If so, what was the last version that worked? (Visit http://www.byond.com/download/build to download old versions for testing.)

Workarounds:

Apr 22 2015, 5:12 am
How bad is a stack of 100 objects on 1 tile walking together vs 100 objects lined up in a 100 tile wide line moving north?
Apr 22 2015, 5:33 am
In response to MisterPerson
I suspect not very. The movement code is concerned only with the contents of the tiles involved in each move.
Apr 22 2015, 5:41 am
In response to MisterPerson
100 objects on 1 tile causes high CPU usage.
100 objects on different tiles causes almost none. Infact, I had to get 200 objects walking before world.CPU would tell me anything.

What I suspect is happening with 100 objects in the same location moving is each of those 100 objects is checking the other 99 everytime they move. Which is 9900 checks everytime they move, which even at 10 FPS is 99000 checks a second.
Apr 22 2015, 5:58 am
The new pixel movement code definitely plays a part in this. There is an extent to which this is an inescapable issue, if pixel movement is actually in play. However I did find several inefficiencies that only come up when actual pixel movement is involved here, that won't when the objects are all tile-based. (Specifically, when it's calculating which movs it overlaps and which it will overlap when movement is finished, gathering the list of each has a lot more memory allocation calls than it should. But tile movers are skipped.)

If it's all tile movement, sheer quantity could conceivably be an issue, but it doesn't seem like that'd be enough to trigger anything on exit. A turf's contents don't impact Exit() one iota.
Apr 22 2015, 6:13 am
I've been playing around with it some more.

Having 10 groups each consisting of 10 moving objects in the same location causes minimal CPU usage (0-2).
Changing this to 5 groups of 20 moving objects doubles CPU usage (2-4).
4 Groups of 25 increases CPU usage from this a small amount (5-6).
2 Groups of 50 triples CPU usage (15-18).

As a further test, 1 group of 75 objects in the same location results in about 20-22 CPU usage.
Apr 22 2015, 6:21 am
For clarity's sake, is pixel movement a factor here? Or are all of these objects tile movers, occupying a single tile?

DM will activate some of the new code in builds from 490 onward, but the square-law performance issue you're seeing would tend to crop up much more with pixel movement in play. Otherwise the only potential problem is turf/Enter(), which I don't think would be in play here either as all objects are leaving the same tile. (Of course if they're all moving together to the same destination, then the new turf would have to go through progressively more objects to give a yes/no on density. That'd be an issue even going back to old versions, though.)

I also wonder if you have a little demo you've been playing around with that might be useful for me in testing.

[edit]
Actually it occurs to me that even with skipping tile movers, there's a slight O(N^2) factor involved just with traversing the movables in each tile. But it should be extremely minor.
Apr 22 2015, 6:34 am
All pixel movement with a step_size of 2. Gimme a few minutes to throw together something more extensive for testing, I'm just using a single verb and changing it as needed at the moment.
Apr 22 2015, 6:35 am
Okay, then it's likely that the inefficiencies I discovered are the problem. That gives me a good angle of attack. If you do have a demo you can upload somewhere it would help me a lot in terms of gauging how well the fix goes.
Apr 22 2015, 6:58 am
https://mega.co.nz/#!9Bgh0YLB!zwbfQ4tdfGlFN3UNUuWXjweKll1LZx R67ZBInNozK10

This is essentially all I've been doing to play around with things.
Apr 22 2015, 8:05 am
lol, you're making a MOBA too and running into literally the same issues as me with walk()
Apr 22 2015, 4:16 pm
In response to The Magic Man
So, just checking, but in these tests you were using walk_towards and not walk right?
Apr 23 2015, 1:41 am
In response to Turboskill
I used all of the walk procs, walk_to and walk_towards result in more CPU usage than walk, and walk_rand results in less CPU usage due to the objs not all being stacked in the same location).

It's clearly stated in the opening post I tried all of the procs and what the results were.
Apr 23 2015, 6:22 am
No, i'll try to be clearer -denoting a reply as being to a specific comment doesn't seem to work so well.

What i was asking to be clarified was whether in these(below) tests specifically you were focussing on walk_towards rather than walk -i'm not sure why now, but initially i recall thinking that walk was more the focus initially-

The Magic Man wrote:
I've been playing around with it some more.

Having 10 groups each consisting of 10 moving objects in the same location causes minimal CPU usage (0-2).
Changing this to 5 groups of 20 moving objects doubles CPU usage (2-4).
4 Groups of 25 increases CPU usage from this a small amount (5-6).
2 Groups of 50 triples CPU usage (15-18).

As a further test, 1 group of 75 objects in the same location results in about 20-22 CPU usage.

Anyway, glancing back through this post, it was apparently just me reading things in a specific way when i first saw this. The whole point of me asking was because i was going to mention that in your OP walk was recorded as effecting a 15-19% cpu rise for 100 mobs on one tile, so i was confused as to how later on that was the same cpu value recorded for 2 groups of 50.
Not to worry though, since it was just me assuming wrongly what you were testing. Unto the next thing!