高效扫描一个大文件内字节出现的频率？

[zungmou]

比如一个5G的文件，统计每个字节出现的频率，如果是读取一部分到缓存，逐个字节从缓存中扫描的话速度非常慢，伪代码：

内存1 = 读取10MB数据；
扫描 内存1 的每个字节，然后统计；

还有没有更高效的方法？WinHex 就有这样的功能，几乎在瞬间就完成了扫描，它是如何做到的？

[wuxqing]

5G的文件，肯定要扫一边的。只能在统计的地方优化。

stat = char[256]

内存1 = 读取1000MB数据； 看机器的内存，可以分配大点，比如1000M
扫描 内存1 的每个字节
stat[字节值] += 1

[zungmou]

@wuxqing 这样的速度非常慢，慢在扫描的过程。

[billlee]

算法就是类似1楼的啦，I/O 方面用 mmap 会快一点吧

[ncisoft]

不贴代码谁知道怎么回事

[zungmou]

@ncisoft 给出 C# 代码。

class VScan
{
MemoryMappedFile _mappedFile;
MemoryMappedViewAccessor _viewAccessor;
long _position;
int[] _count;

public VZipStream(string filename)
{
_mappedFile = MemoryMappedFile.CreateFromFile(filename, FileMode.Open, "VScan");
_viewAccessor = _mappedFile.CreateViewAccessor();
_count = new int[256];
}

public void Compress(Stream output)
{
byte[] buffer = new byte[20480000];
int read = 1;

while (read > 0)
{
read = _viewAccessor.ReadArray(_position, buffer, 0, buffer.Length);
if (read == 0) break;
_position += read;

for (int i = 0; i < read; i++)
{
_count[buffer[i]]++;
}

Console.WriteLine(_position);
}
}

~VScan()
{
_viewAccessor.Dispose();
_mappedFile.Dispose();
}
}

[wuxqing]

按理说应该慢在文件读入内存的地方。内存扫一遍应该很快的，5G的内存扫一遍应该不超过1s

[zungmou]

@wuxqing 1s 这么快？用 for 循环能做到 1s 扫完 5G 内存？

[batman2010]

考虑下 cache 的命中？

[zungmou]

@batman2010 直接用 int[] 不是比任何Cache都要快吗？索引位置代表字节，数组值代表出现的次数。

[ledzep2]

考虑并行扫描 或者 异步扫描

[batman2010]

http://stackoverflow.com/questions/17925051/fast-textfile-reading-in-c

[ncisoft]

@zungmou 还需要提供两个profile数据，w/wo count loop，用来判断瓶颈是c#的磁盘读还是count

另外，count loop那部分代码不够优化，我对c#不熟，用熟悉的c给你贴示例代码
chatr*cp_last = buffer + read;
char *cp = buffer;
while (cp < cp_last) {
_count[*cp++]++;
}

read = _viewAccessor.ReadArray(_position, buffer, 0, buffer.Length);
这段代码也很诡异，读文件怎么还要指定position呢，反正你都是顺序读，linux是这么定义文件读api的
ssize_t read(int fd, void *buf, size_t count);
如果要指定位置，则有pread函数
ssize_t pread(int fd, void *buf, size_t count, off_t offset);
我不确定指定position会不会导致磁盘移动开销

还有一个奇怪的地方，既然你用到了MemoryMappedFile ，我理解和linux下的mmap是类似的东西，可是linux下的mmap之后，就可以直接当内存读取了，根本就不再需要有read操作。

对c#实在不熟悉，比如MemoryMappedViewAccessor这层封装是不是会引起额外的内存开销，以及由此触发的gc开销，拼性能的时候，api封装越少越好。

讲速度，必须要有硬件条件为前提，cpu主频、硬盘类型（SSD OR SATA OR RAID10)，内存总线速度。

一会我在atom小机器上写段c代码测试一下。

[constroy]

如果对精度要求不严的话，可以考虑随机投点法:-D

[ncisoft]

@zungmou 小机器的测试结果出来了

dd if=/dev/zero of=5G.bin bs=1024k count=5242880

A.1 wo/count
real 1m1.869s
user 0m27.836s
sys 0m5.412s

A.2 w/count

real 1m18.648s
user 0m45.452s
sys 0m4.648s

B.1 wo/count+mmap
real 0m22.094s
user 0m22.080s
sys 0m0.000s

B.2 w/count+mmap
real 0m46.465s
user 0m43.320s
sys 0m2.260s

C.1 wo/count+mmap（不启用系统文件缓存）
real 0m22.118s
user 0m22.100s
sys 0m0.008s

C.2 w/count+mmap+ O_DIRECT（不启用系统文件缓存）
real 0m35.925s
user 0m31.856s
sys 0m2.272s


基本结论：
1. mmap 的加持很明显，尤其体现在sys调用消耗上（对比A B的测试结果）
2. mmap 配合 O_DIRECT 效果更为出色（对比 B C 的测试结果）
3. 内存遍历也是相当消耗cpu的，参照B.1 B.2的对比
4. mmap 的方式实际上仍然需要磁盘io，所以不确定并发多线程统计会有帮助
5. 传统文件读取方式，可以考虑用并发多线程去做统计，感觉效果有限
6. 以上测试基于2G内存的atom小主机，不足以容纳5G的文件缓存，故测试结果是可信的，缓存因素已被排除
7. 如果你机器内存够大，可以创建内存虚拟盘，把文件放上去测试，首先去除磁盘io影响因素
8. 我用的atom小主机性能很烂的，还不到500块钱，你的机器性能更好，性能应该能得到保证

测试代码放在github上了，时间紧，写得不够完善：[file.c](https://github.com/ncisoft/ncisoft.github.io/blob/master/file.c)

[ncisoft]

还以为回复支持MD，，，重贴一次测试代码链接

https://github.com/ncisoft/ncisoft.github.io/blob/master/file.c

[Andiry]

@ncisoft 很有意思的实验，不过我很好奇你的5Gfile是放在什么文件系统和存储设备上。就我的理解，O_DIRECT对mmap 不起作用，因为mmap是映射page cache，除非你的存储设备是byte addressable的，不然不能直接映射到内存空间，像普通的SSD和HDD都是block addressable。

我用你的code在Ext4 SSD上跑了下，mmap加不加O_DIRECT几乎没有区别。直接read不成功，应该是buf对齐的原因。

[ncisoft]

@Andiry
淘宝地址奉上，我的atom小主机，eMMC硬盘，比ssd逊色，比普通机械硬盘快一些，关键是便宜啊，linux开发对机器性能又没有要求，是我目前的主力开发机

文件格式也是ext4，debian testing x64。肯定是 block device。

http://item.taobao.com/item.htm?id=43136382454

[liuhaotian]

@Livid 手机容器被撑破

[zungmou]

@ncisoft 十分感谢您的回复。

C#的MemoryMappedFile是封装mmap的类，当使用mmap方法和直接读取文件做对比，感觉性能差不了多少，基于C#测试。

public static int[] Count(Stream stream)
{
byte[] buffer = new byte[204800000];
int read = 1;
int[] count = new int[256];

DateTime begin = DateTime.Now;
while (read > 0)
{
read = stream.Read(buffer, 0, buffer.Length);
if (read == 0) break;

DateTime start = DateTime.Now;
for (int i = 0; i < read; i++)
{
count[buffer[i]]++;
}
Console.WriteLine((DateTime.Now - start).TotalSeconds);
}
Console.WriteLine((DateTime.Now - begin).TotalSeconds);
Console.ReadKey();
return count;
}

我把统计方法封装成上面这段函数，用于统计一个流内出现的字节频率，可以输入FileStream或MemoryMappedFileStream。每读取200MB的数据到缓存，扫描的平均时间（不包括IO时间）为1.40秒左右，读取一个4.78G的文件总耗费37秒左右。

不知以上方法是否还能再优化？

[Andiry]

@zungmou 如果你的内存够大，一次性用mmap把整个文件映射到用户空间，然后开多个thread，每个thread分段扫描然后归并。

[yangff]

@zungmou 直觉告诉我memorymappedfile的那个stream.read可能有一次内存的复制。。
c#的话你统计一下各个调用各花了多少时间吧。。？
还有你的硬盘是机械还是固态？我觉得这时间好像也差不多了。。

[zungmou]

@Andiry mmap 虽然映射过去了，可IO时间真的能缩减吗？

[Andiry]

@zungmou 不能，只要你的文件放在普通硬盘上，mmap还是要先读到内存里
只不过一次性读取可以快一些

[frankzeng]

找台内存大点的机器，全部load到内存里，扫一遍就结了，真正耗时的是文件的IO，简单又暴力，还不费脑子。

[ncisoft]

@zungmou 既然硬盘IO才是瓶颈，那是无法绕过去的，这是物理限制，没法通过代码实质优化。上SSD加持IO速度吧，有了SSD，随机读取也不是问题了，可以开多线程读取统计。在我的老笔记本做了测试，和atom比差距很大，机械硬盘 vs eMMC。不知windows上有没有类似 flashcache 这样逆天的玩意？

mgwin32不支持mmap函数，就只好屏蔽不测了

D.2 w/count（laptop）
real 3m7.672s
user 0m0.031s
sys 0m0.046s

A.2 w/count（atom）

real 1m18.648s
user 0m45.452s
sys 0m4.648s

[billlee]

@zungmou mmap 主要是可以避免数据从内核空间拷贝到用户空间的开销

[zungmou]

@wuxqing
@billlee
@ncisoft
@batman2010
@Andiry
@yangff

首先感谢各位的回复。

我的操作系统是 Win7 x64，CPU I5-4430主频3G，内存16GB，普通机械硬盘，开发环境是VS2013+C#；
经过一夜优化调试，现总结给大家，一个5G 文件，扫描统计后的结果如下：

x64编译：
每200MB扫描耗时0.85秒（不包括IO时间）
总耗时23.37秒（包括IO时间）

x86编译：
每200MB扫描耗时0.58秒（不包括IO时间）
总耗时16.66秒（包括IO时间）

优化主要将C#的数组改为指针去统计，绕过托管内存的消耗。
当中试过并行计算，使用的是.NET的并行类，但扫描时间比 for 循环稍长。

备注：每次缓存的数据大小和扫描时间成正比增长，所以不考虑是否全部载入内存。

源代码如下：

unsafe static class Analyzing
{
public static int[] Count(Stream stream)
{
byte[] buffer = new byte[204800000];
int read = 1;

// 用于保存统计数据的内存。
int* count = (int*)Marshal.AllocHGlobal(sizeof(int) * 256);

// 用0填充内存；
for (int i = 0; i < 256; i++)
{
count[i] = 0;
}

// 记录工作开始的时间。
DateTime begin = DateTime.Now;

// 循环读取数据到内存；
while (read > 0)
{
read = stream.Read(buffer, 0, buffer.Length);
if (read == 0) break;
// 记录扫描开始的时间。
DateTime start = DateTime.Now;
// 扫描内存的数据，并进行统计；
// count为int类型，256大小的内存区域；
// count的索引位置（0-255），代表字节0-255；
// count的索引内容，代表字节出现的频率。
for (int i = 0; i < read; i++)
{
count[buffer[i]]++;
}
// 输出扫描耗费的时间。
Console.WriteLine((DateTime.Now - start).TotalSeconds);
}

Marshal.FreeHGlobal((IntPtr)count);

// 输出工作耗费的时间。
Console.WriteLine((DateTime.Now - begin).TotalSeconds);
Console.ReadKey();

// 将非托管内存转换为托管数组，并返回该结果。
int[] result = new int[256];
Marshal.Copy((IntPtr)count, result, 0, result.Length);

return result;
}
}

[zungmou]

@wuxqing
@billlee
@ncisoft
@batman2010
@Andiry
@yangff

最后一个问题，为什么 x64 比 x86 进行 for 循环所需的时间更长？

[ncisoft]

@zungmou 这一般要看汇编码才能知道，尤其是c#这种高阶语言，里面隐藏了了太多的实现细节

一般来说，x64指针长度是一个需要考虑的方向

[ncisoft]

@zungmou 给你找了个小bug，统计用int类型是否不妥？刚查了c#的int是32位的，5G全零必然溢出

[zungmou]

@ncisoft 您很细心～ 改成long类型，200MB平均耗时0.76秒，总耗时21秒。

[xlrtx]

载入内存后吧内存分块多线程会不会有提高?