Rust测速

Posted by wyj on August 9, 2020 / Edited on October 8, 2024

此文章比较了一些常用数据结构和算法的C++实现和Rust实现的速度。

此处的C++,指g++ 10.0.1和clang++ 10.0.0;Rust指rustc 1.43.0。C++的编译参数是-Ofast -march=native -std=c++20;Rust的编译参数是-C opt-level=3 -C target-cpu=native。速度,指user time。

为了排除读入速度的差异,使用了相同的快读实现(在Rust中我实在是找不到一种原生的快读方法,只好extern "C"了)。C++使用printf输出,Rust使用std::io::BufWriter输出;两者的速度经我测试没有肉眼可见的差别。

int read(){
	int r=0,c;
	do c=getchar();while(!isdigit(c));
	do r=r*10+c-48,c=getchar();while(isdigit(c));
	return r;
}
extern "C"{fn getchar()->i32;}

fn read()->i32{
	let mut r=0;let mut c;
	loop{
		unsafe{c=getchar();}
		if c>=48 && c<48+10{break;}
	}
	loop{
		r=r*10+c-48;unsafe{c=getchar();}
		if c<48 || c>=48+10{break;}
	}
	r
}

let	out=&mut BufWriter::new(stdout());

std::sort VS <[T]>::sort_unstable

对于长度为$2^{24}$的随机数列进行排序,然后输出。数列中元素范围是$[1,10^9]$。两个排序均为不稳定的,底层实现均为快速排序的某个变种。

const int N=1<<24;
vector<int> a(N);
ranges::generate(a,read);
ranges::sort(a);
for(int i:a)printf("%d\n",i);
const N:usize=1<<24;
let mut v=vec![];
v.resize_with(N,read);
v.sort_unstable();
for i in v{writeln!(out,"{}",i).ok();}

g++运行时间:2.432s;clang++运行时间:2.399s;rust运行时间:1.676s。每个语言都有0.725s时间花在输出上,0.286s时间花在读入上,可见Rust的sort效率是C++的2倍以上。由于测输入输出时间太烦了,以后的输入和输出的时间我都认为与输入/输出的数个数成正比,不再继续测量了。

std::vector VS Vec

输入一个$2^{24}$个点的随机树,输出邻接表。

const int N=1<<24;
vector<vector<int>> v(N);
for(int _=1;_<N;_++){
	int x=read(),y=read();
	v[x].push_back(y);v[y].push_back(x);
}
for(int i=0;i<N;i++){
	for(int j:v[i])printf("%d ",j);
	puts("");
}
const N:usize=1<<24;
let mut v=vec![vec![];N];
for _ in 1..N{
	let (x,y)=(read()as usize,read()as usize);
	v[x].push(y);v[y].push(x);
}
for i in 0..N{
	for &j in &v[i]{write!(out,"{} ",j).ok();}
	writeln!(out,"").ok();
}

C++实现为啥不用std::array或者原生数组?因为栈里开不下。为什么不用static?因为开static vector<int> v[N];的一瞬间,我电脑死机了。Rust实现不用原生数组也是一样的道理。

g++用时10.601s;clang++用时10.372s;rust用时10.508s。可见在这方面还是半斤八两的;无论什么语言都别想开超过一百万个vector,否则神仙也难救。

std::unordered_map VS std::collections::HashMap

进行$2^{24}$次操作,每次操作有$\dfrac{1}{2}$的概率插入(随机的)键值对,如果键已存在就更新值;另外$\dfrac{1}{2}$的概率询问一个键对应的值(键有$\dfrac{1}{3}$左右的概率不存在)。键和值的范围均是$[1,10^9]$。底层实现均为哈希表,并且Rust的实现不可能被卡(哈希函数是随机选择的)

const int N=1<<24,QRY=2;
unordered_map<int,int> mp(N);
for(int _=N;_--;){
	int op=read(),key=read();
	if(op==QRY)
		printf("%d\n",mp.contains(key)?mp[key]:-1);
	else mp[key]=read();
}
const N:usize=1<<24;
const QRY:i32=2;
let mut mp=HashMap::<i32,i32>::with_capacity(N);
for _ in 0..N{
	let (op,key)=(read(),read());
	if op==QRY{
		writeln!(out,"{}",if mp.contains_key(&key){mp[&key]}else{-1}).ok();
	}else{mp.insert(key,read());}
}

值得一提的是怎么gen数据,即怎么从一个很大的集合中随机选出一个元素。我使用了pbds,*t.find_by_order(rand()%t.size())。不知道有没有什么更简单的方法。

g++用时3.932s;clang++用时3.766s;rust用时3.181s。可见Rust的哈希表效率是C++的1.3倍左右。

std::set VS std::collections::BTreeSet

进行$2^{24}$次操作,每次操作有$\dfrac{1}{2}$的概率插入一个(随机的)元素(可能已经存在);另外$\dfrac{1}{2}$的概率询问集合中$\ge x$的最小值(即lower_bound),可能不存在。元素范围是$[1,10^9]$。底层实现是不同的,C++实现是红黑树,Rust实现是B Tree。

const int N=1<<24,QRY=2;
set<int> st;
for(int _=N;_--;){
	int op=read(),key=read();
	if(op==QRY){
		auto it=st.lower_bound(key);
		printf("%d\n",it==st.end()?-1:*it);
	}else st.insert(key);
}
const N:usize=1<<24;
const QRY:i32=2;
let mut st=BTreeSet::<i32>::new();
for _ in 0..N{
	let (op,key)=(read(),read());
	if op==QRY{
		let mut r=st.range((Included(key),Unbounded));
		writeln!(out,"{}",r.next().unwrap_or(&-1)).ok();
	}else{st.insert(key);}
}

可怕!g++用时14.850s,clang++用时15.131s,rust用时5.622s。红黑树被打爆了。Rust的set效率是C++的set的三倍以上。

std::priority_queue VS std::collections::BinaryHeap

进行$2^{24}$次操作,$\dfrac{2}{3}$概率插入一个随机数,$\dfrac{1}{3}$概率弹出堆顶并输出弹出的元素(保证堆非空)。元素范围是$[1,10^9]$。底层实现均为二叉堆,并且Rust的堆是可以遍历的。

const int N=1<<24,QRY=2;
priority_queue<int> pq;
for(int _=N;_--;){
	int op=read();
	if(op==QRY){
		int x=pq.top();pq.pop();
		printf("%d\n",x);
	}else pq.push(read());
}
const N:usize=1<<24;
const QRY:i32=2;
let mut pq=BinaryHeap::<i32>::with_capacity(N);
for _ in 0..N{
	let op=read();
	if op==QRY{
		writeln!(out,"{}",pq.pop().unwrap()).ok();
	}else{pq.push(read());}
}

这里C++的代码没有先reserve,因为priority_queuereserve比较麻烦(因为c是保护成员变量,要先继承),并且没有变快。

g++用时1.170s,clang++用时1.132s,rust用时0.979s。虽然表面上差距不大,不要忘了IO所用时间是很多的。减去IO时间可以估算出Rust的堆效率是C++的1.6倍左右。

std::deque VS std::collections::VecDeque

进行$2^{24}$次操作,每次操作可能是:在头部或尾部插入随机数,各有$\dfrac{1}{5}$概率;弹出头部或尾部元素(保证非空),各有$\dfrac{1}{5}$概率;输出某一特定下标上的元素(保证非空),也有$\dfrac{1}{5}$的概率。元素范围是$[1,10^9]$。我太菜了,不清楚底层实现。

const int N=1<<24;
deque<int> v;
for(int _=N;_--;){
	int op=read();
	switch(op){
		case 0:{v.push_front(read());break;}
		case 1:{v.push_back(read());break;}
		case 2:{printf("%d\n",v.front());v.pop_front();break;}
		case 3:{printf("%d\n",v.back());v.pop_back();break;}
		case 4:printf("%d\n",v[read()]);
	}
}
const N:usize=1<<24;
let mut v=VecDeque::<i32>::with_capacity(N);
for _ in 0..N{
	let op=read();
	match op{
		0=>v.push_front(read()),
		1=>v.push_back(read()),
		2=>{writeln!(out,"{}",v.pop_front().unwrap()).ok();},
		3=>{writeln!(out,"{}",v.pop_back().unwrap()).ok();},
		4=>{writeln!(out,"{}",v[read()as usize]).ok();},
		_=>()
	}
}

C++的deque貌似是没有reserve这种功能的。但是就算公平竞争,把Rust的with_capacity(N)改成new(),rust也只需0.804s。

g++用时0.936s,clang++用时0.939s,rust用时0.798s。减去IO时间,Rust的deque效率是C++的1.8倍到两倍左右。