[WIP] Refactor: Significant speed-up for ManaOptions

[Alex-Vasile]

Benchmark Results: 1,400x faster and 224x less RAM allocation

PRE: https://github.com/magefree/mage/commit/f99da274cdac3c566a2e5d6b7fcb986ddf2dfca1 POST: latest commit to this branch Execution time of testCascadingCataracts: 510s -> 0.35s Memory usage of addManaWithCosts(): 20,220 MB -> 90 MB

To get times, run all of ManaOptionsTest so that the startup time is not being counted as part of testCascadingCataracts.

Results are from a 16GB M1 MacBook Pro. Difference will likely become even more pronounced on computers with slower RAM and lower RAM bandwith.

Changes

• Change ManaOption from an ArrayList to a LinkedHastList in order to speed up computations by not adding duplicates in the first place.
• Changed getPossiblePayCombinations to use a LinkedHashSet rather than a List in order to speed up computations by not adding duplicates in the first place.
• Removed assertDuplicatedManaOptions and removeDuplicated since they are not needed anymore.
• Removed removeFullyIncludedVariations since the speed-up did not appear to be worth the effort of doing it.

TODO

• [x] Answer and address all TODO comments
• [x] Figure out why .contains() isn't working as expected.
• [x] Add hashCode() and equals() to both ConditionalMana
• [x] Re-implement getPossiblePayCombinations to no longer use String to decrease memory requirement (It accounts for use 97% of subtractCostAddMana memory usage. https://github.com/magefree/mage/blob/e2c7db0a47ea62b854c4333737a45a0b61e05897/Mage/src/main/java/mage/abilities/mana/ManaOptions.java#L494-L522
• [x] Figure out why isExistingManaCombination is using Mana.getMoreValuableMana. (Mana.getMoreValuableMana accounts for 99% of subtractCostAddMana CPU usage. https://github.com/magefree/mage/blob/e2c7db0a47ea62b854c4333737a45a0b61e05897/Mage/src/main/java/mage/abilities/mana/ManaOptions.java#L536-L544
• [x] Figure out failing tests
• [x] Figure out how to write a reproducible benchmark test to calculate before and after. (currently connecting to server and adding problem cards (Cascading Cataracts, even post #9068 it will slow down the game if you add 5+ as well as 5 of each land under the same player)

Potential improvements on this

• Memoizing getPossiblePayCombinations since it gets called multiple times a round and accounts for the vast majority of the computation time. Much of that can be eliminated at the cost of slightly higher memory usage on the server.

Closes #7710.

[Alex-Vasile]

Below is the scaling for a variation of testCascadingCataracts. Comment out the Assert.asserEquals line since that has a hardcoded number. Then replace the card numbers with n so that the same number of each card is added.

n	manaOptions.size()
4	3,698
5	11,146
6	28,289
7	63,343

At these larger sizes removeFullyIncludedVariations starts becoming the bottleneck in terms of CPU again. The RAM usage is dominated by Mana.copy() and adding to the HashSet, neither of which are really avoidable at this point since I avoided copying or creating a new Mana object whenever I could.

There is not much to be done about the memory allocation since all of those Mana objects are needed. ~But disabling removeFullyIncludedVariations significantly speeds up the run time at these larger sizes.~ I have disabled it

[Alex-Vasile]

I think to get better performance/scaling (certainly for the memory aspect) we'd have to switch our mana calcs to the way that humans do it: starting with the abilities we want to activate first.

Pick an ability we want to activate, search for sources that can satisfy the mana requirements and stop looking as soon as we find the first one that does.

Now, I have a feeling this will scale better than trying to generate every possible combination of mana, but I don't know what kind of problem we would get instead, and if we can avoid infinite loops. Perhaps something to look into at some point in the future if the current approach becomes a bottleneck.

[DeepCrimson]

Great work finding and implementing this huge performance win! 🎉

[Alex-Vasile]

@DeepCrimson. Did you take a look at the rest of the changes here (particularly in ManaOptions) and see anything strange with the actual algorithm changes?

[DeepCrimson]

@DeepCrimson. Did you take a look at the rest of the changes here (particularly in ManaOptions) and see anything strange with the actual algorithm changes?

Yes I took a look, left a few comments but changes look good to me! I'd approve this if I had merge access.

[JayDi85]

Possible research/idea: use standard lib to work with a combinations data (see google's guava lib).

[Alex-Vasile]

Possible research/idea: use standard lib to work with a combinations data (see google's guava lib).

Use Gauava for which part? I can see if I can use any of it's caching to deal with caching getPossiblePayCombinations (at least for one round) as it gets called so many times, and is costly.

[JayDi85]

Use Gauava for which part?

Possible mana's combinations/collections. It's can generate combinations, store it, sorting, deduplicating, etc. And it's already optimized for performance and memory usage.

[Alex-Vasile]

1. ~~Equal/hash fixes in inherited classes~~, docs about it.

2. Research color depended code in ManaOptions usage (is it exists);

3. Additional test for ConditionalMana;

I think 3 is satisfied. I don't know what you mean by 2.

[Alex-Vasile]

Possible research/idea: use standard lib to work with a combinations data (see google's guava lib).

We can open a separate issue into this (seeing if there is a library that can make this faster).

But I think this PR will solve the issue well enough for now.

[Alex-Vasile]

• ~Equal/hash fixes in inherited classes~, docs about it.
• Research color depended code in ManaOptions usage (is it exists);
• Additional test for ConditionalMana;

I plan to merge this soon and move on. What do you mean by "Research color depended code in ManaOptions usage (is it exists);"?

[JayDi85]

@Alex-Vasile do not merge active PRs until active discussion/research finish (it's a bad thing and goes to unstable/unfinished code and technical debt, see your use case with auto-choices in #9206). Also do not merge any UI/UX related PRs until review.

What do you mean by "Research color depended code in ManaOptions usage (is it exists);"?

You must take ManaOptions objects and research the usage. Are there any code that:

• uses a color searching in ManaOptions (you added "any" instead multicolors -- is it broke something or not -- good unit tests aren't a proof due low coverage percentage, must be code review);
• uses color priority for AI calculation and mana payments. As example: mana payment uses color priority (pays colored mana first).

[Alex-Vasile]

@Alex-Vasile do not merge active PRs until active discussion/research finish (it's a bad thing and goes to unstable/unfinished code and technical debt, see your use case with auto-choices in #9206). Also do not merge any UI/UX related PRs until review.

Fair enough, I should have tested that one more.

What do you mean by "Research color depended code in ManaOptions usage (is it exists);"?

You must take ManaOptions objects and research the usage. Are there any code that:

• uses a color searching in ManaOptions (you added "any" instead multicolors -- is it broke something or not -- good unit tests aren't a proof due low coverage percentage, must be code review);

Not in this PR. {ANY} has been added to ManaOptions for a variety of cards, I did not create the AnyColorManaAbility. I am not sure what part of the changes you think would impact this.

• uses color priority for AI calculation and mana payments. As example: mana payment uses color priority (pays colored mana first).

Which part of the changes do you think would impact this?

[Alex-Vasile]

Okay. I think I have addressed all of the concerns from before.

Instead of removing getPossiblePayCombinations I tried implementing a more efficient version of it but ultimately couldn't get it working properly. I scrapped it and just went back to the O(n^2) approach that we had before. Even with it's poor scaling, the board will have to get quiet large before it it becomes noticeable.

The benchmark listed at the top, 115MB of ram used (not retained all at once) and 0.5s, is for the following board:

• 5x Plain
• 5x Island
• 5x Swamp
• 5x Mountain
• 5x Forest
• 5x Desert
• 3x Cascading Cataracts

That's 33 lands total for 1 player. I don't think that many lands or mana sources will ever show up in most games. And if they do, I think that other portions of the engine (specifically the copying of state over and over) will be the bottleneck.

[Alex-Vasile]

I plan to merge this at the end of the week unless any issues can be found with it