Allow filter uniques to have conditionals and work with modifiers #12404
Conversation
|
The edits for stuff like Policy and Techs might look weird, however, they are to plan ahead incase they get their filter information cached as well |
| @@ -298,6 +298,9 @@ open class UniqueMap() { | |||
|
|
|||
| fun hasUnique(uniqueType: UniqueType, state: StateForConditionals = StateForConditionals.EmptyState) = | |||
| getUniques(uniqueType).any { it.conditionalsApply(state) && !it.isTimedTriggerable } | |||
|
|
|||
| fun hasUnique(uniqueTag: String, state: StateForConditionals = StateForConditionals.EmptyState) = | |||
There was a problem hiding this comment.
For all of these, I'm not sure I understand the difference in naming convention between tags and types. It would imply to me that the typed version should also be renamed to "hasTypedUnique". And since what we're doing between each version of the function is fundamentally the same code (it's literally copy-pasted), there doesn't seem to be a good reason for the distinction
There was a problem hiding this comment.
Uniques are known text strings that indicate code, they are known.
Tag uniques are arbitrary text strings that are used for matching only.
If we're looking for a known UniqueType, that's a unique. If we're looking for arbitrary text, as in filters, that's a tag.
The naming here still feels very wrong, I'm willing to give it a go but if it confuses me in the future I'll change it to tags.
There was a problem hiding this comment.
From a technical standpoint, I feel like the distinction between tags and uniques is minor. Once we actually have the unique, how we manipulate it is functionally the same, and the only difference is that for performance and maintainability reasons, we typically only deal in UniqueTypes
Actually, there is a spot where one can build their own functioning unique via tags. As a ruins reward, do "[{This Unit} {non-[Does not upgrade from ruins-like effects]}] upgrades for free including special upgrades". No, we don't have a unique for this. And from a modder perspective, there's no reason to view the tag as if it's just a tag
| @@ -307,6 +310,10 @@ open class UniqueMap() { | |||
| ?.asSequence() | |||
| ?: emptySequence() | |||
|
|
|||
| fun getUniques(uniqueTag: String) = innerUniqueMap[uniqueTag] | |||
| @@ -317,10 +324,24 @@ open class UniqueMap() { | |||
| else -> it.getMultiplied(state) | |||
| } | |||
| } | |||
|
|
|||
| fun getMatchingUniques(uniqueTag: String, state: StateForConditionals = StateForConditionals.EmptyState) = | |||
|
|
||
| fun hasMatchingUnique(uniqueType: UniqueType, state: StateForConditionals = StateForConditionals.EmptyState) = | ||
| getUniques(uniqueType).any { it.conditionalsApply(state) } | ||
|
|
||
| fun hasMatchingUnique(uniqueTag: String, state: StateForConditionals = StateForConditionals.EmptyState) = |
|
I'm unclear on the use case you intend for this. Can you give me an example? Also, this change seems to not cache tag uniques which do not require state, which seems unnecessary - all uniques with no modifiers can be checked for in singleFilter and cached. This change could have significant performance implications, essentially negating the filter caching, since it means that to check for filters we need to check tag uniques with extra steps |
| val otherUniqueSources = promotions.getPromotions().flatMap { it.uniqueObjects } + | ||
| statuses.flatMap { it.uniques } | ||
| val uniqueSources = unitUniqueSources + otherUniqueSources |
There was a problem hiding this comment.
What's with assuming that promotions won't provide conditional tags? I can totally see modders using this
There was a problem hiding this comment.
I'm not sure I understand the question. Promotions are being checked here, no?
Tbh, I haven't explored all of the possible use cases myself yet. I've mostly been focused on other stuff, since I've distracted by a number of other projects. So I probably would need to look at what other mods are currently doing, before I can give an answer here. That said
It is possible that a mod would want something like
I have actually a separate question here: Is it known how expensive multifilter is? Because imo, it would seem to me that this would be where the primary concern should be for uniques with no conditonals. While I'm aware that there would be a cost regardless, it seems to me that at that if we're worried about tags without conditionals the only real thing would be to add a cache in the unique itself to skip through I'm not trying to downplay the performance impact (I'm sure you've profiled it and tbh, I kinda expected this to be the biggest issue given the caching that was done), but it seems unlikely to me that this is where the performance hit would be (besides, I guess, the fact that we're doing a lookup twice) and not, say, building a |
|
The performance hit is especially significant for terrains - any tile you want to check tileFilter on, you need to check all of its terrains, and if that can be conditional you're looking at a lot of checks. And when automating e.g. workers you need to check a lot of tiles, and the multiplication hurts. The performance hit is not in constructing the states, as much as it is in the hashmap access - which for all it's "O(n)"-ness is still non-trivial (that's why I separated uniques to a EnumMap which is much more efficient) With caching (on 30s profiling session): Without: So that's like a 700ms / 30,000, which is like a 2.3% difference, which all in all is not huge and definitely something we can forgo for a good enough feature gain |
Sure, but in this case no matter what you do you're going through a HashMap with strings as keys. That's why I would expect that while there would be an impact, it shouldn't be in whether or not we cache information on uniques with no conditionals, but rather in either checking |
|
Status update:
So I still haven't actually looked through other mods or so for use cases yet. And since I didn't ping modders when I asked on discord, my question got buried. Tbh, I'm not sure how productive asking the question "what use case would this be for", given that the current mod devs (probably especially including myself as I focus on other projects more) won't be thinking about stuff in terms of new features unless they themselves were trying to implement said feature. And tbh the main purpose of this PR is mostly to open up potential options for mod devs
So, I still don't have a way of profiling this without getting a license for Idea Ultimate. But I can write a micro benchmark using https://github.com/Kotlin/kotlinx-benchmark, though you can take my results with a grain of salt if you want tbh. Tl;dr: I think your initial assumption is wrong, the problem 100% is Multifilter, and you just got lucky by dumping multifilter inside of the cache too. Checking the terrains for conditionals is extremely cheap, especially if it has none, even without caching. And I'm pretty sure we can optimize this to not be that big a deal Benchmark methodologyIt's extremely likely that some aspect of my methodology is flawed here. Actually it probably is flawed. First things first, I changed fun matchesFilter(filter: String, state: StateForConditionals? = null): Boolean =
when (Constants.vers) {
1 -> firstTest(filter, state)
2 -> secondTest(filter, state)
3 -> thirdTest(filter, state)
else -> secondTest(filter, state)
}
fun firstTest(filter: String, state: StateForConditionals? = null): Boolean =
MultiFilter.multiFilter(filter, {
cachedMatchesFilterResult.getOrPut(it) { matchesSingleFilter(it) } ||
state != null && hasUnique(it, state) ||
state == null && hasTagUnique(it)
})
fun secondTest(filter: String, state: StateForConditionals? = null): Boolean =
cachedMatchesFilterResult.getOrPut(filter) { MultiFilter.multiFilter(filter, { matchesSingleFilter(it) || hasTagUnique(it) }) }
fun thirdTest(filter: String, state: StateForConditionals? = null): Boolean =
cachedMatchesFilterResult.getOrPut(filter) { MultiFilter.multiFilter(filter, { matchesSingleFilter(it) }) } ||
state != null && hasUnique(filter, state) ||
state == null && hasTagUnique(filter)I also added a var to Constants so it can check which version it's checking. In the benchmark itself, I'm using the code in the unit tests to help setup the game details. Then the actual benchmark uses the following to test. Ignore the function name, I simplified the test later on while I was doing it @Test
@Benchmark
fun cityTestForExample3() {
Constants.vers = 3
actualTest()
}
fun actualTest() {
game.makeHexagonalMap(3)
game.setTileTerrain(Vector2(0f, 1f), Constants.grassland)
game.setTileTerrainAndFeatures(Vector2(0f, 2f), Constants.grassland, Constants.forest)
for (i in 0..<300) {
val t1 = game.tileMap.tileList.filter { it.matchesFilter(Constants.grassland) }
val t2 = game.tileMap.tileList.filter { it.matchesFilter(Constants.forest) }
val t3 = game.tileMap.tileList.filter { it.matchesFilter("matchesTest") }
}
}Each of the benchmarks are the same except for the It should be obvious something went wrong for test 3. Apparently the laptop running this got unplugged during it and stopped running in performance mode as a result. However, it's results prior to being unpluged ranged around 457 ops/s Conclusions
|
|
This pull request has conflicts, please resolve those before we can evaluate the pull request. |
# Conflicts: # core/src/com/unciv/logic/automation/ai/TacticalAnalysisMap.kt
|
Conflicts have been resolved. |
|
@yairm210 2 updates from last real push, about 10 days from last real discussion. Can I get an update on where this PR is in terms of blockers? Avoiding multifilter where available should address your concerns about performance, questions about use cases likely would be a difficult question to answer without this in practice, and the only open question in my eyes is the naming convention of the new functions, to which I already stated why I didn't agree your suggestion |
|
Mergeable 👍🏿 |
|
Another 1% runtime addition that we can remove by caching is the building of the state every tile we check |
Also this other state can be the same one as used above
|
Again, I'm not sure that's the case given my micro benchmark. Even looking at your screenshots, the cost of the function went down from 1010 ms to 460 ms which should be far more notable than the cost from the second hashmap lookup. Again, not saying there isn't an extra cost there (would be strange if there wasn't, but that the cost is minimal compared to that of multiFilter. Also I don't think the string lookups are as cheap as you think they are (at this scale, obviously), but could be wrong. There's a reason Kotlin often works with |
|
The latency cost went up with this commit, not down |
|
That's an unfair comparison though |
|
Methodology: Run IntelliJ Profiler on ConsoleLauncher for 30s Regarding variance: There are 2 kinds of 'function triggers function' calls: 1:1 and 1:N. The 1:N calls (for example "for unit in units" "for tile in tiles") can vary significantly depending on number of players, map size, and turn. The 1:1 calls are relatively stable - meaning if a child is X% runtime of its parent that's largely consistent, and this holds for stacks of 1:1 calls as well. All that said Current master
The time spent on multifilter in general for checking if this is indeed 'multi' is around 10%, so we did shave off some runtime here Your branch
All in all matching itself is now ~2x as expensive. Multifilter in general: That's with your "avoid multifilter function when possible* changes, and it's still 1400 ms more Add to that the matchesTerrainSingleFilter increase of 900ms, which doesn't use multifilter at all, we're getting to 2300 extra ms out of 30,000 ms runtime, or 7.6% of runtime spent on these changes |
|
You were right about the conditional check being really fast though, the major timesink is the hashmap retrieval (as usual) |
|
To be fair, part of the reason that this is such a heavy change is because the rest of Unciv is so hyper optimized now. If you had introduced this change 2 years ago it would have been barely noticable |
|
Huh... Well, guess I was wrong then on where the costs are. Considering how there's basically nothing else here to discuss regarding performance (multiFilter isn't as bad as I thought it was, especially given my micro benchmark, and conditionalsApplies had a minor effect as I suspected), it really is the hashmap lookup itself that's this expensive. Kinda surprised just that is so much more expensive than everything here, to the point where I'd half wonder if there's a way to have a more optimized hash code here or something. I don't necessarily think any amount of caching for known uniques would help either since you still need to actually get the unique somehow to check conditionalsApplies |
|
Side note on state creation, btw: we can probably in theory cut a bit more more on it as we can precalculate states for units and cities as well. I was almost toying with the idea when I was looking into fixing the state for cities with uninitialized tiles, but I figured it was out of scope |
… once when loading map and again every time there is an ownership change
…ditionals will work
The purpose of this PR is to allow for filter uniques to have conditionals of their own, to add flexibility to mod creators. I'm not entirely sure where the use cases would be in the current known mods (aside from a known side effect I'll mention later), however, it should minimum allow for
"filter <hidden from user>"uniques to work properly in all cases, rather than the current situation (which is currently inconsistent and relies on the object in question to have been updated to usehasTagUniqueinstead ofuniques.containsKnown side effects/notable changes
This is especially helpful for Rekmod which is missing a civ in Lekmod that has this functionality in for city centers