ocaml - Hashtbl.find 对性能的影响有多大？

Question

当我使用 Hashtbl.find 测量执行时间时，程序比不使用它时慢 16 倍。这是为什么？

请注意，无论是否有查找表(Map 或 Object)，Node 中的等效代码都不会显示出太大差异(仅慢 3 倍)

OCaml 代码:

let fib =
  let table  = Hashtbl.create 1000 in
  let rec f n =
    try Hashtbl.find table n 
    with Not_found -> (
      match n with
      | 0 -> 0
      | 1 -> 1
      | n ->
          let r = f (n - 1) + f (n - 2) in
          (* Hashtbl.add table n r ; *)
          r 
    )
  in
  f

Hashtbl.add 是有意注释的，我只是对 Hashtable find 的性能成本感兴趣。

Answer 1

即使应用于空哈希表，Hashtbl.find 函数也不是免费的，因为它计算所提供 key 的哈希值。由于您使用的是多态哈希表实现，因此使用通用(用 C 实现)哈希函数。这些都会对斐波那契函数的默认有效负载产生一些开销，斐波那契函数只有三个算术运算(即 20x3=60 次算术运算的开销)。

如果我们使用 functorial 接口(interface)来提供更高效的哈希函数，我们将把开销减少到接近 x3:

module Table = Hashtbl.Make(struct
    type t = int
    let equal : int -> int -> bool = fun x y -> x = y [@@inline]
    let hash x = x [@@inline]
  end)

let table  = Table.create 127

let fib1 x =
  let rec f n = match n with
    | 0 -> 0
    | 1 -> 1
    | n -> match Table.find_opt table n with
      | Some x -> x
      | None ->
        let r = f (n - 1) + f (n - 2) in
        (* Hashtbl.add table n r ; *)
        r in
  f x

请注意，我还从使用异常切换到选项类型。在递归函数内部设置异常处理程序意味着每次递归调用都会产生额外的开销。基本上，try 语句具有运行时成本。

如果我们比较使用哈希表 (fib1) 和不使用 (fib2) 的实现的运行时间，我们将得到以下数字(以毫秒为单位，在我的2Ghz 机器，n=32)

fib1: 53.3791
fib2: 18.1501

这给我们带来了 x3 的开销(斐波那契内核本身之上的 6 个算术运算)，这或多或少对应于模运算(两个算术运算)以及三个额外调用(查找本身)的开销、我们的 hash 函数和 Array.length 函数。

您还可以尝试 Janestreet Core 库提供的哈希表实现，通常效率更高。