I am very much new to Haskell and I am trying to achieve something. If anyone could help me it would be really helpful. I have install ghc and other related packages required for haskell in my laptop. I am trying to achieve the following and stuck with error.
I have downloaded the base package that implements all the function of list, map and everything which is in the github https://github.com/ghc/packages-base/blob/master/GHC/List.lhs. I am trying to create a simple main file in which I implement a Data.List function which is being imported from the cloned github folder. FYI I renamed the base name to MyPack. If anyone can help me on how to or navigate me to any blog post who has already implemented such kinda projects it would be really helpful.
I am doing a dissertation project where I am trying to measure of impact of prefetch in the no-fib benchmarks. For this I have to modify the Data.List library used in 21 benchmarks of no-fib. Which is the best way to approach this. Currently I think my approach is bad since I have created a new cabal project with criterion benchmark and ran a small haskell program reimplementing one of the data.list function. But when I am trying to rewrite the benchmarks and run it, I am facing compilation issue.
I think the way to go is to build your own GHC with your changes to base included. That way you won’t have to modify nofib at all. It’s more difficult to build than a standard cabal project, but shouldn’t be that hard (hadrian · Wiki · Glasgow Haskell Compiler / GHC · GitLab). And it will take some time to compile GHC, but it shouldn’t take much more than 30 minutes unless you have a slow computer.
Sorry for the delay in the reply. I did try working out that way and it was way more difficult than I thought. Instead I had created a criterion project with cabal with the benchmark and the lib functions that I want to modify. I am trying to use the GHC Prim prefetch function but the documentations are very limited on how to use. Any insights would be really helpful. I have been trying to implement prefetchByteArray3# function for a very long time and had no success. Any sample program would be really helpful. I am trying to add the prefetch in the sort code of the existing library. I am adding the sort code here for your reference.
sort :: ByteString -> ByteString
sort (BS input l)
-- qsort outperforms counting sort for small arrays
| l <= 20 = unsafeCreateFp l $ \destFP -> do
memcpyFp destFP input l
unsafeWithForeignPtr destFP $ \dest -> c_sort dest (fromIntegral l)
| otherwise = unsafeCreateFp l $ \p -> allocaArray 256 $ \arr -> do
fillBytes (castPtr arr) 0 (256 * sizeOf (undefined :: Int))
unsafeWithForeignPtr input (\x -> countOccurrences arr x l)
let go 256 !_ = return ()
go i !ptr = do n <- peekElemOff arr i
when (n /= 0) $
fillBytes ptr (fromIntegral @Int @Word8 i) n
go (i + 1) (ptr `plusPtr` fromIntegral n)
unsafeWithForeignPtr p (go 0)
where
-- Count the number of occurrences of each byte.
countOccurrences :: Ptr Int -> Ptr Word8 -> Int -> IO ()
countOccurrences !counts !str !len = go 0
where
go !i | i == len = return ()
| otherwise = do k <- fromIntegral `fmap` peekElemOff str i
x <- peekElemOff counts k
pokeElemOff counts k (x + 1)
putStr $ show k ++ " "
go (i + 1)
I know this is back to back messages but could you help me with the following functions to add a prefetch. It would be really helpful to understand how you approach it. I basically wanna prefetch values in a list operation. Which is the best prefetch to be used.
transpose :: [[a]] -> [[a]]
transpose [] = []
transpose ([] : xss) = transpose xss
transpose ((x : xs) : xss) = combine x hds xs tls
where
(hds, tls) = unzip [(hd, tl) | hd : tl <- xss]
combine y h ys t = (y:h) : transpose (ys:t)
{-# NOINLINE combine #-}
foldl :: forall a b. (b -> a -> b) -> b -> [a] -> b
{-# INLINE foldl #-}
foldl k z0 xs =
foldr (\(v::a) (fn::b->b) -> oneShot (\(z::b) -> fn (k z v))) (id :: b -> b) xs z0
nubBy :: (a -> a -> Bool) -> [a] -> [a]
#if defined(USE_REPORT_PRELUDE)
nubBy eq [] = []
nubBy eq (x:xs) = x : nubBy eq (filter (\ y -> not (eq x y)) xs)
#else
nubBy eq l = nubBy' l []
where
nubBy' [] _ = []
nubBy' (y:ys) xs
| elem_by eq y xs = nubBy' ys xs
| otherwise = y : nubBy' ys (y:xs)
First note that lists in Haskell are linked lists, so prefetching the nth element requires dereferencing n pointers. But if you really want to do that, it seems there are prefetchValue*# primops that you could try to use:
prefetchValue3 :: a -> IO ()
prefetchValue3 x = IO (\s -> (# prefetchValue3# x s, () #))
prefetchElem3 :: [a] -> Int -> IO ()
prefetchElem3 xs i = prefetchValue3 (xs !! i)
Thank you for this one Jaror. Unfortunately this doesn’t seems to work. I understand the comparison between the previous one and this one but why only this one throws an error with the type state and not the previous one? The following is the error that I am facing. Any insights on why would be helpful.
Couldn’t match expected type: State# RealWorld
with actual type: State# d0 → State# d0
* In the expression: prefetchValue3# x
In the expression: (# prefetchValue3# x, () #)
In the first argument of IO', namely (\ s → (# prefetchValue3# x, () #))’
|
233 | prefetchValue3 x = IO (\s → (# prefetchValue3# x, () #))
Ah, I had some bugs in the snippets. I’ve fixed them now.
Also, I with prefetchValue there may be problems involving laziness. Maybe you need to first evaluate the element that you get from the list like this:
prefetchElem3 :: [a] -> Int -> IO ()
prefetchElem3 xs i = let !x = xs !! i in prefetchValue3 x
Or something like this if you don’t want to evaluate the element but do want to make sure the indexing is finished before you do the prefetch:
prefetchElem3' :: [a] -> Int -> IO ()
prefetchElem3' xs i = go xs i where
go (x:_) 0 = prefetchValue3 x
go (_:xs) n = go xs (n - 1)
Is the prefetchValue3 in the above refers to the previous defined function or prefetchValue3# function? Coz for both I am facing issue.
If it refers to the previous method the same error prevails
Couldn’t match expected type: State# RealWorld
with actual type: State# d0 → State# d0
In the expression: prefetchValue3# x
In the expression: (# prefetchValue3# x, () #)
In the first argument of IO', namely (\ s → (# prefetchValue3# x, () #))’
if its prefetchValue3# then
Couldn’t match expected type: IO ()
with actual type: State# d0 → State# d0
Probable cause: prefetchValue3#' is applied to too few arguments In the expression: prefetchValue3# x In the expression: let !x = xs !! i in prefetchValue3# x In an equation for prefetchElem3’:
prefetchElem3 xs i = let !x = xs !! i in prefetchValue3# x
Thank you Jaror and this worked like charm. I tried modifying the transpose function into the following with the above code and I modified into this. But I am trying to combine it with
[inlinePerformIO] function but unable to do so. Any idea on how I can proceed?