- URL: https://yzy1.blog.uoj.ac/blog/9339
- Added At: 2025-09-25 14:09:59
本文提出一种基于 WebAssembly 和 Word-RAM 模型的算法竞赛评测方案，旨在解决传统评测中的性能波动、环境差异等问题。通过在统一虚拟环境中执行代码并计算指令代价作为运行时间，确保评测结果稳定可靠。方案兼容性强、部署灵活，已在部分平台应用，未来有望支持更多语言并优化赛制。
文章提出了一种基于 WebAssembly（WASM）和Word-RAM模型的算法竞赛题目评测方案，旨在解决传统评测系统中的不稳定性、环境差异和整体性能随时间提升带来的问题。
传统方案的不足
- 评测不稳定：同一代码多次提交可能因评测机波动导致结果不一致（如AC或TLE）。
- 环境差异：本地与评测环境性能不同，选手需过度优化常数来适应。
- 整体性能提升：硬件升级使得旧时间限制无法区分暴力与正解算法。
JudgeDuck方案的局限性
- 部署复杂：需专用系统部署，不适合选手端使用。
- 资源利用率低：机器仅用于评测，无法执行其他任务。
- 依赖实体机或虚拟机：可能仍有资源分配波动问题。
- 硬件兼容性差：需为不同硬件编写驱动，维护复杂。
方案目标
- 稳定性：确保评测结果在不同环境一致。
- 易于部署：支持选手端和评测端灵活部署。
- 兼容性：减少硬件依赖，支持多平台。
方案设计思路
- 使用WASM作为编译目标，将代码编译为WASM字节码，利用其可移植性和安全性。
- 基于Word-RAM模型，为WASM指令分配权值（最终调整为所有指令代价为1），通过模拟执行计算总代价作为“运行时间”，避免真实硬件差异。
- 实施内存限制控制，通过ResourceLimiter接口动态监控内存使用。
潜在问题与调整
- 初始方案中，Clang编译WASM时未优化常数除法，导致代价计算不准确。
- 调整为所有指令代价为1，符合Word-RAM模型简化原则，并利用wasmtime的fuel功能优化评测，避免手动补丁。
实验与评估
- 测试用例包括多种算法（如二叉搜索树、最大流、排序等）。
- 结果显示WASM代价与本地执行时间高度线性相关（相关系数0.979），证明方案有效性。
- 内存使用与传统方案接近，性能稳定。
优缺点
- 优点：绝对稳定性、安全性（沙盒机制）、统一接口（便于交互题）、环境兼容性高（用户程序层部署）。
- 缺点：评测速度较慢（1x-3x于传统方案）、语言兼容性有限（暂不支持Java等）。
改进方向
- 随着WASM GC提案推进，未来可支持更多语言（如Java、Python）。
- 推动算法竞赛更注重理论复杂度而非常数优化。
在线比赛赛制改进
- 提出预评测在客户端执行、系统评测在服务器的混合赛制，减轻服务器负载，提高选手体验和公平性。
现有集成
- 方案已在UOJ等平台部署，并提供代码示例和测试OJ（https://waj.11316396.xyz/）供实践。
后记
- 通过测试OJ收集了大量数据（截至2025-07-03共1416条有效点），进一步验证方案相关性，并鼓励社区参与贡献。