查找命令运算符的结合性及其对执行速度的影响

查找命令运算符的结合性及其对执行速度的影响

假设在一个文件夹结构中,有扩展名为ext1ext2、的文件ext3(按每种类型的文件数量递减顺序排列),以及一些我们不太关心的文件(总共可能有 100,000 个文件)

ext1由于比 更有可能,以下速度是否存在差异ext2

find . -name "*.ext1" -or -name "*.ext2" -or -name "*.ext3"
find . -name "*.ext3" -or -name "*.ext2" -or -name "*.ext1"
... other permutations ...

这假设运算符具有从左到右的关联性or。是这样吗?

答案1

find我在 tmpfs 中测试了 GNU 。(你使用了不可移植的-or,因此或许你的find是 GNU find。)


准备

这是我用来创建 25,000,000 个常规文件的方法:

#!/bin/bash
exts=(ext1 ext1 ext1 ext1 ext1 ext1 ext1 ext1 ext1 ext1 ext1 ext1 ext2 ext2 ext2 ext3)
for d in d{0000..4999}; do
   mkdir -p "$d"
   (
   cd "$d" || exit 1
   for f in f{0000..4999}; do
      : >"$f.${exts[RANDOM%16]}"
   done
   )
done

对于每个文件,代码随机选择扩展名,理论分布是:

ext1:ext2:ext3 = 12:3:1

我确认有 25,000,000 个常规文件 ( find . -type f | wc -l)。在我的测试中,具有不同扩展名(来自等)的文件的实际数量find . -name "*.ext1"为:

  • ext1– 18747859 – 约 12/16 x 25M,符合预期
  • ext2– 4689687 – 约 3/16 x 25M,符合预期
  • ext3– 1562454 – 约 1/16 x 25M,符合预期

测试

每次测试前无需刷新缓存,因为tmpfs 是缓存。这是我的测试方法:

#!/bin/bash
sequence() {
   repeat=$1
   shift
   printf -- '---\n%sx' "$repeat"
   printf -- ' %s' "$@"
   for e do
      shift
      set -- "$@" -o -name "*.$e"
   done
   shift
   time for ((i=0; i<repeat; i++)); do
      find . "$@" >/dev/null
   done
}

sequence 10 ext1 ext2 ext3
sequence 10 ext1 ext3 ext2
sequence 10 ext2 ext1 ext3
sequence 10 ext2 ext3 ext1
sequence 10 ext3 ext1 ext2
sequence 10 ext3 ext2 ext1

sequence 10 ext3 ext2 ext1
sequence 10 ext3 ext1 ext2
sequence 10 ext2 ext3 ext1
sequence 10 ext2 ext1 ext3
sequence 10 ext1 ext3 ext2
sequence 10 ext1 ext2 ext3

echo

sequence 10 ext1 ext2
sequence 10 ext1 ext3
sequence 10 ext2 ext3
sequence 10 ext2 ext1
sequence 10 ext3 ext1
sequence 10 ext3 ext2

sequence 10 ext3 ext2
sequence 10 ext3 ext1
sequence 10 ext2 ext1
sequence 10 ext2 ext3
sequence 10 ext1 ext3
sequence 10 ext1 ext2

echo

sequence 10 ext1
sequence 10 ext2
sequence 10 ext3

sequence 10 ext3
sequence 10 ext2
sequence 10 ext1

echo

sequence 10 ext4

sequence 10 ext4

(序列的序列以相反的方式重复,以减轻对前一个序列的依赖的影响;但可能没有影响。)


原始结果

我的原始结果如下(几乎是原始的;制表符已扩展为空格;网站无论如何都会这样做,只是更糟)。10x extK extL …意味着内置函数已经测量了10 次find . …with调用,时间就在下面。-name "*.extK" -o -name "*.extL" -o …time

---
10x ext1 ext2 ext3
real    2m32,247s
user    1m40,585s
sys     0m51,656s
---
10x ext1 ext3 ext2
real    2m37,432s
user    1m45,416s
sys     0m51,992s
---
10x ext2 ext1 ext3
real    1m55,497s
user    1m4,254s
sys     0m51,236s
---
10x ext2 ext3 ext1
real    2m18,621s
user    1m27,806s
sys     0m50,814s
---
10x ext3 ext1 ext2
real    1m51,599s
user    1m0,787s
sys     0m50,808s
---
10x ext3 ext2 ext1
real    2m10,800s
user    1m19,634s
sys     0m51,165s
---
10x ext3 ext2 ext1
real    2m10,505s
user    1m19,051s
sys     0m51,453s
---
10x ext3 ext1 ext2
real    1m51,650s
user    1m0,522s
sys     0m51,128s
---
10x ext2 ext3 ext1
real    2m18,674s
user    1m27,835s
sys     0m50,838s
---
10x ext2 ext1 ext3
real    1m55,752s
user    1m4,960s
sys     0m50,791s
---
10x ext1 ext3 ext2
real    2m35,521s
user    1m43,698s
sys     0m51,822s
---
10x ext1 ext2 ext3
real    2m32,456s
user    1m40,719s
sys     0m51,733s

---
10x ext1 ext2
real    2m7,787s
user    1m16,501s
sys     0m51,285s
---
10x ext1 ext3
real    2m10,536s
user    1m19,645s
sys     0m50,877s
---
10x ext2 ext3
real    2m5,538s
user    1m14,720s
sys     0m50,811s
---
10x ext2 ext1
real    1m48,453s
user    0m57,699s
sys     0m50,744s
---
10x ext3 ext1
real    1m48,495s
user    0m58,017s
sys     0m50,475s
---
10x ext3 ext2
real    2m2,048s
user    1m10,816s
sys     0m51,218s
---
10x ext3 ext2
real    2m2,034s
user    1m11,322s
sys     0m50,702s
---
10x ext3 ext1
real    1m49,923s
user    0m58,695s
sys     0m51,212s
---
10x ext2 ext1
real    1m49,566s
user    0m58,463s
sys     0m51,097s
---
10x ext2 ext3
real    2m9,148s
user    1m16,823s
sys     0m52,298s
---
10x ext1 ext3
real    2m11,738s
user    1m20,098s
sys     0m51,635s
---
10x ext1 ext2
real    2m8,252s
user    1m16,468s
sys     0m51,782s

---
10x ext1
real    1m40,265s
user    0m49,733s
sys     0m50,523s
---
10x ext2
real    1m37,325s
user    0m45,893s
sys     0m51,419s
---
10x ext3
real    1m35,712s
user    0m43,861s
sys     0m51,843s
---
10x ext3
real    1m35,031s
user    0m43,405s
sys     0m51,616s
---
10x ext2
real    1m36,307s
user    0m44,767s
sys     0m51,537s
---
10x ext1
real    1m39,299s
user    0m47,972s
sys     0m51,318s

---
10x ext4
real    1m35,309s
user    0m43,013s
sys     0m52,290s
---
10x ext4
real    1m33,985s
user    0m42,482s
sys     0m51,503s

处理和整理结果;初步分析和评论

不等同检查单个扩展的测试:

已测试单个扩展 测试 ▲ 实际时间[秒]find
ext4 -name "*.ext4" 9,4647
扩展 -name "*.ext3" 9,53715
扩展2 -name "*.ext2" 9,6816
扩展1 -name "*.ext1" 9,9782

find . -name "*.ext4"只是为了确认当有一个-name测试没有匹配项(因此没有要打印的内容)时,它所花的时间比任何find单个-name测试匹配任何内容的情况都要少。扩展越频繁,打印所有匹配文件的路径名(即使是到)所花的时间就越长/dev/null。看起来不错。

检查两个扩展的测试:

测试扩展(按顺序) 测试 ▲ 实际时间[秒]find 相对速度[%]
A ext2,扩展1 -name "*.ext2" -o -name "*.ext1" 10,90095 100
ext3,扩展1 -name "*.ext3" -o -name "*.ext1" 10,9209 100
C ext3,扩展2 -name "*.ext3" -o -name "*.ext2" 12,2041 100
C 扩展2, ext3 -name "*.ext2" -o -name "*.ext3" 12,7343 95.8
A 扩展1,ext2 -name "*.ext1" -o -name "*.ext2" 12,80195 85.2
扩展1, ext3 -name "*.ext2" -o -name "*.ext3" 13,1137 83.3

同一组中的测试是等效的,我的意思是它们“找到”同一组文件。然后“相对速度”告诉我们相对于同一组中最快的执行速度有多快。我们可以看到,在测试两个扩展的情况下,频率比另一个更高的扩展(粗体)在排在最后时会给我们更快的执行速度。这令人惊讶(为什么?见下文)。

检查三个扩展的测试,都彼此等价:

测试扩展(按顺序) 测试 ▲ 实际时间[秒]find 相对速度[%]
ext3,扩展1,ext2 -name "*.ext3" -o -name "*.ext1" -o -name "*.ext2" 11,16245 100.0
ext2,扩展1, ext3 -name "*.ext2" -o -name "*.ext1" -o -name "*.ext3" 11,56245 96.5
ext3、ext2、扩展1 -name "*.ext3" -o -name "*.ext2" -o -name "*.ext1" 13,06525 85.4
ext2、ext3、扩展1 -name "*.ext2" -o -name "*.ext3" -o -name "*.ext1" 13,86475 80.5
扩展1、ext2、ext3 -name "*.ext1" -o -name "*.ext2" -o -name "*.ext3" 15,23515 73.3
扩展1、ext3、ext2 -name "*.ext1" -o -name "*.ext3" -o -name "*.ext2" 15,64765 71.3

“相对速度”告诉我们相对于最快的执行速度,执行速度有多快。我们可以看到最常用的扩展(粗体)应该排在第二位;下一个最佳选择排在第三位。这又是一个惊喜(为什么?见下文)。


理论以及上述结果令人惊讶的原因

POSIX 规范find状态:

expression -o expression
主元交替;或运算符。如果第一个表达式为真,则不应计算第二个表达式。

我还没有发现 ifA -o B -o C应该被解释为A -o ( B -o C )or ( A -o B ) -o C,但这并不重要。众所周知,这些括号不会改变逻辑结果。在评估时,请考虑这一点:

  • 在两种情况下都A首先进行评估。
    • 如果为真,则它会抑制对(第一种情况)A的评估,或者(第二种情况)它会抑制对的评估,然后为真,因此它会抑制对的评估。B -o CB( A -o B )C
    • 如果A为假,那么在两种情况下B都是下一个要评估的情况。
      • 如果B为真,则它会抑制对(第一种情况)的评估C,或者(第二种情况)( A -o B )为真,因此它会抑制对的评估C
      • 如果B为假,则在两种情况下C都会进行评估。

这意味着评估的顺序是A,,并且第一个评估为真的表达式将抑制对后面的表达式的评估BC

这可以推广到A -o B -o C -o …

为了加快速度A -o B -o …,我们希望尽早获得 true,因此跳过尽可能多的后续表达式(即不进行评估)。就您的问题而言,理论上-name "*.ext1" -o -name "*.ext2" -o -name "*.ext3"应该是最快的,因为-name "*.ext1"最有可能给我们 true,而-name "*.ext3"最有可能给我们 true。

然而,我对 GNU 的测试find并不认同这一点。这就是我称之为令人惊讶的原因。


实践以及 GNUfind真正做的事情

如果你研究GNU手册find,你会发现它会尝试自行节省你的时间:

在某些优化级别,find重新排序测试以加快执行速度,同时保留整体效果;也就是说,具有副作用的谓词不会相对于彼此重新排序。

因此,该工具并不严格遵循 POSIX,通常它会重新排序测试以获得等效的“整体效果”,以期加快速度。据我所知,目前无法完全关闭此功能。

对于我们测试的两个或三个扩展,我们能够判断哪个扩展最好在哪个扩展之前进行测试,因为我们提前知道(或大致知道,或怀疑)分布情况。find无法知道这一点,因此对每个扩展一视同仁-name。不幸的是,即便如此(至少在我当前的 GNU 中如此find;请参阅下面的“测试平台”),它的优化引擎实际上会重新排序这些测试,并且没有选项使其“稳定”(例如稳定排序)。

该工具可以告诉我们新的顺序:

( find -D opt /dev/null -name "*.ext1" -o -name "*.ext2" >/dev/null ) 2>&1 | tail -n 2

给出:

Optimized command line:
 ( -name *.ext2 [est success rate 0,8] -o [est success rate 1] -name *.ext1 [est success rate 0,8]  ) -a [est success rate 1] -print [est success rate 1]

如您所见,两个-name测试互换了位置。这就是为什么我的测试使用了两个扩展,但最后的结果却出人意料地好-name "*.ext1"。我不太确定 GNU 的这种行为是否find具有确定性。

对于三个扩展,我向 GNU 进行find如下查询:

( find -D opt /dev/null -name "*.ext1" -o -name "*.ext2" -o -name "*.ext3" >/dev/null ) 2>&1 | tail -n 2

我得到:

Optimized command line:
 (  ( -name *.ext2 [est success rate 0,8] -o [est success rate 1] -name *.ext3 [est success rate 0,8]  ) -o [est success rate 1] -name *.ext1 [est success rate 0,8]  ) -a [est success rate 1] -print [est success rate 1]

所以实际顺序是 2、3、1。这就是为什么我获得了最快的执行速度-name "*.ext3" -o -name "*.ext1" -o -name "*.ext2";在这种情况下,我的 GNUfind重新排序了测试并获得了最优顺序。另一方面,当我输入最优顺序时,该工具将其更改为次优顺序。


结论

如果您find完全符合 POSIX 标准,那么-name "*.ext1" -o -name "*.ext2" -o -name "*.ext3"应该会为您提供最快的执行速度。

也许您的命令find行是(类似)GNU find,它会悄悄地改变顺序。一般来说您无法知道。具体来说,对于 GNU,find您可以使用它-D opt并找出答案。一旦您找到了答案,您就可以重建命令行,因此在find对测试进行打乱后,最优顺序就会出现。


但是这值得吗?

在我的测试中,我处理了 25,000,000 个常规文件。在最坏的情况下,我损失的时间不到 5 秒(15.6 秒 - 11.2 秒)。现在让我们估算一下:

  • 如果扩展的分布不太均匀,差异可能会更大;但不会任意变大。如果我的测试*.ext4需要 9.5 秒,则以任何顺序测试任何 3 个扩展都不应超过 30 秒;因此,即使最佳顺序根本不需要时间(您希望!),我最多也会损失 30 秒。
  • 我的 CPU 速度非常快,在较慢的硬件上,所有操作都会花费更多时间,我也会损失更多。
  • 但是您提到“100,000 个文件”,这个数字要少两个数量级。
  • 无论测试顺序如何,使用 HDD 或 SSD 代替 RAM 都会增加大致相同的“惩罚” -name

毕竟,我们谈论的似乎是十分之一秒,也许要节省几秒钟。查询 GNUfind和重建命令行需要更多时间。甚至想知道哪个扩展比其他扩展更频繁也可能需要更多时间。

除非你只创建一个命令,但要运行很多次,否则以这种方式进行优化是不值得的。GNU 内部的优化find可能有意义,因为它们花费的时间比它们可能节省的时间要少。问题所涉及的优化需要更多时间。


测试平台

  • Ubuntu 23.04
  • 内核 6.2.0-31-通用
  • find来自 GNU findutils 4.9.0

相关内容