deniok: (ухмыляюсь)
[personal profile] 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)

Date: 2016-03-07 02:26 pm (UTC)
From: [identity profile] nealar.livejournal.com
Что такое магические хэши? Это когда одновременно и считаются быстро и свойства хорошие?

Date: 2016-03-07 03:15 pm (UTC)
From: [identity profile] lionet.livejournal.com
{-# LANGUAGE MagicHash #-}

Date: 2016-03-07 03:25 pm (UTC)
From: [identity profile] nealar.livejournal.com
Это чтобы можно было прямо из GHCi в твиттер писать?

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

Date: 2016-03-07 04:17 pm (UTC)
From: [identity profile] deni-ok.livejournal.com
Unboxed types:
https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/primitives.html
Считаются быстро, свойства плохие.

Date: 2016-03-07 07:44 pm (UTC)
From: [identity profile] kodt-rsdn.livejournal.com
А length0 - она вообще энергичная?
Там не может получиться, что компилятор построит мега-санки I# (...(((0# +# 1#) +# 1#) + 1#)...), которые влезли в память (в отличие от length''' только потому, что боксированные данные занимают вдвое больше места)?

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

Date: 2016-03-07 08:17 pm (UTC)
From: [identity profile] deni-ok.livejournal.com
Какие санки, это же чисто сишные типы и операции, они unlifted (и unboxed). Их даже в полиморфные функции передавать нельзя и в полиморфных типах данных хранить.

Date: 2016-03-07 09:39 pm (UTC)
From: [identity profile] sassa-nf.livejournal.com
а код какой генерирует? А то мало ли, все они проводят кучу времени в GC или еще какой конфуз

Date: 2016-03-07 09:46 pm (UTC)
From: [identity profile] deni-ok.livejournal.com
Библиотечный length? Сомневаюсь:) Может потом гляну, мысль разумная.

Date: 2016-03-07 10:47 pm (UTC)
From: [identity profile] sassa-nf.livejournal.com
так не length, а [1..1000000000]

Date: 2016-03-08 08:23 am (UTC)
From: [identity profile] migmit.livejournal.com
Слушай, тут на ЛОРе обсуждают задачку, говорят, что из твоего курса (сам не проверял): https://www.linux.org.ru/forum/development/12415360

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

Date: 2016-03-08 08:24 am (UTC)
From: [identity profile] migmit.livejournal.com
А, пардон, я там недопонял. Говорят, ответ неизвестен. Прошу пардону.

Date: 2016-03-08 10:34 am (UTC)
From: [identity profile] deni-ok.livejournal.com
Ты имеешь в виду, что instance Num мы можем для стрелочного типа сделать?

Date: 2016-03-08 11:15 am (UTC)
From: [identity profile] deni-ok.livejournal.com
Спасибо!

Date: 2016-03-08 10:39 am (UTC)
From: [identity profile] deni-ok.livejournal.com
Да, надо на Char поменять.

Date: 2016-03-09 11:03 am (UTC)
From: [identity profile] qnikst (from livejournal.com)
Разведка докладывает, что поменяли на String (без указания типа), но с ним можно (если контекст в котором фунция задана можно менять и добавить OverloadedStrings):
{-# LANGUAGE OverloadedStrings #-}
instance Blah where
   fromString = undefined


?

Date: 2016-03-09 11:25 am (UTC)
From: [identity profile] deni-ok.livejournal.com
Это уже вне рамок стандарта. Ясно, что расширения могут менять стандартное поведение достаточно сильно.

Date: 2016-03-09 11:37 am (UTC)
From: [identity profile] qnikst (from livejournal.com)
(не очень серьёзно), а потом люди доучиваются, приходят в реальную жизнь и начинается, почему length (1,2) = 1 :)

Date: 2016-03-09 11:28 pm (UTC)
From: [identity profile] nponeccop.livejournal.com
Ну кто так меряет! ghci вроде как сильно хуже кодогенит, чем ghc -O. Реквестирую нативный бенч с Criterion.
Edited Date: 2016-03-09 11:29 pm (UTC)

Date: 2016-03-10 07:20 am (UTC)
From: [identity profile] deni-ok.livejournal.com
Так там и грузится отоптимизированный модуль, там же сначала ghc -O2 Length.hs

Profile

deniok: (Default)
deniok

April 2017

S M T W T F S
      1
23 45678
9101112131415
16171819202122
23242526272829
30      

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 25th, 2017 02:52 pm
Powered by Dreamwidth Studios