performance - Raku 慢速混合排序

Question

更新
在同一台计算机上，使用 Rakudo 编译器“rakudo-moar-2021.06-01-macos-x86_64-clang.tar”，与我在原始帖子中的计算时间相比，我获得了 3-10 倍的加速。

.elems: 100000
.head(3): (id.20444 => 81.95246687507492 id.81745 => 34.859323339828464 id.79973 => 97.33816856420829)
time of .sort({-$_.value}) : 0.764283216
time of .sort(-*.value)    : 0.618963783
time of .sort.reverse      : 0.584477656
time of .values.sort       : 1.68912663

请注意，这些时间接近 R 时间。因此，在这些类型的计算中，Raku 具有我期望的性能。

原帖
我最近观看了 Elizabeth Mattijsen 的 FOSDEM 演示，标题为
"Raku - Sets without Borders"
并决定采用 Raku Mix我的一些计算工作流中的对象。
我注意到对 Mix 进行排序(成对) object 非常慢——我会说比我预期的慢 100 到 1000 倍。请参阅下面的 Raku 代码和输出。 (我还在同一台计算机上提供了相关的 R 代码和输出。)
这是预期的缓慢吗？是否有解决更快计算的方法？
(更具体地说，我对快速反向排序和快速检索 Mix 中的前 K 个最大元素感兴趣。)
(时间是在几年前的 Mac Book Pro，Mac OS 10.15.7 上，使用最新的 Rakudo 编译器“rakudo-moar-2021.02.1-01-macos-x86_64-clang.tar.gz”。)
乐

#!/usr/bin/env perl6

my @words = Array(1 .. 100_000).map({ 'id.' ~ $_.Str });
my $m0 = Mix(@words.map({ $_ => 100.rand() }));
say '.elems: ', $m0.elems;
say '.head(3): ', $m0.head(3);

my $start = now;
my $m1 = $m0.sort({-$_.value});
say 'time of .sort({-$_.value}): ', now - $start;

$start = now;
my $m2 = $m0.sort(-*.value);
say 'time of .sort(-*.value)   : ', now - $start;

$start = now;
my $m3 = $m0.sort.reverse;
say 'time of .sort.reverse     : ', now - $start;

$start = now;
my $m4 = $m0.values.sort;
say 'time of .values.sort      : ', now - $start;

# .elems: 100000
# .head(3): (id.96239 => 87.89629474533156 id.89110 => 11.661698290245525 id.24795 => # 64.80528155838671)
# time of .sort({-$_.value}): 3.64936396
# time of .sort(-*.value)   : 4.0388654
# time of .sort.reverse     : 4.5783556
# time of .values.sort      : 4.3461059

电阻
这是 R 中类似的数据和排序代码:

words <- paste0( 'id.', 1:100000)
m <- setNames( runif(n = length(words), min = 0, max = 100), words)
cat( "length(m)                          : ", length(m), "\n")
cat( "m[1:3]:\n"); print(m[1:3]); cat("\n")
cat( "system.time( sort(m) )             : ", system.time( sort(m) ), "\n")
cat( "system.time( m[order(-m)] )        : ", system.time( m[order(-m)] ), "\n")
cat( "system.time( rev(sort(names(m))) ) : ", system.time( rev(sort(names(m))) ), "\n")

# length(m)                          :  100000 
# m[1:3]:
#     id.1     id.2     id.3 
# 89.99714 54.31701 11.57415 
#
# system.time( sort(m) )             :  0.011 0     0.011 0 0 
# system.time( m[order(-m)] )        :  0.011 0     0.011 0 0 
# system.time( rev(sort(names(m))) ) :  0.298 0.001 0.3   0 0 

以下是@raith 对问题的回答:

“R 代码中的 m 是可变的吗？”
不，R 对象大多是不可变的。

“sort(m) 是建立一个新的数据结构，还是只是在现有的 m 结构中建立一个新索引？”
创建了一个新的数据结构。 R 是 LISP 的后代，因此它在精神上主要遵循函数式编程范式。

“对 m[order(-m)] 有同样的问题？”order(-m)给出一个整数向量(索引)。索引向量用于检索 m 的元素。成一个新对象。

“还有 rev(sort(names(m)))？”names(m)获取 m 的“ key ”的元素。这些键被排序并放入一个字符向量中，然后该字符向量被反转。 (即创建了一个新对象。)

“据推测，仅构建索引可能会快得多。也许 Raku 可以为元组提供一种排序变体，该变体产生依赖于的 Seq
在那种方法上？”
我认为我不应该对此发表评论，但我想提一下:

Julia —— 也是 LISP 的后代 —— 对其数据结构做了类似的事情。 Julia 的创造者和开发者声称，总的来说，比 R 和 Mathematica 快得多。 (哪些是用于数学计算的其他 LISP 后代。)

我更喜欢并期望函数范式风格的 Raku 代码速度更快。

更新的 R 基准
一些人要求更详细的 R 基准测试:

library(microbenchmark)
set.seed(32)
words <- paste0( 'id.', 1:100000)
m <- setNames( runif(n = length(words), min = 0, max = 100), words)
cat( "length(m): ", length(m), "\n")
cat( "m[1:3]:\n"); print(m[1:3]); cat("\n")

microbenchmark::microbenchmark(
  sort(m, decreasing = T),
  sort(-m),
  m[order(-m)],
  rev(sort(m)),
  rev(sort(names(m))),
  unit = "s", times = 100
)

# length(m) :  100000
#
# m[1:3]:
#     id.1     id.2     id.3
# 50.58405 59.48084 80.87471
#
# Unit: seconds
#                     expr         min          lq        mean      median          uq        max neval cld
#  sort(m, decreasing = T) 0.006246853 0.007789205 0.009215613 0.008263348 0.009002414 0.02450786   100 a
#                 sort(-m) 0.006857755 0.008376058 0.010292145 0.008939605 0.010069702 0.02469324   100 a
#             m[order(-m)] 0.006658089 0.008257555 0.009726704 0.008718414 0.009811200 0.02294023   100 a
#             rev(sort(m)) 0.008975013 0.010939122 0.014965756 0.011692480 0.012571979 0.22022085   100  b
#      rev(sort(names(m))) 0.256036106 0.268526455 0.278385866 0.277794917 0.288586351 0.31160492   100   c
#

Answer 1

[ 编辑 2021-03-06:由于过去 ~ 天的一系列提交(谢谢，Liz!)，这种放缓现在基本上固定在 HEAD ;这些性能提升应该会出现在下一个月度版本中。我将下面的答案作为如何深入研究此类问题的示例，但它诊断出的具体问题已在很大程度上得到解决。]
基于@Elizabeth Mattijsen 的评论:这里的缓慢性能是 大部分 由于 Rakudo 编译器未正确优化生成的代码(截至 2021-03-05)。随着编译器的不断改进，您上面编写的(惯用的)代码应该会表现得更好。
但是，今天我们可以使用一些变通方法来加速此计算。虽然在这里 Raku 的性能与 R 相比仍然没有特别的竞争力，但一些分析驱动的重构可以使此代码接近 快一个数量级 .
这是我们如何做到的:
首先，我们从分析代码开始。如果你用 raku --profile=<filename> 运行你的脚本，然后你会得到一个写到 <filename> 的个人资料.默认情况下，这将是一个 HTML 文件，允许您在浏览器中查看配置文件。然而，我的偏好是指定一个 .sql扩展，它生成一个 SQL 配置文件。然后我用 MoarProf 查看此个人资料, 修正了 Timo Paulssen 的探查器正在 build 。
查看此配置文件准确地显示了 Liz 提到的问题:应该内联的调用没有。为了解决这个问题，让我们创建自己的排序函数，JIT 编译器会很乐意优化它:

sub my-reverse($a, $b) {
    $a.value > $b.value ?? Order::Less !! Order::More
}

使用此函数(与 $m0.sort(&my-reverse) 一起)可以立即减少 25% 的运行时间，但它仍然太高了。回到分析器!
接下来让我吃惊的是我们仍然有太多的电话给 Bool .特别是，看起来乐堂目前正在转换 Ordering到 Bool .我认为这是一个错误，并计划在发布此内容后对其进行调查，但无论如何，我们可以节省 Rakudo 的努力:

sub my-reverse1($a, $b) {
    $a.value > $b.value ?? False !! True
}

在我的机器上，这再次将执行时间缩短了一半，使我们达到了 .sort({-$_.value}) 原始运行时间的 28% 左右。 .这变得体面了，将是一个停下来的好地方。
不过，让我们继续:再次检查分析器表明我们仍然将大量时间用于调用 Bool。 (即使我们打电话的频率减半)。目前要解决这个问题，我们需要下拉到 NQP在不构建 Bool 的情况下比较数字:

sub nqp-reverse($a, $b) {
    use nqp;
    nqp::isge_n($a.value, $b.value) ?? False !! True
}

这再次将我们的执行时间减少了一半，并使我们获得了我想要的 Raku 性能。
以下是我得到的计时结果，包括我添加的函数和您问题中的函数，以您使用的相同格式报告:

.elems: 100000
.head(3): (id.195 => 80.81458886131459 id.31126 => 84.25690944480021 id.60237 => 45.63311676798485)
time of .sort(&nqp-reverse): 0.3226533
time of .sort(&my-reverse1): 0.76803384
time of .sort(&my-reverse) : 1.4643238
time of .sort({-$_.value}) : 2.6780952
time of .sort(-*.value)    : 1.8549689
time of .sort.reverse      : 2.5862973
time of .values.sort       : 2.078715