Производительность исключений OCaml

Я часто читал, что исключения несколько медленные, и их следует избегать, если производительность является проблемой (например, в Java, F # и т.д.). Это относится к общим функциям OCaml, таким как Hashtbl.find, которые возвращают исключения для элементов, которые не найдены?

В частности, если я хочу, чтобы мое приложение было эффективным, я должен всегда проверять членство элемента, используя, например, Hashtable.mem перед вызовом Hashtbl.find? Или дополнительное сравнение функции mem отрицательно скажется на производительности?

Ответ 1

Обработка исключений OCaml делает чрезмерное повышение и улавливание исключений - см. этот поток SO для внутренних подробностей о том, как это реализовано. Я не позаботился о том, чтобы точно оценить его, но мое случайное предположение было бы в том, что оно находится в непосредственной близости от вызова косвенной функции.

Известно, что исключения OCaml значительно быстрее, по сравнению с остальной частью языка, чем исключения F #, например, - это привело к возникновению проблемы с производительностью для переноса их кода с OCaml на F #. В OCaml исключения не вызывают проблем с производительностью.

Вызов Hashtbl.mem до Hashtbl.find скорее всего будет медленнее, чем поиск исключения. Идиоматический стиль имеет тенденцию быть try Hashtbl.find .. with Not_found -> ....

Тем не менее, в сообществе OCaml есть разумное движение, чтобы использовать более явный стиль обработки ошибок, используя option типы, а не исключения. Обоснование не основано на характеристиках, а на том, что контролер типа останавливает вас от забывания, чтобы справиться с ситуацией с ошибкой. Я бы предпочел, чтобы при разработке нового API. При использовании сторонней функции, которая генерирует исключения, немедленно удалите все возможные исключения; иначе это запах дизайна в целом и должен быть очень оправданным.

Из-за их удобства исключения OCaml также часто используются в качестве чистого механизма управления потоком (и не сигнализируют о редком случае отказа). Вы столкнетесь с кодом, например:

try
  for i = 0 to .... do
    if .. then raise Exit
  done; false
with Exit -> true

Наконец, я чувствую, что вы можете плохо относиться к вариантам реализации. Задавать общие микро-вопросы о выступлениях, как правило, не так. Сначала подумайте о правильности и удобочитаемости. Вопросы эффективности, как правило, должны появляться позже, и только в ситуации, когда это измеримо/возможно.

Ответ 2

Чтобы сначала ответить на конкретный вопрос для Hashtbl.mem до Hashtbl.find: Не делайте этого, поскольку проверка наличия элемента в таблице должна быть не дважды; в то время как для обеих стратегий стоимость будет O (1), при вызове Hashtbl.mem сначала будет вычисляться хэш-значение и поиск дважды, что может занять больше времени, чем выбор исключения.

В качестве общего совета создайте только функции, которые генерируют исключения, если вероятность исключения является низкой. Исключения не учитываются для системы типов, поэтому более надежные реализации будут иметь возвращаемое значение 'a option вместо 'a плюс возможное исключение. В основной библиотеке ocaml используется суффикс _exn, чтобы ясно показать, что функция может вызывать исключение, но обычно предпочитает не исключающие бросание.

Итак, для хэш-таблицы вы должны (в идеальном мире) иметь две функции:

Hashtbl.find_exn : 'a t -> key -> 'a (* throws Not_found *)

Hashtbl.find : 'a t -> key -> 'a option

Если есть сомнения, используйте второй. Если это не для чистой скорости, вы можете написать простую оболочку вокруг оригинальной хеш-таблицы:

find_safe h k = try Some (Hashtbl.find h k) with Not_found -> None

Ответ 3

Я часто читал, что исключения несколько медленные, и их следует избегать, если производительность является проблемой (например, в Java, F # и т.д.). Это относится к общим функциям OCaml, таким как Hashtbl.find, которые возвращают исключения для элементов, которые не найдены?

Нет. Фольклор вокруг исключений, являющихся медленными, и для исключительных обстоятельств в основных языках - это бред. Исключения - это просто еще одна конструкция потока управления. Исключения OCaml бывают быстрыми и обычно используются для непредвиденных обстоятельств. Последнее, что я посмотрел (несколько лет назад), было примерно в 6 раз быстрее в OCaml, чем на С++, примерно в 100 раз быстрее, чем Java, и примерно в 600 раз быстрее, чем .NET.

Люди иногда избегают исключений в OCaml не по причинам, связанным с производительностью, а потому, что им нужен явный локальный поток управления, обычно заставляя вызывающего абонента match использовать тип объединения success/failure вместо потенциального распространения нелокальных исключений. Они делают это, чтобы улучшить правильность, что более важно, чем производительность.