Customizing Base Package

Learn
23

Modified transpose code:

transpose :: [[a]] -> [[a]]
transpose [] = []
transpose ([] : xss) = transpose xss
transpose ((x : xs) : xss) = combine x hds xs tls
  where
    -- We tie the calculations of heads and tails together
    -- to prevent heads from leaking into tails and vice versa.
    -- unzip makes the selector thunk arrangements we need to
    -- ensure everything gets cleaned up properly.
    (hds, tls) = unzip [(hd, tl) | hd : tl <- xss]
    prefetchTails :: IO ()
    prefetchTails = mapM_ (\tl -> prefetchElem3 tl 0) tls
    combine y h ys t = (y:h) : transpose (ys:t)
    {-# NOINLINE combine #-}

But I am not sure ho to invoke prefetchTails in the actual main.

24

Can you explain what you’re trying to do? This does not seem very useful to me.

Anyways, you could do something like this:

import System.IO.Unsafe (unsafePerformIO)

transpose :: [[a]] -> [[a]]
transpose [] = []
transpose ([] : xss) = transpose xss
transpose ((x : xs) : xss) = prefetchTails `seq` combine x hds xs tls
  where
    -- We tie the calculations of heads and tails together
    -- to prevent heads from leaking into tails and vice versa.
    -- unzip makes the selector thunk arrangements we need to
    -- ensure everything gets cleaned up properly.
    (hds, tls) = unzip [(hd, tl) | hd : tl <- xss]
    prefetchTails :: ()
    prefetchTails = unsafePerformIO (mapM_ (\tl -> prefetchElem3 tl 0) tls)
    combine y h ys t = (y:h) : transpose (ys:t)
    {-# NOINLINE combine #-}
1 Like
25

Jaror thank you for the input. What I am trying to experiment is that if this addition of prefetch reduces the runtime and L2 cache misses in Haskell. This is just an experimental test.

26

Ran into the following error in the line

prefetchElem3 xs i = prefetchValue3 (xs !! i)

nofib-prefetch.exe: Prelude.!!: index too large
CallStack (from HasCallStack):
error, called at libraries\base\GHC\List.hs:1368:14 in base:GHC.List
tooLarge, called at libraries\base\GHC\List.hs:1378:50 in base:GHC.List

27

The reason I’m asking what you’re planning is because it seems you’re prefetching the elements of the double nested linked list, while those are never accessed by the algorithm. So you’re only adding extra work without any benefit.

To understand where prefetching is useful you need to have a firm grasp of the code that GHC generates. That’s definitely something I consider out of reach for beginners. I think there are only very few people who can really reliably reason about things like this (sadly).

^ That error message means what it says. You’re giving it a linked list as input that is shorter than the index that you’re trying to prefetch. In this case you’re prefetching the element with index 0 (the first element of the list), so that must mean you’re giving it an empty list as input.

1 Like
28

I have few benchmarks that uses few of the list functions and transpose is one of them. I want to try to use prefetch in transpose and see if it helps in optimising. I would love to take my time in learning the depth and the concept and then do it, unfortunately this is my dissertation and I should complete it by the end of march and hence seeking help. The resources available on the internet is pretty much very less and hence posting questions. I am very grateful to you for helping me out as I am able to understand bits and pieces and most of the things makes sense.

30

Jaror! Would it be too much to ask if you can provide input on any one of the following function on how to incorporate prefetch so that I can test out my theory.

(),
(++),
map,
head,
foldr1,
repeat,
reverse,
(!!),
transpose,
unlines,
zipWith,
foldr1,
splitAt,
nub

Thanks in advance!

31

I don’t mind helping you by explaining a few error message here and there, but I think it would also take me days (if not more) to figure out how properly to apply prefetching here. I don’t know that much about prefetching. So, I don’t think I can help you much further.

32

No worries Jaror. Thank you so much for helping this far. I really appreciate it… I will try understanding and doing some and if I face some issue I will post it in the thread and if it strikes of anything you can help out.