循环与迭代优化

在以太坊虚拟机（EVM）中，循环结构（for / while）是 Gas 消耗的放大器。由于 EVM 按照指令逐步计费，且循环体内部的每一次迭代都会重复执行条件判断、跳转与状态读取，未经优化的循环极易引发巨额 Gas 浪费甚至触及区块 Gas 限制（Block Gas Limit）导致合约瘫痪。

循环成本由每次迭代的操作、迭代次数和编译器优化共同决定。常数开销优化与算法复杂度变化需要分别比较。

典型伪优化陷阱：所谓的“嵌套循环扁平化（笛卡尔积合并）”

在传统高层语言（如某些 JIT 优化的 Web 运行时）中，有时会通过将两层嵌套循环压缩为单层循环来减少循环边界检查。然而，在 EVM 底层，这种做法是严重的负优化（Gas Regression 陷阱）。

1. 常见错误写法对比

// 方案 A：标准双层循环 (10 x 10 = 100 次迭代)
for (uint256 i = 0; i < 10; ) {
    for (uint256 j = 0; j < 10; ) {
        // 核心业务处理
        unchecked { ++j; }
    }
    unchecked { ++i; }
}

// 方案 B：所谓的“扁平化优化”（错误观念）
for (uint256 k = 0; k < 100; ) {
    uint256 i = k / 10; // 严重负优化：每次迭代强制引入 DIV 运算
    uint256 j = k % 10; // 严重负优化：每次迭代强制引入 MOD 运算
    // 核心业务处理
    unchecked { ++k; }
}

2. EVM 底层操作码成本真实核算

方案 A 与方案 B 的差异可按生成的指令和访存操作比较：

方案 A（双层嵌套）：
- 外层循环重置内层计数器 j = 0 仅发生 10 次（10 次极低成本的堆栈压栈操作，约 30 Gas）。
- 跳转与累加指令均在栈顶或局部变量就地完成，总开销平稳。
方案 B（扁平化单层循环）：
- 在整整 100 次迭代中的每一次，都必须强制执行 k / 10 与 k % 10！
- DIV 与 MOD 操作码在 EVM 中各自消耗 5 Gas，配合参数压栈与栈置换（DUP, SWAP, POP），每次迭代额外引入至少 30-40 Gas 的无谓计算开销。
- 结果核算：100 次迭代下来，方案 B 比方案 A 额外多消耗了 3,000 至 4,000 Gas！同时使原本直观的双重坐标遍历变得极其晦涩。

工程准则：严禁为了盲目消除一层循环而引入高阶的运行时除法与求模运算。

真实有效的循环工程优化范式

1. 数组长度缓存 (Cache Array Length)

在读取动态数组（memory 或 storage）进行遍历时，Solidity 高级语法在每次循环条件判断中若直接书写 i < arr.length：

若 arr 位于 storage：每次迭代强制执行一次 SLOAD（冷读 2100 Gas / 暖读 100 Gas），构成严重的存储浪费。
若 arr 位于 memory：每次条件判断都会触发一次 MLOAD 读取长度字段。

// ✅ 正确范式：提前将长度缓存至栈变量中
function processMemory(uint256[] memory arr) external pure {
    uint256 len = arr.length; // 一次 MLOAD 读入寄存器
    for (uint256 i = 0; i < len; ) {
        _doSomething(arr[i]);
        unchecked { ++i; } // 关闭自增溢出校验
    }
}

2. 循环自增使用 `unchecked { ++i; }`

在 Solidity 0.8 之后，算术操作默认开启溢出断言。对于循环计数器 i 而言，只要循环边界被限定在合理的数值范围（如 len < 2**256 - 1），自增操作在数学上绝不可能发生溢出。

普通 i++：编译后会插入额外的溢出检查分支与条件回滚指令，单次消耗约 20-30 Gas。
unchecked { ++i; }：仅生成纯粹的 ADD 与压栈指令，单次仅消耗约 5 Gas。前置自增 ++i 在部分旧版编译器中比后置自增 i++ 略省临时变量压栈。

3. Yul 汇编内存批量遍历 (Assembly Array Traversal)

Solidity 访问 arr[i] 时，编译器会在每次数组下标寻址时隐式插入一段边界安全检查指令（若 i >= arr.length 则触发 Panic）。在明确保证安全的只读计算中，使用内联汇编直接操作内存指针可完全抹去该开销：

function sumAssembly(uint256[] memory arr) public pure returns (uint256 total) {
    assembly {
        let len := mload(arr)
        let dataPtr := add(arr, 0x20) // 跳过前 32 字节长度字段
        let endPtr := add(dataPtr, mul(len, 0x20))

        for {} lt(dataPtr, endPtr) { dataPtr := add(dataPtr, 0x20) } {
            total := add(total, mload(dataPtr))
        }
    }
}

优化原理：消除每轮的边界大小比较与算术乘法偏移量计算，指针线性向后单调步进（步长 32 字节），充分利用 CPU 预取与 EVM 连续内存读取优势。

4. 循环展开 (Loop Unrolling)

对于确定且迭代轮次极小（如 3 - 5 轮）的计算逻辑，手动展开循环：

// 手动展开固定 4 轮的数据处理
function processFour(bytes32[4] memory data) internal pure {
    _processItem(data[0]);
    _processItem(data[1]);
    _processItem(data[2]);
    _processItem(data[3]);
}

收益：彻底消除计数器更新、条件判定及跳转指令（JUMP / JUMPI），消除了循环控制流本身的额外开销。

终极架构设计：从循环遍历转向映射与链下证明

在智能合约架构设计中，避免循环的价值永远大于优化循环：

状态查询：映射（mapping）优于数组遍历：
- 数组寻找目标需要 \(O(N)\) 遍历，而映射提供确定性的 \(O(1)\) 常数级哈希寻址。
批量结算：链下计算 + 链上 Merkle 证明：
- 大规模白名单分发、空投、代币申领严禁在链上通过循环遍历数组。
- 应在链下将所有资格树归纳为一颗 Merkle 树，链上仅保存 32 字节的 merkleRoot，用户提取时提交单一 Merkle Proof 进行原子验证，将 \(O(N)\) 循环彻底降维为 \(O(1)\) 验证。

Xu's Blog