Quadratic complexity in `npc_regen_ai_cache`

[CLIDragon]

Describe the bug

npc_regen_ai_cache calls has_potential_los for each npc and each monster. This leads to $O(n^2 + nM)$ time, where $n$ is the number of npcs and $M$ is the number of monsters. In this case, there are 43 npcs and 62 creatures in total.

Attach save file

N/A.

Steps to reproduce

1. Spawn a new character
2. Debug teleport your way to the refugeee hub.
3. | - wait till next day.
4. Make yourself coffee, read a book, etc.

Expected behavior

Not taking this long?

Screenshots

Versions and configuration

• OS: Windows
  • OS Version: 10.0.22631.3958 (23H2)
• Game Version: 0.G-10670-g28e6a2a175-dirty [64-bit]
• Graphics Version: Tiles
• Game Language: System language []
• Mods loaded: [ Dark Days Ahead [dda], Disable NPC Needs [no_npc_food], Portal Storms Ignore NPCs [personal_portal_storms], Slowdown Fungal Growth [no_fungal_growth] ]

Additional context

I'm not familiar enough with this part of the code to tell what needs to be changed. I suspect that regen_ai_cache should be called less often, though it is also possible that skew_vision_cache is doing extra work. Or possibly lru_cache_t is just really poorly implemented.

[CLIDragon]

Patch set to replace lru_cache_t with a plain std::unordered_map. Performance seems to consistently improve from ~40% to ~37% CPU time, but there's too much noise to observe a measurable change in wall clock time.

Patch Set

``` diff --git a/src/map.cpp b/src/map.cpp index 566af69b02..3e9bfb6bd5 100644 --- a/src/map.cpp +++ b/src/map.cpp @@ -7807,10 +7807,12 @@ bool map::sees( const tripoint_bub_ms &F, const tripoint_bub_ms &T, const int ra return false; // Out of range! } const point key = sees_cache_key( F, T ); - char cached = skew_cache.get( key, -1 ); - if( cached >= 0 ) { - return cached > 0; + auto cached = skew_vision_cache.find(key); + if (cached != skew_vision_cache.end()) + { + return cached->second > 0; } + bool visible = true; // Ugly `if` for now @@ -7827,7 +7829,7 @@ bool map::sees( const tripoint_bub_ms &F, const tripoint_bub_ms &T, const int ra } return true; } ); - skew_cache.insert( 100000, key, visible ? 1 : 0 ); + skew_cache[key] = visible ? 1 : 0; return visible; } @@ -7860,7 +7862,7 @@ bool map::sees( const tripoint_bub_ms &F, const tripoint_bub_ms &T, const int ra last_point = new_point; return true; } ); - skew_cache.insert( 100000, key, visible ? 1 : 0 ); + skew_cache[key] = visible ? 1 : 0; return visible; } @@ -11108,9 +11110,10 @@ void map::invalidate_max_populated_zlev( int zlev ) bool map::has_potential_los( const tripoint_bub_ms &from, const tripoint_bub_ms &to ) const { const point key = sees_cache_key( from, to ); - char cached = skew_vision_cache.get( key, -1 ); - if( cached >= 0 ) { - return cached > 0; + auto cached = skew_vision_cache.find( key ); + if (cached != skew_vision_cache.end()) + { + return cached->second > 0; } return true; } diff --git a/src/map.h b/src/map.h index d804021569..36e0e66aa6 100644 --- a/src/map.h +++ b/src/map.h @@ -2601,7 +2601,7 @@ class map /** * Cache of coordinate pairs recently checked for visibility. */ - using lru_cache_t = lru_cache; + using lru_cache_t = std::unordered_map; mutable lru_cache_t skew_vision_cache; mutable lru_cache_t skew_vision_wo_fields_cache; ```

[CLIDragon]

has_potential_los reduced from ~40% to ~5% using just a std::unordered_map

This is substantiated when using an lru_cache, with the cache adding a 1% total time (~20%) overhead.