Performance: unit movement over shroud in huge maps is laggy (GNA #25299)

[wesnoth-bugs]

Original submission by shiki on 2016-11-14

1)Build the debug version of wesnoth 1.13.6(+dev)

2) Start the first scenario of UTBS (doesn't matter if the reamke or the old)

3)send a unit to the north, or somewhere else where much shroud is.

When a unit discovers shrouded area in it's movement, there's graphically a short delay between each hex.

Compared to 1.13.4, this effect does exist there too, but the delays are shorter.

If you build the release version of wesnoth 1.13.4, together with march=native, the delays are even more short.

When I used the random map generator in 1.13.6+dev and enabled shroud, there weren't delays.

Not sure if Graphics are the problem, or rather some UTBS events.

(Reproduced on Archlinux) Release: 1.13.6+dev Priority: 5 - Normal Severity: 3 - Normal

[wesnoth-bugs]

Modified on 2016-11-14

gfgtdf wrote:

You you please try retesting this with "minimap terrain drawing" deactivated? to do so click on the hexagonal togglebuton under the minimap.

[wesnoth-bugs]

Modified on 2016-11-14

gfgtdf wrote:

When I used the random map generator in 1.13.6+dev and enabled shroud, there weren't delays.

This coudl be becasue your map was too small to reproduce try with a max size (100x100) map in the stardard map generator

[wesnoth-bugs]

Modified on 2016-11-15

shiki wrote:

That's it, on 100x100 it's really bad.

Without minimap terrain drawing it's as bad as with.

I also noticed that campaigns take longer to load - there's a ~2 sec delay before the characters talking starts and the scenario prologue takes as well a bit longer.

(in difference to before I compare with 1.12, not 1.13.4)

[wesnoth-bugs]

Modified on 2016-11-15

gfgtdf wrote:

Without minimap terrain drawing it's as bad as with.

Hm and when youd deactivate all the minimaostuff (to that all the minmap buttons (except zoom) are 'blue')

[wesnoth-bugs]

Modified on 2016-11-15

shiki wrote:

I did build wesnoth again with your last commits.

Then it works. Only when the Hexagon is active it's bad.

And hexagon + alternative terrain drawing works quite good, but it's not the same "good" like if all is disabled.

[Vultraz]

Seems fixed on a_r

[Vultraz]

Still reproducible at a09e2bb8583c.

[Vultraz]

Closing since accelerated_rendering has since been merged into master.

[CelticMinstrel]

Should this be reopened?

[Wedge009]

I don't think I was ever able to replicate this - similar to the water animations causing performance burden, I tend to test on high performance machines. Is it just a question of shroud removal? I somehow doubt it's specific to UtBS.

[knyghtmare]

since Hardware accelerated rendering has been enabled again on 1.17.x, can this be closed now?

[Wedge009]

For those able to replicate the original issue, please re-test now that #6855 is merged. Although, given knyghtmare asked the question nearly two months ago maybe it should just be closed anyway.

[soliton-]

I think it's fine to close. I can't see an issue either (though also fast machine) and with the recent changes it's unlikely this still exists in this form.

[gfgtdf]

The minimap code https://github.com/wesnoth/wesnoth/blob/1.17.14/src/minimap.cpp seems to have two codepaths: The Hardware-accelerated render_minimap and the non-Hardware-accelerated getMinimap, from looking at the code it seems like the render_minimap is only used for the minimap widget, for example in the lobby, the ingame minimap still uses getMinimap. Since this issue is exclusively (form what i tested some time ago) about the ingame minimap. There is little reason to believe this has changed.

[gfgtdf]

That said, i was never able to reproduce this with UtBS, only with very large maps, so maybe it shoudl be removed from the UtBS project

[gfgtdf]

Last time i tested/profiled this, (quite some time ago), wesnoth spend the most of the cputime in this call:

https://github.com/wesnoth/wesnoth/blob/f4ac9e03de6b4de85679955379a418adaac8a471/src/minimap.cpp#L285

[gfgtdf]

I just tested that this is still an issue, below an extreme case that will hopefully reproduce this even on better machines. To test it its important to have all minimap terrain drawings activated (none of the icons below the minimap should be blue ) (one can also test that it gets significantly better once you turn on all the buttons below the minimap (which woudl then be blue))

EDIT: And of course you must have shroud activated to test this.

[multiplayer]
    id = "gfg_test_large"
    name = "gfg_test_large"
    map_generation = lua
    [generator]
        id=gfg_test_largemap
        config_name=gfg_test_largemap
        create_map = <<
            local map = wesnoth.map.create(400,400, "Gg")
            map.special_locations["1"] = { 10, 10}
            map.special_locations["2"] = { 20, 10}
            return map.data
        >>
    [/generator]
    [side]
        side = 1
    [/side]
    [side]
        side = 2
    [/side]
[/multiplayer]

[Kaltxi]

Hello! I would like to take this as my first Wesnoth issue, if you don't mind :)

I took a stab at it (thanks @gfgtdf for the above map snippet) and found the following:

1. getMinimap is called multiple times during the movement, so at first I just made a flag and lazily recreated it after the whole movement is complete. But this leads to minimap not updating during the actual movement (only at the start and the end), which might not be desirable. So I suppose this one is a miss.
2. Indeed scale_surface_sharp takes a lot of time, so I went to investigate it.

First things first, it is possible to pull the lines calculating x/ysrcint and retrieving the pixel out of the two innermost loops, since they retrieve the same pixel over and over again. This gives a good boost, but still the lag is present.

The fact that the above change doesn't have any side-effects, I pondered why was it even there - by the looks of it, it is trying to do a weighted average of pixels in the src image region corresponding to the dest image pixel. But since we're retrieving the same pixel, that seems useless, and the whole calculation should yield the same pixel multiplied by some value and then divided by the same value. If I fix this by supplying the current pixel in region, then indeed we get an average, which yields a very blurry image.

My current guess is that the algorithm initially did the blurry average scaling, and then was modified to do sharp scaling by taking a single pixel, but the rest of the code remained unchanged. Above this function there are a bunch of variations, including some library's (xbrz) implementation of nearest neighbor.

I simplified the function to just do nearest neighbor like this:

const float xratio = static_cast<float>(src_w) / w;
const float yratio = static_cast<float>(src_h) / h;
for(int ydst = 0; ydst != h; ++ydst) {
    for(int xdst = 0; xdst != w; ++xdst) {
        const int xsrc = std::floor(static_cast<float>(xdst) * xratio);
        const int ysrc = std::floor(static_cast<float>(ydst) * yratio);
        dst_pixels[ydst*dst->w + xdst] = src_pixels[ysrc*src_w + xsrc];
    }
}

This yields almost identical image, and now takes absolutely no time (profiler can't even sample it). The movement now is snappy and there is no lag in user input, though there is still a small delay on move and corresponding 100% core utilization, but now it is attributed to image copying and memory handling. I might improve this further, but on smaller maps it should be good already.

Can someone provide feedback on this part and advise on the current implementation of scale_surface_sharp?

Also, another question: CONTRIBUTING.md suggests to run clang-format, which I would be happy to do, but I see no .clang-format file in the root of the repo, and my current;y editor simply applies default formatting botching everything. Where can I obtain the correct .clang-format?

[gfgtdf]

Interesting find! I looked at the code and i fully agree that the current code makes no sense at all.

This yields almost identical image

Wait, if what you said before is true, shouldn't it yield exactly the same image ?

Can someone provide feedback on this part and advise on the current implementation of scale_surface_sharp?

I doubt that anyone of the current team member knows that code well but i might be wrong

but I see no .clang-format file in the root of the repo, and my current;y editor simply applies default formatting botching everything. Where can I obtain the correct .clang-format?

I think it's in src/

[gfgtdf]

That said, in the long run we might want to use the gpu for this anyways, (remove the 'getMinimap' function and make the render_minimap function able to handle that case too). (clearly fixing this before would be good though, especially if it seems to be rather easy)

[Vultraz]

I'll try and make it use render_minimap. I just need to make it able to render the damn thing centered in the minimap area.

[Vultraz]

@Kaltxi tested your code, BTW, result looks perfect to me. Can you open a PR?

[Kaltxi]

Wait, if what you said before is true, shouldn't it yield exactly the same image ?

In my local testing I see a few pixels becoming a tad bit draker or lighter, perhaps there is a slight difference due to all the floating operations in the current implementation.

I think it's in src/

Ok, so it seems like the clangd looks at all parent folders for this file and it was finding it correctly, its just that all the files I've examined weren't formatted according to it. Should I run it anyway on the files I touch, even if that breaks all the hand-formatting that was there @gfgtdf?

@Vultraz Ok, I'll open a PR later today, thanks for testing.

[CelticMinstrel]

Should I run it anyway on the files I touch, even if that breaks all the hand-formatting that was there @gfgtdf?

It's up to you, but if you do run it, keep the reformatting in a separate commit from the actual code changes – the commit should have no functional changes at all.

[Vultraz]

Please don't include a formatting pass as part of the NN PR. There're a lot of files which aren't formatted properly at all, but there're also a lot which are hand-formatted to some extent. We don't blindly follow the clang-format output since it isn't always very good (maybe configuring it further could help, though).

[CelticMinstrel]

Basically the style guide is a guideline that hasn't always been followed. The Wesnoth source is quite old, and either the style guide has changed over time without updating older code, or there originally was no style guide and each contributor did whatever they preferred.

I don't think automatically running clang-format would ever be viable, honestly – there's always places where it's unable to get things right. However, it definitely isn't viable now. Someone would need to spend a huge amount of time and effort to (1) make sure the clang-format actually properly reflects the style guide, (2) reformat all the code to match the clang-format, and (3) add clang-format ignore comments to blocks of code that need them.

Just make sure that any code you add is hand-formatted (or even auto-formatted via "Format Selection") to either match the surrounding code or to conform to the style guide document. (I prefer the latter, but the former is probably acceptable too.)

[Vultraz]

"Format Selection" is what I do, FTR. Most of the time it produces the right results since the clang-format file is basically up-to-date.