基于 WASM 和 Word-RAM 模型的算法竞赛题目评测方案

本方案旨在通过 WebAssembly（WASM）技术，构建基于 Word-RAM 的模型，对算法竞赛题目进行评测．

传统方案的不足

• 评测不稳定性：同一份代码多次提交，由于评测机波动，导致结果随机出现通过（AC）或超时（TLE）．
• 环境差异：在本机测试样例时，运行时间不到 1 秒，而在评测时相同的数据却需要 3 秒才能完成．选手们常常担心因做题环境与评测环境的差异而被卡住，因此花费大量时间进行常数优化以应对未知环境．
• 随时间的整体性能提升：模拟赛中使用了一道多年前的经典题，结果由于几年间机器性能的提升，原本的时间限制现已无法区分暴力和正解做法．

第一种情况目前已经有 JudgeDuck 等解决方案，但后面两个问题仍然是较大的挑战．

JudgeDuck 的工作与局限性

JudgeDuck 采用一个重新实现的操作系统 JudgeDuck OS 来消除评测的不稳定性，而不是一个运行在操作系统之上的应用层程序．然而，这种方法存在一些缺点：

• 部署复杂性：JudgeDuck OS 需要在评测端进行专门的部署，这使得其不适合在选手端使用．选手无法在自己的环境中进行测试和验证，限制了其灵活性．
• 资源利用率低：一旦部署完成，该机器只能用于评测，无法执行其他任务．这种单一用途的设计导致资源的浪费，尤其是在评测需求不高的情况下．
• 实体机依赖性：如果使用虚拟机进行评测，仍然会依赖宿主操作系统的资源分配．这可能导致与传统沙盒环境相似的波动，无法真正消除评测的不稳定性．
• 硬件兼容性问题：由于 JudgeDuck OS 是一个独立的操作系统，可能会出现与某些硬件不兼容的情况．在这种情况下，可能需要为每一种新硬件单独编写驱动代码，增加了维护的复杂性．

方案目标与需求

为了克服上述问题，我们需要一个更灵活、高效且易于部署的评测方案．具体而言，理想的评测系统应具备以下特征：

• 稳定性：能够在不同的硬件和软件环境中提供一致的评测结果，消除因环境差异导致的评测不稳定性．
• 易于部署：能够在选手端和评测端都能方便地进行部署和使用，降低技术门槛．
• 兼容性：支持多种硬件平台，减少因硬件不兼容而导致的额外维护工作．

通过结合 WebAssembly 和 Word-RAM 模型，我们可以设计出一个满足上述需求的评测方案，从而提升算法竞赛的公平性和效率．

解决方式

首先，我们需要一种方式来运行选手代码．由于传统的直接运行 ELF/PE 可执行文件的格式行不通，我们考虑换一种方式——将高级语言编写的程序编译成一种类似机器代码的格式，然后模拟其执行，并在模拟过程中计算代价．根据上述要求，我们需要一个通用的、能够作为各种语言编译目标的格式——这让我们自然地想到 WASM．

接下来，我们需要一个「估价函数」：输入一段 WASM 执行的过程，输出这段过程对应的代价．同时，考虑到我们要解决「随时间的整体性能提升」问题，这个估价函数最好不是真正在模拟某一款 CPU 执行的时间，而是一个能够概括大部分 CPU 执行的理论模型．这使我们联想到 Word-RAM 模型．

Word-RAM 模型是一种理论计算模型，它假设计算机的基本操作是在一个固定大小的字（word）上进行的．每个字可以存储一个数据项，且所有的基本操作（如加法、乘法、存取等）都在常数时间内完成．该模型的优势在于它能够简化对算法复杂度的分析，尤其是在处理大规模数据时．

根据 Word-RAM 模型的思想，我们可以直接对每种 WASM 汇编指令赋予一个权值，然后用所有执行过的指令的权值和加起来，来代表「代码运行的时间」．

考虑到目前的 CPU 架构，我们选择 Word-RAM 的字长 w=64，并采用以下代价表：

汇编指令	注释	代价
I32DivS, I32DivU, I32RemS, I32RemU	32 位整数除法与取模	32
I64DivS, I64DivU, I64RemS, I64RemU	64 位整数除法与取模	64
F32Sqrt, F32Div	32 位浮点数除法与开根	32
F64Sqrt, F64Div	64 位浮点数除法与开根	64
...	其他运算指令（加减乘，比较，位运算等）	1
I32Load, F64Store, ...	单个变量的读写	1
If, Loop, Call, ...	流程控制指令	1

在选择代价表时，我们充分考虑了算法竞赛中常见的操作特性以及 Word-RAM 模型的理论基础．首先，Word-RAM 模型的设计初衷是为了简化算法复杂度的分析，尤其是在处理大规模数据时．因此，我们需要确保代价表能够准确反映出不同操作在实际执行中的相对复杂度．

在算法竞赛中，除法和平方根操作通常被认为是相对较为复杂的操作，尤其是在处理大数据量时．与加法、减法、乘法等基本操作相比，除法和平方根的计算往往需要更多的时间和资源．同时算法竞赛中常用的 Word-RAM 模型一般不认为除法和平方操作是 O(1) 的．因此，我们将这些操作的代价设定为较高的值（例如，32 或 64），以反映它们在实际执行中的复杂性．这种设定不仅符合理论模型的预期，也与竞赛选手在实际编程时的经验相符．

具体来讲，在处理非基本操作时，我们采取了将其「视为」基本操作的方式．这一策略的选择是基于以下考虑：直接禁止非基本操作的使用需要对编译器的底层实现进行复杂的修改，这在实际操作中是复杂且较难维护的．因此，我们决定通过定义非基本操作的代价为其用基本操作实现的代价和，来间接反映其复杂性．这种方法不仅保留了选手的灵活性，还能有效地评估其代码的性能．具体的实现参考了 armv7 下的 GCC 的软件实现（注：armv7 架构也不包含除法指令）．

从另一个角度来看，我们可以借助鸭子定律来给出定义这些操作代价为非 1 的理由：如果一个操作在 Word-RAM 模型中被定义为 O(\log n) 的复杂度，在实际的 x86_64 CPU 架构中，该操作的吞吐量（throughput）通常是加法操作的约 log 倍，并且在实际运行时，这类操作的执行时间也大致是加法操作的 log 倍，那我们就完全有理由将这些操作的代价定义为 O(\log n) 的．

实现步骤

• 编译选手代码：首先，将选手提交的代码编译为符合 WebAssembly System Interface (WASI) 0.1 API 的 WASM 字节码．这一过程利用了 WASI 提供的标准化接口，使得编译后的代码能够在不同的执行环境中保持一致性和可移植性．通过使用 WASI，选手的代码可以轻松访问输入输出等系统资源，而无需担心底层平台的差异．
• 补丁处理：在编译完成后，对生成的 WASM 文件进行补丁处理．具体而言，我们在全局变量区新建一个计数器变量，用于跟踪代码执行过程中消耗的资源．对于每个控制型指令（如 if、br、call 等），我们计算从前一个控制指令到当前指令之间所有指令的代价和，并在适当的位置插入一段更新计数器的指令．这段指令还包括判断是否超时的逻辑，以确保代码执行不会超过预设的时间限制．
• 内存限制控制：在运行时层面实施内存限制控制，以确保选手代码在执行过程中不会超出预设的内存使用限制．我们设计了一种内存管理策略，通过实现 ResourceLimiter 接口，动态监控和限制内存的增长．具体来说，当代码尝试申请超过设定限制的内存时，系统会拒绝该请求，并标记为内存超限．

实验与评估

实验设置

测试用例的选择

为了全面评估基于 WebAssembly 和 Word-RAM 模型的算法竞赛题目评测方案，我们选择了多种经典算法和数据结构作为测试用例．这些用例包括二叉搜索树（bst）、最大流算法（max-flow）、筛法（sieve）、排序算法（sort）等，涵盖了不同的算法复杂度和数据处理需求，以确保评测的全面性和代表性．

评测环境的配置

评测环境采用了标准化的配置，确保所有测试在相同条件下进行．我们使用了具有 512MB 内存限制和 10 秒 CPU 时间限制的环境．选手提交的代码首先被编译为符合 WebAssembly System Interface (WASI) 0.1 API 的 WASM 字节码，并经过补丁处理以跟踪资源消耗．评测过程中，系统会记录每个程序的执行时间、内存使用情况以及基于 Word-RAM 模型计算的代价．

评估指标

我们主要关注以下几个评估指标：

• 执行时间：记录程序在给定输入下的运行时间，以纳秒为单位．
• 内存使用：监控程序在执行过程中的内存消耗，以字节为单位．
• WASM 代价：基于 Word-RAM 模型计算的代价，反映程序执行的复杂度．

实验结果分析

在实验中，我们对每个测试用例的所有程序进行了基准测试，并将结果与传统的本地执行方案进行了对比．通过对比 WASM 执行的代价与本地执行的时间，我们可以评估两者之间的相关性．

与传统方案的对比

实验结果显示，WASM 执行的代价与本地执行的时间之间存在显著的线性相关性，相关系数达到 0.979．这表明，基于 Word-RAM 模型的代价评估能够有效反映程序的实际执行性能．此外，WASM 方案在内存使用方面表现出色，能够以与传统方案几乎一致的内存占用完成评测任务．

通过绘制散点图，我们可以直观地观察到本地执行时间与 WASM 代价之间的关系．图中红色的线性回归线进一步验证了两者之间的正相关性，说明我们的评测方案在理论模型与实际性能之间建立了有效的联系．

方案的优缺点

优点

• 绝对稳定性：本方案通过模拟程序执行，确保在任何机器上运行多次均能获得完全一致的结果．这种稳定性对于算法竞赛的评测至关重要，因为它消除了因环境差异导致的结果不一致性．
• 安全性：WebAssembly（WASM）运行时自带沙盒机制，能够有效隔离执行环境，降低安全风险．这意味着在评测过程中，选手的代码无法对宿主系统造成影响，从而保障了系统的安全性．
• 统一接口：WASM 提供了标准化的接口，使得在处理交互题和通信题时更加便捷．这种统一性不仅简化了开发过程，还提高了不同题目之间的兼容性．
• 环境兼容性：与 JudgeDuck 运行在操作系统层不同，本方案运行在用户程序层．这一特性使得本方案能够兼容绝大多数的执行环境，极大地简化了部署过程，降低了对特定平台的依赖．

缺点

• 评测时间较慢：相较于传统方案，本方案的评测时间通常较长，约为传统方案的 1x 至 3x．具体的倍数取决于内存访问模式．例如，对于多组数据的 100x100 矩阵乘法，评测时间接近 1x，而对于需要随机读写大量内存的算法（如筛法），评测时间可能达到 3x．然而，考虑到 WASM 指令相对简单，并且现代 WASM 运行时经过优化，最慢的评测时间仍然保持在 3x 以内，且优于 Java 虚拟机（JVM）等其他执行环境．
• 语言兼容性有限：目前，WASM 对主流编程语言的兼容性尚不够丰富．虽然 C、C++、Rust、Pascal、Zig 和 Kotlin 等语言已具备较好的兼容性，但对于 Python 等脚本语言，虽然存在能够在 WASM 上运行的解释器，但 Java 语言目前尚未实现兼容．这一限制可能影响某些选手的代码提交和评测．

可能的改进方向

随着 WASM 垃圾回收（GC）提案的逐步支持，未来可能会有更多编程语言能够与 WASM 兼容．这将进一步扩展本方案的适用范围，使得更多选手能够参与到算法竞赛中来．

对未来算法竞赛的影响

本方案与传统方案的最大区别在于是否考察缓存（Cache）及其他相关因素（如分支预测）．我个人认为，算法竞赛的发展方向应当更加关注算法的复杂度而非常数因素．如果将理论与实验的偏向性放在数轴上，理论偏向一侧大致对应于现代的数学奥林匹克（MO），而实验偏向一侧则代表数十年前的算法竞赛（OI）．我很高兴看到 OI 在发展过程中逐渐向理论倾斜，而本项目的普及将进一步促进这一趋势，推动算法竞赛向更高层次的发展．

在线比赛赛制的改进

基于上述方案，我们提出了一种改进的在线比赛赛制．它类似于 pre test - system test 赛制和 OI 赛制的结合．具体而言，数据集被划分为预评测集和系统评测集，两者均采用相同的数据生成器，但使用不同的随机数种子进行生成．

在比赛过程中，预评测的评测全部在客户端执行，服务器的主要职责是收集选手提交的代码，而不参与评测．这一设计显著减轻了服务器的负担，避免了传统预评测-系统评测赛制中因服务器评测队列过长而导致的选手做题时间受到影响的问题．

与传统的 pre test - system test 赛制相比，这种新赛制不仅提高了评测效率，还提升了选手的体验．选手可以在本地环境中快速获得反馈，从而更专注于算法的优化和代码的调试，而不必担心因服务器延迟而浪费宝贵的比赛时间．

与 OI 赛制相比，该改进赛制有效消除了因环境差异导致的结果不一致性．选手在本地进行预评测时，能够确保其代码在相同的环境下运行，从而避免了因细节处理不当而导致的意外错误．这种一致性使得选手能够将更多精力集中在算法设计和实现上，而不是在环境和细节调整上．

综上所述，这种改进的在线比赛赛制通过优化评测流程和提升环境一致性，为选手提供了更为高效和公平的比赛体验，值得在未来的在线编程竞赛中推广应用．

现有平台的集成

本方案已经在 UOJ（含社区版，官方版和 QOJ）上通过自定义 judger 成功部署并工作．

同时，此处代码 给出了一种将该方案集成到 OJ 的实例，可供参考．

相关代码示例

https://codeberg.org/aberter0x3f/wasm-judge-demo

后记

我们正在筹备在进行一次大规模的样本征集和实验评估活动．届时，各位读者可以通过提交代码的方式为测试样本贡献力量．活动的初步形式如下：

• 在平台上将开放若干题目，读者可以提交与题目对应的 C++ 代码．
• 提交的代码将被编译为原生二进制格式和 WebAssembly（WASM）格式．
• 每个测试点将分别采用传统评测方案和 WASM 评测方案进行评测．
• 我们将在提交记录中选择那些答案正确且用时在合理范围内的测试点，以计入数据集．

我们期待您的积极参与，共同推动这一项目的发展与完善．感谢您的支持与关注！

Update: 测试 OJ 现已部署成功．可通过 https://waj.11316396.xyz/ 进行访问．注意提交时必须遵循首页提示的 guidelines，否则我们将不会采用你的提交作为数据集．