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函数也不是免费的，因为它计算所提供密钥的哈希值。由于您使用的是多态哈希表实现，因此使用了泛型（在C中实现）哈希函数。这些都会对Fibonacci函数的默认有效载荷产生一些开销，这只是三个算术运算（即20x3 = 60算术运算的开销）。

如果我们将使用functorial接口来提供更有效的散列函数，我们将把开销减少到接近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）进行比较，我们将获得以下数字（以ms为单位，在我的2Ghz机器上，对于n = 32）

fib1: 53.3791
fib2: 18.1501

这给了我们一个x3的开销（在Fibonacci内核本身之上的6个算术运算），它或多或少地对应于模运算（两个算术运算）的开销以及三个额外的调用（查找本身，我们的hash）功能和Array.length功能。

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