时间戳

首页 > 解决方案 > Hashtbl.find 对性能有多大影响？

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

问题描述

当我测量程序的执行时间Hashtbl.find比没有它时慢 16 倍。这是为什么？

Map请注意，Node 中的等效代码在有或没有查找表（或）的情况下都没有显示出太大的差异Object（仅慢 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。

标签： ocaml

解决方案

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

fib1: 53.3791
fib2: 18.1501

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

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

推荐阅读