Каковы локальные свойства Haskell?

Современные ЦП оптимизированы таким образом, чтобы доступ и изменение одного и того же места в памяти (временная локальность), а также последовательные места в памяти (пространственная локальность) были чрезвычайно быстрыми.

Теперь, поскольку Haskell является чисто неизменным языком, вы, естественно, не можете перезаписывать существующие блоки памяти, что может сделать такие вещи, как foldl намного медленнее, чем цикл for с непрерывно доступной переменной результата будет в C.

Предоставляет ли Haskell что-либо внутренне, чтобы уменьшить эту потерю производительности? И вообще, каковы его свойства относительно местности?

Ответ 1

Общее правило заключается в том, что для программирования "vanilla" Haskell вы получаете очень мало (если есть) контроль над расположением памяти и локальностью памяти.

Однако существует ряд более продвинутых функций, которые позволяют такой контроль, и библиотеки, которые выставляют дружественные абстракции поверх них. Библиотека vector, вероятно, самая популярная из последних. Эта библиотека предоставляет несколько типов массивов фиксированного размера, два из которых (Data.Vector.Unboxed и Data.Vector.Storable) дать вам местоположение данных, представляя векторы и их содержимое как непрерывные массивы памяти. Data.Vector.Unboxed даже содержит простую автоматическую трансформацию "структуры массивов" - распакованный вектор пар будет представлен как пара нераспознанных векторов, по одному для каждой из парных компонентов.

Другим примером является библиотека JuicyPixels для обработки изображений, которая представляет изображения в памяти как непрерывные растровые изображения. Это фактически заканчивается на Data.Vector.Storable, который использует стандартную установку (Foreign.Storable) для перевода пользовательских типов данных Haskell в и из необработанных байтов.

Но общий шаблон таков: в Haskell, когда вы заинтересованы в локальности памяти, вы определяете, какие данные должны извлечь выгоду из этого и объединить их вместе в пользовательский тип данных, реализация которого была разработана для обеспечения локальности и гарантии производительности, Написание такого типа данных является передовой задачей, но большая часть работы была уже сделана уже многократно (обратите внимание, например, что JuicyPixels в основном просто повторяет vector).

Обратите внимание, что:

vector обеспечивает оптимизацию потока для устранения промежуточных массивов при применении вложенных векторных преобразований. Если вы создаете вектор от 0 до 1 000 000, отфильтруйте четные числа, сопоставьте функцию (^2) над этим и суммируйте элементы результата, ни один массив не будет выделен - библиотека имеет умение переписывать это в цикл аккумулятора от 0 до 1 000 000. Таким образом, foldl вектора не обязательно медленнее, чем цикл for - не может быть никакого массива вообще!
vector также предоставляет изменяемые массивы. В более общем плане, в Haskell вы можете перезаписать существующую память, если вы действительно настаиваете. Это просто (а) не парадигма по умолчанию на языке, и поэтому (б) немного неуклюжий, но абсолютно послушный, если вам просто нужно это в нескольких чувствительных к производительности местах.

Поэтому большую часть времени ответ "Я хочу местность памяти" - "use vector."

Ответ 2

Haskell - чрезвычайно высокоуровневый язык, и вы задаете вопрос о чрезвычайно низкой детализации.

В целом, производительность Haskell, вероятно, похожа на любой собранный мусором язык, такой как Java или С#. В частности, Haskell имеет изменяемые массивы, которые будут иметь производительность, аналогичную любому другому массиву. (Вам могут понадобиться распакованные массивы, чтобы соответствовать производительности C.)

Для чего-то вроде складки, если конечный результат является чем-то вроде целого числа машины, вероятно, заканчивается в регистре процессора на весь период цикла. Таким образом, окончательный машинный код в значительной степени идентичен "переменной с непрерывным доступом в C". (Если результатом является словарь или что-то еще, то, вероятно, нет. Но это то же самое, что и C.)

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

Все эти переговоры велики и все, но если вы действительно хотите знать, насколько быстро работает конкретная программа Haskell, сравните ее. Оказывается, хорошо написанные программы Haskell обычно бывают довольно быстрыми. (Как и большинство скомпилированных языков.)

Добавлено: вы можете попросить GHC вывести частично скомпилированный код в формате Core, который является более низким, чем Haskell, но более высоким, чем машинный код. Это позволяет вам понять, что решил компилятор (в частности, когда материал был встроен, где абстракции удалены и т.д.). Это поможет вам узнать, как выглядит последний код, без необходимости идти полным путем вплоть до машинного кода.