Насколько Hashtbl.find влияет на производительность?

Question

Когда я измеряю время выполнения с помощью Hashtbl.find, программа работает в 16 раз медленнее, чем без него. Это почему?

Обратите внимание, что эквивалентный код в Node не показывает такой большой разницы с таблицей поиска или без нее (Map или 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.

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), мы получим следующие числа (в мс, на моей машине с частотой 2 ГГц, для n = 32)

fib1: 53.3791
fib2: 18.1501

Это дает нам служебную нагрузку x3 (6 арифметических операций поверх самого ядра Фибоначчи), которая более или менее соответствует служебной информацииоперации по модулю (две арифметические операции), а также три дополнительных вызова (сама находка, наша функция hash и функция Array.length.

Вы также можете попробовать реализацию хеш-таблицы, предоставляемуюБиблиотека Janestreet Core, которая обычно более эффективна.