嵌套函数是否有效？

Question

在Scala或Lua等编程语言中,我们可以定义嵌套函数,如

function factorial(n)
  function _fac(n, acc)
    if n == 0 then
      return acc
    else
      return _fac(n-1, acc * n)
    end
  end

  return _fac(n, 1)
end

这种方法是否会导致效率低下,因为每次调用外部函数时都会定义或创建嵌套函数实例？

Answer 1

这种方法是否会导致效率低下,因为每次调用外部函数时都会定义或创建嵌套函数实例？

效率是一个广泛而广泛的话题.我假设"低效"你的意思是"每次递归调用方法都有开销"？

我只能代表Scala发言,特别是针对JVM的风格,因为其他风格的行为可能不同.

我们可以根据你的真实含义将这个问题分成两部分.

Scala中的嵌套(局部范围)方法是一个词法范围功能,这意味着它们为您提供了外部方法值的可访问性,但是一旦我们发出字节码,它们就在类级别定义,就像普通的java方法一样.

为了完整性,请确保Scala还具有函数值,这些函数值是一等公民,这意味着您可以将它们传递给其他函数,然后这些将产生分配开销,因为它们是使用类实现的.

可以用尾递归的方式编写因子,就像你在你的例子中写的那样.Scala编译器足够智能,它会注意到你的方法是尾递归并将其转换为迭代循环,避免了每次迭代的方法调用.如果可能的话,它还可以尝试内联该factorial方法,避免额外的堆栈帧分配的开销.

例如,请考虑Scala中的以下因子实现:

def factorial(num: Int): Int = {
  @tailrec
  def fact(num: Int, acc: Int): Int = num match {
    case 0 => acc
    case n => fact(n - 1, acc * n)
  }

  fact(num, 1)
}

从表面上看,我们有一个递归方法.让我们看看JVM字节码的样子:

private final int fact$1(int, int);
  Code:
   0: iload_1
   1: istore        4
   3: iload         4
   5: tableswitch   { // 0 to 0
                 0: 24
           default: 28
      }
  24: iload_2
  25: goto          41
  28: iload         4
  30: iconst_1
  31: isub
  32: iload_2
  33: iload         4
  35: imul
  36: istore_2
  37: istore_1
  38: goto          0
  41: ireturn

我们在这里看到的是递归变成了一个迭代循环(一个tableswitch +一个跳转指令).

关于方法实例创建,如果我们的方法不是尾递归的,那么JVM运行时需要为每次调用解释它,直到C2编译器发现它足以使JIT编译它并为每个方法重用机器代码.之后打电话.

一般来说,我会说这不应该让你担心,除非你已经注意到这个方法是在执行你的热路径并且分析代码导致你问这个问题.

总而言之,效率是一个非常微妙的,用例特定的主题.我认为,如果这是为您的用例选择的最佳选择,我们没有足够的信息告诉您,从您提供的简化示例中.我再说一遍,如果这不是你的探查器出现的东西,不要担心这个.

Answer 2

让我们在Lua中使用/不使用嵌套函数对其进行基准测试.

变体1(每次调用都会创建内部函数对象)

local function factorial1(n)
   local function _fac1(n, acc)
      if n == 0 then
         return acc
      else
         return _fac1(n-1, acc * n)
      end
   end

   return _fac1(n, 1)
end

变体2(函数不嵌套)

local function _fac2(n, acc)
   if n == 0 then
      return acc
   else
      return _fac2(n-1, acc * n)
   end
end

local function factorial2(n)
   return _fac2(n, 1)
end

基准测试代码(计算12!10毫秒次并以秒为单位显示使用的CPU时间):

local N = 1e7

local start_time = os.clock()
for j = 1, N do
   factorial1(12)
end
print("CPU time of factorial1 = ", os.clock() - start_time)

local start_time = os.clock()
for j = 1, N do
   factorial2(12)
end
print("CPU time of factorial2 = ", os.clock() - start_time)

Lua 5.3的输出(翻译)

CPU time of factorial1 = 8.237
CPU time of factorial2 = 6.074

LuaJIT的输出(JIT编译器)

CPU time of factorial1 = 1.493
CPU time of factorial2 = 0.141

Answer 3

答案取决于当然的语言.

特别是Scala中发生的事情是内部函数被编译为它们位于定义它们的函数范围之外.

通过这种方式,语言只允许您从定义它们的词法范围中调用它们,但实际上并不实际多次实例化该函数.

我们可以通过编译两个变体来轻松地测试它

第一个是您的Lua代码的相当忠实的端口:

class Function1 {

  def factorial(n: Int): Int = {
    def _fac(n: Int, acc: Int): Int =
      if (n == 0)
        acc
      else
        _fac(n-1, acc * n)

    _fac(n, 1)
  }

}

第二个或多或少相同,但尾递归函数的定义超出了以下范围factorial:

class Function2 {

  def factorial(n: Int): Int = _fac(n, 1)

  private final def _fac(n: Int, acc: Int): Int =
    if (n == 0)
      acc
    else
      _fac(n-1, acc * n)

}

我们现在可以编译这两个类,scalac然后用它javap来查看编译器输出:

javap -p Function*.scala

这将产生以下输出

Compiled from "Function1.scala"
public class Function1 {
  public int factorial(int);
  private final int _fac$1(int, int);
  public Function1();
}
Compiled from "Function2.scala"
public class Function2 {
  public int factorial(int);
  private final int _fac(int, int);
  public Function2();
}

我加入了private final关键字,以减少两者之间的差别,但需要注意的主要事情是,在这两种情况下的定义出现在一流水平,具有自动定义为内部函数private,并final与小装饰,以确保没有名字的类(如如果你loop在两个不同的内部定义一个内部函数).

不确定Lua或其他语言,但我可以期望至少大多数编译语言采用类似的方法.