Fields performance

[Aivean]

I'm planning to do some improvements to fields processing. This is an aggregate issue to keep track of the progress.

Current fields processing profile looks like this (scenario: hotel on fire):

Some key highlights:

---

I can identify several things that could be improved.

Improvements pertinent to the fields in general:

1. Improve memory layout

Currently fields are stored in array2d<map<type,field_entry>>, which optimizes memory usage when fields are very sparse. However, that doesn't work well for dense fields of same type (fire, hot air), in essence, current memory layout optimizes already fast case.

Current cases when fields are densely packed: fire, vents, migo camp, spiderweb.

The better layout would be: map<type,array2d<field_entry>>, which wastes some memory in case of the sparse fields, but at the same time saves memory when fields are dense and ensures cache coherency when checking neighbors.

Another possible layout could be: map<type,{ array2d<intensity>, array2d<age>, ... }>.

2. Split fields processing by type

Looking at map::process_fields_in_submap, every field entry is processed in arbitrary order. Each entry can have different type which is not known in advance, so for each entry lots of unrelated if clauses is executed. More than that, the whole processing is a huge code chunk, which doesn't work very well for instruction cache.

What could be done: split processing logic into bunch of small methods ("processors"). List of processors can be pre-calculated once per field type. When processing a field_entry, only processors that correspond to its type are executed, probably 2-3 out of ≈20+.

This also synergizes nicely with (1: memory layout), as field processing can be grouped per type.

Fire processing

1. item::weight is an obvious dominator. I think it could be cached, at least partially. Also, see Picking up items is too slow #47007
2. rng is overused to the point that it becomes a bottleneck.
   Per the discussion with Kevin it would be possible to replace some rng calls with faster (but slightly less fair) version as a stopgap measure. In the future rng calls could be reduced by utilizing approach based on Gillespie algorithm, i.e. calculate in advance when the next significant event (such as spreading) will occur.

[Aivean]

So far, I prototyped "memory layout change" + "fields processors" and it improved fire processing speed by factor of 1.5x.

The changes are pretty significant, so I'll be trying to split them into reviewable chunks.

[actual-nh]

Have you had time to look at the recurrent Fields test failures (#46256), BTW?

[Aivean]

Have you had time to look at the recurrent Fields test failures (#46256), BTW?

No, I haven't. Will do.

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions. Please do not 'bump' or comment on this issue unless you are actively working on it. Stale issues, and stale issues that are closed are still considered.