将函数声明为内联可以避免闭包吗？

Question

我正在阅读一篇博客文章：

http://flyingfrogblog.blogspot.com/2009/07/ocaml-vs-f-burrows-wheeler.html

这是一个简单的Burrow Wheeler压缩算法实现：

# compare two strings str[i..end,0..i-1] and str[j..end,0..j-1]
let cmp (str: _ array) i j =
  let rec cmp i j =
    if i=str.Length then 1 else
      if j=str.Length then -1 else
        let c = compare str.[i] str.[j] in
        if c<>0 then c else
          cmp (i+1) (j+1)
  cmp i j
# sort n strings
let bwt (str: byte array) =
  let n = str.Length
  let a = Array.init n (fun i -> i)
  Array.sortInPlaceWith (cmp str) a
  Array.init n (fun i -> str.[(a.[i] + n - 1) % n])

这个实现看起来相当高效，但实际上很慢，因为排序 Array.sortInPlaceWith (cmp str) a 使用一个闭包函数 (cmp str)，并且调用它太多次（平均 O(n log n)）！

通过使排序算法和比较函数都内联，速度更快。

我的问题是，内联函数是否意味着看似闭包的调用不再是闭包了？

我还在思考的另一件事是 C 中的函数指针。当我们使用 qsort 时：

void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );

我们需要传递比较函数的指针。在C语言中，速度似乎不会太慢。

谢谢！

- Yin Zhu

Answer 1

我们需要传递一个比较函数的指针。在C语言中，速度似乎不会太慢。

但如果与C++实现的std::sort进行比较，则速度会变慢。

你可以将C++版本视为上面提到的内联代码。通过使用模板，您无需运行时间接调用函数指针，而是编译器可以直接在编译时插入和优化给定的比较谓词。

对于您上述的F#代码，第一种实现将需要编译器生成一个闭包对象，在运行时通过间接调用来调用它，而内联版本不需要间接调用，因为它的实现在编译时已知。（但由于.NET的JIT编译器甚至可以在运行时执行这样的优化，我从未想过差异会那么大）

- Dario

---

谢谢。我在qsort和std::sort方面有相当丰富的经验。sort更快，但只是稍微快一点。Jon Harrop说他的内联版本大约快了100倍。也许那是旧版F#编译器，它仍在不断发展。 - Yin Zhu