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

[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分段扫描然后归并。