Previous Entry Share Next Entry
2016-01

Почему программы тормозят

...функция - это такая абстракция, которая заставляет внутри делать то, что потом не нужно снаружи.

if(a.count() > 1) {...} via tonsky

Кстати, модные в узких кругах споры, что быстрее - Array of Structures, Structure of Arrays, column-based, row-based и т.д. - это всё то же самое, про абстракции.

Ну и еще оптимизатору effect tracking нужен, конечно.

Причем умный, чтобы знал, что два подряд fsync() можно выбрасывать, а fwrite, fsync, fwrite, fsync - нельзя.

This entry was originally posted at http://wizzard.dreamwidth.org/392317.html. It has comment count unavailable comments. Please comment there using OpenID.

  • 1
enternet September 25th, 2014
Ню-ню. Абстрагируйся-ка от кеша процессора. Когда сможешь, тогда и column-based будет идентичен по производительности с row-based.

wizzard0 September 25th, 2014
Здрасте. А я про что пишу?

thedeemon September 25th, 2014
Rewrite Rules to the rescue.

sergiej September 25th, 2014
пользуйся жавой, там что так что сяк - будет тормозить :)

dmytrish September 25th, 2014
Так effect tracking всем нужен, вот только, как его правильно сделать — это вопрос открытый.

В Хаскеле попробовали заставить программиста привязывать эффекты к монадам по мере возможности — так нет, не то, не серебряная пуля, не годится.

wizzard0 September 25th, 2014
Я чем дальше, тем худшего мнения про систему типов Хаскеля, если что ;-)
Не с точки зрения выразительности, а с точки зрения удобства прежде всего.

Самый крутой рисерч, который я видел - это Sage.

dmytrish September 25th, 2014
Удобство там, конечно, не на высоте.

А можно коротко, чем sage крут? После быстрого гугления увидел, что это a free open-source mathematics software system. Как это соотносится с general-purpose programming language?

Edited at 2014-09-25 01:40 pm (UTC)

wizzard0 September 25th, 2014
Эм, первый раз слышу про mathematics software.

Первая ссылка же

Sage is a prototype functional programming language designed to provide high-coverage checking of expressive program specifications (types). Sage allows a programmer to specify not only simple types such as "Integers" and "Strings" but also arbitrary refinements from simple ranges such as "Positive Integers" to data structures with complex invariants such as "Balanced binary search trees." In addition to featuring these predicates upon types, Sage merges the syntactic categories of types and terms, in the spirit of Pure Type Systems, to express dependent types such as that of the infamous printf function.

https://sage.soe.ucsc.edu/

dmytrish September 25th, 2014
У меня даже на первой странице по запросу Sage ничего такого нет (что проклятая социальность делает с гуглом!).

# let xor (x1:Bool) (x2:Bool) = ((x1 && (not x2)) || ((not x1) && x2));;
Binding for: xor
Type: (x1:Bool -> x2:Bool ->
(Refine Bool
(fn (z:Bool) =>
(iff z (or (and x1 (not x2)) (and (not x1) x2))))))

— эх, в плане удобства по сравнению с типом результата Bool, который вывел бы Хаскель, это как-то, гм, неубедительно.

gds September 25th, 2014
х-ь выводит Bool, но по нему нельзя судить, не зная внутренностей xor, о том, чему будет равно значение этого типа в зависимости от значений x1 x2 (это как раз и есть неубедительность -- вернули хз что, а дальше сам разбирайся, что там). Тут же -- спецификация в явном виде, полезная для рассуждений об этой функции.

sassa_nf September 25th, 2014
не, это хелловорлд.

вот пусть этот сейдж покажет, что foldt и foldr равны, если переданная функция ассоциативна. вот что-то такое было бы интересно посмотреть.

gds September 25th, 2014
а с какой практической целью полезно знать, что эти функции равны?

sassa_nf September 25th, 2014
ну, раз хочется узнать, что какая-то функция возвращает не просто Bool, а весьма специфическое значение, то вот у функции f аргумент такого же типа, что и у foldr blah, так нельзя ли передать туда foldt?

gds September 25th, 2014
а с какой практической целью полезно знать, что в функцию, принимающую аргумент foldr.., можно передать аргумент foldt..?

wizzard0 September 25th, 2014
Exploratory programming, вообще говоря - весьма важная и нужная штука.

gds September 25th, 2014
тут не оно.

sassa_nf September 25th, 2014
ммммммммммммммммммммм.................

не знаю, где начать.

Ну, хочется мне сказать, что передай мне x и C(x), где C(x) задаёт конкретный тип со свойствами, определёнными значением x. Я же здесь не говорю, что именно foldr подходит как значение типа C(x). Но если foldr подходит, нельзя ли выяснить, подходит ли туда же foldt?

Вот ещё пример: bubblesort подходит; а нельзя ли туда quicksort подставить?

Практическое значение - примерно как полиморфизм.


Или взять вот этот хелловёлд с xor. Проку особого нет в том, чтобы компилятор сказал, что функция xor делает xor. Прок в том, что можно "соединить" функцию xor с ожиданиями другой функции - которая либо ждёт xor-подобное на входе, либо должно использовать для конструирования своего результата (передаёт эстафету на другой уровень сложности).

Edited at 2014-09-25 11:15 pm (UTC)

mbr September 25th, 2014
Я уже говорил, идеальный язык это тот, который способен работать без блокировок вообще. Нужна подзадача - порождай процесс с конечным автоматом. Но это и близко не стояло с функциональным программированием, а как следствие - с современными операционными системами и современным железом. Ближайшая итерация, пожалуй - minix.

wizzard0 September 25th, 2014
А при чем здесь блокировки? о_О

109 September 25th, 2014
или, наоборот, при чём здесь язык :)
lock-free библиотек полно, только они жрут больше cpu и работают медленнее.

sassa_nf September 25th, 2014
"чтобы знал, что два подряд fsync() можно выбрасывать, а fwrite, fsync, fwrite, fsync - нельзя."

Во, а это уже не просто effect tracking, а целая модель эффектов.

Тут уже помянули джаву - правда, недобрым словом - так вот, например, vstore(x,0); vstore(y,0) таки оптимизируется компилятором в один vstore и один просто store с барьером (который на целевой платформе может оказаться NOP). Но для этого финта нужна Memory Model и её отражение на конкретном хардвере.

Там где-то ещё упоминалось NUMA-aware allocation и CPU-cache-aware layout - дык, и это тоже есть

Edited at 2014-09-25 04:18 pm (UTC)

nponeccop September 25th, 2014
У Тонского там по существу вопроса ошибка.

Берешь в Хаскеле натуральные числа Пеано, обычный список и стандартную функцию genericLength. И ничего ненужного не вычисляется.

Т.е. genericLength x < (1 :: Natural) работает на ура.

Дальше читать не стал и тем более дискуссию здесь. Тьфу.

Edited at 2014-09-25 05:39 pm (UTC)

thedeemon September 26th, 2014
Это не существо вопроса. Там числа вообще не при чем.

nponeccop September 26th, 2014
----
sequence придется вычислить весь, даже на языке с нормальной системой типов™ и правильной ленивостью™. Как будто два кусочка кода, внутри count() и снаружи, должны поговорить друг с другом, но не могут.
---

В случае Пеано они вполне говорят друг с другом, через санки.

Т.е. Х-ь этот пример полностью опровергает. Пример неудачный.

thedeemon September 26th, 2014
Нормальный пример. То, что "если этот код переписать, то одна частная проблема в этом месте будет решена", не меняет сути.

nponeccop September 26th, 2014
Фразу "даже на языке с нормальной системой типов™ и правильной ленивостью™" вычеркнуть - будет норм.

Power of optimizers is overrated

nponeccop September 25th, 2014
мечтать конечно не вредно (это называется active libraries и частично есть много где)

Но вообще-то даже с cross module inlining уже не всё так гладко, как хотелось. Так что надо начинать с малого.

  • 1
?

Log in

No account? Create an account