SCRMaps
/
Sign in

Arrays are not free

Which of EUDArray and EUDVArray is faster depends on whether the index is a constant or a variable - and precomputing the multiply usually loses.

10 min read

There are two kinds of array for a reason. EUDArray puts the value in plain memory - one entry is 4 bytes, which is one EPD. EUDVArray and PVariable put the value inside a trigger's action - one entry is a whole trigger, 72 bytes, which is 18 EPD.

That difference sets the read cost. An EUDVArray read is one trigger regardless of how big the number is, because the value is sitting in the action. An EUDArray copies bit by bit, so it gets more expensive as the range of values actually used grows.

Indexed by a variable
보통 읽기VArray is under 2x faster.
손으로 최적화한 읽기VArray is about 3x faster.
쓰기VArray is slower.

The reason VArray is not 18x faster for 18x the space is the unit the index is in. An EUDArray entry is one EPD, so the index you pass is the offset and no conversion happens at all. A VArray entry is 18 EPD, so the pointer needs 72 times the index and the SetDeaths needs 18 times it - two multiplies on every access. Artanis calls this the curse of the constant multiplier.

At this point everybody has the same idea: precompute 18*i and 72*i into variables. Stepping them alongside i through a loop is genuinely right - three Adds replace two multiplies.

const p18, p72 = EUDVariable(0, Add, 0), EUDVariable(0, Add, 0);
SetVariables(list(p, p18, p72), list(0, 0, 0));
// 반복 끝마다 / at the end of each iteration:
SetVariables(list(p, p18, p72), list(1, 18, 72), list(Add, Add, Add));
Stepping them is cheap.

Stepping them is cheap; spending them is not. Putting a variable's value into a trigger field costs at minimum 2 triggers and 3 actions - a VProc to aim the variable at the field, then the variable's own trigger. Nine fields to patch means nine of those.

Counted, for code that reads three PVariables at the same index, written three ways:

The three versions
그냥 pvarrayN[cp] 세 번32 triggers, 48-75 actions
손으로 패치, 미리 계산한 18×cp / 72×cp 사용20 triggers, 47 actions
손으로 패치, cp를 그대로 쓰고 3비트 분해9 triggers, 3 conditions, 20-47 actions

The precomputed version costs more than twice as much. The bit decomposition patches all nine fields in one pass of three conditional triggers, and the actions only run for the bits that are set. The loop's length comes from the array size, not from 32 - it is max((size-1).bit_length() - 1, 0), so an 8-entry array means three triggers.

So the multiply was never the expensive part. Break down one PVariable[cp] read and it is 8 triggers and 12-21 actions, of which the multiply is 3 triggers; the rest is the SeqCompute, the hop through the variable index, and the array's own trigger.

Two corollaries from the same analysis
Modifier까지 고치면 더 느려진다Flipping the inner trigger to Add and back to SetTo so nothing else breaks costs more than the one trigger it saves.
dest와 nextptr은 괜히 생긴 게 아니다This is why euddraft 0.9.5.4 (2022-05-05) added dest and nextptr keyword arguments to EUDVArray: fix the destination and the continuation at compile time and never patch them at all. UnitGroup is built on them.

For a plain value comparison EUDArray takes less space and performs the same. Keep the VArray for a value read every cycle on a hot path - and there, look at fixing dest and nextptr before anything else.

Which way round you write a condition is the costA variable is a trigger
Sign in to track your progress