Здравствуйте, Аноним, Вы писали:
А>Говорят что хаскель медленоват. А>Интересно, а разве нельзя использовать Glasgow Haskell Compiler, который сконвертирует хаскель в Сишный код?
Ну, собственно, все так и делают. Просто реализация ленивой модели вычислений ведёт к некоторым накладным расходам в рантайме. Если максимальное быстродействие критично, то лучше писать на чём-нибудь низкоуровневом, на том же C, например. Или аккуратно расставлять strictness флаги в своём коде.
А>Говорят что хаскель медленоват. А>Интересно, а разве нельзя использовать Glasgow Haskell Compiler, который сконвертирует хаскель в Сишный код?
Две глупости сразу.
Во-первый, в общем случае он не медленноват.
Во-вторых, просто перевод его Сишный код мало что меняет. Это что, карго культ такой, что код на Це обязательно быстрый?
На данный момент в GHC, как мне видится, основные причины тормозов следующие:
1. слабосьть компилятора в таких областях, как strictness analysis, escape analysis
2. похоже GHC не может понять, когда можно использовать thread-local память. Также часто не просекает, когда можно держать данные в небольшом блоке и вместо этого лезет в heap.
3. неспособность FFI работать с структурами данных, передаваемыми по значению а не по ссылке
4. нет реализации некоторых полезных примитивов вроде bid endian <-> small endian и float/double -> binary representation
RD>>3. неспособность FFI работать с структурами данных, передаваемыми по значению а не по ссылке
L>Это проблема не только хаскелевских FFI. L>Вообще, если конкретнее, то проблема тут в Си.
А>>Интересно, а разве нельзя использовать Glasgow Haskell Compiler, который сконвертирует хаскель в Сишный код?
D>Ну, собственно, все так и делают. Просто реализация ленивой модели вычислений ведёт к некоторым накладным расходам в рантайме. Если максимальное быстродействие критично, то лучше писать на чём-нибудь низкоуровневом, на том же C, например. Или аккуратно расставлять strictness флаги в своём коде.
Насколько я разбираюсь в медицине
а) при компиляции haskell через C ленивость никуда не девается. Наоборот, могут быть проблемы из-за того что всякие хитрые трюки реализовать на C не столько тривиально.
б) ленивая модель вычислений ведет к часто непродуктивным расходам в рантайме. Особенно, когда эта ленивость и даром не нужна.
Пример:
sum $ map (+1) [1..n]
Нормальный компилятор мог бы догадаться, что результат — число. И при попытке получить это число вычислил бы результат "энергично". Но обычно сооружается куча глупого кода, в результате чего все делается "лениво" и через пень-колоду. Как правило, выделяя n*k объектов, постоянно проверяя вычислены ли thunkи и т.д.
RD>а) при компиляции haskell через C ленивость никуда не девается. Наоборот, могут быть проблемы из-за того что всякие хитрые трюки реализовать на C не столько тривиально.
Ничего не понял... Ленивость не девается, да. Зачем ей куда-то деваться?
Программы в любом случае транслируются из STG-языка в C--, а потом уже в машинный код. Но из-за полиморфных HOF (скажем в zipWith я могу передать функцию хоть двух, хоть трёх, хоть 20 аргументов) должна использоваться довольно специфическая модель исполнения. В GHC пробовали eval/applay и более традиционную push/enter — для Хаскеля первая оказалась лучше.
RD>б) ленивая модель вычислений ведет к часто непродуктивным расходам в рантайме. Особенно, когда эта ленивость и даром не нужна.
RD>Пример:
sum $ map (+1) [1..n]
RD>Нормальный компилятор мог бы догадаться, что результат — число. И при попытке получить это число вычислил бы результат "энергично". Но обычно сооружается куча глупого кода, в результате чего все делается "лениво" и через пень-колоду. Как правило, выделяя n*k объектов, постоянно проверяя вычислены ли thunkи и т.д.
Нормальный программист мог бы мог бы догадаться, что результат — число, вычисляемое за три арифметических операции
Здравствуйте, Аноним, Вы писали:
А>Говорят что хаскель медленоват. А>Интересно, а разве нельзя использовать Glasgow Haskell Compiler, который сконвертирует хаскель в Сишный код?
RD>>а) при компиляции haskell через C ленивость никуда не девается. Наоборот, могут быть проблемы из-за того что всякие хитрые трюки реализовать на C не столько тривиально.
D>Ничего не понял... Ленивость не девается, да. Зачем ей куда-то деваться?
Конечно ленивости не нужно никуда деваться, да и не может она.
В изначальном посте было неявное недоумение, почему это хаскель не может быть быстрым, если его можно перегнать в С.
Вы написали, что ленивая модель вычислений приводит к накладным расходам (с этим согласен).
Я уточнил, что конвертация кода на haskell в код на С не факт что улучшит скорость, так как ленивость останется там, где была. И накладные расходы тоже. Причем из-за различия подходов в исполнении кода могут быть еще дополнительные накладные расходы.
D>Программы в любом случае транслируются из STG-языка в C--, а потом уже в машинный код.
Да ну? Даже если кодогенерация идет через С или LLVM? Не верю. Там С-- и даром не нужен.
D>Но из-за полиморфных HOF (скажем в zipWith я могу передать функцию хоть двух, хоть трёх, хоть 20 аргументов) должна использоваться довольно специфическая модель исполнения. В GHC пробовали eval/applay и более традиционную push/enter — для Хаскеля первая оказалась лучше.
Спору нет, все так и есть. Однако справедливости ради следует заметить, что обычно типы известны довольно точно, и компилятор мог бы этим воспользоваться. Но как правило этого не делает.
RD>>б) ленивая модель вычислений ведет к часто непродуктивным расходам в рантайме. Особенно, когда эта ленивость и даром не нужна.
RD>>Пример:
sum $ map (+1) [1..n]
RD>>Нормальный компилятор мог бы догадаться, что результат — число. И при попытке получить это число вычислил бы результат "энергично". Но обычно сооружается куча глупого кода, в результате чего все делается "лениво" и через пень-колоду. Как правило, выделяя n*k объектов, постоянно проверяя вычислены ли thunkи и т.д.
D>Нормальный программист мог бы мог бы догадаться, что результат — число, вычисляемое за три арифметических операции
n * (n + 3) `div` 2
и не парил бы мозги компилятору
Похоже Вы предпочитаете прикалываться над искусственным (и специально простым) примером, а не обсудить проблемы существующего компилятора.
Здравствуйте, Rtveliashvili Denys, Вы писали:
RD>>>Пример:
sum $ map (+1) [1..n]
RD>>>Нормальный компилятор мог бы догадаться, что результат — число. И при попытке получить это число вычислил бы результат "энергично". Но обычно сооружается куча глупого кода, в результате чего все делается "лениво" и через пень-колоду. Как правило, выделяя n*k объектов, постоянно проверяя вычислены ли thunkи и т.д.
D>>Нормальный программист мог бы мог бы догадаться, что результат — число, вычисляемое за три арифметических операции
n * (n + 3) `div` 2
и не парил бы мозги компилятору
RD>Похоже Вы предпочитаете прикалываться над искусственным (и специально простым) примером, а не обсудить проблемы существующего компилятора.
Хорошо. Что предлагается делать компилятору в программе
sum $ take 3 $ map (+1) [1..100500+n]
Результат — число. При попытке получить это число вычислять результат "энергично"? Разместить в памяти список на 100500+n элементов, увеличить каждый элемент на 1, а затем просуммировать первые его три элемента? Нет? А здесь
sum $ take n $ map (+1) [1..100500+n]
При маленьких n считать лениво, а при больших энергично?
RD>>Похоже Вы предпочитаете прикалываться над искусственным (и специально простым) примером, а не обсудить проблемы существующего компилятора.
D>Хорошо. Что предлагается делать компилятору в программе D>
sum $ take 3 $ map (+1) [1..100500+n]
D>Результат — число. При попытке получить это число вычислять результат "энергично"? Разместить в памяти список на 100500+n элементов, увеличить каждый элемент на 1, а затем просуммировать первые его три элемента? Нет? А здесь D>
sum $ take n $ map (+1) [1..100500+n]
D>При маленьких n считать лениво, а при больших энергично?
1. В данном случае всегда считать энергично.
2. Умный комприлятор легко может догадаться, что список этот видно только в контексте этого выражения, так что хранить его в памяти и даром не надо. Поэтому и создавать этот список не нужно. Он вообще не должен быть в скомпилированном коде. Как вариант, выражение [1..100500+n] следует превратить в одну переменную и код, играющий роль итератора (a-la fusion). Причем без всяких этих богомерзких вручную написанных rewrite rules. Что-то вроде вот этого (псевдоассемблер):
; блок данных
upper_bound:
data long
item:
data long
; инициализация
init:
; предполагаем, что регистр acc хранит значение n
add acc, 100500
mov upper_bound, acc
mov item, 0
jpm #return_from_init
; итератор
next_val:
mov acc, item
inc acc
cmp acc, upper_bound
jg #end_of_list ; переход по адресу, соответствующему концу списка
jpm #next_element_of_list ; переход по адресу, соответствующему считыванию очередного элемента списка. сам элемент - в регистре acc
Ну как, покатит? Или есть принципиальная проблема, почему так делать нельзя и приходится платить цену за ленивость вычислений да захламлять heap?
