FSharp работает мой алгоритм медленнее, чем Python
Несколько лет назад я решил проблему с помощью динамического программирования:
https://www.thanassis.space/fillupDVD.html
Решение было написано на Python.
В рамках расширения своих горизонтов я недавно начал изучать OCaml/F#. Что может быть лучше для тестирования воды, чем сделать прямой перенос императивного кода, который я написал на Python, на F# - и начать с этого, шаг за шагом переходя к функциональному программному решению.
Результаты этого первого прямого порта... сбивают с толку:
Под Питоном:
bash$ time python fitToSize.py
....
real 0m1.482s
user 0m1.413s
sys 0m0.067s
Под FSharp:
bash$ time mono ./fitToSize.exe
....
real 0m2.235s
user 0m2.427s
sys 0m0.063s
(в случае, если вы заметили "моно" выше: я также тестировал под Windows, с Visual Studio - та же скорость).
Я... озадачен, если не сказать больше. Python выполняет код быстрее, чем F#? Скомпилированный двоичный файл, использующий среду выполнения.NET, запускает МЕДЛЕННО, чем интерпретируемый код Python?!?!
Я знаю о стоимости запуска виртуальных машин (в данном случае моно) и о том, как JIT улучшают работу с такими языками, как Python, но все же... Я ожидал ускорения, а не замедления!
Возможно, я сделал что-то не так?
Я загрузил код здесь:
https://www.thanassis.space/fsharp.slower.than.python.tar.gz
Обратите внимание, что код F# является более или менее прямым, построчным переводом кода Python.
PS Конечно, есть и другие преимущества, например, безопасность статического типа, предлагаемая F#, но если результирующая скорость императивного алгоритма хуже при F# ... Я разочарован, если не сказать больше.
РЕДАКТИРОВАТЬ: Прямой доступ, как требуется в комментариях:
код Python: https://gist.github.com/950697
код FSharp: https://gist.github.com/950699
3 ответа
Доктор Джон Харроп, с которым я связался по электронной почте, объяснил, что происходит:
Проблема в том, что программа была оптимизирована для Python. Конечно, это часто встречается, когда программист лучше знаком с одним языком, чем с другим. Вам просто нужно выучить другой набор правил, определяющих, как следует оптимизировать программы на F#... Несколько вещей бросились в глаза, например, использование цикла "for i in 1..n do" вместо "for" для i Цикл = от 1 до n do (который в общем быстрее, но не имеет существенного значения), многократно выполняющий List.mapi для списка, чтобы имитировать индекс массива (который без необходимости распределял промежуточные списки) и использование F# TryGetValue для Dictionary, который выделяет излишне (.NET TryGetValue, который принимает ссылку, быстрее в целом, но не так много здесь)
... но настоящей проблемой-убийцей оказалось использование хеш-таблицы для реализации плотной 2D-матрицы. Использование хеш-таблицы является идеальным в Python, потому что его реализация хеш-таблицы была чрезвычайно хорошо оптимизирована (о чем свидетельствует тот факт, что ваш код Python работает так же быстро, как F#, скомпилированный с нативным кодом!), Но массивы являются гораздо лучшим способом представления плотных матрицы, особенно если вы хотите значение по умолчанию ноль.
Самое смешное, что когда я впервые кодировал этот алгоритм, я использовал таблицу - для ясности я изменил реализацию на словарь (избегание проверок границ массива сделало код проще - и намного легче рассуждать).
Джон преобразовал мой код (обратно:-)) в версию массива, и он работает со скоростью 100x.
Мораль истории:
- Словарь F# нуждается в работе... при использовании кортежей в качестве ключей скомпилированный F# работает медленнее, чем интерпретируемые хэш-таблицы Python!
- Очевидно, но повторение не повредит: более чистый код иногда означает... намного более медленный код.
Спасибо, Джон - высоко ценится.
РЕДАКТИРОВАТЬ: тот факт, что замена Dictionary на Array делает F#, наконец, работающим на скоростях, ожидаемых для запуска скомпилированного языка, не отменяет необходимости исправления скорости Dictionary (я надеюсь, что F# люди из MS читают это). Другие алгоритмы зависят от словарей / хэшей и не могут быть легко переключены на использование массивов; заставлять программы страдать от "скорости интерпретатора" всякий раз, когда кто-то использует словарь, возможно, является ошибкой. Если, как некоторые говорили в комментариях, проблема не в F#, а в.NET Dictionary, то я бы сказал, что это... ошибка в.NET!
РЕДАКТИРОВАТЬ 2: Самое ясное решение, которое не требует алгоритма для переключения на массивы (некоторые алгоритмы просто не поддаются этому), это изменить это:
let optimalResults = new Dictionary<_,_>()
в это:
let optimalResults = new Dictionary<_,_>(HashIdentity.Structural)
Это изменение заставляет код F# работать в 2,7 раза быстрее, и, наконец, превосходит Python (в 1,6 раза быстрее). Странно то, что кортежи по умолчанию используют структурное сравнение, поэтому в принципе сравнения словаря по ключам одинаковы (со структурой или без нее). Доктор Харроп теоретизирует, что разница в скорости может быть связана с виртуальной диспетчеризацией: "AFAIK,.NET мало что делает для оптимизации виртуальной диспетчеризации, а стоимость виртуальной диспетчеризации чрезвычайно высока на современном оборудовании, потому что это" вычисляемый переход ", который запускает программу противостоит непредсказуемому местоположению и, следовательно, подрывает логику прогнозирования ветвлений и почти наверняка вызовет сброс и перезагрузку всего конвейера ЦП ".
Говоря простым языком, и как предложил Дон Сайм ( посмотрите на 3 нижних ответа), "будьте недвусмысленны в отношении использования структурного хеширования при использовании ссылочных ключей в сочетании с коллекциями.NET". (Доктор Харроп в комментариях ниже также говорит, что мы всегда должны использовать структурные сравнения при использовании коллекций.NET).
Уважаемая команда F# в MS, если есть способ автоматически это исправить, пожалуйста.
Как отметил Джон Харроп, просто создавая словари, используя Dictionary(HashIdentity.Structural) дает значительное улучшение производительности (в 3 раза на моем компьютере). Это почти наверняка минимально инвазивное изменение, которое вам нужно внести, чтобы получить лучшую производительность, чем в Python, и оно делает ваш код идиоматическим (в отличие от замены кортежей структурами и т. Д.) И параллельным реализации Python.
Изменить: я был неправ, это не вопрос типа значения против ссылочного типа. Проблема производительности была связана с хэш-функцией, как объяснено в других комментариях. Я держу свой ответ здесь, потому что есть интересная дискуссия. Мой код частично исправил проблему производительности, но это не чистое и рекомендуемое решение.
-
На моем компьютере я сделал ваш пример в два раза быстрее, заменив кортеж структурой. Это означает, что эквивалентный код F# должен работать быстрее, чем ваш код Python. Я не согласен с комментариями о том, что хеш-таблицы.NET работают медленно, я думаю, что нет существенной разницы с реализациями на Python или других языках. Кроме того, я не согласен с тем, что "Вы не можете перевести код 1-к-1, ожидайте, что он будет быстрее": код F#, как правило, будет быстрее, чем Python, для большинства задач (статическая типизация очень полезна для компилятора). В вашем примере большая часть времени уходит на поиск хеш-таблиц, поэтому справедливо представить, что оба языка должны быть почти одинаково быстрыми.
Я думаю, что проблема производительности связана с коллекцией gabage (но я не проверял с профилировщиком). Причина, по которой использование кортежей здесь может быть медленнее, чем структур, обсуждалась в вопросе SO ( Почему новый тип кортежа в.Net 4.0 является ссылочным типом (классом), а не типом значения (структурой)) и страницей MSDN ( сборка кортежи):
Если они являются ссылочными типами, это означает, что может быть много мусора, если вы изменяете элементы в кортеже в узком цикле. [...] Кортежи F# были ссылочными типами, но у команды сложилось впечатление, что они могут добиться улучшения производительности, если вместо них два, а может и три, кортежа элементов будут типами значений. Некоторые команды, которые создали внутренние кортежи, использовали значения вместо ссылочных типов, потому что их сценарии были очень чувствительны к созданию большого количества управляемых объектов.
Конечно, как сказал Джон в другом комментарии, очевидная оптимизация в вашем примере - заменить хеш-таблицы массивами. Массивы, очевидно, намного быстрее (целочисленный индекс, без хеширования, без обработки коллизий, без перераспределения, более компактный), но это очень специфично для вашей проблемы и не объясняет разницу в производительности с Python (насколько я знаю, Код Python использует хеш-таблицы, а не массивы).
Чтобы воспроизвести мое ускорение на 50%, вот полный код: http://pastebin.com/nbYrEi5d
Короче говоря, я заменил кортеж на этот тип:
type Tup = {x: int; y: int}
Кроме того, это похоже на деталь, но вы должны переместить List.mapi (fun i x -> (i,x)) fileSizes из замкнутой петли. Я верю питону enumerate фактически не распределяет список (поэтому справедливо распределять список только один раз в F#, или использовать Seq модуль или использовать изменяемый счетчик).
Хм... если хеш-таблица является основным узким местом, то это, собственно, сама хеш-функция. Я не смотрел на конкретную хеш-функцию, но для одной из наиболее распространенных хеш-функций, а именно
((a * x + b) % p) % q
Операция модуля% очень медленная, если p и q имеют форму 2^k - 1, мы можем выполнить модуль с операциями and, add и shift.
Универсальная хеш-функция Дитцфельбингера h_a: [2^w] -> [2^l]
нижняя граница (((a * x) % 2^w)/2^(wl))
Где - случайное нечетное начальное число w-бита.
Его можно вычислить как (a*x) >> (wl), что на величину скорости выше, чем у первой хеш-функции. Мне пришлось реализовать хеш-таблицу со связанным списком для обработки столкновений. На внедрение и тестирование потребовалось 10 минут, нам пришлось протестировать его с обеими функциями и проанализировать разницу в скорости. Вторая хеш-функция имела, насколько я помню, примерно в 4-10 раз прирост скорости в зависимости от размера таблицы. Но здесь нужно усвоить, что если узким местом ваших программ является поиск по хеш-таблице, хеш-функция тоже должна быть быстрой.