假设在一个文件夹结构中,有扩展名为ext1
、ext2
、的文件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 C
B
( A -o B )
C
- 如果
A
为假,那么在两种情况下B
都是下一个要评估的情况。- 如果
B
为真,则它会抑制对(第一种情况)的评估C
,或者(第二种情况)( A -o B )
为真,因此它会抑制对的评估C
。 - 如果
B
为假,则在两种情况下C
都会进行评估。
- 如果
- 如果为真,则它会抑制对(第一种情况)
这意味着评估的顺序是A
,,并且第一个评估为真的表达式将抑制对后面的表达式的评估B
。C
这可以推广到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