递归函数的性能问题

时间：2008-03-21 来源：剑心通明

性能问题

尽管编写 bash 脚本可以实现递归函数，但是由于先天性的不足，使用 bash 脚本编写的递归函数的性能都比较差，问题的根本在于它的主要流程都是要不断地调用其他程序，这会 fork 出很多进程，从而极大地增加运行时的开销。下面让我们来看一个计算累加和的例子，清单 15 和清单 16 给出了两个实现，它们分别利用全局变量和标准输入输出设备来传递返回值。为了简单起见，我们也不对输入参数进行任何判断。

清单15. 累加和，利用全局变量传递返回值

[root@localhost shell]# cat -n sum1.sh
     1 #!/bin/bash
     2
     3 sum()
     4 {
     5    local i=$1
     6
     7    if [ $i -eq 1 ]
     8    then
     9      rtn=1
    10    else
    11      sum `expr $i - 1`
    12      rtn=`expr $i + $rtn `
    13    fi
    14
    15    return $rtn
    16 }
    17
    18 if [ -z $1 ]
    19 then
    20    echo "Need one parameter."
    21    exit 1
    22 fi
    23
    24 sum $1
    25
    26 echo $rtn

清单16. 累加和，利用标准输入输出设备传递返回值

[root@localhost shell]# cat -n sum2.sh
     1 #!/bin/bash
     2
     3 sum()
     4 {
     5    local i=$1
     6
     7    if [ $i -eq 1 ]
     8    then
     9      echo 1
    10    else
    11      local j=`expr $i - 1`
    12      local k=`sum $j`
    13      echo `expr $i + $k `
    14    fi
    15 }
    16
    17 if [ -z $1 ]
    18 then
    19    echo "Need one parameter."
    20    exit 1
    21 fi
    22
    23 rtn=`sum $1`
    24 echo $rtn

下面让我们来测试一下这两个实现的性能会有多大的差距：

清单17. 利用全局变量和标准输入输出设备传递返回值的性能比较

[root@localhost shell]# cat -n run.sh
     1 #!/bin/bash
     2
     3 if [ $# -lt 2 ]
     4 then
     5    echo "Usage: $0 [number] [executable list]"
     6    exit 1
     7 fi
     8
     9 NUM=$1
    10 shift
    11
    12 for i in $*
    13 do
    14    echo "Running command: $i $NUM"
    15    time ./$i $NUM
    16
    17    sleep 5
    18    echo
    19 done
[root@localhost shell]# ./run.sh 500 sum1.sh sum2.sh
Running command: sum1.sh 500
125250

real    0m8.336s
user    0m0.532s
sys     0m7.772s

Running command: sum2.sh 500
125250

real    0m20.775s
user    0m1.316s
sys     0m17.741s

在计算 1 到 500 的累加和时，利用标准输入输出设备传递返回值的方法速度要比利用全局变量慢 1 倍以上。随着迭代次数的增加，二者的差距也会越来越大，主要原因标准输入输出设备都是字符设备，从中读写数据耗时会很长；而全局变量则是在内存中进行操作的，速度会明显快很多。

为了提高 shell 脚本的性能，在编写 shell 脚本时，应该尽量多使用 shell 的内嵌命令，而不能过多地调用外部脚本或命令，因为调用内嵌命令时不会 fork 新的进程，而是在当前 shell 环境中直接执行这些命令，这样可以减少很多系统开销。以计算表达式的值为例，前面的例子我们都是通过调用 expr 来对表达式进行求值的，但是 bash 中提供了一些内嵌的计算表达式手段，例如 ((i = $j + $k)) 与 i=`expr $j + $k` 的效果就是完全相同的，都是计算变量 j 与 k 的值，并将结果赋值给变量 i，但是前者却节省了一次 fork 新进程以及执行 expr 命令的开销。下面让我们对清单 15 中的脚本进行一下优化，如清单 18 所示。

清单18. 优化后的计算累加和的脚本

[root@localhost shell]# cat -n sum3.sh
     1 #!/bin/bash
     2
     3 sum()
     4 {
     5    local i=$1
     6
     7    if [ $i -eq 1 ]
     8    then
     9      rtn=1
    10    else
    11      sum $(($i - 1))
    12      ((rtn = rtn + i))
    13    fi
    14
    15    return $rtn
    16 }
    17
    18 sum $1
    19
    20 echo $rtn

现在让我们来比较一下优化前后的性能差距，如清单 19 所示。

清单19. 优化前后的性能对比

[root@localhost shell]# ./run.sh 2000 sum1.sh sum3.sh
Running command: sum1.sh 2000
2001000

real    1m19.378s
user    0m15.877s
sys     1m3.472s

Running command: sum3.sh 2000
2001000

real    0m12.202s
user    0m10.949s
sys     0m1.220s

可以看出，在迭代 2000 次时，优化后的脚本速度要比优化前快 5 倍以上。但是无论如何，使用 shell 脚本编写的递归函数的执行效率都不高，c 语言的实现与其相比，快了可能都不止一个数量级，详细数据请参看清单 20。

清单20. c 语言与 bash 脚本实现递归函数的对比

[root@localhost shell]# cat -n sum.c
     1 #include <stdlib.h>
     2 #include <stdio.h>
     3
     4 int sum(int i)
     5 {
     6    if (i == 1)
     7      return 1;
     8    else
     9      return i + sum(i-1);
    10 }
    11
    12 int main(int argc, char **argv[])
    13 {
    14    printf("%d\n", sum(atoi((char *)argv[1])));
    15 }
[root@localhost shell]# gcc -O2 -o sum sum.c

[root@localhost shell]# ./run.sh 3000 sum sum3.sh
Running command: sum 3000
4501500

real    0m0.004s
user    0m0.000s
sys     0m0.004s

Running command: sum3.sh 3000
4501500

real    0m31.182s
user    0m28.998s
sys     0m2.004s

因此，如果编写对性能要求很高的递归程序，还是选择其他语言实现好了，这并不是 shell 的强项。