Previous Entry Share Next Entry
2016-01

дыбр

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

Про computer science. Везде утверждают об одинаковой (с точностью до константы) стоимости lazy/eager evaluation, т.е. что построить дерево санков и потом его схлопнуть стоит столько же, сколько и посчитать это всё жадно - но ведь нет! что в теории, что в иерархиях стореджа (регистры-кэш-...) аллокация и даже просто pointer dereference стоят log N, где N - обьем используемой приложением RAM, следовательно, best-case для lazy evaluation будет C1 * N log N, супротив C2 * N для eager!

это уж не говоря о том, что куча софта в рамках оптимизаций закладывает максимальные размеры хипа как "N чего-то там хватит всем", что потом вызывает изрядный батхерт когда файлик, например, в 200 мбайт обрабатывается прекрасно, а в 210 мбайт падает (а если авторы еще и не подумали, то там случаются разные креативные heap corruption вместо "просто out of memory")

Про жизнь. Абсолютное большинство раз, когда я раздумываю над тем, чтобы что-то купить - это воскресенье или праздники. Ну, потому что не надо никуда бежать и можно полезть на сайт посмотреть, то-се.
Почему, при том что в наших широтах уже немало магазинов научились даже доставлять "за 2-3 часа" - в воскресенье никто не работает? Как раз в воскресенье удобно и встретить курьера же.

Реальный вопрос, конечно, не в магазине, а в том, чтобы склад работал в воскресенье, но... это же тоже не такая уж сложность, ну камон. Посадите туда одного человека, сделайте доставку +100 грн в воскресенье, в конце концов...

(Это я видеокарточку хотел заказать, а то HD 7870 уже всякое современное не тянет).

Кстати, про игры. вот последние несколько лет я в них почти не играю, и у меня уплыли фактические вкусы, а память о вкусах осталась старая. В итоге я что-то покупаю на стиме, ревьюшки там Overwhelmingly Positive - а оно не вставляет. Упс. Как бы так узнать, что мне теперь на самом деле нравится?

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

  • 1
nponeccop October 24th, 2016
> построить дерево санков и потом его схлопнуть

ты что-то путаешь, нету такого. Тебя наверное гомоиконность попутала! Узлы дерева санков находятся в сегменте кода же, который O(1). Хинт: там же, где узлы дерева вызовов в CBV.

А в сегменте данных у нас столько же указателей, сколько и без санков

Санки играют роль дерева вызовов в CBV. Но потребление памяти в CBV пропорционально не общему числу вызовов (привет вызову функции в цикле!), а глубине дерева.

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

К примеру можно взять гиломорфизм - sum (enum 1 X). Который даже безо всяких оптимизаций занимает O(1) памяти. Санки-то выделяются, но на месте старых, т.е. N в формуле, учитывающей иерархию памяти, у нас здесь пропорционален интервалу сборки, а не X. Но это вырожденный пример для иллюстрации неравенства общего числа операций и давления на память санками. В древообразном случае ситуация будет похожа на CPS-реализацию CBV, или просто ситуацию, когда при CBV у нас много фунаргов.

Edited at 2016-10-24 07:06 pm (UTC)

wizzard0 October 27th, 2016
Количеству незафоршенных, да.

wizzard0 October 27th, 2016
Ну и фунарг у cbv это санок и есть. Я не про теоретическую эквивалентность, а про практический оверхед похожего кода в разных моделях.

nponeccop October 27th, 2016
рантайм-оверхед вполне может быть и теоретическим :)

Практический оверхед там - не давление на кеш, а давление на предсказатель косвенных переходов.

wizzard0 October 28th, 2016
Предсказание косвенных переходов дает 5х оверхед, а давление на кеш - 250х. Ну и с моим опытом это тоже согласуется

nponeccop October 28th, 2016
Мерять надо. Я считаю это априорно, из общих соображений - это бред (что GHC создает ощутимое дополнительное давление на кеш, с оверхедами я согласен).

Если ты просто сделаешь дерево - то санки будут там же, где и вершины. Причём их будет много только при обходе в ширину.

Кодовых санков (которые по сути те же санки дерева, но дерева вызовов) не так много "холодных", а "горячие" давят практически только на косвенные переходы.

Наверняка кто-то мерял, я спрошу на SO

Upd: оказалось гуглением можно найти статью 2009 года Cache Performance of Lazy Functional Programs on Current Hardware

Говорят что on Core 2 Quad 6600 processor .. we found that L2 cache misses now account for at most 20% in the worst case. Так что дальше можно обсуждать валидность их результатов.

Edited at 2016-10-28 03:36 pm (UTC)

  • 1
?

Log in