the real bottleneck

[Tobi]

Following up on the other thread here, where a non bottleneck was optimized, I typed a blog post about part of result of Spring profiling done by BrainDamage.

I might even make more posts, some of which may even be useful as documentation

clicky

[jK]

would be nice to know the used miplevels for the losmaps

PS: it would be nice too to know what lua he had run (it ate ~40% of his cpu)

[Decimator]

So what would happen if we had a separate type of los that ignores terrain?

[lurker]

12.70% LOS
12.83% sqrt

By the way, before I saw this post I was wondering about trying to speed up the vector los squares get shoved into. Looks like capacity may or may not be 0 after clear() is called. If it is, then we should probably reserve() a size in the hundreds range. It seems that gcc tends to not touch capacity, but it never hurts to be explicit about such things.

[jK]

hmmm seems to be an old build too, Camera::InView() spends >4% in sqrt, but I already optimized that stuff with square functions.

[lurker]

What was used to make this?

[Argh]

So what would happen if we had a separate type of los that ignores terrain?

Gee, I've only asked for that maybe 4-5 times now

Seriously... I think that issue no. 1 is:

1. LOS handler needs to update only if Unit exits the current LOS square (i.e., the larger the squares, the less frequently it bothers, no matter how fast things move).

2. Aircraft shouldn't bother checking terrain, because they move so fast that no. 1 still won't result in a large enough cost savings.

Just my opinion, of course, but I don't see a lot of benefit, in terms of gameplay, for the way things currently work.

[lurker]

In no particular order:
It already waits for units to move.
Aircraft tend to not be that high, compared to cliffs. And they can also land.
Circular LOS would be pretty simple to code to have as a lobby option, we already even have the same code for ALOS. It just takes someone to get around to it.

[el_matarife]

Aircraft tend to not be that high, compared to cliffs. And they can also land.

I think we should just assume aircraft fly high enough to ignore terrain checks unless landed or told otherwise through some sort of unit tag. (I know NOTA has some low flying units they may want terrain LOS checks on, plus who knows what else.)

[quantum]

Reducing LOS miplevels has had a huge effect on chicken mode in CA and no visible drawback. It's possibly an easy solution to this problem.

[lurker]

No assuming imo. Go with a tag and use terrain if that tag isn't there.

[Tobi]

As far as I know BrainDamage used Spring 0.77b5 for his testing, so indeed an old build

I think he used XTA 9.53. He had IceUI and other heavy LUA stuff running. I'll update the post later today, I have the replays at my home PC.

[lurker]

It seems XTA uses default. Maybe we should bump the default to 2 for LOS.

[el_matarife]

What was used to make this?

Yeah, can you document how to do this performance profiling? It'd be an interesting way to test possible performance improvements.

[koshi]

the profiler BrainDamage used:
http://oprofile.sourceforge.net/about/

some utils scripts:
http://code.google.com/p/jrfonseca/wiki/Gprof2Dot
http://code.google.com/p/jrfonseca/wiki/XDot

[el_matarife]

Reducing LOS miplevels has had a huge effect on chicken mode in CA and no visible drawback. It's possibly an easy solution to this problem.

FatController just tested this in BA by changing the AirLOSMipMap to 4 from the current 2 and LOSMipMap to 2 from 1 and had 15% lower CPU usage with 1200 patrolling Vampire stealth fighters after switching teams so they didn't render. I'm assuming that's an extreme edge case, but even a 5% to 10% bump would be pretty nice for no appreciable sacrifice in quality.

[FLOZi]

S44 also had significant gains when we changed the los settings. I'm afraid I've forgotten the numbers though..

[imbaczek]

Most interesting post. Good visualizations there.

What's the complexity of LOS today in big-O notation? Is it O(units*map_squares)? There is an algorithm for square LOS which works in O(map_squares); I'm not sure if it can be repurposed for circular LOS though, also it ignores height differences. For view-blocking stuff, there's recursive shadowcasting available in several roguelike(!) libs.

[Kloot]

It's Omega(n * m), where n is the number of units that moved from their last SlowUpdate position and m the total number of squares covered (not counting overlap). Since each unit sees an amount of squares that grows quadratically as a function of its LOS radius (which all need explicit updating) the bottleneck very quickly becomes visible, patrolling fighter swarms are the worst offenders of course.

Aircraft shouldn't bother checking terrain

... And that would mean _all_ squares within a plane's LOS would _always_ need to be visited with the current tabular representation, thus making the problem even more acute.

[Tobi]

Most interesting post. Good visualizations there.

What's the complexity of LOS today in big-O notation? Is it O(units*map_squares)? There is an algorithm for square LOS which works in O(map_squares); I'm not sure if it can be repurposed for circular LOS though, also it ignores height differences. For view-blocking stuff, there's recursive shadowcasting available in several roguelike(!) libs.

Thanks. Have a link to this algorithm for square LOS that works in O(map_squares)?