递归函数的性能问题

性能问题

尽管编写 脚本可以实现函数，但是由于先天性的不足，使用 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 的内嵌命令，而不能过多地调用外部脚本或命令，因为调用内嵌命令时不会 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
     2  #include
     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 的强项。