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中实现）哈希函数。所有这些都会给斐波那契函数的默认有效载荷带来一些开销，该开销仅是三个算术运算（即，20x3 = 60算术运算的开销）。

如果我们将使用函子接口提供更有效的哈希函数，我们将把开销减少到接近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的开销（在Fibonacci内核本身之上的6个算术运算），它或多或少地对应于模运算（两个算术运算）以及三个额外的调用（find本身，我们的hash函数）的开销。，以及Array.length功能。

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