.net - 使函数内联避免关闭？

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 的情况下，速度并不差。

谢谢!

Answer 1

we need to pass in the pointer of a comparison function. It seems that in C's case, the speed does not suck much.

如果将其与 std::sort 的 C++ 实现进行比较，它确实如此.

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

对于上面的 F# 代码，第一个实现将要求编译器生成一个在运行时通过间接调用的闭包对象，而内联版本不需要间接，因为它的实现在编译时是已知的。 (但由于 .NET 的 JIT 编译器甚至可以在运行时进行此类优化，我从没想过差异会这么大)