The Q6600
Benchmarks Game

spectral-norm Haskell GHC #4 program

source code

--
-- The Computer Language Benchmarks Game
-- https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
--
-- Modified by Gabriel Gonzalez
-- Modified by Ryan Trinkle: 1) change from divInt# to uncheckedIShiftRA#
--                           2) changed -optc-O to -optc-O3
--                           3) added -optc-ffast-math
-- Translation from Clean by Don Stewart
-- Parallelized by Louis Wasserman
--
-- Should be compiled with:
-- 	-threaded -funbox-strict-fields -O2 -fvia-c -optc-O3 
-- 	-fexcess-precision -optc-ffast-math 
-- Should be run with:
-- 	+RTS -N<number of cores>

import System.Environment
import Foreign.Marshal.Array
import Foreign
import Text.Printf
import Control.Concurrent
import Control.Monad
import GHC.Base
import GHC.Conc

type Reals = Ptr Double

main = do
    n <- getArgs >>= readIO . head
    allocaArray n $ \ u -> allocaArray n $ \ v -> do
      forM_ [0..n-1] $ \i -> pokeElemOff u i 1 >> pokeElemOff v i 0

      powerMethod 10 n u v
      printf "%.9f\n" =<< eigenvalue n u v 0 0 0

------------------------------------------------------------------------

eigenvalue :: Int -> Reals -> Reals -> Int -> Double -> Double -> IO Double
eigenvalue !n !u !v !i !vBv !vv
    | i < n     = do	ui <- peekElemOff u i
			vi <- peekElemOff v i
			eigenvalue n u v (i+1) (vBv + ui * vi) (vv + vi * vi)
    | otherwise = return $! sqrt $! vBv / vv

------------------------------------------------------------------------

-- Essentially borrowed from the Java implementation.
data CyclicBarrier = Cyclic !Int !(MVar (Int, [MVar ()]))

await :: CyclicBarrier -> IO ()
await (Cyclic k waitsVar) = do
	(x, waits) <- takeMVar waitsVar
	if x <= 1 then do
		mapM_ (`putMVar` ()) waits
		putMVar waitsVar (k, [])
	  else do
	  	var <- newEmptyMVar
	  	putMVar waitsVar (x-1,var:waits)
	  	takeMVar var

newCyclicBarrier :: Int -> IO CyclicBarrier
newCyclicBarrier k = liftM (Cyclic k) (newMVar (k, []))

powerMethod :: Int -> Int -> Reals -> Reals -> IO ()
powerMethod z n u v = allocaArray n $ \ !t -> do
	let chunk = (n + numCapabilities - 1) `quotInt` numCapabilities
	!barrier <- newCyclicBarrier $! (n + chunk - 1) `quotInt` chunk
	let timesAtAv !s !d l r = do
		timesAv n s t l r
		await barrier
		timesAtv n t d l r
		await barrier
	let thread !l !r = GHC.Base.foldr (>>) (return ()) $ replicate z $ do
		timesAtAv u v l r
		timesAtAv v u l r
	let go l = case l + chunk of
		r | r < n	-> forkIO (thread l r) >> go r
		  | otherwise	-> thread l n
	go 0

timesAv :: Int -> Reals -> Reals -> Int -> Int -> IO ()
timesAv !n !u !au !l !r = go l where
    go :: Int -> IO ()
    go !i = when (i < r) $ do
	let avsum !j !acc
		| j < n = do
			!uj <- peekElemOff u j
			avsum (j+1) (acc + ((aij i j) * uj))
		| otherwise = pokeElemOff au i acc >> go (i+1)
	avsum 0 0

timesAtv :: Int -> Reals -> Reals -> Int -> Int -> IO ()
timesAtv !n !u !a !l !r = go l
  where
    go :: Int -> IO ()
    go !i = when (i < r) $ do
	let atvsum !j !acc 
		| j < n	= do	!uj <- peekElemOff u j
				atvsum (j+1) (acc + ((aij j i) * uj))
		| otherwise = pokeElemOff a i acc >> go (i+1)
	atvsum 0 0

--
-- manually unbox the inner loop:
-- aij i j = 1 / fromIntegral ((i+j) * (i+j+1) `div` 2 + i + 1)
--
aij (I# i) (I# j) = D# (
    case i +# j of
        n -> 1.0## /## int2Double# 
        	(((n *# (n+#1#)) `uncheckedIShiftRA#` 1#) +# (i +# 1#)))
    

notes, command-line, and program output

NOTES:
64-bit Ubuntu quad core
The Glorious Glasgow Haskell Compilation System,
version 8.8.1


Tue, 05 May 2020 23:19:11 GMT

MAKE:
mv spectralnorm.ghc-4.ghc spectralnorm.ghc-4.hs
/opt/src/ghc-8.8.1/bin/ghc --make -fllvm -O2 -XBangPatterns -threaded -rtsopts -XMagicHash spectralnorm.ghc-4.hs -o spectralnorm.ghc-4.ghc_run
Loaded package environment from /home/dunham/.ghc/x86_64-linux-8.8.1/environments/default
[1 of 1] Compiling Main             ( spectralnorm.ghc-4.hs, spectralnorm.ghc-4.o )

spectralnorm.ghc-4.hs:41:21: warning: [-Wtabs]
    Tab character found here, and in 68 further locations.
    Please use spaces instead.
   |
41 |     | i < n     = do    ui <- peekElemOff u i
   |                     ^^^^
You are using an unsupported version of LLVM!
Currently only 7 is supported.
We will try though...
Linking spectralnorm.ghc-4.ghc_run ...
rm spectralnorm.ghc-4.hs

23.61s to complete and log all make actions

COMMAND LINE:
./spectralnorm.ghc-4.ghc_run +RTS -N4 -RTS 5500

PROGRAM OUTPUT:
1.274224153