[Performance] Cache same-tick command-queue length in UpdateRecordedOrders

[zhanghm18GIT]

Environment

• Upstream M28 version: 311
• Pinned source commit used for analysis: 3dc23ea4acd2e0bca2fb4844d78ae5f46a7f70e5
• File: lua/AI/M28Orders.lua

The private test label V89 is not an official M28 version, release, branch, or endorsement.

Description

In upstream M28, UpdateRecordedOrders obtains the command queue and then only uses its length:

M28AI/lua/AI/M28Orders.lua

Lines 187 to 206 in 3dc23ea

	--Also acts as a bcakup for special micro not resetting
	if bDontConsiderCombinedArmy or oUnit.M28Active then
	if oUnit[M28UnitInfo.refbSpecialMicroActive] and (oUnit[M28UnitInfo.refiGameTimeToResetMicroActive] or 0) > 0 and GetGameTimeSeconds() > oUnit[M28UnitInfo.refiGameTimeToResetMicroActive] then
	oUnit[M28UnitInfo.refbSpecialMicroActive] = false
	end
	if not(oUnit[reftiLastOrders]) then
	oUnit[reftiLastOrders] = nil
	oUnit[refiOrderCount] = 0
	else
	if (oUnit[refiOrderCount] or 0) == 0 then
	oUnit[refiOrderCount] = table.getn(oUnit[reftiLastOrders])
	end
	local tCommandQueue
	if oUnit.GetCommandQueue and M28UnitInfo.IsUnitValid(oUnit) then
	tCommandQueue = oUnit:GetCommandQueue()
	end
	local iCommandQueue = 0
	if tCommandQueue then iCommandQueue = table.getn(tCommandQueue) end
	if iCommandQueue < oUnit[refiOrderCount] then
	if iCommandQueue == 0 then

local tCommandQueue
if oUnit.GetCommandQueue and M28UnitInfo.IsUnitValid(oUnit) then
    tCommandQueue = oUnit:GetCommandQueue()
end

local iCommandQueue = 0
if tCommandQueue then
    iCommandQueue = table.getn(tCommandQueue)
end

UpdateRecordedOrders is reached from tracked-order and micro paths. In a large battle, the same unit can be checked more than once in one simulation tick.

Private diagnostics recorded very high order-tracking call volume in later-game windows, making this a high-value path to reduce redundant work.

Proposed change

Cache only the integer command-queue length for the same unit within the same simulation tick.

Reuse is allowed only when:

• the unit is identical;
• the simulation tick is identical;
• no tracked M28 command mutation has occurred since the real queue query;
• no yield or external command-mutation boundary has occurred.

Invalidate the cached length whenever M28:

• clears or replaces commands;
• appends a command;
• changes a navigator goal;
• performs another tracked command mutation.

Do not:

• retain the full command-queue table;
• reuse the value across ticks;
• add a periodic scan or background thread;
• reduce production, target selection, unit diversity, manager cadence, or micro cadence.

A small mutation-generation counter is safer than relying on same-unit/same-tick identity alone.

Conceptually:

function InvalidateQueueLength(oUnit)
    oUnit.M28QueueMutationGeneration =
        (oUnit.M28QueueMutationGeneration or 0) + 1
end

function GetQueueLengthSameTick(oUnit)
    local tick = GetGameTick()
    local generation = oUnit.M28QueueMutationGeneration or 0

    if oUnit.M28QueueCacheTick == tick
        and oUnit.M28QueueCacheGeneration == generation then
        return oUnit.M28QueueCacheLength or 0
    end

    local queue = oUnit:GetCommandQueue()
    local length = queue and table.getn(queue) or 0

    oUnit.M28QueueCacheTick = tick
    oUnit.M28QueueCacheGeneration = generation
    oUnit.M28QueueCacheLength = length

    return length
end

This is a reference implementation of the tested design contract, not a byte-for-byte export of the private fork.

Observed evidence

The private cache was tested as part of the memory investigation documented in:

FAForever/fa#7195

A cache-active run still reached:

Heap Total / Committed = 1.930 GiB / approximately 1.24-1.26 GiB

A separate run using both the cache and the HEAPMNG allocator candidate stabilized at:

1.406 GiB / approximately 1.30-1.33 GiB

Therefore:

• the cache is part of the lowest-growth observed configuration;
• the cache alone is not proven to produce the full reduction;
• its independent benefit should be measured by real queue-call counters and a controlled A/B test.

Allocator-side record:

FAForever/FA-Binary-Patches#163

Expected benefit

When the same unit is queried repeatedly in one tick without an intervening command mutation:

without cache: N helper reads -> N real GetCommandQueue calls
with cache:    N helper reads -> 1 real call + N-1 scalar hits

Expected benefits:

• fewer real GetCommandQueue() calls;
• less Lua/C++ bridge work;
• fewer temporary queue representations if the engine materializes them;
• lower short-lived allocation pressure;
• lower profiler cost in large battles.

The intended M28 gameplay behavior must remain unchanged.

Test Plan

Add temporary counters for:

• helper invocations;
• real GetCommandQueue() calls;
• cache hits and misses;
• explicit invalidations;
• invalidations after yield/external boundaries;
• maximum hits for one unit in one tick;
• stale-read assertions.

Run at least three repetitions with the cache off and on while holding constant:

• map and map version;
• seed;
• AI count and personality;
• unit cap;
• mod list;
• executable SHA-256;
• graphics settings;
• duration.

Record:

• Heap Total and Committed;
• process virtual size/private bytes;
• real queue-call count;
• cache statistics;
• M28 profiler cost;
• simulation speed;
• any order-tracking or micro regression.

Regression coverage must include:

• replace versus append;
• clear/stop;
• move, patrol, aggressive move, and navigator goals;
• attack, reclaim, guard, repair, build, transport, capture, teleport, and missile commands;
• queue completion between ticks;
• dead or invalid units;
• same-tick reads before and after a mutation;
• reads after WaitTicks, WaitSeconds, or another yield;
• command changes made by engine or non-M28 code.

Scope

The exact private-fork diff is not currently attached. This issue preserves the analyzed upstream path, the tested cache contract, the evidence boundary, and a safe reference implementation for review or reimplementation.

Attachment

UPLOAD_M28_SAME_TICK_CACHE_EVIDENCE.zip

[zhanghm18GIT]

Paired engine-side HEAPMNG implementation PR:
FAForever/FA-Binary-Patches#164

[maudlin27]

Am I right in understanding you're proposing changing:

local tCommandQueue
            if oUnit.GetCommandQueue and M28UnitInfo.IsUnitValid(oUnit) then
                tCommandQueue = oUnit:GetCommandQueue()
            end
            local iCommandQueue = 0
            if tCommandQueue then iCommandQueue = table.getn(tCommandQueue) end

To:

local iCommandQueue = GetQueueLengthSameTick(oUnit)

(with GetQueueLengthSameTick as per the above)?

And that if the HEAPMNG PR for FAF is implemented this results in a notable reduction in the heap?

[zhanghm18GIT]

Am I right in understanding you're proposing changing:

local tCommandQueue
            if oUnit.GetCommandQueue and M28UnitInfo.IsUnitValid(oUnit) then
                tCommandQueue = oUnit:GetCommandQueue()
            end
            local iCommandQueue = 0
            if tCommandQueue then iCommandQueue = table.getn(tCommandQueue) end

To:

local iCommandQueue = GetQueueLengthSameTick(oUnit)

(with GetQueueLengthSameTick as per the above)?

And that if the HEAPMNG PR for FAF is implemented this results in a notable reduction in the heap?

Yes, broadly — that is the read-side part of the proposed M28 change:

replace the local GetCommandQueue / table.getn block in
UpdateRecordedOrders with:

local iCommandQueue = GetQueueLengthSameTick(oUnit)

There are two important implementation details, though.

First, GetQueueLengthSameTick should preserve the existing validity check:

• oUnit exists;
• oUnit.GetCommandQueue exists;
• M28UnitInfo.IsUnitValid(oUnit) is true.

Otherwise it should return 0 rather than calling GetCommandQueue.

Second, the other half of the change is cache invalidation. Whenever M28
actually changes that unit's commands — for example IssueClearCommands,
replacing or appending an order, issuing an Issue* command, or
Navigator:SetGoal — it must call InvalidateQueueLength(oUnit).

Without that invalidation, a second UpdateRecordedOrders call for the same
unit in the same tick could reuse a queue length from before the command
changed.

Regarding the heap result: yes, the notable reduction I observed was with
the combined configuration:

• the M28 same-unit/same-tick queue-length cache; and
• the HEAPMNG changes in PR V126 #164.

However, I do not yet have a complete controlled 2x2 test proving how much
of the reduction comes from each change independently.

One cache-active test still reached about 1.930 GiB Heap Total, while the
documented combined cache + HEAPMNG run stabilized at about 1.406 GiB.
In my later extreme mod-heavy tests, the process generally remained below
about 1.8 GB during long games.

So I would describe the result as:

• the M28 change should reduce repeated GetCommandQueue calls and associated
  Lua/C++ bridge or temporary queue-representation work;
• PR V126 #164 improves HEAPMNG bookkeeping and high-address free-region reuse;
• together they produced a notable reduction in my stress tests.

I would not claim yet that the one-line replacement alone, or PR #164 alone,
accounts for the full reduction.

[maudlin27]

Sounds like it may be worth me holding off for now on the change then, and if/when the FAF PR gets accepted I can then run a test to make sure the above changes for M28 work as expected (e.g. one test I've got in mind is just seeing if a replay desyncs after the changes), as well as meaning i could more easily confirm in local tests the impact (as conceptually it seems strange to me that memory usage is decreased by storing results temporarily, as I'd normally expect caching to improve CPU performance at the cost of increased memory usage)