Small performance patch: skip empty freelist slots during sync_step

[victor_18993]

While profiling fast-forward simulation on a large pak128.german save, I found that freelist_iter_tpl::sync_step was checking every slot in every chunk, including the empty ones.

Across the freelist users measured in this save, around 89% of the tested slots were empty. This was not true for the expensive private_car pool, which is densely occupied, but it caused a lot of unnecessary work in sparse, high-churn pools such as movingobj, smoke clouds, road signs and part of the pedestrian pool.

The attached patch changes the iteration so that it jumps directly from one active bit to the next in the occupancy bitmap, instead of testing every slot.

The processed objects remain the same, the ascending order is preserved, and the live bitmap is read again after every object, so self-removal during sync_step keeps the same behaviour as before.

Since std::bitset has no portable way to find the next active bit, the patch uses a small fixed-size bitmap with a portable trailing-zero scan:

- GCC and Clang: __builtin_ctzll
- 64-bit MSVC: _BitScanForward64
- 32-bit MSVC: _BitScanForward on the low and high halves

A/B results on the same heavy save, using 50,000 fast-forward steps and 6 runs per version:

Code Select Expand

                baseline          patched
total step      776-807 ms        702-750 ms
mean            791 ms            729 ms
movingobj sync  ~62 Mcyc          ~4 Mcyc
pedestrian      ~273 Mcyc          ~248 Mcyc
private_car      ~1025 Mcyc        ~1001 Mcyc
route calls      846-847            846-847

The total-time distributions did not overlap: the fastest baseline run was still slower than the slowest patched run. The mean improvement was about 7.8% in this workload.

The largest local improvement is movingobj, which drops from roughly 62 to 4 Mcyc. private_car does not change significantly, as expected, because its pool is dense and most of its cost is the real per-car work in do_drive and can_enter_tile.

I also added a standalone equivalence test covering:

- empty and full bitmaps;
- first and last slots;
- the 63/64 word boundary;
- multiple bitmap sizes;
- thousands of random patterns;
- self-removal and later-bit changes during iteration.

The new and old scans produce the same index sequence in all tested cases. In the game benchmark, route calculations, the final simulated month and the observed convoy behaviour were also unchanged. The patch does not modify the savegame format.

The patch is one file, tpl/freelist_iter_tpl.h, against r12100.

I am attaching:

- the patch;
- the standalone equivalence test;
- the technical README;
- a Word/PDF performance report with the graphs and A/B results.

The approximately 8% result is specific to this heavy fast-forward workload. In normal windowed play, rendering may dominate, so the visible FPS improvement can be smaller.

[victor_18993]

Update after an additional instrumentation check:

I found an important issue in the interpretation of one part of the original
profile. The heavy512 save contains no live private_car_t objects after loading
(live count = 0, with only a few residual sync calls). The roughly 13,000 road
vehicles visible in that save are AI bus/road convoys, not city cars.

This does not change the freelist A/B result: the total-time improvement,
movingobj reduction, pedestrian reduction and identical route-call counts remain
valid. However, the earlier attribution of roughly half of the step to live
private cars was not supported by this workload and should be disregarded.

I am preparing a separate workload with sustained city-car traffic before making
any further claims about private_car performance.

[victor_18993]

I have completed a deeper audit of the performance measurements, and I need to correct one part of my original explanation.
The freelist patch itself is still valid. Its iterator-equivalence tests pass, including live bitmap mutations, it preserves ascending processing order, and the repeated whole-run A/B benchmark still shows a consistent improvement. The route-call count also remains unchanged.
What was not valid was my attribution of roughly half of the measured cost to

Code Select Expand

private_car.
The original heavy save contained no sustained live city cars. A few exceptional stalls in the virtualised test environment were captured by the micro-timer and incorrectly attributed to the first

Code Select Expand

private_car timing block. The normal samples were tiny; almost the entire accumulated value came from only a handful of approximately 75 ms stalls.
I therefore retract the claim that

Code Select Expand

private_car represented around 50% of the workload in that save, together with any projection based on that percentage.
I subsequently built a separate workload with sustained city traffic and confirmed that

Code Select Expand

private_car_t can genuinely be a dominant cost when hundreds of cars are alive. However, that is a separate result: the cost is mostly legitimate per-car movement work, and no small, safe, behaviour-neutral optimisation candidate was found.
So the corrected conclusion for this patch is:

• the freelist optimisation remains valid;
• the global repeated A/B result remains the relevant performance evidence;
• the previous subsystem breakdown involving
  
  Code Select Expand
  private_car should be disregarded;
• no additional
  
  Code Select Expand
  private_car patch is being proposed.

I wanted to post the correction explicitly rather than leave an inaccurate explanation attached to an otherwise valid patch.

[victor_18993]

I went back over this patch, checked it again against the current trunk, and repeated the benchmark using a stricter method. The patch still holds up as a modest optimisation, but one part of my original performance explanation was wrong and I want to correct it openly.
The correction
In the earlier write-up, I described private_car movement as roughly half of the simulation step and used that as background. That attribution was invalid.
The save I profiled had no sustained live city cars, and the cycle count came from virtual-machine wall-clock stalls captured inside the microtimer, not from real per-car work. I am therefore withdrawing that subsystem figure and any projection based on it. It was never evidence for this patch.
The patch itself
The patch remains valid and unchanged. It applies cleanly to r12100 and modifies only

Code Select Expand

tpl/freelist_iter_tpl.h.
Instead of testing every slot in every freelist chunk,

Code Select Expand

freelist_iter_tpl::sync_step() jumps directly from one active bit to the next in the occupancy bitmap. It visits the same objects in the same ascending order; only the checks of empty slots are removed.

Code Select Expand

std::bitset, which has no portable next-set-bit operation, is replaced by a small POD bitmap with the same number of bits and compiler-guarded trailing-zero helpers. The live bitmap is read again on every advance, so removal of the current slot during iteration behaves like the previous

Code Select Expand

test(i) walk.
I also reviewed the

Code Select Expand

sync_step() implementations of all current users and covered the relevant mutation cases in the standalone equivalence harness. The savegame format is not affected.
Compilers
The standalone equivalence harness was compiled and executed with both GCC 16.1 and Clang 22.1 using the same warning flags. Both compiled with zero warnings and produced the same result:

Code Select Expand

ALL FREELIST BITMAP EQUIVALENCE TESTS PASSED
 The guarded MSVC

Code Select Expand

_BitScanForward64 and 32-bit fallback paths were reviewed statically, but I could not compile them in this environment.
Updated benchmark
heavy512 with pak128.german, 50,000 fast-forward steps, 10 interleaved A/B runs for each build, with warm-up runs discarded:

Code Select Expand

baseline patched
 whole run median 776 ms 726 ms
 whole run mean 774 ms 732 ms
 range 736–836 ms 704–767 ms
paired result patched faster in 10/10 rounds
 mean paired gap about 43 ms
 route calculations 846–847 846–847
 final month 23455 23455
 That corresponds to approximately 5–6% in this particular fast-forward workload.
I do not want to oversell the result. The raw distributions overlap slightly because the measurements were made in a virtual machine with normal run-to-run noise. The stronger evidence is that all 10 paired rounds favoured the patched build, while the functional counters remained unchanged.
This measures fast-forward/headless simulation time. During normal windowed play, rendering takes a larger share of the frame, so the visible FPS effect will be smaller. The percentage should therefore be treated as specific to this save and test environment.
Conclusion
The patch remains a modest but measurable optimisation for sparse freelist pools, with behaviour preserved in the tests performed.
The current evidence does not depend on the invalid private_car figure. I am not proposing any private_car change here; I investigated that separately and found no small, safe, behaviour-neutral optimisation candidate.
Attached are the one-file patch against r12100 and a short PDF containing the full method and individual run data.
I would also be happy to use an existing project bit-scan helper if there is one I have overlooked.

[prissi]

I did not see much improvement on a quick test but the idea is solid. Incorporated in r12102

[victor_18993]

Thanks for testing and integrating it.

That matches the conclusion of the revalidation: the improvement depends quite a lot on how sparse and active the freelist pools are, so I would not expect the same gain in every save or in a short general test.

The important part for me was confirming that the iterator avoids unnecessary empty-slot checks without changing the processing order or behaviour.

Thanks again for taking the time to review it.

[prissi]

Now a lot is recomputed each time. I wonder if a real iterator remembering the current word (maybe even shifted) would not be even more effective. Not sure though, how much the compiler's optimiser already avoid this. That woudl men the end condition has only to be checked for the very last word, not before.