Текущее состояние длин

[deniok]

Померил тут, похоже про магические хэши не надо рассказывать. Тут length' - текущая реализация из GHC, length0 - трех?летней давности:

{-# LANGUAGE MagicHash #-}
module Length where

import GHC.Prim
import GHC.Exts (Int(I#))
import Data.List

length0    :: [a] -> Int
length0 l  =  len l 0#
  where
    len           :: [a] -> Int# -> Int
    len []     a# =  I# a#
    len (_:xs) a# =  len xs (a# +# 1#)

length' :: [a] -> Int
length' xs = lenAcc xs 0 where
  lenAcc []     n = n
  lenAcc (_:ys) n = lenAcc ys (n+1)

length'' :: [a] -> Int
length'' = foldl' (const . succ) 0

length''' :: [a] -> Int
length''' []     = 0
length''' (_:xs) = 1 + length''' xs

Результаты

C:\Users\deniok\Documents\Haskell>ghc -O2 Length.hs
[1 of 1] Compiling Length           ( Length.hs, Length.o )

C:\Users\deniok\Documents\Haskell>ghci Length.hs
GHCi, version 7.10.3: http://www.haskell.org/ghc/  :? for help
Ok, modules loaded: Length.
> :set +s
> length [1..100000000]
100000000
(1.56 secs, 8,014,793,624 bytes)
> length0 [1..100000000]
100000000
(1.55 secs, 8,002,029,776 bytes)
> length' [1..100000000]
100000000
(1.55 secs, 8,001,085,992 bytes)
> length'' [1..100000000]
100000000
(2.00 secs, 9,601,216,960 bytes)
> length''' [1..100000000]
*** Exception: stack overflow
>
> length [1..50000000]
50000000
(0.86 secs, 3,938,034,240 bytes)
> length0 [1..50000000]
50000000
(0.84 secs, 3,937,631,120 bytes)
> length' [1..50000000]
50000000
(0.84 secs, 4,240,225,000 bytes)
> length'' [1..50000000]
50000000
(1.08 secs, 4,845,463,912 bytes)
> length''' [1..50000000]
50000000
(1.34 secs, 4,420,898,928 bytes)

Comments

[nealar.livejournal.com]

Что такое магические хэши? Это когда одновременно и считаются быстро и свойства хорошие?

[lionet.livejournal.com]

{-# LANGUAGE MagicHash #-}

[nealar.livejournal.com]

Это чтобы можно было прямо из GHCi в твиттер писать?

И, как побочный эффект, литералы хавали меньше памяти?

[deni-ok.livejournal.com]

Unboxed types:
https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/primitives.html
Считаются быстро, свойства плохие.

[kodt-rsdn.livejournal.com]

А length0 - она вообще энергичная?
Там не может получиться, что компилятор построит мега-санки I# (...(((0# +# 1#) +# 1#) + 1#)...), которые влезли в память (в отличие от length''' только потому, что боксированные данные занимают вдвое больше места)?

Как насчёт заведомо энергичного
length00 = I# . foldl' (const . inc) 0# where inc h = h +# 1#

[deni-ok.livejournal.com]

Какие санки, это же чисто сишные типы и операции, они unlifted (и unboxed). Их даже в полиморфные функции передавать нельзя и в полиморфных типах данных хранить.

[sassa-nf.livejournal.com]

а код какой генерирует? А то мало ли, все они проводят кучу времени в GC или еще какой конфуз

[deni-ok.livejournal.com]

Библиотечный length? Сомневаюсь:) Может потом гляну, мысль разумная.

[sassa-nf.livejournal.com]

так не length, а [1..1000000000]

[migmit.livejournal.com]

Слушай, тут на ЛОРе обсуждают задачку, говорят, что из твоего курса (сам не проверял): https://www.linux.org.ru/forum/development/12415360

И бают, будто бы в ответе сказано, что corge не может привести к расходимости. Так оно вполне может, если только там тип явно не указан. Я, конечно, не вполне понимаю, что значит "корректный набор аргументов", но уж corge стопудово может быть чем угодно.

[migmit.livejournal.com]

А, пардон, я там недопонял. Говорят, ответ неизвестен. Прошу пардону.

[deni-ok.livejournal.com]

Ты имеешь в виду, что instance Num мы можем для стрелочного типа сделать?

[migmit.livejournal.com]

Ну да.

[deni-ok.livejournal.com]

Спасибо!

[deni-ok.livejournal.com]

Да, надо на Char поменять.

[qnikst (from livejournal.com)]

Разведка докладывает, что поменяли на String (без указания типа), но с ним можно (если контекст в котором фунция задана можно менять и добавить OverloadedStrings):

{-# LANGUAGE OverloadedStrings #-}
instance Blah where
   fromString = undefined

?

[deni-ok.livejournal.com]

Это уже вне рамок стандарта. Ясно, что расширения могут менять стандартное поведение достаточно сильно.

[qnikst (from livejournal.com)]

(не очень серьёзно), а потом люди доучиваются, приходят в реальную жизнь и начинается, почему length (1,2) = 1 :)

[nponeccop.livejournal.com]

Ну кто так меряет! ghci вроде как сильно хуже кодогенит, чем ghc -O. Реквестирую нативный бенч с Criterion.

[deni-ok.livejournal.com]

Так там и грузится отоптимизированный модуль, там же сначала ghc -O2 Length.hs