[Agda] Does Agda2 have fast arrays?

Don Stewart dons at galois.com
Mon Oct 4 18:52:20 CEST 2010


ajeffrey:
> On 10/03/2010 12:59 AM, Don Stewart wrote:
>> What can we do about the coercions? I suspect they make GHC sad.
>
> Sorry, I'm being dense here -- what's the runtime penalty for  
> unsafeCoerce?  I'd expect that most compilers implement it as a no-op.

It's a no-op, that generates a constraint type:

    ActualType ~ CoerceType

And doing so creates a bit of an optimization boundary.
 
> There may be cases where ghc's optimizer can't do as good a job because  
> of unsafeCoerce, due to lack of type information, but I doubt that would  
> have much of an impact in practice.
>
> As a dumb benchmark, I merge-sorted 20K of data, first in Agda:
>
> 1.23user 0.48system 0:01.72elapsed 99%CPU (0avgtext+0avgdata  
> 1282352maxresident)k
> 0inputs+48outputs (0major+80211minor)pagefaults 0swaps
>
> then in Haskell:
>
> 1.22user 0.64system 0:01.85elapsed 100%CPU (0avgtext+0avgdata  
> 1282368maxresident)k
> 0inputs+48outputs (0major+80212minor)pagefaults 0swaps
>
> This is a deliberately (honest!) not-very-clever sorting algorithm which  
> generates lots of cons cells.  I ran it with 2G heap to minimize the  
> impact of the GC (about 13% GC time).

But we'd like to use arrays (e.g.
http://hackage.haskell.org/package/vector) not lists, right?
 
    > 
    > split :: Char -> [Char] -> [Char] -> [Char] -> ([Char],[Char])
    > split x xs ys []             = (xs,ys)
    > split x xs ys (z:zs) | x < z = split x xs (z:ys) zs
    > split x xs ys (z:zs)         = split x (z:xs) ys zs
    >   
    > sort :: [Char] -> [Char]
    > sort [] = []
    > sort (x:xs) = merge (sort ys) (x : sort zs) where (ys,zs) = split x [] [] xs
    > 
    > main = getContents >>= putStr . sort

I'm mostly interested in embeddings that take advantage of fast
"backends" from Hackage.

-- Don


More information about the Agda mailing list