I broke the chunks!

ID:2077405
 
Apr 30 2016, 7:06 am
Resolved
BYOND Version:510.1340
Operating System:Windows 7 Ultimate 64-bit
Web Browser:Chrome 49.0.2623.112
Applies to:Dream Daemon
Status: Resolved
This issue has been resolved.
Descriptive Problem Summary:
Repeatedly removing and adding the same overlay with only an alpha change causes oddities with map chunks

https://tgstation13.org/msoshit/2016-04-30-0524-06.flv example.

This was triggered by a change in how the purple confetti like overlay that represents the gas called "plasma" in our atmos system, was done to make it change the alpha of the gas overlay based on how much there was.

old code:
/turf/open/proc/update_visuals()
    var/list/new_overlay_types = tile_graphic()

    for(var/overlay in atmos_overlay_types-new_overlay_types) //doesn't remove overlays that would only be added
        overlays -= overlay
        atmos_overlay_types -= overlay

    for(var/overlay in new_overlay_types-atmos_overlay_types) //doesn't add overlays that already exist
        overlays += overlay

    atmos_overlay_types = new_overlay_types

/turf/open/proc/tile_graphic()
    . = new /list
    var/list/gases = air.gases
    for(var/id in gases)
        var/gas = gases[id]
        if(gas[GAS_META][META_GAS_OVERLAY] && gas[MOLES] > gas[GAS_META][META_GAS_MOLES_VISIBLE])
            . += gas[GAS_META][META_GAS_OVERLAY]

new code:
/turf/open/proc/update_visuals()
    var/list/new_overlay_types = tile_graphic()

    for(var/overlay in atmos_overlay_types-new_overlay_types) //doesn't remove overlays that would only be added
        overlays -= overlay
        atmos_overlay_types -= overlay

    for(var/overlay in new_overlay_types-atmos_overlay_types)
        var/atom/A = overlay
        if (isnull(atmos_overlay_types[overlay]))
            A.alpha = new_overlay_types[overlay]
            overlays += overlay //New
        else if (new_overlay_types[overlay] == atmos_overlay_types[overlay])
            continue //Unchanged
        else
            //changed
            overlays -= overlay
            A.alpha = new_overlay_types[overlay]
            overlays += overlay

    atmos_overlay_types = new_overlay_types

/turf/open/proc/tile_graphic()
    . = new /list
    var/list/gases = air.gases
    for(var/id in gases)
        var/gas = gases[id]
        if(gas[GAS_META][META_GAS_OVERLAY])
            .[gas[GAS_META][META_GAS_OVERLAY]] = tile_graphic_alpha(gas[GAS_META], gas[MOLES])

/turf/open/proc/tile_graphic_alpha(list/meta, moles)
    return Clamp(255/meta[META_GAS_MOLES_VISIBLE]*moles,0,255)


There are some obvious bugs with this, (it doesn't round the alpha, so it would almost always be seen as changed.) and i haven't tested rather or not removing then re-adding the overlay is needed (re-adding might just work) but it seems to cause the issue in the video above.
Apr 30 2016, 10:53 am (Edited on Apr 30 2016, 11:02 am)
Is it the old code or the new code that triggers the issue?

I took a look at the video, and the way turfs are disappearing like that, that looks like potentially some kind of view anomaly. Chunks don't control whether turfs are shown or not, unless they're "extended" turfs with out-of-bounds objects on them, and even then the turf itself should not be made visible inappropriately; what you're seeing looks like turfs that should be visible disappearing.

I strongly suspect this issue is not beta-related, but I even more strongly I think I'm unlikely to make any headway on this without a test case. This is something I'm going to have to puzzle over in the debugger for sure. Is there any way you can strip down a test case?
Apr 30 2016, 2:45 pm
Also I should mention: You'll have a lot less appearance churn if you assign the overlays list in one shot. Adding and removing frequently also causes ID array churn. Performance will be much better if you can reduce that.
Apr 30 2016, 4:28 pm
its the new code that triggered it.

and i know its rather lame, it was mainly a proof of concept to see if using the same obj for all turfs's overlays, and changing the alpha before adding, would even work. it seems it does. I was gonna work on pref after that, when i noticed the bug.

I say its chunking related, because it seems like the effect is centered around map chunks. if i go up more, the black goes down relative to my mob more, resets, then repeats.

(oh, and mind you, my mob in that video has the ability see thru walls and in darkness)
Apr 30 2016, 5:19 pm (Edited on Apr 30 2016, 5:42 pm)
So this actually seems to be with dreamdeamon, i reproduced it easily by just repeating the same plasma gas dispersal test, and it happened in the same spots on reconnect. dd even crashed! (have the dump if you want it)

so i should be able to break this down to a test case and shoe horn that into sightcheck.zip.

(I can't find a app crash event for it (i think my crash handler is preventing them) but i was able to open it and get the crash info. it was in byondcore.dll address 7010EC96 (start address is 0x70050000 giving that an offset of 0xBEC96) Error was invalid memory access.)
Apr 30 2016, 5:59 pm
ok, so here is an odd occurrence.

The plasma overlay's alpha goes up, but not down.

I'm assuming this means that it's treating it as a new overlay, so that this is basically creating a fuckton of overlays? Meaning that the -= part isn't working because it has a different alpha (since it's a singleton shared object, and other turfs would have changed the alpha)?

Edit: Ya, the memory usage is definitely increasing more than it should.
May 1 2016, 12:09 am
If you're modifying an object before subtracting it from an overlays list, that will definitely interfere, because the exact same appearance has to be subtracted away.

This is definitely not a chunk issue (at least not directly), because 1) turfs disappearing in the patterns you're seeing isn't consistent with that, and 2) turfs aren't governed by the chunk code unless it's to make them visible when they're out of bounds.
May 1 2016, 2:27 am
I'm assuming this means that it's treating it as a new overlay, so that this is basically creating a fuckton of overlays? Meaning that the -= part isn't working because it has a different alpha (since it's a singleton shared object, and other turfs would have changed the alpha)?

Overlays lists are specialized lists that are content-unique. Every time you add or subtract something from the overlays list, the engine has to search for a matching overlays list. This is fast. I'm sure it uses some kind of binary algorithm. I'm not clear on the details.

Overlays can be added using:

* Icons
* Icon states (strings)
* Objects
* Appearances

However, internally the overlays and underlays lists only contain appearances.

When you add an object, you aren't actually adding the object itself to the overlays, you are adding the object's appearance.

That's why you can use one object and change its appearance-related values and then add the object to the overlays over and over again.

The trick to getting rid of the overlay if you do this is keeping track of the appearance itself.

In the case of alpha values, appearance churn can be a real bugbear. It might be of benefit to you to pre-generate 255 appearance variants at world startup and then cache them in a list by index:

var/list/alphaoverlays

var/lighting_manager/__lighting_manager = new()

lighting_manager
    New()
        alphaoverlays = list()
        var/obj/o = new()
        o.icon = 'lighting.dmi'
        o.layer = LIGHTING_LAYER
        o.appearance_flags = RESET_ALPHA|RESET_TRANSFORM|RESET_COLOR
        for(var/alpha in 0 to 255)
            o.alpha = alpha
            alphaoverlays += o.appearance


When you want to change the light level of a tile, you need to know two values: The old lighting alpha and the new.

var/list/l
if(t.overlays.len)
    l = t.overlays.Copy() //avoid double appearance churn
    l -= alphaoverlays[old_alpha+1]
else
    l = list()
l += alphaoverlays[new_alpha+1]
t.overlays = l


You can avoid the list copy on startup, since you are only doing a single operation:

turf/New()
    overlays += alphaoverlays[256-floor(255*clamp(light_level,0,1)]


TL;DR: I'd avoid the global singleton since you are working with appearances. Since you have a limited number of total permutations, you can probably just get away with 255 cached appearances. This will prevent a ton of churn and lookup that the singleton method induces.

I'm sure you can apply the light-level concept to your gas molar concentrations pretty easily. You are a capable ent, sir.

Check out Lummox's post on appearances and if you have more questions on the subject, I think Lummox and I are the only two people here that actually at any time had an understanding of what they were before I requested that they be exposed to the developer end of things. So... Yeah. Maybe Nadrew.
May 1 2016, 3:39 am
Wouldn't it be easier to just assign it to a new list.

We already track enough to know when something changes, maintain a gas overlays list, update it when needed, then assign it.

This would avoid the overhead of overlays.Copy().
May 1 2016, 4:32 am (Edited on May 1 2016, 4:38 am)
Wouldn't it be easier to just assign it to a new list.

If I understand your question, assigning the overlays via a new list would wipe out any existing overlays that the turf might potentially have. The copy is necessary to avoid the double appearance churn caused by a removal and then an addition.

It's my guess that the overhead of copying a list probably only containing one or two values is significantly lower than two binary searches through what is going to be (judging from SS13's reputation for limit pushing) a gargantuan amount of appearance data.

In this case, yes, the appearance churn is 2*O(log A), and the list copy is 1*O(log A) + O(B), but A will more than likely be on the order of tens of thousands and B will likely be on the order of a handful.

Seeing as you are mucking with SS13's airflow by the looks of it, you are touching some parts of that game's core that comprise likely the majority of the CPU consumption.

I could be wrong about an awful lot of this, though. Appearance caching and appearance (ab)use are two techniques I fielded to Eternia (resulted in a net failure that made me actually understand the churn problem) and that I helped Yut with for E:L and Epoch (I think this fixed a few of the issues he was running into).
May 1 2016, 6:03 am
Ya, we have made tile_graphic really fast before, (note the old code, it removes any overlays that no longer exist, and adds any that are new, rarely are both of these cases true)

But ya, while right now the only overlays a turf/open(anything not a wall) should have is atmos gas overlays, that could change, so a copy might be best.

It's too bad you can't += a list of things and get the same result, or that byond doesn't just process the new/old overlays on the next map tick/end of proc to auto batch.

This works splendidly.
May 1 2016, 6:07 am
In response to Lummox JR
Lummox JR wrote:
If you're modifying an object before subtracting it from an overlays list, that will definitely interfere, because the exact same appearance has to be subtracted away.

This is definitely not a chunk issue (at least not directly), because 1) turfs disappearing in the patterns you're seeing isn't consistent with that, and 2) turfs aren't governed by the chunk code unless it's to make them visible when they're out of bounds.

I should note that fixing this issue made the bug go away (and made the code much faster).

So it's something to do with massive fucktons of overlays, and it might be best to close or defer this as thats not something I'd imagine you want to prioritize looking at.

In fact, it could easily be an overflow from the massive amount of overlays, I'd imagine the crash offset would hint to that.

If you want, I can revert my changes and give you a test case, but i could only reproduce the crashing, not the blacking out issue.
May 1 2016, 3:27 pm
My guess is that some kind of overflow broke something in the engine, so yeah, I think I'm just gonna mark this resolved.

To address Ter's point, when new unique overlay lists (ID arrays) are created or looked up, the search is actually roughly O(N), N being the total number of arrays. The algorithm looks something like this:

1) For each ID array:
2) Does the length match?
3) Loop through each item and bail out if it's not a match.
4) If a match was found, use it. Otherwise this is a new array.

Subtracting an object from overlays looks like this:

1) For overlays -= O, grab src's and O's appearances.
2) Find the ID list used by src's appearance for overlays, and call IdArray_Remove() which will return an existing or new ID array ID (or NONE, if empty). This process grabs the ID list for the old array, removes the given ID, and then tries to find an existing list that matches the result or create a new one otherwise.
3) Create a copy of src's appearance, but change the ID array for overlays to the new ID.
4) Assign the new appearance to src. This will incref the new overlays ID array, and decref the old one. (Also, any appearance IDs in the overlays lists get inc/decref'd appropriately.)

Appending to the overlays list is similar, except it calls IdArray_Append() instead of IdArray_Remove().

Naturally doing this multiple times will cause a lot of churn, because you're inc/decrefing a lot of appearances and ID arrays both. If you assign the overlays list in one shot, you avoid multiple ID array lookups and inc/decref calls.
May 1 2016, 3:28 pm
Lummox JR resolved issue
May 1 2016, 5:20 pm (Edited on May 1 2016, 5:25 pm)
In response to Lummox JR
Lummox JR wrote:
To address Ter's point, when new unique overlay lists (ID arrays) are created or looked up, the search is actually roughly O(N), N being the total number of arrays.

Oh. Wow. Yeah, that's way worse than I thought. In SS13's case, then, where there are probably going to be tens of thousands of unique appearances/overlays lists, then it makes even more sense to do an O(A)+O(B) rather than 2(O(A)).

With an O(log N) appearance generation method, the optimization would be pretty small, but with an O(N) implementation, it's just damn smart for a bigger game.
May 1 2016, 5:23 pm
It's only the ID arrays that are O(N) of course. Appearances themselves are O(log N) because they use a self-balancing binary tree. Still, even if the ID arrays weren't an issue, doing multiple remove/add operations on the overlays list would still be worse than doing one.