Achievement tracker takes 40% of game load time (≈13 seconds)

[Aivean]

Describe the bug

Working on the savefile from #45822 I noticed that achievements_tracker::deserialize takes 40% of save loading time, or ≈13 seconds on my machine:

The culprit seems to be unordered_map constructor:

full signature

std::__1::unordered_map <std::__1::map<
        std::__1::basic_string < char, std::__1::char_traits <
                                       char>, std::__1::allocator<char>>, cata_variant, std::__1::less <std::__1::basic_string<char,
        std::__1::char_traits < char>, std::__1::allocator<char>> >, std::__1::allocator <std::__1::pair<
        std::__1::basic_string < char, std::__1::char_traits <
                                       char>, std::__1::allocator<char>> const, cata_variant> > >, event_summary, cata::range_hash, std::__1::equal_to <std::__1::map<
        std::__1::basic_string < char, std::__1::char_traits <
                                       char>, std::__1::allocator<char>>, cata_variant, std::__1::less <std::__1::basic_string<char,
        std::__1::char_traits < char>, std::__1::allocator<char>> >, std::__1::allocator <std::__1::pair<
        std::__1::basic_string < char, std::__1::char_traits <
                                       char>, std::__1::allocator<char>> const, cata_variant> > > >, std::__1::allocator <std::__1::pair<
        std::__1::map < std::__1::basic_string < char, std::__1::char_traits <
                                                       char>, std::__1::allocator<char>>, cata_variant, std::__1::less <std::__1::basic_string<char,
        std::__1::char_traits < char>, std::__1::allocator<char>> >, std::__1::allocator <std::__1::pair<
        std::__1::basic_string < char,
        std::__1::char_traits < char>, std::__1::allocator<char>> const, cata_variant> > > const, event_summary> > >
::unordered_map(std::__1::unordered_map<
        std::__1::map < std::__1::basic_string < char, std::__1::char_traits < char>, std::__1::allocator<char>
>, cata_variant, std::__1::less <std::__1::basic_string<char,
        std::__1::char_traits < char>, std::__1::allocator<char>> >, std::__1::allocator <std::__1::pair<
        std::__1::basic_string < char, std::__1::char_traits <
                                       char>, std::__1::allocator<char>> const, cata_variant> > >, event_summary, cata::range_hash, std::__1::equal_to <std::__1::map<
        std::__1::basic_string < char, std::__1::char_traits <
                                       char>, std::__1::allocator<char>>, cata_variant, std::__1::less <std::__1::basic_string<char,
        std::__1::char_traits < char>, std::__1::allocator<char>> >, std::__1::allocator <std::__1::pair<
        std::__1::basic_string < char, std::__1::char_traits <
                                       char>, std::__1::allocator<char>> const, cata_variant> > > >, std::__1::allocator <std::__1::pair<
        std::__1::map < std::__1::basic_string < char, std::__1::char_traits <
                                                       char>, std::__1::allocator<char>>, cata_variant, std::__1::less <std::__1::basic_string<char,
        std::__1::char_traits < char>, std::__1::allocator<char>> >, std::__1::allocator <std::__1::pair<
        std::__1::basic_string < char, std::__1::char_traits <
                                       char>, std::__1::allocator<char>> const, cata_variant> > > const, event_summary> > > const&)

Steps To Reproduce

1. Profile the loading of the savefile from Game hangs for a couple seconds when approaching my base after being far away from it. #45822

Expected behavior

The serialized json form for achievement tracking is not that big, so I suspect some inefficiency in the implementation.

Versions and configuration

- OS: MacOs
    - OS Version: Name: Mac OS X; Version: 10.14.6; Build: 18G103; 
- Game Version: 0.E-8922-gb130292b1c [64-bit]
- Graphics Version: Tiles
- Game Language: English [en]
- Mods loaded: [
    Dark Days Ahead [dda],
    Disable NPC Needs [no_npc_food],
    SpeedyDex [speedydex],
    Stats Through Kills [stats_through_kills],
    Mythical Martial Arts [MMA],
    Alternative Map Key [alt_map_key],
    Magiclysm [magiclysm],
    Graphical Overmap [Graphical_Overmap],
    Graphical Overmap Magiclysm [Graphical_Overmap_Magiclysm],
    No Fungal Monsters [No_Fungi]
]

[Aivean]

Some of the relevant discord discussion:

BrettD:

   event_multiset &stats_tracker::get_events( event_type type )
   {
       return data.emplace( type, event_multiset( type ) ).first->second;
   }

stats_tracker.cpp line 226
Feels like it's constructing a event_multiset every time it's called

Aivean:
changing stats_tracker::get_events to lookup first didn't help, as jbtw predicted, and the offender method didn't change, I think it means that get_events actually inserts elements more often than not.
And the real problem is somewhere up the stack

[jbytheway]

OK, I've figured out two reasons why this was so slow:

• A lot of statistics were being computed twice in quick succession when we could instead just reuse the previous computation.
• value_constraint::permits can be used to constrain a particular value to equal some statistic. Currently it recomputes the value of that statistic every time it compares against it, which is unnecessarily expensive.

Working on fixes now.

[jbytheway]

Note that all the slowness is due to achievement_return_to_first_omt, because that involves a constraint against a value of a statistic which is expensive to compute.