LINUX.ORG.RU

[Haskell] Почему такая разница в производительности?

 


1

4

Доброго времени суток.

Задача простая, есть массив чисел. Необходимо посчитать сколько значений в попало в заданные интервалы. Два решения (оба скучные и слишком ручные):

let r1 = 580
let r2 = 1000
let r3 = 1500
let r4 = 5500
-- (1)
print $ length $ filter (\x -> x < r1) result
print $ length $ filter (\x -> r1 < x && x < r2) result
print $ length $ filter (\x -> r2 < x && x < r3) result
print $ length $ filter (\x -> r3 < x && x < r4) result
print $ length $ filter (\x -> r4 < x) result
-- (2)
print $ show $ foldl (\(a,b,c,d,e) x 
                      -> case x of
                          x | x < r1 -> (a+1,b,c,d,e)
                          x | x < r2 -> (a,b+1,c,d,e)
                          x | x < r3 -> (a,b,c+1,d,e)
                          x | x < r4 -> (a,b,c,d+1,e)
                          otherwise  -> (a,b,c,d,e+1)
                     ) (0, 0, 0, 0, 0) result
Первый вариант, как и ожидается, считается примерно мгновение (хотя второй вариант кажется более оптимальным, так как исходный список проходится 1 раз, а не 10). Второй же сперва пыхтит, а потом падает в переполнение стека.

В генерируемый код не смотрел.

Ответ на: комментарий от exlevan

Плюсмного. И я бы ещё посмотрел на то, что там с ленивостью (+); возможно, имеет смысл заменить a+1 на (+ 1) $! a.

Miguel ★★★★★
()

Кстати, первый вариант проходит список не десять раз, а только пять. Вызов length скорее всего фьюзится с filter, промежуточный список не строится вообще.

Miguel ★★★★★
()

Это тот самый случай, когда накладываются два неприятных момента. Во-первых, a, b, c, d и e складываются в кучу thunk'ов, потому что не вычисляются во время прохода foldl'я, от этого спасет элегантное (+ 1) $! a от Мигеля. Но есть и второй момент, анализатор строгости не справляется с выводом строгости x (по крайней мере в ghc 7.0.4), поэтому его тоже надо бы указать как-нибудь.

Я бы предпочел убить двух зайцес с помощью BangPatterns.

Вместо

\(a,b,c,d,e) x ->
накалякать
\(!a,!b,!c,!d,!e) !x ->
и вуаля.

anonymous
()
Ответ на: комментарий от vasaka

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

anonymous
()
Ответ на: комментарий от vasaka

чтобы код работал

Код в OP уже работает. «Сначала сделай так, чтобы работало, потом делай, чтобы работало быстро». Настройка строгости (strict - bang patterns, seq, ($!)) это всё на тему «чтобы работало быстро» (более подробно про это есть в одной известной книжке). Профайлингом ведь тоже иногда заниматься нужно.

quasimoto ★★★★
()
Ответ на: комментарий от vasaka

В топике написано что не работал, а падал в переполнение стека.

Алгоритм может быть вполне рабочий - работать на списке в 10, 10^2, ..., 10^6 элементов, но при этом сильно кушать стек и на списке в 10^7 элементов его исчерпать. Тут можно либо дать больше стека (+RTS -K200M -RTS, но не нужно), либо добавить строгости, как тут. Во втором случае даже не понадобится больше стека и свёртка будет работать быстрее нескольких фильтров, как от неё и ожидается.

Только непонятно, чем такой тюнинг хаскельной программы (чтобы алгоритм не просто работал, но работал на _больших_ массивах данных) отличается от профилирования программ в других языках? Т.е. чему удивляться?

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

> Т.е. чему удивляться?

Тому, что программист, пишуший код, не знает, на каких объёмах входных данных его программа будет работать, а на каких - … нет, не сообщать пользователю о недопустимо большом объёме входных данных, а тупо падать.

непонятно, чем такой тюнинг хаскельной программы (чтобы алгоритм не просто работал, но работал на _больших_ массивах данных) отличается от профилирования программ в других языках?

При профилировании определяют «узкие места» в корректно работающей программе, а не ищут причину, по которой она аварийно завершается на определенном подмножестве входных данных.

Всегда ваш, к.О.

LamerOk ★★★★★
()
Ответ на: комментарий от LamerOk

При профилировании определяют «узкие места» в корректно работающей программе

Корректно работающих программ всегда и везде не бывает - память ограничена, I/O bounded программы могут попадать в стрессовые условия.

Тому, что программист, пишуший код, не знает, на каких объёмах входных данных его программа будет работать

Почему же, он догадывается об этом, а после первого же тестирования получает готовые цифры.

Претензии могут быть только к non-strictness по-умолчанию и отсутствию в GHC optimistic evaluation.

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto
Ответ на: комментарий от exlevan

Optional laziness doesn't quite cut it

Tim Sweeney, кажется, писал, что от хаскеля он бы хотел, чтобы тот был ленивым только по требованию, но строгим по умолчанию.

Аргументы по ссылке не вполне понял. Там ведь про такие конструкции:

{-# LANGUAGE NoMonomorphismRestriction #-}

import Data.List ( foldl' )
import Control.DeepSeq ( ($!!) )

lazy = take 5
strict = foldl' (+) 0

test = strict . lazy
test' xs = strict $! lazy xs
test'' xs = strict $!! lazy xs

values = (test [1 ..], test' [1 ..], test'' [1 ..])

проблем с аппликацией строгих и нестрогих функций в хаскеле вроде бы нет (?).

We currently have no plans to inocrporate the optimistic evaluation branch, due to its significant complexity

SPJ то же самое в рассылке писал:

It was great stuff — and some lazy programs went a lot faster — but it was also jolly complicated when all the details were worked out, and interacted with a lot of other tricky details of the run-time system. In the end we decided it was just too complicated to permanently incorporate in GHC's code base, alas.

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

> Корректно работающих программ всегда и везде не бывает

Про «везде» речь не идёт, в отличие от «всегда». Речь идёт о корректно работающих при соответствии окружения заявленным минимальным требованиям. Слово «всегда» упоминать не надо, программа корретно работающая лишь «иногда» мало кому интересна.

- память ограничена

Какая неожиданность.

, I/O bounded программы могут попадать в стрессовые условия.

И что? С каких это пор стрессовые условия - повод работать криво?

LamerOk ★★★★★
()
Ответ на: комментарий от LamerOk

Да вы просто выдумали, что «о, тут у ребят с хацкелем какие-то проблемы, надо над ними пошутить!». А никаких проблем нет. Если есть - конкретные примеры в студию, мне самому интересно. Чисто теоретически оценка потребления памяти ленивыми программами - не тривиально, но к практике это отношения не имеет.

Речь идёт о корректно работающих при соответствии окружения заявленным минимальным требованиям.

Так чем хаскель в этом отношении отличается от других языков?

И что? С каких это пор стрессовые условия - повод работать криво?

Где вы увидели в этом топике «криво»?

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

Так вот он пример и есть, где на глаз определить сколько программе понадобится памяти, и на каком количестве данных она грохнется не получается.

vasaka ★★★
()
Ответ на: комментарий от vasaka

Так вот он пример

Это пример того, как, бывает, нельзя лениво обмолотить список из порядка 10^7 элементов - слишком много санков складывается в стек. Поэтому надо думать и писать правильно, т.е. выставлять строгость с помощью BangPatterns.

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

> оценка потребления памяти к практике отношения не имеет.

/0

Где вы увидели в этом топике «криво»?

Я еще раз процитирую, на что эта фраза была ответом:

Корректно работающих программ всегда и везде не бывает - память ограничена, I/O bounded программы могут попадать в стрессовые условия.

LamerOk ★★★★★
()
Ответ на: комментарий от anonymous

необходимость так написать и в чем вообще тут причина не следует из описания языка.

такое можно узнать только с опытом, попытавшись решить всплывшую проблему, или спросив у опытного товарища, значит факт не тривиален.

vasaka ★★★
()
Ответ на: комментарий от quasimoto

Почему в нормальных языках код сразу работает быстро, а в хаскеле надо заниматься хаскиартом? Вообще, это общеизвестный факт, что в практичном языке вычисления должны быть энергичными по дефолту, а ленивыми - опционально. просто потому, что энергичность нужна в 99% случаев, а ленивость - в 1% оставшихся.

anonymous
()
Ответ на: комментарий от quasimoto

> Только непонятно, чем такой тюнинг хаскельной программы (чтобы алгоритм не просто работал, но работал на _больших_ массивах данных) отличается от профилирования программ в других языках?

Очевидно, тем, что в других языках все это получается сразу, искаробки. Без тьюнинга и профилирования.

anonymous
()
Ответ на: комментарий от anonymous

>Очевидно, тем, что в других языках все это получается сразу, искаробки. Без тьюнинга и профилирования.

Т.е. в других языках «искаробки» есть ленивость + «хиндли-миллер» + предупреждение аршинными буквами не использовать всё это для больших массивов данных? И даже, если ты тупорылая скотина и не читаешь доки, компилятор тебе вежливо напомнит, что ты делаешь нехорошо?

Боже, я уже в раю? =)

yyk ★★★★★
()
Ответ на: комментарий от yyk

> Т.е. в других языках «искаробки» есть ленивость + «хиндли-миллер»?

Нет, это все искаробки есть в хаскиле. В результате приходится писать (+1) $! 2. В нормальных языках искаробки есть энергичность, безо всяких хиндли-милнеров, так что спокойно пишешь 1+2 и не паришь мозги - все работает быстро и ничего не вылетит, гарантированно.

anonymous
()
Ответ на: комментарий от yyk

>Т.е. в других языках «искаробки» есть ленивость + «хиндли-миллер» + предупреждение аршинными буквами не использовать всё это для больших массивов данных

А на кой эта ленивость, если она на больших массивах данных падает? По идее именно когда данных много как раз и важна ленивость, чтобы лишний раз по данным не ходить.

На малых массивах, подозреваю, накладные расходы на ленивость больше чем потери от лишнего пробега по данным в кеше.

vasaka ★★★
()
Ответ на: комментарий от anonymous

>В результате приходится писать (+1) $! 2.

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

yyk ★★★★★
()
Ответ на: комментарий от vasaka

Все дело в алгоритмах. Ленивость или строгость — это скорее свойство алгоритма или структуры данных, нежели языка целиком. Анализаторы строгости в компиляторах более-менее научились выявлять эти свойства алгоритмов, но иногда им нужно немного подсказать.

Плюс к этому каждому человеку, который начинает писать код на ленивом языке, следует помнить, что (1 + 1) — это не готовое 2, а отложенное вычисление, которое при выполнении вернет 2. Это знать надо обязательно.

anonymous
()
Ответ на: комментарий от anonymous

А от 1 + 2 и тут ничего не вылетит. Судя по твоим фразам, тебя интересует скорее калькулятор с простейшей арифметикой, чем ЯП общего назначения. ХМ и лень в таком случае явно лишние, согласен.

anonymous
()
Ответ на: комментарий от vasaka

> необходимость так написать и в чем вообще тут причина не следует из описания языка.

Это какое-то плохое описание языка, если там не написали про то, как действует ленивость и как ей грязно пользо^W^Wуправлять.

акое можно узнать только с опытом, попытавшись решить всплывшую проблему, или спросив у опытного товарища, значит факт не тривиален.

Да я тебя умоляю, с каким опытом? Каждый, кто осилил туториал по хацкелю, знает, что foldl без оптимизаций на большом объеме данных жрет память и падает.

anonymous
()
Ответ на: комментарий от anonymous

Почему в нормальных языках код сразу работает быстро, а в хаскеле надо заниматься хаскиартом?

Симметрично. Есть куча кода который работает лучше именно лениво, а «нормально» вообще работать не будет (уйдёт в бесконечный цикл).

Каждый, кто осилил туториал по хацкелю, знает, что foldl без оптимизаций на большом объеме данных жрет память и падает.

В этом примере замена foldl на foldl' не спасает - если реализация не умеет строгость в конструкторах (как BangPatterns у GHC), то тогда вообще никак.

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

как BangPatterns у GHC

Ну или руками (и по стандарту) с помощью `seq` и ($!).

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

(\!x -> ...) — это не строгость в конструкторах.

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.