Cataclysm-DDA icon indicating copy to clipboard operation
Cataclysm-DDA copied to clipboard

Improve performance in npc::has_potential_los

Open CLIDragon opened this issue 1 year ago • 0 comments

Summary

Performance "NPCs take less time to check for enemies."

Purpose of change

See #75947.

Describe the solution

Replace using a point as a key to the cache with int64_t. Honestly, I am not sure why this works. I thought perhaps that the hash function for points was bad, but running a benchmark on QuickBench (link) returns basically the exact same numbers, for both hits and misses, which is not what I would expect from an ~8x speedup.

Function call numbers also seem low - at 50 NPCs each acting every tick, there should be approximately 9,000,000 calls to npc::has_potential_los each in-game hour, but VS only measured ~350000 over several.

A potential problem is it relies on all dimensions in the given tripoint_bub_ms being <1024. I didn't add bounds checking because the previous solution (using a point and two int32s) has the same issue.

Describe alternatives you've considered

  • Replacing std::unordered_map with an alternative implementation. The benchmarks I looked at - here and here - indicate that the best alternative implementations are 2-3x faster. In this case, I managed to get a decent speedup without but it may still be an option in future.

Testing

Before image

After image

Additional context

CLIDragon avatar Aug 28 '24 11:08 CLIDragon