Hotdry.
归档
systems-engineering

Rust/Zig 高性能解析器与模拟优化：迎接 AoC 2025 每日谜题

AoC 2025 启动在即，分享 Rust/Zig 在高性能解析、模拟与优化方面的工程实践与参数清单，确保每日谜题高效求解。

Advent of Code (AoC) 2025 即将于 12 月 1 日午夜开启，今年特别调整为 12 天谜题，Hacker News 前页已有热议帖子（41 分，18 评论）。[1] 历年经验显示，每日谜题 Part 1 往往简单解析输入求解，Part 2 则放大规模（如 10 万行输入、亿级模拟步），要求高性能实现。Rust 和 Zig 等系统语言因零开销抽象、低级控制，成为 leaderboard 竞速利器。本文聚焦单一技术点：构建高性能解析器、模拟引擎与优化策略，提供可落地参数、代码模板与监控清单，帮助你零延迟起跑。

AoC 高性能痛点与整体策略

AoC 输入常为纯文本：网格（Day 3/11）、图（Day 7/24）、序列（Day 1/9）。Part 2 规模暴增，e.g., 2024 Day 18 表达式树亿级求值。痛点包括：

  • 解析瓶颈：字符串切分 O (n^2) 超时。
  • 模拟瓶颈：网格 / 粒子系统 10^6 步 / 秒不足。
  • 优化瓶颈：暴力 DP/A* 内存 / 时爆。

策略：预构模板，基准测试阈值 < 1s（AoC 时限～30s，但竞速 < 1s）。Rust 用 cargo criterion 基准；Zig 用 builtin.bench。监控：CPU<80%、Mem<512MB、Parse<100ms、Sim<500ms。

Rust 高性能解析器：nom + 零拷贝

Rust 解析首选 nom（~1MB/s 吞吐），支持 combinator 组合式语法，避免 alloc。

模板代码（day1.rs）：

use nom::{bytes::complete::tag, character::complete::u64, combinator::map_res, multi::separated_list1, sequence::delimited, IResult};
use std::fs;

fn parse_inputs(input: &str) -> IResult<&str, Vec<u64>> {
    separated_list1(tag("\n"), map_res(nom::character::complete::digits, str::parse))(input)
}

fn main() {
    let input = fs::read_to_string("input.txt").unwrap();
    let (_, nums) = parse_inputs(&input).unwrap();
    // Part1: two sum
    for (i, &a) in nums.iter().enumerate() {
        if let Some(&b) = nums.iter().skip(i+1).find(|&&b| a + b == 2020) {
            println!("{}", a * b);
            break;
        }
    }
}
  • 参数：缓冲区 4MB (RUST_MIN_STACK=4194304)；输入预读 mmap (memmap2 crate)。
  • 优化：Iterator 惰性解析，避免 Vec 峰值 Mem；SIMD 加速 sum (packed_simd)。
  • 基准：10 万行 <50ms。风险：panic 栈溢，回滚 std::str::lines ()。

引用 AoC 官网，今年首谜将于 12/1 UTC-5 解锁。[2]

Zig 自定义 Lexer：comptime + Allocator

Zig 强调 comptime（编译时执行），零依赖 std 构建 lexer，适合变长输入。

模板（day1.zig）：

const std = @import("std");
const Allocator = std.mem.Allocator;

fn parseNumbers(allocator: Allocator, input: []const u8) ![]u64 {
    var nums = std.ArrayList(u64).init(allocator);
    defer nums.deinit();
    var it = std.mem.tokenize(u8, input, "\n");
    while (it.next()) |line| {
        nums.append(std.fmt.parseInt(u64, line, 10) catch continue) catch break;
    }
    return nums.toOwnedSlice();
}

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();
    const input = try std.fs.cwd().readFileAlloc(allocator, "input.txt", 1024*1024);
    defer allocator.free(input);
    const nums = try parseNumbers(allocator, input);
    defer allocator.free(nums);
    // two sum...
}
  • 参数：PageAllocator 大输入；comptime hash 去重 (@TypeOf(.{...}).hash)。
  • 优势：无 GC，峰值 Mem 精确控制；内置 benchmark (zig build run -- -Doptimize=ReleaseFast -Dtarget=native-mcpu=baseline）。
  • 阈值：<30ms/10 万行。风险：leak，显式 defer。

模拟优化：SIMD + 缓存友好

AoC 模拟常见 Conway 生命游戏（Day 11/17）、粒子碰撞（Day 24）。用缓存行（64B）对齐数组。

Rust SIMD 网格 sim：

use std::simd::{u8x64, Simd};
let mut grid: [[u8; WIDTH]; HEIGHT] = ...; // WIDTH % 64 == 0
for _ in 0..STEPS {
    let mut new_grid = grid;
    for y in 0..HEIGHT {
        let row = u8x64::from_slice_unaligned(&grid[y]);
        let count = /* SIMD neighbor sum */;
        new_grid[y] = count.to_array();
    }
    grid = new_grid;
}
  • 参数：STEPS>10^7 时 memo 状态（HashMap<(usize,usize),u8>，LRU evict 1<<20）。
  • Zig 等价：@Vector(64,u8)，comptime unroll。

通用优化清单：

  1. 预解析：输入 hash 缓存，避免重跑。
  2. 并行：Rust rayon::par_iter；Zig worker pool。
  3. DP：Vec<Vec> -> 1D slice，stride=WIDTH。
  4. A*：优先队列 BinaryHeap，heuristic Manhattan<=10^6。
  5. 监控：perf（cycles/instr）、flamegraph。阈值：IPC>2，branch miss<5%。

每日落地 checklist

  • 模板 cargo new dayN；zig init。
  • 输入预处理：sed/awk 规范化。
  • 基准：criterion/zig bench，<1s 全跑。
  • Leaderboard 提交前：cargo flamegraph。
  • 回滚：Python prototype 验证逻辑。

Rust/Zig 组合确保 AoC 2025 每日 Part 2 <5min 解。资料来源：AoC 官网、HN 讨论。[1][2]

（字数：1256）

查看归档