linux大文件快速读取

Reference

https://www.byvoid.com/zhs/blog/fast-readfile

Intro

平台

archlinux x86_64

i7-7700HQ 8G

最近需要完成课程”并行与分布式计算”的项目, 并行Dijkstra的项目编写. 问题详情如下:

给定输入文件input.txt(1.8GiB), 以邻接表形式给出200017000w边的图. 要求给出从020000的最短路径. 要求使用(MPI+OpenMP)编程.

注意到给出起点和终点, 在不追求最优解的情况下可以使用双向Dijkstra算法, 好处是MPI通信不需要同步. 实际测试中, 串行版本30s中99%的时间都在读取文件. 最初版本是使用fstream编写的, 实在太慢. 所以想通过linux的API获取更快的速度. 于是, 我有了三种选择:

  • fread
  • read
  • mmap

使用以下.cpp生成10000000个浮点数

1
2
3
4
5
6
7
8
#include <ctime>
#include <stdio.h>
int main()
{
int start = clock();
for (int i = 0; i < 10000000; i++)
printf("%.3lf\n",double(clock()-start)/CLOCKS_PER_SEC);
}

在终端运行

1
2
clang++ get_nums.cpp -o get_nums
./get_nums > ./input.txt

获取测试文件(55MiB).

编程语言API

不管怎么说, 我都先测试一下普通情况下的读取花费. 总的来说, scanf最快. (当然我猜没有输入挂快)

scanf

1
2
3
4
5
6
7
#include <cstdio>
void scanf_read()
{
freopen("input.txt", "r", stdin);
for (int i=0; i<MAXN; i++)
scanf("%lf", &numbers[i]);
}
1
2
time ./main
./main 1.57s user 0.04s system 109% cpu 1.472 total

cin

1
2
3
4
5
6
7
#include <iostream>
void cin_read()
{
freopen("input.txt","r",stdin);
for (int i=0;i<MAXN;i++)
std::cin >> numbers[i];
}
1
2
time ./main
./main 3.92s user 0.07s system 110% cpu 3.597 total

cin nosync

cin默认情况需要与stdio保持同步, 保持输入输出顺序正确. 为了兼容, 有大量开销, 我们可以关闭这个兼容.

1
2
3
4
5
6
7
8
#include <iostream>
void cin_read_nosync()
{
freopen("data.txt","r",stdin);
std::ios::sync_with_stdio(false);
for (int i=0;i<MAXN;i++)
std::cin >> numbers[i];
}
1
2
time ./main
./main 2.26s user 0.02s system 109% cpu 2.087 total

操作系统API

其实, read和mmap谁快的争论很早就有人提出了 https://blog.csdn.net/ryder001/article/details/7949132

  • 大家关于“mmap()”更快的认识来自于 read() 是需要内存拷贝的;
  • 当今硬件技术的发展,使得内存拷贝消耗的时间已经极大降低了;
  • 但“mmap()”的开销在于一次 pagefault,这个开销相比而言已经更高了,而且 pagefault 的处理任务现在比以前还更多了;
  • 而且,mmap之后,再有读操作不会经过系统调用,在 LRU 比较最近使用的页的时候不占优势;
  • 于是,普通读情况下(排除反复读之类的文艺与2B读操作),read() 通常会比 mmap() 来得更快。

在这里我们将分别测试将整个文件读入内存的花费时间, 以及文件加载入内存并进行处理的总时间. 测试对象是之前提到的7000w行的邻接表. 处理函数为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
inline void get_int(int &res, char &ch, char* &mbuf)
{
res = 0;
ch = *mbuf;
while (isdigit(ch)) {
res = res * 10 + (ch^'0');
mbuf++;
ch = *mbuf;
}
mbuf++;
}

void read_worker(char* mbuf, char* end)
{
int from, to, weight;
char ch;
while (mbuf < end) {
get_int(from, ch, mbuf);
get_int(to, ch, mbuf);
get_int(weight, ch, mbuf);

table[from * n + to] = weight;
}
}

fread

会有系统调用read与进程的数据拷贝开销.

1
2
3
4
5
6
7
8
9
10
11
struct stat file_info;
FILE *fd;
char *mbuf;

fd = fopen(file_name, "rb");
stat(file_name,&file_info);
mbuf = (char*)malloc(file_info.st_size + 1);
fread(mbuf,sizeof(char),file_info.st_size,fd);
fclose(fd);
mbuf[file_info.st_size]='\n';
char* end = mbuf + file_info.st_size;
1
2
time ./test                      
./test 9.49s user 0.91s system 109% cpu 9.482 total

mmap

将文件映射到内存, 每次访问到新的页帧, 产生缺页, 造成文件读取, 好处是减少了一层拷贝, 坏处是缺页的代价较高.

1
2
3
4
5
6
char *mbuf;

int fd = open(file_name, O_RDONLY);
int size = lseek(fd, 0, SEEK_END);
mbuf = (char *) mmap( NULL, size ,PROT_READ, MAP_PRIVATE, fd, 0 );
char* end = mbuf + size;
1
2
time ./test
./test 8.93s user 0.38s system 108% cpu 8.589 total
文章目录
  1. 1. Reference
  2. 2. Intro
  3. 3. 编程语言API
    1. 3.1. scanf
    2. 3.2. cin
    3. 3.3. cin nosync
  4. 4. 操作系统API
    1. 4.1. fread
    2. 4.2. mmap
|