摘要

Julia 中频道的基准测试时间 - 使用 ~5GB tsv 文件

基线：Bash 工具(cat、grep - 用 C 编写的基线)
- ~ 2 秒
朱莉娅：每条线的简单循环
- ~ 4-5 秒(第二次运行，非预编译等)
朱莉娅频道实现
- ~ 11 秒(第二次运行，非预编译等)

也：

纯蟒蛇
- ~ 4-5 秒

更长的解释

我一直在努力制作性能最高/标准类型的多处理设计模式，其中数据要么从磁盘流式传输，要么从下载流中流式传输，片段被馈送到系统上的所有内核，然后从中输出被序列化到磁盘。这显然是一个非常重要的设计，因为大多数编程任务都属于这个描述。

朱莉娅似乎是一个很好的选择，因为它应该具有高性能。

为了将IO序列化到磁盘或从磁盘下载，然后将数据发送到每个处理器，通道似乎是Julia的建议选择。

但是，到目前为止，我的测试似乎表明这是非常不高性能的。

最简单的例子显示了频道(和朱莉娅！)在这方面是多么慢。这是非常令人失望的。

grep 和 cat 的简单示例(为清楚起见，删除多处理位)：

朱莉娅代码：

using CodecZlib: GzipDecompressorStream
using TranscodingStreams: NoopStream

"""
A simple function to "generate" (place into a Channel) lines from a file
- This mimics python-like behavior of 'yield'
"""
function cat_ch(fpath)
Channel() do ch
codec = endswith(fpath, ".gz") ? GzipDecompressorStream : NoopStream
open(codec, fpath, "r") do stream
for (i, l) in enumerate(eachline(stream))
put!(ch, (i, l))
end
end
end
end

function grep_ch(line_chnl, searchstr)
Channel() do ch
for (i, l) in line_chnl
if occursin(searchstr, l)
put!(ch, (i, l))
end
end
end
end
function catgrep_ch(fpath, search)
for (i, l) in grep_ch(cat_ch(fpath), search)
println((i, l))
end
end
function catgrep(fpath, search)
codec = endswith(fpath, ".gz") ? GzipDecompressorStream : NoopStream
open(codec, fpath, "r") do stream
for (i, l) in enumerate(eachline(stream))
if occursin(search, l)
println((i,l))
end
end
end
end
if abspath(PROGRAM_FILE) == @__FILE__
fpath = ARGS[1]
search = ARGS[2]
catgrep_ch(fpath, search)
end

性能基准

1) 基线：

user@computer>> time (cat bigfile.tsv | grep seachterm)
real    0m1.952s
user    0m0.205s
sys 0m2.525s

3)在朱莉娅中没有频道(简单)：

julia> include("test1.jl")
julia> @time catgrep("bigfile.tsv", "seachterm")
4.448542 seconds (20.30 M allocations: 10.940 GiB, 5.00% gc time)
julia> @time catgrep("bigfile.tsv", "seachterm")
4.512661 seconds (20.30 M allocations: 10.940 GiB, 4.87% gc time)

因此，在最简单的情况下，情况更糟 2-3 倍。这里根本没有做任何花哨的事情，也不是由于预编译。

3)朱莉娅的频道：

julia> @time catgrep_ch("bigfile.tsv", "seachterm")
11.691557 seconds (65.45 M allocations: 12.140 GiB, 3.06% gc time, 0.80% compilation time)
julia> @time catgrep_ch("bigfile.tsv", "seachterm")
11.403931 seconds (65.30 M allocations: 12.132 GiB, 3.03% gc time)

这真的很可怕，我不知道它是如何变得如此迟钝的。

这里使用频道的方式是错误的吗？

Julia，grep和Python在字符串搜索中使用不同的算法。有很多算法，有些在特定情况下比其他算法好得多。

grep 经过高度优化，因此在许多情况下都可以快速运行，包括在您的特定用例中。事实上，根据GNU文档，Boyer-Moore快速字符串搜索算法用于匹配单个固定模式，而Aho-Corasick 算法用于匹配多个固定模式。在您的特定用例中，可以选择Boyer-Moore，它通常很快，因为它可以根据搜索的字符串跳过部分输入。其最佳情况复杂度为Ω(n/m)，最坏情况复杂度为O(mn)。如果文本很少包含搜索字符串的字符，则速度非常快。例如，在目标文件中不存在this is a test with a pretty long sentence中搜索seachterm(重复 5850 万次)比搜索iss快 10 倍。这是因为Boyer-Moore在文本中搜索搜索字符串(m)的最后一个字母，但找不到它，所以它可以非常快。还有其他原因解释了为什么与大多数替代方法相比，grep 如此之快。其中之一是 grep 不会为每行创建/分配子字符串，而是使用巨大的原始缓冲区。请注意，cat bigfile.tsv | grep seachterm可能比grep seachterm bigfile.tsv慢得多，因为当解析足够快时，管道会引入大量开销。

CPython混合使用不同的算法，因此在大多数情况下要高效。基于实现，他们混合使用Boyer-Moore算法"结合Horspool和Sunday的想法"。他们声称生成的算法比其他算法(例如Knuth-Morris-Pratt)更快。对于长字符串，他们使用一种非常有效的更快算法：Crochemore 和 Perrin's Two-Way 算法(BM 和 KMP 的混合)。这个在最坏的情况下以O(n+m)运行，这是最佳的。请注意，虽然此实现很棒，但拆分文件的行并创建许多字符串对象可能会显著降低性能。这当然是为什么你的python实现与grep相比没有那么快的原因。

在 Julia 代码中，文件分成几行，这引入了大量的开销，并对垃圾收集器施加了压力。此外，occursin似乎没有特别优化。代码中没有关于使用哪种算法的注释。话虽如此，它看起来像一个天真的通用暴力算法O(mn)运行它。这样的代码无法与高效算法的优化实现竞争，例如 Python 和 grep 中的算法。

通道有点类似于协程和光纤(或任何"轻线程")，具有FIFO队列，以便管理消息。由于昂贵的软件定义的上下文切换(也称为yield主要包括保存/恢复一些寄存器)，这种结构引入了大量开销。对性能的负面影响可能会延迟。事实上，轻线程系统有自己的堆栈和自己的代码上下文。因此，当处理器执行轻线程上下文切换时，这可能会导致数据/代码缓存未命中。有关频道的更多信息，您可以阅读有关它的文档(其中提到了嵌入式任务计划程序)或直接阅读代码。

此外，通道创建的对象/消息比垃圾回收器需要管理的对象/消息要大，这给它带来了更大的压力。事实上，在基于通道的版本中，分配数量是>3 倍。有人可能会争辩说，报告的 GC 开销很低，但这些指标通常低估了总体开销，包括分配、内存扩散/碎片、GC集合、缓存效应等(在这种情况下，甚至是 I/O 重叠效应)。

我认为基于通道的实现的主要问题是代码的通道是无缓冲的(请参阅有关它的文档)。使用宽缓冲区有助于显著减少上下文切换的数量，从而减少开销。这可能会增加延迟，但通常需要在延迟和吞吐量之间进行权衡(尤其是在调度中)。或者，请注意，有些包可能比内置通道更快。

缓冲通道确实加快了这段代码的速度，但主要问题仍然存在：不应该使用这样的通道。处理时间/传输时间比太小，此任务不合理，因此大部分时间都花在通过通道传输数据和分配/释放内存上。

尽管这里有一些代码改进：

向通道Channel(f, buffer_size)添加一些缓冲区
异步执行操作。Channel(f, buffer_size; spawn=true)
提供类型稳定性Channel{Tuple{Int,String}}(f, buffer_size; spawn=true)

因此，假设您正在从文件中读取大行并对其执行几个高负载步骤，则可以同时执行，您可以像这样实现它

function step1(ch_out)
open(file, "r") do stream
for l in eachline(stream)
res = process1(l)
put!(ch_out, res)
end
end
end
function step2(ch_in, ch_out)
for el in ch_in
res = process2(el)
put!(ch_out, res)
end
end
...
function main(args)
ch1 = Channel{TYPE1}(step1, bufsize1; spawn=true)
ch2 = Channel{TYPE2}(step2, bufsize2; spawn=true)
...
ch_end = Channel{TYPE_END}(step_end, bufsize_end; spawn=true)
for el in ch_end
process_end(el)
end # or simply collect(ch_end)
end

您可以使用Distributed更好地控制任务的生成、计划等方式。

最后，您可以以某种方式分析此代码，以跟踪每个通道缓冲区的使用情况并优化其大小以获得不间断的传送带。

编辑(关于来自@chase的新信息)

@chase据我了解，您正在比较 Python 中yield的性能，Python 是非物化列表的生成器与 Julia 中的Channel，Julia 是一个 FIFO 队列，支持元素的多线程插入和轮询。在这种情况下，您正在比较两种非常不同的东西(例如苹果和橙子)。

如果您的目标是实现与 grep 类似的处理，请查看下面的性能提示。

性能提示

通道将像任何其他通信层一样增加很大的开销。如果您需要性能，您需要：

使用@distributed或Threads.@threads创建并行工作线程
每个工作人员打开文件进行读取
使用seek分配它们的位置(例如，有一个 1000 字节的文件和 2 个工作线程，第一个从字节 0 开始，第二个seek(500)。
请记住以这样一种方式实现机制，即处理您的工作人员在生产线中间获取数据的情况
直接对原始字节而不是String进行操作(为了提高性能)

巨大的性能问题 - 在 Julia 中使用频道

摘要