使用并行计算优化对拍

背景 什么是对拍？对拍的核心是对比两个程序的输出是否一致。如果两个程序的输出在所有测试用例上都相同，那么可以认为它们的行为是等价的；如果输出不同，则说明其中一个程序可能存在错误。集训期间做不动题，于是想写一个专门用于线上比赛的对拍，询问ai之后，发现如下操作： system(".\\code_a.exe < input.txt > output_a.txt"); system(".\\code_b.exe < input.txt > output_b.txt"); ifstream fa("output_a.txt"), fb("output_b.txt"); int a, b; fa >> a; fb >> b; // 比较结果 if (a != b) { cout << "Error found on test case #" << testCount << "!\n"; break; } 传统对拍一般都用的是freopen之类的，需要在写好的代码手动加入头文件，还需要手动定义输出文件名。这样每次对拍都需要搞很长时间。 但是有了> output_a.txt 和 > output_b.txt：将程序的输出重定向到文件中之后，不需要修改代码，只需要借助系统命令对数据生成器进行调用，再调用两份代码重定向输出文件并比较即可。使得对拍在理论上可以作为一个模板——只需粘入两份代码，即可实现对拍操作。尽管改进后的对拍方法简化了操作，但由于频繁的 I/O 操作和结果检查，任务仍然具有 I/O 密集的特点。为了弥补 I/O 等待时间，本框架引入了并行计算技术。通过多线程并行执行测试用例生成、程序执行和结果比对，充分利用多核 CPU 的计算能力，显著提高了对拍的效率。本框架采用生产者-消费者模型实现并行测试，主要优化点集中在文件操作和并行计算策略。通过多线程并行执行测试用例生成、程序执行和结果比对，实现了80.6%的性能提升。 核心优化策略 1. 并行文件生成 // 生产者线程代码片段 system((".\\generator.exe > " + input_file).c_str()); 优化原理：每个生产者线程独立生成测试输入文件基于原子计数器生成唯一ID保证跨线程文件操作安全性便于结果追溯和调试并行执行多个generator.exe进程避免单线程文件生成的IO等待 2. 延迟文件读取 // 消费者线程代码片段 auto read_file = [](const string& filename) { ifstream file(filename); return string((istreambuf_iterator<char>(file)), istreambuf_iterator<char>()); }; 仅在结果不一致时读取文件内容采用流式读取方式按需加载文件数据 并行计算架构 无锁队列设计 template <typename T, size_t Capacity> class LockFreeQueue { // 使用原子操作实现无锁同步 atomic<size_t> head{0}; atomic<size_t> tail{0}; // 内存序优化 tail.store(..., memory_order_release); head.load(..., memory_order_acquire); }; 使用memory_order_acquire/release保证可见性环形缓冲区设计避免内存分配支持多生产者/多消费者并发访问 生产者和消费者模型

生产者线程负责生成数据，将结果推送到无锁队列：

读取两个输出文件的内容，并将测试结果封装到一个结构体（ TestResult）中。

使用无锁队列（Lock-Free Queue）将结果推送到共享队列中，供消费者线程处理。无锁队列通过原子操作实现线程安全，避免了传统锁机制带来的性能开销。

消费者线程负责从共享队列中取出数据，并对数据进行处理。消费者线的主要职责包括：

按需读取详细文件内容： 如果发现错误，消费者线程会读取输入文件和两个输出文件的详细内容，以便后续分析和调试。

首个错误触发终止机制： 如果发现错误，消费者线程会触发终止机制，停止所有生产者和消费者线程的运行。这可以通过原子变量（如 errorFound）来实现，确保线程安全。

在对拍框架中，生产者线程的 I/O 操作（如生成输入文件和运行程序）和消费者线程的 I/O 操作（如读取输出文件）可以并行进行，减少了因 I/O 操作导致的等待时间。

性能优化数据

测试点采用了CF一道题的代码，每次测试随机生成500组数据，计算时间 O ( n ) O(n) O(n) 。

#include <iostream> #include <random> using namespace std; int main() { // 设置随机数引擎 random_device rd; mt19937 gen(rd()); uniform_int_distribution<> dis(1, 1000); // 生成两个随机整数作为测试数据 int n = dis(gen); cout<<n<<endl; for(int i=1;i<=n;i++){ cout<<dis(gen)<<" "; } cout<<endl; return 0; } 测试项优化前(s)优化后(s)提升幅度Test 1354.1886.0675.7%Test 2334.5070.2279.0%Test 3441.3271.5183.8%Test 4398.8072.2181.9%Test 5409.9175.2181.6%

由于我的cpu是24核，于是消费者和生产者都开的24，经过测试这样较快，无锁队列开到8192即可，再大几乎对性能无影响。

在main函数里手动修改即可 constexpr int producer_num = 24; constexpr int consumer_num = 24; 项目仓库:

github /bestdo77/Duipai

写了一个makefile，直接make run就可以跑，make clean清除所有生成文件。