朱莉娅的大规模性能问题--使用频道

Question

摘要

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

• 基准: Bash工具(cat，grep -用C编写的基线)
  • ~2秒

• 朱莉娅:带有每一行的简单循环
  • ~4-5秒(第二次运行，不是预编译，等等)

• 朱莉娅信道实现
  • ~11秒(第二次运行，不是预编译，等等)

另外：

• 纯Python
  • ~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)

所以，在最简单的情况下，情况就更糟了。这里没有什么花哨的东西，也不是预编译的结果。

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)

这真是太可怕了，我不知道它是怎么变得如此迟缓的。

这里使用频道的方式不对吗？

Answer 1

朱莉娅、grep和Python在字符串搜索方面使用不同的算法。算法有很多种，有些算法在具体情况下要比其他算法要好得多。

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

CPython使用了多种不同的算法，所以在大多数情况下都是高效的。基于实现，他们使用了Boyer算法的混合算法“融合了Horspool和Sunday的思想”。例如，他们声称生成的算法比其他算法(例如克努斯-莫里斯-普拉特 )更快。对于长字符串，它们使用一个非常高效的更快的算法：Crochemore和Perrin的双向算法 ( BM和KMP的混合物)。在最坏的情况下，它运行在O(n+m)中，这是最优的。注意，虽然这个实现很好，但拆分文件行和创建多个string对象会显著降低性能。THis无疑是您的python实现速度不如grep的原因。

在朱莉娅代码中，文件分裂成行，这会引入一个重要的开销，并给垃圾收集器带来压力。此外，occursin 似乎没有特别优化的。在代码中没有关于使用哪种算法的评论。尽管如此，它看起来像一个天真的通用蛮力算法运行它的O(mn)时间。这样的代码不能与Python和grep中的高效算法的优化实现竞争。

通道与具有FIFO队列的协同线和光纤(或任何“光线程”)有点相似，因此可以管理消息。这种结构由于昂贵的软件定义的context-switches (也称为yield，主要是保存/恢复某些寄存器)而带来了很大的开销。对性能的负面影响可以延迟。实际上，轻型线程系统有自己的堆栈和代码上下文。因此，当处理器执行轻线程上下文切换时，这可能会导致数据/代码缓存丢失。有关通道的更多信息，您可以使用阅读文件 (其中提到嵌入式任务调度程序)或直接读取代码。

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

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

Answer 2

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

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

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

性能提示

通道将增加很大的开销，就像任何额外的通信层一样。如果需要性能，则需要：

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