10

我仍处于学习 OCaml 的早期阶段，我很想知道从 OCaml 中的通用代码中提取最大性能的最佳方法是什么。

作为一个小实验，我编写了两个多态函数：一个在 C++ 中，另一个在 OCaml 中，用于查找给定数组中的最大元素。

我观察到的是，虽然在 C++ 中你不会为这种抽象付出任何代价，但在 OCaml 中的代价是性能下降了一个数量级。顺便说一句，我快速编写的 C++ 解决方案比 OCaml 更通用，但我主要将其归咎于我对这门语言缺乏经验。

我的问题如下：如何在 OCaml 中编写和使用多态函数而不付出我刚刚观察到的巨大性能损失？

对于这个特定问题，我观察到的另一件事是，我在 OCaml 中的函数式解决方案比命令式解决方案慢，而 C++ 中的“函数式”解决方案与模拟命令式方法相比没有受到任何惩罚。

C++ 代码g++ -std="c++0x" -O3 -o max_cpp max.cpp使用 gcc-4.6.3 编译，OCaml 代码使用：ocamlopt -o max_ml max.ml使用 ocamlopt 版本 3.12.1。生成的两个可执行文件都是 32 位并在 Ubuntu x64 11.04 上运行

我提交了两个程序的代码。

C++ 代码（当然不完全安全；））

#include <iostream>
#include <vector>
#include <numeric>
template <typename T> T max (T a, T b) {
     return (a>b)? a : b;
}

template <typename I> typename I::value_type find_max (I begin, I end) {
    auto max = *begin;
    for (begin++;begin!=end;begin++)
            if (*begin > max) max = *begin;
    return max;
}

template <typename I> typename I::value_type find_max1(I begin, I end) {
    return std::accumulate(begin, end, *begin, max< typename I::value_type> );
}

int main(int argc, char ** argv) {
    const size_t nElem = atoi(argv[1]);
    const size_t nIter = atoi(argv[2]);
    std::vector<int> intA(nElem);
    std::vector<double> dubA(nElem);
    for (int i=0;i<nIter;i++) {
            auto res1 = find_max(intA.begin(), intA.end());
            auto res2 = find_max(dubA.begin(), dubA.end());
            std::cout << "Max int: " << res1 << " " << "Max dub: " << res2 << std::endl;
    }
}

OCaml 代码

let max a b = if a > b then a else b

(* functional version *)
let find_max vector =
    Array.fold_right max vector vector.(0)

(* imperative version *)
let find_max1 vector =
    let length = Array.length vector in
    let max = ref (vector.(0)) in
    for i=1 to length-1 do
            if vector.(i) > !max then max := vector.(i)
    done; max

let nElems = int_of_string Sys.argv.(1)

let nIter  = int_of_string Sys.argv.(2)

let _ = let intA = Array.make nElems 0 in
    let dubA = Array.make nElems 0.0 in
    for i=1 to nIter do
            let res1 = find_max intA in
            let res2 = find_max dubA in
            print_int !res1;
            print_newline ();
            print_float !res2;
    done

但是，如果我“重载”函数来区分整数和浮点数，那么程序的性能甚至超过我的 C++ 代码的 50%！我想知道为什么。

let find_max_int (vector : int array) =
    let length = Array.length vector in
    let max = ref (vector.(0)) in
    for i=1 to length-1 do
            if vector.(i) > !max then max := vector.(i)
    done; max

let find_max_float (vector : float array) =
    let length = Array.length vector in
    let max = ref (vector.(0)) in
    for i=1 to length-1 do
            if vector.(i) > !max then max := vector.(i)
    done; max

时间安排相当粗略地执行： time ./max_cpp 1000000 100和 time ./max_ml 1000000 100

4

2 回答 2

8

在 OCaml 中，比较运算符(<)是类型的通用函数'a -> 'a -> bool（同样用于相等等）。这意味着它是由运行时系统中的一个特殊原语实现的，该原语可以有效地对任何类型的数据结构进行临时比较。类型检查器能够优化整数和浮点数的单态比较到专门的比较操作，而不是在多态情况下在运行时进行类型检查。如果只测试这个操作，效率的十倍差异并不奇怪。

请注意，为了获得最大的灵活性，您应该抽象find_max. 然而，这会阻止单态优化，因此内联版本仍然会表现得更好。

我认为您的方法（进行微基准测试并希望学习有关真实程序性能的有趣事物）是有缺陷的。您遇到了一个非常具体的 OCaml 性能行为案例，并从那里错误地得出结论，多态函数的性能“很差”。这显然是过早优化的错误结论。为您打算运行的计算编写一个具有实际代表性的示例，然后对这段真实代码的性能进行推理。你从这类微基准测试中学到的东西很少，还有很多不相关的细节。

（然而，C++ 代码专业化方法确实可以生成比 OCaml 编译技术更高效的代码，OCaml 编译技术只为所有类型编译函数的一个版本，但必须做出相应的数据表示妥协；在 OCaml 中可能会有开销与多态性有关。但是，这仅在相当特定的情况下才能观察到，并且您通常可以在代码的小关键部分中进行特定的内联传递。您获得的回报是编译速度更快（无重复）和实际可读的错误消息——就像你可能会在 C++ 中集成概念一样。）

编辑：实际上我说对比较进行抽象会阻止类型导向的优化是错误的。下面的代码虽然仍然不如手动内联版本快，但仍然明显快于使用多态比较的版本：

let find_max1 comp vector =
    let length = Array.length vector in
    let max = ref (vector.(0)) in
    for i=1 to length-1 do
      if comp !max vector.(i) then max := vector.(i)
    done;
    !max

let find_max_int (vector : int array) = find_max1 (fun x y -> x < y) vector
let find_max_float (vector : float array) = find_max1 (fun x y -> x < y) vector
于 2012-12-19T17:42:02.313 回答
2

实际上，您是在比较编译时专用函数与运行时分派的函数。ocaml 方面更合适的代码将使用仿函数，理论上可以将间接调用的数量减少到零，但我想它仍然会受到优化不足的影响。另一个问题是数据表示是统一的，并且在任何情况下都不是针对用户类型专门/内联的。

于 2012-12-20T09:36:05.677 回答