Cleanup haddocks in dph-prim-*
authorBen Lippmeier <benl@ouroborus.net>
Fri, 3 Feb 2012 05:01:21 +0000 (16:01 +1100)
committerBen Lippmeier <benl@ouroborus.net>
Fri, 3 Feb 2012 05:01:21 +0000 (16:01 +1100)
15 files changed:
dph-lifted-copy/Data/Array/Parallel/PArray.hs
dph-lifted-copy/Data/Array/Parallel/PArray/Scalar.hs
dph-lifted-vseg/Data/Array/Parallel/PArray/PData/Base.hs
dph-lifted-vseg/Data/Array/Parallel/PArray/PData/Nested.hs
dph-lifted-vseg/Data/Array/Parallel/PArray/PData/Sum2.hs
dph-prim-interface/Data/Array/Parallel/Unlifted.hs
dph-prim-interface/interface/DPH_Header.h
dph-prim-interface/interface/DPH_Interface.h
dph-prim-par/Data/Array/Parallel/Unlifted.hs
dph-prim-par/Data/Array/Parallel/Unlifted/Parallel/Text.hs
dph-prim-par/Data/Array/Parallel/Unlifted/Parallel/UPSel.hs
dph-prim-par/Data/Array/Parallel/Unlifted/Parallel/UPVSegd.hs
dph-prim-seq/Data/Array/Parallel/Unlifted.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/Sequential/USel.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/Sequential/UVSegd.hs

index 66755e4..423540e 100644 (file)
@@ -87,14 +87,12 @@ import Data.Array.Parallel.Lifted.PArray
 import Data.Array.Parallel.PArray.PReprInstances        ()
 import Data.Array.Parallel.Lifted.Combinators
 import Data.Array.Parallel.Lifted.Scalar
+import Data.Array.Parallel.Base.Text
 import qualified Data.Array.Parallel.Unlifted           as U
-
-import Data.Array.Parallel.Base ( showsApp )
-
 import qualified System.Random as R
-
 import Prelude          hiding ( length, replicate, zip, unzip, enumFromTo, concat )
 
+
 -- NOTE: 
 -- Most of these functions just export the corresponding "vectorised" 
 -- function from "Data.Array.Parallel.Lifted.Closure". We don't export
index 0a0788e..7ba6c2c 100644 (file)
@@ -24,7 +24,8 @@ module Data.Array.Parallel.PArray.Scalar (
 )
 where
 import Data.Array.Parallel.PArray.PData
-import Data.Array.Parallel.Base                 (intToTag, traceF )
+import Data.Array.Parallel.Base
+import Data.Array.Parallel.Base.DTrace
 import qualified Data.Array.Parallel.Unlifted   as U
 import GHC.Exts                                 (Int(..))
 
index b8bf464..215108a 100644 (file)
@@ -202,7 +202,7 @@ class PR a where
   --        instead of going via a SSegd.
   extractvsPR    :: PDatas a -> U.VSegd -> PData a
   extractvsPR pdatas vsegd
-        = extractssPR pdatas (U.demoteToSSegdOfVSegd vsegd)
+        = extractssPR pdatas (U.unsafeDemoteToSSegdOfVSegd vsegd)
   
   -- Pack and Combine ---------------------------
   -- | Select elements of an array that have their corresponding tag set to
index ddddac7..ae9eabc 100644 (file)
@@ -461,7 +461,7 @@ instance PR a => PR (PArray a) where
 
   {-# INLINE_PDATA extractvsPR #-}
   extractvsPR pdatas vsegd
-   = extractssPR pdatas (U.demoteToSSegdOfVSegd vsegd)
+   = extractssPR pdatas (U.unsafeDemoteToSSegdOfVSegd vsegd)
 
                 
   -- Pack and Combine -------------------------------------
index 37be694..8772018 100644 (file)
@@ -372,7 +372,7 @@ instance (PR a, PR b) => PR (Sum2 a b)  where
 
   {-# INLINE_PDATA extractvsPR #-}
   extractvsPR pdatas vsegd
-   = extractssPR pdatas (demoteToSSegdOfVSegd vsegd)
+   = extractssPR pdatas (unsafeDemoteToSSegdOfVSegd vsegd)
 
 
   -- Pack and Combine ---------------------------
index f041c12..58cea0f 100644 (file)
@@ -1,20 +1,19 @@
 {-# LANGUAGE TypeOperators, CPP #-}
 
 -- | WARNING: 
---   This is a fake module and most of the functions here will just 
---   `error` if called. 
+--   This is an abstract interface. All the functions will just `error` if called. 
 --
---   This "dph-prim-interface" module provides an API and a partial reference
---   implentation for the unlifted array primitives used by DPH. This code is 
---   not used during runtime.
+--   This module provides an API for the unlifted array primitives used by DPH.
+--   None of the functions here have implementations.
 --
---  Client programs should use the @dph-prim-seq@ or @dph-prim-par@ packages
---  instead, provide the same API and contain real code.
+--   Client programs should use either the @dph-prim-seq@ or @dph-prim-par@
+--   packages, as these provide the same API and contain real code.
 --
 
---  NOTE: The API is enforced by the DPH_Header.h and DPH_Interface.h headers.
---  The dph-prim-interface, dph-prim-seq, and dph-prim-par modules all import
---  the same headers so we can be sure we're presenting the same API.
+--   NOTE: The API is enforced by the DPH_Header.h and DPH_Interface.h headers.
+--   The dph-prim-interface, dph-prim-seq, and dph-prim-par modules all import
+--   the same headers so we can be sure we're presenting the same API.
+
 #include "DPH_Header.h"
 
 import qualified Prelude as P
@@ -22,24 +21,15 @@ import Prelude ( Eq(..), Num(..), Bool(..), ($), (.) )
 
 #include "DPH_Interface.h"
 
--- NOTE -----------------------------------------------------------------------
--- See DPH_Interface.h for documentation. 
---   As these functions are defined multiple times in different packages, 
---   we keep all the docs there.
---
--- The definitions should appear in the same order as they are defined in DPH_Interface.h
---
-#define ASSERT assert __FILE__ __LINE__
-
-assert :: P.String -> Int -> Bool -> a -> a
-assert file line False _
-  = P.error $ file P.++ " (line " P.++ P.show line P.++ "): assertion failure"
-assert _ _ _ x = x
 
+------------------------------------------------------------------------------
 notImplemented :: P.String -> a
 notImplemented fnName
- = P.error $ "Not implemented: dph-prim-interface:Data.Array.Parallel.Unlifted."
-   P.++ fnName
+ = P.error $ P.unlines
+ [ "dph-prim-interface:Data.Array.Parallel.Unlifted." P.++ fnName
+ , "This module is an abstract interface and does not contain real code."
+ , "Use dph-prim-seq or dph-prim-par instead." ]
+{-# NOINLINE notImplemented #-}
 
 
 -- Types ----------------------------------------------------------------------
@@ -49,131 +39,86 @@ type Array a    = [a]
 
 
 -- Constructors ---------------------------------------------------------------
-empty   = []
-
-(+:+)   = (P.++)
-
-append_s _ xd xs yd ys 
-        = P.concat (P.zipWith (P.++) (nest xd xs) (nest yd ys))
-
-replicate
-        = P.replicate
-
-replicate_s segd xs
-        = P.concat
-        $ zipWith replicate (lengthsSegd segd) xs
-
-replicate_rs n xs
-        = P.concat
-        $ P.map (P.replicate n) xs
-
-repeat n _ xs
-        = P.concat (replicate n xs)
-
-indexed xs
-        = zip [0 .. length xs - 1] xs
-
-indices_s segd
-        = P.concat [[0 .. n-1] | n <- segd_lengths segd] 
-
-enumFromTo m n          = [m .. n]
-enumFromThenTo m n s    = [m, n..s]
-enumFromStepLen i k 0   = []
-enumFromStepLen i k n   = i : enumFromStepLen (i+k) k (n-1)
-
-enumFromStepLenEach size starts steps lens
-  = ASSERT (size == sum lens)
-    P.concat
-  $ P.zipWith3 (\x y z -> P.enumFromThenTo x (x+y) (x+y*z)) starts steps lens
+empty                           = notImplemented "empty"
+(+:+)                           = notImplemented "(+:+)"
+append_s                        = notImplemented "append_s"
+replicate                       = notImplemented "replicate"
+replicate_s                     = notImplemented "replicate_s"
+replicate_rs                    = notImplemented "replicate_rs"
+repeat                          = notImplemented "repeat"
+indexed                         = notImplemented "indexed"
+indices_s                       = notImplemented "indices_s"
+enumFromTo                      = notImplemented "enumFromTo"
+enumFromThenTo                  = notImplemented "enumFromThenTo"
+enumFromStepLen                 = notImplemented "enumFromStepLen"
+enumFromStepLenEach             = notImplemented "enumFromStepLenEach"
+
+
+-- Conversions ----------------------------------------------------------------
+nest                            = notImplemented "nest"
+toList                          = notImplemented "toList"
+fromList                        = notImplemented "fromList"
+toList_s                        = notImplemented "toList_s"
+fromList_s                      = notImplemented "fromList_s"
 
 
 -- Projections ----------------------------------------------------------------
-length          = P.length
-index _         = (P.!!)
-indexs          = notImplemented "indexs"
-indexs_avs      = notImplemented "indexs_avs"
-
-extract xs i n  = P.take n (P.drop i xs)
-extracts_nss    = notImplemented "extract_nss"
-extracts_ass    = notImplemented "extract_ass"
-extracts_avs    = notImplemented "extract_avs"
-
-drop            = P.drop
+length                          = notImplemented "length"
+index                           = notImplemented "index"
+indexs                          = notImplemented "indexs"
+indexs_avs                      = notImplemented "indexs_avs"
+extract                         = notImplemented "extract"
+extracts_nss                    = notImplemented "extract_nss"
+extracts_ass                    = notImplemented "extract_ass"
+extracts_avs                    = notImplemented "extract_avs"
+drop                            = notImplemented "drop"
 
 
 -- Update ---------------------------------------------------------------------
-update          = notImplemented "update"
+update                          = notImplemented "update"
 
 
 -- Permutation ----------------------------------------------------------------
-permute         = notImplemented "permute"
-bpermute xs ns  = map (xs P.!!) ns
-mbpermute       = notImplemented "mbpermute"
-bpermuteDft     = notImplemented "bpermuteDft"
+permute                         = notImplemented "permute"
+bpermute                        = notImplemented "bpermute"
+mbpermute                       = notImplemented "mbpermute"
+bpermuteDft                     = notImplemented "bpermuteDft"
 
 
 -- Zipping and Unzipping ------------------------------------------------------
-zip             = P.zip
-zip3            = P.zip3
-unzip           = P.unzip
-unzip3          = P.unzip3
-fsts            = map P.fst
-snds            = map P.snd
+zip                             = notImplemented "zip"
+zip3                            = notImplemented "zip3"
+unzip                           = notImplemented "unzip"
+unzip3                          = notImplemented "unzip3"
+fsts                            = notImplemented "fsts"
+snds                            = notImplemented "snds"
 
 
 -- Map and zipWith ------------------------------------------------------------
-map             = P.map
-zipWith         = P.zipWith
+map                             = notImplemented "map"
+zipWith                         = notImplemented "zipWith"
 
 
 -- Scans and Folds -----------------------------------------------------------
-scan f z
-        = P.init . P.scanl f z
-
-fold    = P.foldr
-
-fold_s  f z segd xs
-        = P.map (P.foldr f z) (nest segd xs)
-
-fold_ss = notImplemented "fold_ss"
-
-fold_r  f z segSize xs 
-        = notImplemented "fold_r"
-
-fold1   = P.foldr1
-
-fold1_s f   segd xs
-        = P.map (P.foldr1 f)  (nest segd xs)
-
-fold1_ss = notImplemented "fold1_ss"
-
-sum     = P.sum
-
-sum_r segSize xs 
-        = notImplemented "sum_r"
-
-and     = P.and
+scan                            = notImplemented "scan"
+fold                            = notImplemented "fold"
+fold_s                          = notImplemented "fold_s"
+fold_ss                         = notImplemented "fold_ss"
+fold_r                          = notImplemented "fold_r"
+fold1                           = notImplemented "fold1"
+fold1_s                         = notImplemented "fold1_s"
+fold1_ss                        = notImplemented "fold1_ss"
+sum                             = notImplemented "sum"
+sum_r                           = notImplemented "sum_r"
+and                             = notImplemented "and"
 
 
 -- Packing and Combining ------------------------------------------------------
-pack xs bs
-        = [x | (x,b) <- P.zip xs bs, b]
-
-filter  = P.filter
-
-
--- Combine and Interleave -----------------------------------------------------
-combine [] [] [] = []
-combine (True  : bs) (x : xs) ys       = x : combine bs xs ys
-combine (False : bs) xs       (y : ys) = y : combine bs xs ys
-
-combine2 tags _ xs ys = go tags xs ys
-  where
-    go [] [] [] = []
-    go (0 : bs) (x : xs) ys = x : go bs xs ys
-    go (1 : bs) xs (y : ys) = y : go bs xs ys
-
-interleave xs ys = P.concat [[x,y] | (x,y) <- P.zip xs ys]
+pack                            = notImplemented "pack"
+filter                          = notImplemented "filter"
+combine                         = notImplemented "combine"
+combine2                        = notImplemented "combine2"
+interleave                      = notImplemented "interleave"
 
 
 -- Selectors ------------------------------------------------------------------
@@ -184,33 +129,19 @@ data Sel2
         , sel2_elements0 :: Int
         , sel2_elements1 :: Int }
 
-mkSel2 tags idxs n0 n1 _ 
-        = Sel2 tags idxs n0 n1
-
-tagsSel2        = sel2_tags
-indicesSel2     = sel2_indices
-elementsSel2_0  = sel2_elements0
-elementsSel2_1  = sel2_elements1
-repSel2 _       = ()
-
-
 type SelRep2    = ()
-mkSelRep2 _     = ()
-
-indicesSelRep2 tags _ 
-  = P.zipWith pick tags
-  $ P.init
-  $ P.scanl add (0,0) tags
-  where
-    pick 0 (i,j) = i
-    pick 1 (i,j) = j
-
-    add (i,j) 0 = (i+1,j)
-    add (i,j) 1 = (i,j+1)
 
-elementsSelRep2_0 tags _ = P.length [() | 0 <- tags]
-elementsSelRep2_1 tags _ = P.length [() | 1 <- tags]
+mkSel2                          = notImplemented "mkSel2"
+tagsSel2                        = notImplemented "tagsSel2"
+indicesSel2                     = notImplemented "indicesSel2"
+elementsSel2_0                  = notImplemented "elementsSel2_0"
+elementsSel2_1                  = notImplemented "elementsSel2_1"
+repSel2                         = notImplemented "repSel2"
 
+mkSelRep2                       = notImplemented "mkSelRep2"
+indicesSelRep2                  = notImplemented "indicesSelRep2"
+elementsSelRep2_0               = notImplemented "elementsSelRep2_0"
+elementsSelRep2_1               = notImplemented "elementsSelRep2_1"
 
 
 -- Segment Descriptors --------------------------------------------------------
@@ -220,14 +151,14 @@ data Segd
         , segd_indices  :: [Int]
         , segd_elements :: Int }
 
-mkSegd                          = Segd
-emptySegd                       = Segd [] [] 0
+mkSegd                          = notImplemented "mkSegd"
+emptySegd                       = notImplemented "emptySegd"
 singletonSegd                   = notImplemented "singletonSegd"
 validSegd                       = notImplemented "validSegd"
-lengthSegd                      = length . lengthsSegd
-lengthsSegd                     = segd_lengths
-indicesSegd                     = segd_indices
-elementsSegd                    = segd_elements
+lengthSegd                      = notImplemented "lengthSegd"
+lengthsSegd                     = notImplemented "lengthsSegd"
+indicesSegd                     = notImplemented "indicesSegd"
+elementsSegd                    = notImplemented "elementsSegd"
 
 
 -- Scattered Segment Descriptors ----------------------------------------------
@@ -237,17 +168,17 @@ data SSegd
         , ssegd_sources :: [Int]
         , ssegd_segd    :: Segd }
 
-mkSSegd                         = SSegd
+mkSSegd                         = notImplemented "mkSSegd"
 validSSegd                      = notImplemented "validSSegd"
-emptySSegd                      = SSegd [] [] emptySegd
+emptySSegd                      = notImplemented "emptySSegd"
 singletonSSegd                  = notImplemented "singletonSSegd"
 promoteSegdToSSegd              = notImplemented "promoteSegdToSSegd"
 isContiguousSSegd               = notImplemented "isContiguousSSegd"
-lengthOfSSegd                   = lengthSegd  . ssegd_segd
-lengthsOfSSegd                  = lengthsSegd . ssegd_segd
-indicesOfSSegd                  = indicesSegd . ssegd_segd
-startsOfSSegd                   = ssegd_starts
-sourcesOfSSegd                  = ssegd_sources
+lengthOfSSegd                   = notImplemented "lengthOfSSegd"
+lengthsOfSSegd                  = notImplemented "lenghtsOfSSegd"
+indicesOfSSegd                  = notImplemented "indicesOfSSegd"
+startsOfSSegd                   = notImplemented "startsOfSSegd"
+sourcesOfSSegd                  = notImplemented "sourcesOfSSegd"
 getSegOfSSegd                   = notImplemented "getSegOfSSegd"
 appendSSegd                     = notImplemented "appendSSegd"
 
@@ -258,9 +189,9 @@ data VSegd
         { vsegd_vsegids :: [Int]
         , vsegd_ssegd   :: SSegd }
 
-mkVSegd                         = VSegd
+mkVSegd                         = notImplemented "mkVSegd"
 validVSegd                      = notImplemented "validSSegd"       
-emptyVSegd                      = VSegd [] emptySSegd
+emptyVSegd                      = notImplemented "emptyVSegd"
 singletonVSegd                  = notImplemented "singletonVSegd"
 replicatedVSegd                 = notImplemented "replicatedVSegd"
 promoteSegdToVSegd              = notImplemented "promoteSegdToVSegd"
@@ -268,13 +199,13 @@ promoteSSegdToVSegd             = notImplemented "promoteSSegdToVSegd"
 isContiguousVSegd               = notImplemented "isContiguousVSegd"
 isManifestVSegd                 = notImplemented "isManifestVSegd"
 lengthOfVSegd                   = notImplemented "lengthOfVSegd"
-takeVSegidsOfVSegd              = vsegd_vsegids
-takeVSegidsRedundantOfVSegd     = vsegd_vsegids
-takeSSegdOfVSegd                = vsegd_ssegd
-takeSSegdRedundantOfVSegd       = vsegd_ssegd
+takeVSegidsOfVSegd              = notImplemented "takeVSegidsOfVSegd"
+takeVSegidsRedundantOfVSegd     = notImplemented "takeVSegidsRedundantOfVSegd"
+takeSSegdOfVSegd                = notImplemented "takeSSegdOfVSegd"
+takeSSegdRedundantOfVSegd       = notImplemented "takeSSegdRedundantOfVSegd"
 takeLengthsOfVSegd              = notImplemented "takeLengthsOfVSegd"
 getSegOfVSegd                   = notImplemented "getSegOfVSegd"
-demoteToSSegdOfVSegd            = notImplemented "demoteToSSegdOfVSegd"
+unsafeDemoteToSSegdOfVSegd      = notImplemented "unsafeDemoteToSSegdOfVSegd"
 unsafeDemoteToSegdOfVSegd       = notImplemented "unsafeDemoteToSegdOfVSegd"
 updateVSegsOfVSegd              = notImplemented "updateVSegsOfVSegd"
 updateVSegsReachableOfVSegd     = notImplemented "updateVSegsReachableOfVSegd"
@@ -282,9 +213,11 @@ appendVSegd                     = notImplemented "appendVSegd"
 combine2VSegd                   = notImplemented "combine2VSegd"
 
 
--- 2D Arrays ------------------------------------------------------------------
+-- Irregular two dimensional arrays -------------------------------------------
 class Elts a
-type Arrays a                   = [[a]]
+type Arrays a
+        = [[a]]
+
 emptys                          = notImplemented "emptys"
 lengths                         = notImplemented "lengths"
 singletons                      = notImplemented "singletons"
@@ -296,27 +229,12 @@ toVectors                       = notImplemented "toVectors"
 
 
 -- Random Arrays --------------------------------------------------------------
-randoms n       = P.take n . System.Random.randoms
-randomRs n r    = P.take n . System.Random.randomRs r
+randoms n                       = notImplemented "randoms"
+randomRs n r                    = notImplemented "randomRs"
 
 
 -- Array IO -------------------------------------------------------------------
 class Elt a => IOElt a
-hPut            = notImplemented "hPut"
-hGet            = notImplemented "hGet"
-
-toList x        = x
-fromList x      = x
-
-
--- Other Stuff ----------------------------------------------------------------
-nest :: Segd -> [a] -> [[a]]
-nest (Segd ns is _) xs = go ns xs
-  where
-    go [] [] = []
-    go (n : ns) xs = let (ys, zs) = P.splitAt n xs
-                     in ys : go ns zs
-
-toList_s x      = x
-fromList_s x    = x
+hPut                            = notImplemented "hPut"
+hGet                            = notImplemented "hGet"
 
index 63fff30..eefb150 100644 (file)
@@ -5,13 +5,13 @@ module Data.Array.Parallel.Unlifted (
   -- * Types
   Elt,  Array,
   
-  -- * Array Constructors
+  -- * Constructors
   empty,
-  (+:+),     append_s,
+  generate,
   replicate, replicate_s, replicate_rs,
   repeat,
   indexed,
-  generate,
+  (+:+),     append_s,
   indices_s,
   enumFromTo,
   enumFromThenTo,
@@ -47,13 +47,13 @@ module Data.Array.Parallel.Unlifted (
   -- * Map and ZipWith
   map, zipWith, zipWith3, zipWith4,
 
-  -- * Folds and Scans
+  -- * Scans and Folds
+  scan,
   fold,  fold_s,  fold_ss,   fold_vs, fold_r,  
   fold1, fold1_s, fold1_ss,  fold1_vs,
   sum,   sum_s,   sum_ss,    sum_r,  
   count, count_s, count_ss,
   and, 
-  scan,
 
   -- * Pack and Filter
   pack,
@@ -75,6 +75,7 @@ module Data.Array.Parallel.Unlifted (
   repSel2,
   tagsToSel2,
   
+  -- * Selector Representations
   SelRep2,
   mkSelRep2,
   indicesSelRep2,
@@ -128,15 +129,14 @@ module Data.Array.Parallel.Unlifted (
   takeSSegdRedundantOfVSegd,
   takeLengthsOfVSegd,
   getSegOfVSegd,
-  demoteToSSegdOfVSegd,
+  unsafeDemoteToSSegdOfVSegd,
   unsafeDemoteToSegdOfVSegd,
   updateVSegsOfVSegd,
   updateVSegsReachableOfVSegd,
   appendVSegd,
   combine2VSegd,
   
-
-  -- * Irregular two dimensional arrays.
+  -- * Irregular two dimensional arrays
   Elts, Arrays,
   emptys,
   singletons,
@@ -160,4 +160,4 @@ import System.IO                  (IO, Handle)
 import Data.Word                  (Word8)
 import qualified System.Random
 import qualified Prelude
-import qualified Data.Vector    as VV
+import qualified Data.Vector       as VV
index 9922310..3b6ee16 100644 (file)
@@ -1,6 +1,6 @@
-import Data.Array.Parallel.Base ( Tag, tagToInt, fromBool )
+import Data.Array.Parallel.Base (Tag, tagToInt, fromBool)
 import qualified GHC.Base
-import Prelude ((.), ($), Num(..), Eq(..), seq, snd)
+import Prelude                  ((.), ($), Num(..), Eq(..), seq, snd)
 import qualified Prelude
 
 instance Elt Int
@@ -19,9 +19,11 @@ infixl 9 `index`
 infixr 5 +:+
 
 -- TRAGIC HACKS ===============================================================
--- FIXME: These are the SMVM rules. They are intentionally quite specific and
--- we want to get rid of the ASAP.
-
+-- These hacky rules solve the replicate problem for the SMVM benchmark, 
+-- with dph-lifted-copy but are very fragile and ad-hoc.
+--
+-- Programs written with the new dph-lifted-vseg library don't need rules like
+-- this, so we should dump them at some stage.
 {-# RULES
 
 "map/zipWith (+)/enumFromStepLen" forall m n is.
@@ -56,44 +58,28 @@ infixr 5 +:+
 -- ============================================================================
 
 
-
 -- Constructors ===============================================================
 -- | O(1). Construct an array with no elements.
 empty :: Elt a => Array a
 {-# INLINE_BACKEND empty #-}
 
 
--- Append -----------------------------
--- | O(n). Append two arrays.
-(+:+) :: Elt a => Array a -> Array a -> Array a
-{-# INLINE_BACKEND (+:+) #-}
-
-
--- | Segmented append.
-append_s 
-        :: Elt a
-        => Segd         -- ^ Segment descriptor of result aarray.
-        -> Segd         -- ^ Segment descriptor of first array.
-        -> Array a      -- ^ Data of first array.
-        -> Segd         -- ^ Segment descriptor of second array.
-        -> Array a      -- ^ Data of second array.
-        -> Array a
-{-# INLINE_BACKEND append_s #-}
-
-
-{-# RULES
+-- Generate ---------------------------
+-- | Generate a new array given its length and a function to compute each element.
+generate :: Elt a => Int -> (Int -> a) -> Array a
+generate n f = map f (enumFromTo 0 (n-1))
+{-# INLINE_BACKEND generate #-}
 
-"append_s->interleave" forall n k idxs1 idxs2 idxs3 m1 m2 m3 xs ys.
-  append_s (mkSegd (replicate n k) idxs1 m1)
-           (mkSegd (replicate n (GHC.Base.I# 1#)) idxs2 m2) xs
-           (mkSegd (replicate n (GHC.Base.I# 1#)) idxs3 m3) ys
-    = interleave xs ys
 
-  #-}
+generate_cheap :: Elt a => Int -> (Int -> a) -> Array a
+generate_cheap n f = map f (enumFromTo 0 (n-1))
+{-# INLINE_BACKEND generate_cheap #-}
 
 
 -- Replicate --------------------------
--- | O(n). Construct a new array by replicating a single element the given number of times.
+-- | O(length result). 
+--   Construct a new array by replicating a single element the given
+--   number of times.
 replicate :: Elt a => Int -> a -> Array a
 {-# INLINE CONLIKE PHASE_BACKEND replicate #-}
 
@@ -105,12 +91,17 @@ replicate :: Elt a => Int -> a -> Array a
  #-}
 
 
--- | O(n). Segmented replicate.
+-- | O(length result). Segmented replicate.
+--
+--   Elements of the array are replicated according to the lengths of the 
+--   segments defined by the `Segd`.
 replicate_s :: Elt a => Segd -> Array a -> Array a
 {-# INLINE CONLIKE PHASE_BACKEND replicate_s #-}
 
 
--- | O(n). Regular segmented replicate. All segments have the given length.
+-- | O(length result). Regular segmented replicate.
+-- 
+--   Like `replicate_s`, but all segments are assumed to have the given length.
 replicate_rs :: Elt a => Int -> Array a -> Array a
 {-# INLINE CONLIKE PHASE_BACKEND replicate_rs #-}
 
@@ -134,9 +125,8 @@ replicate_rs :: Elt a => Int -> Array a -> Array a
  #-}
 
 
-
 -- Repeat -----------------------------
--- | O(n). Construct an array by copying a portion of another array.
+-- | O(length result). Construct an array by copying a portion of another array.
 repeat  :: Elt a 
         => Int          -- ^ Number of times to repeat the source.
         -> Int          -- ^ Length of source (can be less than the provided array).
@@ -154,27 +144,51 @@ repeat  :: Elt a
   #-}
 
 
+-- Append -----------------------------
+-- | O(length result). Append two arrays.
+(+:+) :: Elt a => Array a -> Array a -> Array a
+{-# INLINE_BACKEND (+:+) #-}
+
+
+-- | O(length result). Segmented append.
+append_s 
+        :: Elt a
+        => Segd         -- ^ Segment descriptor of result aarray.
+        -> Segd         -- ^ Segment descriptor of first array.
+        -> Array a      -- ^ Data of first array.
+        -> Segd         -- ^ Segment descriptor of second array.
+        -> Array a      -- ^ Data of second array.
+        -> Array a
+{-# INLINE_BACKEND append_s #-}
+
+
+{-# RULES
+
+"append_s->interleave" forall n k idxs1 idxs2 idxs3 m1 m2 m3 xs ys.
+  append_s (mkSegd (replicate n k) idxs1 m1)
+           (mkSegd (replicate n (GHC.Base.I# 1#)) idxs2 m2) xs
+           (mkSegd (replicate n (GHC.Base.I# 1#)) idxs3 m3) ys
+    = interleave xs ys
+
+  #-}
+
+
 -- Indexed ----------------------------
--- | O(n). Tag each element of an array with its index.
+-- | O(length result). Tag each element of an array with its index.
 --
 --   @indexed [42, 93, 13] = [(0, 42), (1, 93), (2, 13)]@ 
 indexed :: Elt a => Array a -> Array (Int, a)
 {-# INLINE_BACKEND indexed #-}
 
 
--- Generate ---------------------------
--- | Generate a new array given its length and a function to compute each element.
-generate :: Elt a => Int -> (Int -> a) -> Array a
-{-# INLINE_BACKEND generate #-}
-generate n f = map f (enumFromTo 0 (n-1))
-
-generate_cheap :: Elt a => Int -> (Int -> a) -> Array a
-{-# INLINE_BACKEND generate_cheap #-}
-generate_cheap n f = map f (enumFromTo 0 (n-1))
-
-
 -- Indices ----------------------------
--- | Segmented indices. Fill an array with [0..len-1] for segment.
+-- | O(length result). Segmented indices. 
+--
+--   Construct an array containing containing the segments defined by the
+--   given `Segd`. 
+--
+--   Each segment will contain the elements @[0..len-1]@ where @len@ is the
+--   length of that segment.
 indices_s :: Segd -> Array Int
 {-# INLINE_BACKEND indices_s #-}
 
@@ -194,17 +208,21 @@ enumFromStepLenEach :: Int -> Array Int -> Array Int -> Array Int -> Array Int
 
 
 -- Projections ================================================================
--- | O(1). Take the number of elements in an array.
+-- | O(1). Yield the number of elements in an array.
 length :: Elt a => Array a -> Int
 {-# INLINE_BACKEND length #-}
 
 
 -- | O(1). Retrieve a numbered element from an array.
+-- 
+--   The first argument gives a source-code location for out-of-bounds errors.
 index :: Elt a => Prelude.String -> Array a -> Int -> a
 {-# INLINE_BACKEND index #-}
 
 
--- | O(n). Scattered indexing from a single `Array`
+-- | O(length result). Scattered indexing from a single `Array`.
+-- 
+--   This is an alias for `bpermute`.
 indexs  :: Elt a
         => Array a
         -> Array Int
@@ -212,17 +230,24 @@ indexs  :: Elt a
 {-# INLINE_BACKEND indexs #-}
 
 
--- | O(n). Scattered indexing through a `VSegd`.
+-- | O(length result). Scattered indexing through a `VSegd`.
+--
+--   The index array contains pairs of segment id and the index within that 
+--   segment. 
+-- 
+--   We use the `VSegd` to map the pairs to 2D indices within the `Arrays`, 
+--   and return an array of the resulting elements.
 indexs_avs
         :: (Elt a, Elts a)
-        => Arrays a
-        -> VSegd
-        -> Array (Int, Int)
+        => Arrays a             -- ^ Irregular 2D array of elements.
+        -> VSegd                -- ^ Maps (segment id, segment index) pairs 
+                                --   to 2D indices in the `Arrays`
+        -> Array (Int, Int)     -- ^ Pairs of (segment id, segment index).
         -> Array a
 {-# INLINE_BACKEND indexs_avs #-}
 
 
--- | O(n). Extract a subrange of elements from an array.
+-- | O(length result). Extract a subrange of elements from an array.
 --  
 --   @extract [23, 42, 93, 50, 27] 1 3  = [42, 93, 50]@
 extract :: Elt a
@@ -233,9 +258,10 @@ extract :: Elt a
 {-# INLINE_BACKEND extract #-}
 
 
--- | O(n). Segmented extract, from a vector of arrays.
---   TODO: This is a transitory interface, we are refactoring code to always
---         use the `Arrays` form.
+-- | O(length result). Extract segments defined by a `SSegd` from a vector of arrays.
+--
+--   NOTE: This is a transitory interface, and will be removed in future versions.
+--         Use `extracts_ass` instead.
 extracts_nss
         :: Elt a
         => SSegd
@@ -244,7 +270,10 @@ extracts_nss
 {-# INLINE_BACKEND extracts_nss #-}
 
 
--- | O(n). Segmented extract.
+-- | O(length result). Extract segments defined by a `SSegd`.
+--
+--   Extract all the segments defined by the `SSegd` from the `Arrays`,
+--   returning them concatenated in a fresh `Array`.
 extracts_ass
         :: (Elt a, Elts a)
         => SSegd        -- ^ `SSegd` defining the slices to extract.
@@ -253,7 +282,10 @@ extracts_ass
 {-# INLINE_BACKEND extracts_ass #-}
 
 
--- | O(n). Segmented extract.
+-- | O(length result). Extract segments defined by a `VSegd`.
+--
+--   Extract all the segments defined by the `VSegd` from the `Arrays`,
+--   returning them concatenated in a fresh `Array`.
 extracts_avs
         :: (Elt a, Elts a)
         => VSegd        -- ^ `VSegd` defining the slices to extract.
@@ -262,7 +294,7 @@ extracts_avs
 {-# INLINE_BACKEND extracts_avs #-}
 
 
--- | O(n). Drop some elements from the front of an array, 
+-- | O(length result). Drop elements from the front of an array, 
 --         returning the latter portion.
 drop :: Elt a => Int -> Array a -> Array a
 {-# INLINE_BACKEND drop #-}
@@ -278,14 +310,18 @@ drop :: Elt a => Int -> Array a -> Array a
 
 
 -- Update =====================================================================
--- | O(n). Copy the source array in the destination, using new values for the
---         given indices.
-update :: Elt a => Array a -> Array (Int, a) -> Array a
+-- | O(length result). 
+--   Copy the source array while replacing some elements by new ones in the result.
+update  :: Elt a 
+        => Array a              -- ^ Source array.
+        -> Array (Int, a)       -- ^ Index and value of new elements.
+        -> Array a
 {-# INLINE_BACKEND update #-}
 
 
 -- Permutation ================================================================
--- | O(n). Forwards permutation of array elements.
+-- | O(length result). Forwards permutation of array elements.
+--
 permute :: Elt a 
         => Array a      -- ^ Source array.
         -> Array Int    -- ^ Indices in the destination to copy elements to.
@@ -293,21 +329,21 @@ permute :: Elt a
 {-# INLINE_BACKEND permute #-}
 
 
--- | O(n). Backwards permutation of array elements.
+-- | O(length result). Backwards permutation of array elements.
 --
---   @bpermute [50, 60, 20, 30] 3 [0, 3, 2]  = [50, 30, 20]@
+--   @bpermute [50, 60, 20, 30] [0, 3, 2] = [50, 30, 20]@
 bpermute 
         :: Elt a 
-        => Array a      -- ^ source array
-        -> Array Int    -- ^ indices in the source to copy elements from.
+        => Array a      -- ^ Source array.
+        -> Array Int    -- ^ Indices in the source to copy elements from.
         -> Array a
 {-# INLINE_BACKEND bpermute #-}
 
 
 -- | Combination of map and bpermute.
 --
---   The advantage of using this combined version is that we dont need
---   to apply the parameter function to source elements that dont appear
+--   The advantage of using this combined version is that we don't need
+--   to apply the parameter function to source elements that don't appear
 --   in the result.
 mbpermute :: (Elt a, Elt b) => (a->b) -> Array a -> Array Int -> Array b
 {-# INLINE_BACKEND mbpermute #-}
@@ -385,21 +421,22 @@ zipWith :: (Elt a, Elt b, Elt c)
 -- | Apply a worker function to corresponding elements of three arrays.
 zipWith3 :: (Elt a, Elt b, Elt c, Elt d)
           => (a -> b -> c -> d) -> Array a -> Array b -> Array c -> Array d
-{-# INLINE zipWith3 #-}
 zipWith3 f xs ys zs
         = zipWith (\(x, y) z -> f x y z)
                   (zip xs ys)
                   zs
+{-# INLINE zipWith3 #-}
+
 
 -- | Apply a worker function to corresponding elements of four arrays.
 zipWith4 :: (Elt a, Elt b, Elt c, Elt d, Elt e)
          => (a -> b -> c -> d -> e)
          -> Array a -> Array b -> Array c -> Array d -> Array e
-{-# INLINE zipWith4 #-}
 zipWith4 f as bs cs ds
          = zipWith (\(a, b) (c, d) -> f a b c d)
                    (zip as bs)
                    (zip cs ds)
+{-# INLINE zipWith4 #-}
 
 
 {-# RULES
@@ -420,9 +457,15 @@ zipWith4 f as bs cs ds
   #-}
 
 
-
 -- Folds and Scans ============================================================
 
+-- Scans ------------------------------
+-- | Similar to `foldl` but return an array of the intermediate states, including
+--   the final state that is computed by `foldl`.
+scan :: Elt a => (a -> a -> a) -> a -> Array a -> Array a
+{-# INLINE_BACKEND scan #-}
+
+
 -- Fold -------------------------------
 -- | Undirected fold over an array.
 --
@@ -435,27 +478,43 @@ fold :: Elt a => (a -> a -> a) -> a -> Array a -> a
 {-# INLINE_BACKEND fold #-}
 
 
--- | Undirected segmented fold.
+-- | Undirected segmented fold. 
+-- 
+--   All segments are folded individually, and the result contains one
+--   element for each segment. 
+--
 --   Same preconditions as `fold`.
 fold_s :: Elt a => (a -> a -> a) -> a -> Segd -> Array a -> Array a
 {-# INLINE_BACKEND fold_s #-}
 
 
 -- | Undirected scattered segmented fold.
+--
+--   Like `fold_s`, but the segments can be scattered through an `Arrays`. 
+--
 --   Same preconditions as `fold`.
 fold_ss :: (Elts a, Elt a)
         => (a -> a -> a) -> a -> SSegd -> Arrays a -> Array a
 {-# INLINE_BACKEND fold_ss #-}
 
 
--- | Regular segmented fold. All segements have the given length.
+-- | Regular segmented fold. 
+--
+--   All segements have the given length.
+--
 --   Same preconditions as `fold`.
 fold_r :: Elt a => (a -> a -> a) -> a -> Int -> Array a -> Array a
 {-# INLINE_BACKEND fold_r #-}
 
 
 -- | Undirected fold over virtual segments.
---   Same preconditions as fold_ss
+--
+--   The physical segments defined by the `VSegd` are folded individually, 
+--   and these results are replicated according to the virtual segment
+--   id table of the `VSegd`. The result contains as many elements as there
+--   virtual segments.
+--
+--   Same preconditions as `fold`.
 fold_vs :: (Elts a, Elt a)
          => (a -> a -> a) -> a -> VSegd -> Arrays a -> Array a
 fold_vs f x vsegd arrs
@@ -487,33 +546,40 @@ fold_vs f x vsegd arrs
 
 
 -- Fold1 -------------------------------
--- | Undirected fold,
---   using the first element to initialise the state.
---   If the array contains no elements then you'll get a bounds check `error`.
---   Same preconditions as `fold`.
+-- | Undirected fold, using the first element to initialise the state.
+--
+--   * The worker function must be associative.
+--
+--   * The provided starting element must be neutral with respect to the worker.
+--     For example 0 is neutral wrt (+) and 1 is neutral wrt (*).
+--
+--   * If the array contains no elements then you'll get a bounds check `error`.
+--
 fold1 :: Elt a => (a -> a -> a) -> Array a -> a
 {-# INLINE_BACKEND fold1 #-}
 
 
--- | Undirected segmented fold,
---    using the first element of each segment to initialise the state of
---    that segment.
---   Same preconditions as `fold`.
+-- | Like `fold_s`, but using the first element of each segment to initialise
+--   the state of that segment.
+--
+--   Same preconditions as `fold1`.
 fold1_s :: Elt a => (a -> a -> a) -> Segd -> Array a -> Array a
 {-# INLINE_BACKEND fold1_s #-}
 
 
--- | Undirected scattered segmented fold,
----   using the first element of each segment to initialise the state of
---    that segment.
---   Same preconditions as `fold`.
+-- | Like `fold_ss`, but using the first element of each segment to intialise 
+--   the state of that segment.
+--
+--   Same preconditions as `fold1`.
 fold1_ss :: (Elts a, Elt a) 
          => (a -> a -> a) -> SSegd -> Arrays a -> Array a
 {-# INLINE_BACKEND fold1_ss #-}
 
 
--- | Undirected fold over virtual segments.
---   Same preconditions as fold_ss
+-- | Like `fold_vs`, but using the first element of each segment to initialise 
+--   the state of that segment.
+--
+--   Same preconditions as `fold1`.
 fold1_vs :: (Elts a, Elt a)
          => (a -> a -> a)  -> VSegd -> Arrays a -> Array a
 fold1_vs f vsegd arrs
@@ -543,23 +609,24 @@ fold1_vs f vsegd arrs
 
  #-}
 
+
 -- Sums -------------------------------
--- | Sum the elements of an array.
+-- | Same as @fold (+) 0@
 sum :: (Num a, Elt a) => Array a -> a
 {-# INLINE_BACKEND sum #-}
 
--- | Segmented sum.
+-- | Same as @fold_s (+) 0@
 sum_s :: (Num a, Elt a) => Segd -> Array a -> Array a
 sum_s = fold_s (Prelude.+) 0
 {-# INLINE sum_s #-}
 
--- | Scattered segmented sum.
+-- | Same as @fold_ss (+) 0@
 sum_ss :: (Num a, Elts a, Elt a) 
        => SSegd -> Arrays a -> Array a
 sum_ss = fold_ss (Prelude.+) 0
 {-# INLINE sum_ss #-}
 
--- | Regular segmented sum. All segments have the given length.
+-- | Same as @fold_r (+) 0@
 sum_r :: (Num a, Elt a) => Int -> Array a -> Array a
 {-# INLINE_BACKEND sum_r #-}
 
@@ -579,8 +646,9 @@ count_s segd xs !x
 
 
 -- | Scattered segmented count.
-
---   TODO: Make this take Arrays directly.
+--
+--   NOTE: This is a transitory interface, and will be removed in future versions.
+---  TODO: Make this take an `Arrays` instead of a Vector.
 count_ss :: (Elt a, Eq a) => SSegd -> VV.Vector (Array a) -> a -> Array Int
 {-# INLINE_BACKEND count_ss #-}
 count_ss ssegd xs !x
@@ -588,20 +656,10 @@ count_ss ssegd xs !x
 
 
 -- And --------------------------------
--- | Compute the conjunction of all elements in a boolean array.
+-- | O(length source). Compute the conjunction of all elements in a boolean array.
 and :: Array Bool -> Bool
 {-# INLINE_BACKEND and #-}
 
-
--- Scans ------------------------------
--- | Similar to `foldl` but return an array of the intermediate states, including
---   the final state that is computed by `foldl`.
-scan :: Elt a => (a -> a -> a) -> a -> Array a -> Array a
-{-# INLINE_BACKEND scan #-}
-
-
-
-
 {-# RULES
 
 "seq/sum" forall xs e.
@@ -634,12 +692,14 @@ scan :: Elt a => (a -> a -> a) -> a -> Array a -> Array a
 
 
 -- Pack and Filter ============================================================
--- | Extract elements of an array where the associated flag is true.
+-- | O(length result).
+--   Extract elements of an array where the associated flag is true.
 pack :: Elt a => Array a -> Array Bool -> Array a
 {-# INLINE_BACKEND pack #-}
 
 
--- | Select the elements of an array that have a corresponding tag.
+-- | O(length result).
+--   Select the elements of an array that have a corresponding tag.
 --   
 --   @packByTag [12, 24, 42, 93] [1, 0, 0, 1] 0 = [24, 42]@
 --
@@ -650,9 +710,9 @@ packByTag
         -> Tag          -- ^ the tag of values to select
         -> Array a      -- ^ data values that had that tag
 
-{-# INLINE_BACKEND packByTag #-}
 packByTag xs tags !tag
         = fsts (filter (\p -> Prelude.snd p == tag) (zip xs tags))
+{-# INLINE_BACKEND packByTag #-}
 
 
 -- | Extract the elements from an array that match the given predicate.
@@ -663,8 +723,8 @@ filter :: Elt a => (a -> Bool) -> Array a -> Array a
 --
 --   @pick [4, 5, 3, 6, 5, 2, 5] 5 = [F, T, F, F, T, F, T]@
 pick :: (Elt a, Eq a) => Array a -> a -> Array Bool
-{-# INLINE pick #-}
 pick xs !x = map (x ==) xs
+{-# INLINE pick #-}
 
 
 {-# RULES
@@ -688,7 +748,8 @@ pick xs !x = map (x ==) xs
 
 
 -- Combine and Interleave =====================================================
--- | Combine two arrays, using a tag array to tell us where to get each element from.
+-- | Combine two arrays, 
+--    using a flags array to tell us where to get each element from.
 --
 --   @combine [T, F, F, T, T, F] [1, 2, 3] [4, 5, 6] = [1, 4, 5, 2, 3, 6]@
 combine :: Elt a => Array Bool -> Array a -> Array a -> Array a
@@ -697,9 +758,8 @@ combine :: Elt a => Array Bool -> Array a -> Array a -> Array a
 
 -- | Like `combine`, but use a precomputed selector to speed up the process.
 -- 
---   See dph-prim-seq:"Data.Array.Parallel.Unlifted.Sequential.Segmented.USel"
---   for a description of how this works.
---   
+--   See the description of `mkSel2` for how this works.
+--
 combine2 :: Elt a => Array Tag -> SelRep2 -> Array a -> Array a -> Array a
 {-# INLINE_BACKEND combine2 #-}
 
@@ -713,80 +773,165 @@ interleave :: Elt a => Array a -> Array a -> Array a
 
 -- Selectors ==================================================================
 -- | O(1). Construct a selector.
+--
+--   A selector is a description of how to perform a `combine` operation.
+--
+--   Suppose we are evaluating the following expression:
+--
+--    @combine [F,F,T,F,T,T] [1,2,3] [4,5,6] = [4,5,1,6,2,3]@
+--
+--   This is difficult to parallelise. For each element in the result, the
+--   source array we get this element from depends on the tag values associated
+--   with all previous elements.
+--
+--   However, if we going to apply `combine` several times with the same flags array, 
+--   we can precompute a selector that tells us where to get each element. 
+--   The selector contains the original flags, as well as the source index telling
+--   us where to get each element for the result array.
+--
+--   For example:
+--
+--   @tagsToIndices2 [F,F,T,F,T,T]   -- tags
+--             = [0,1,0,2,1,2]   -- indices
+--   @
+--
+--    This says get the first element from index 0 in the second array, 
+--     then from index 1 in the second array,
+--     then index 0 in the first array ...
+--  
+--    The selector then consists of both the @tag@ and @indices@ arrays.
+--
 mkSel2  :: Array Tag            -- ^ Tags array.
         -> Array Int            -- ^ Indices array.
         -> Int                  -- ^ Number of elements taken from first source array.
         -> Int                  -- ^ Number of elements taken from second source array.
-        -> SelRep2      
+        -> SelRep2              -- ^ Parallel selector representation.
         -> Sel2
 {-# INLINE CONLIKE PHASE_BACKEND mkSel2 #-}
 
 
--- | O(1). Get the tags array of a selector.
+-- | O(1). Yield the tags array of a selector.
 tagsSel2 :: Sel2 -> Array Tag
 {-# INLINE_BACKEND tagsSel2 #-}
 
 
--- | O(1). Get the indices array of a selector.
+-- | O(1). Yield the indices array of a selector.
 indicesSel2 :: Sel2 -> Array Int
 {-# INLINE_BACKEND indicesSel2 #-}
 
 
--- | O(1). Get the number of elements that will be taken from the first array.
+-- | O(1). Yield the number of elements that will be taken from the first array.
 elementsSel2_0 :: Sel2 -> Int
 {-# INLINE_BACKEND elementsSel2_0 #-}
 
 
--- | O(1). Get the number of elements that will be taken from the second array.
+-- | O(1). Yield the number of elements that will be taken from the second array.
 elementsSel2_1 :: Sel2 -> Int
 {-# INLINE_BACKEND elementsSel2_1 #-}
 
 
--- | O(1). Take the `SelRep2` from a `Sel2`.
+-- | O(1). Yield the parallel representation of a selector.
 repSel2 :: Sel2 -> SelRep2
 {-# INLINE_BACKEND repSel2 #-}
 
 
--- | O(n). Construct a `SelRep2`.
+-- Selector Representations ===================================================
+-- | O(n). Construct a parallel selector representation.
+--
+--   A `SelRep2` describes how to distribute the two data vectors
+--   corresponding to a `Sel2` across several PEs.
+--
+--   Suppose we want to perform the following `combine` operation:
+--
+-- @
+-- combine [F,F,T,T,F,T,F,F,T] [A0,A1,A2,A3,A4] [B0,B1,B2,B3] 
+--   = [A0,A1,B0,B1,A2,B2,A3,A4,B3]
+-- @
+--
+--   The first array is the flags array, that says which of the data arrays to
+--   get each successive element from. As `combine` is difficult to compute
+--   in parallel, if we are going to perform several combines with the same
+--   flags array, we can precompute a selector that tells us where to get each
+--   element. The selector contains the original flags, as well as the source
+--   index telling us where to get each element for the result array.
+-- 
+-- @
+-- flags:   [F,F,T,T,F,T,F,F,T]
+-- indices: [0,1,0,1,2,2,3,4,3]
+-- @
+--
+--  Suppose we want to distribute the combine operation across 3 PEs. It's
+--  easy to split the selector like so:
+--
+-- @
+--            PE0                PE1               PE2
+-- flags:   [F,F,T]            [T,F,T]           [F,F,T] 
+-- indices: [0,1,0]            [1,2,2]           [3,4,3]
+-- @
+--
+--  We now need to split the two data arrays. Each PE needs slices of the data
+--  arrays that correspond to the parts of the selector that were given to it.
+--  For the current example we get:
+--
+-- @
+--            PE0                PE1               PE2
+-- data_A:   [A0,A1]            [A2]              [A3,A4]
+-- data_B:   [B0]               [B1,B2]           [B3]
+-- @
+--
+--  The `SelRep2` contains the starting index and length of each of of these
+--  slices:
+--
+-- @
+--            PE0                PE1               PE2
+--      ((0, 0), (2, 1))   ((2, 1), (1, 2))  ((3, 3), (2, 1))
+--       indices   lens      indices  lens    indices  lens
+-- @
+
 mkSelRep2 :: Array Tag -> SelRep2
 {-# INLINE CONLIKE PHASE_BACKEND mkSelRep2 #-}
 
 
--- | O(n). 
+-- | O(1). Take the `indices` field from a `SelRep2`.
 indicesSelRep2 :: Array Tag -> SelRep2 -> Array Int
 {-# INLINE_BACKEND indicesSelRep2 #-}
 
 
--- | O(n). Count the number of elements to take from the first array.
+-- | O(1). Yield the number of elements to take from the first array.
 elementsSelRep2_0 :: Array Tag -> SelRep2 -> Int
 {-# INLINE_BACKEND elementsSelRep2_0 #-}
 
 
--- | O(n). Count the number of elements to take from the second array.
+-- | O(1). Yield the number of elements to take from the second array.
 elementsSelRep2_1 :: Array Tag -> SelRep2 -> Int
 {-# INLINE_BACKEND elementsSelRep2_1 #-}
 
 
--- | O(n), Compute a selector from a tags array.
+-- | O(n). Compute a selector from a tags array.
 tagsToSel2 :: Array Tag -> Sel2
+tagsToSel2 tags 
+ = let rep = mkSelRep2 tags
+   in  mkSel2 tags (indicesSelRep2    tags rep)
+                   (elementsSelRep2_0 tags rep)
+                   (elementsSelRep2_1 tags rep)
+                   rep
 {-# INLINE tagsToSel2 #-}
-tagsToSel2 tags = let rep = mkSelRep2 tags
-                  in
-                  mkSel2 tags (indicesSelRep2    tags rep)
-                              (elementsSelRep2_0 tags rep)
-                              (elementsSelRep2_1 tags rep)
-                              rep
+
 
 {-# RULES
 
 "tagsSel2/mkSel2"
   forall ts is n0 n1 r. tagsSel2 (mkSel2 ts is n0 n1 r) = ts
+
 "indicesSel2/mkSel2"
   forall ts is n0 n1 r. indicesSel2 (mkSel2 ts is n0 n1 r) = is
+
 "elementsSel2_0/mkSel2"
   forall ts is n0 n1 r. elementsSel2_0 (mkSel2 ts is n0 n1 r) = n0
+
 "elementsSel2_1/mkSel2"
   forall ts is n0 n1 r. elementsSel2_1 (mkSel2 ts is n0 n1 r) = n1
+
 "repSel2/mkSel2"
   forall ts is n0 n1 r. repSel2 (mkSel2 ts is n0 n1 r) = r
 
@@ -794,29 +939,33 @@ tagsToSel2 tags = let rep = mkSelRep2 tags
 
 
 -- Segment Descriptors ========================================================
--- | O(max(segs, threads) . log segs). Construct a segment desciprtor from an
---   array of segment lengths, starting indices, and total number of elements.
+-- | O(max(segs, threads) . log segs). Construct a segment descriptor.
 --
 --   A segment desciptor defines an irregular 2D array based on a flat, 1D array
---   of elements. 
--- 
---   The defined array is an array of segments, where every segment covers
---   some of the elements from the flat array.
+--   of elements. The defined array is a nested array of segments, where every
+--   segment covers some of the elements from the flat array. 
+--
+--   * The starting indices must be equal to @init (scanl (+) 0 lengths)@
+--
+--   * If you don't want to cover all the elements from the flat arrary then
+--     use a `SSegd` instead.
+---
+--   * This ensures that the indices are monotonically increasing,
+--     and all elements from the flat array are covered by some segment.
 -- 
---   /INVARIANT:/ The segment starting indices must be monotonically increasing,
---   and all elements from the flat array must be covered by some segment.
---   This is because, in the implementation of `lengthsToSegd`, we binary
---   search the indices to determine which segment an element of the 
---   flat array belongs to. It also means that the segment indices can always
---   be reconstructed from the segment lengths by `lengthsToSegd`.
---
-mkSegd :: Array Int -> Array Int -> Int -> Segd
+--   * We need this because in the implementation of `lengthsToSegd`, we binary
+--     search the indices to determine which segment an element of the 
+--     flat array belongs to. It also means that the segment indices can always
+--     be reconstructed from the segment lengths by `lengthsToSegd`.
+--
+mkSegd  :: Array Int    -- ^ (lengths) Segment lengths.
+        -> Array Int    -- ^ (indices) Segment indices.
+        -> Int          -- ^ Total number of elements.
+        -> Segd
 {-# INLINE CONLIKE PHASE_BACKEND mkSegd #-}
 
 
 -- | Check whether a `Segd` is well formed.
---
---   * This will only return `False` if there is a bug in the library.
 validSegd :: Segd -> Bool
 {-# NOINLINE validSegd #-}
 --  NOINLINE because it's only used during debugging.
@@ -832,33 +981,33 @@ singletonSegd :: Int -> Segd
 {-# INLINE_BACKEND singletonSegd #-}
 
 
--- | O(max(segs,threads) . log segs). 
----  Construct a `Segd` from an array of segment lengths.
+-- | O(max(segs, threads) . log segs). 
+--   Construct a `Segd` from an array of segment lengths.
 lengthsToSegd :: Array Int -> Segd
 lengthsToSegd ns = mkSegd ns (scan (+) 0 ns) (sum ns)
 {-# INLINE_BACKEND lengthsToSegd #-}
 
 
--- | O(1). Take the length of a `Segd`.
+-- | O(1). Yield the length of a `Segd`.
 lengthSegd :: Segd -> Int
 {-# INLINE_BACKEND lengthSegd #-}
 
 
--- | O(1). Take the segment lengths of a `Segd`.
+-- | O(1). Yield the segment lengths of a `Segd`.
 lengthsSegd :: Segd -> Array Int
 {-# INLINE_BACKEND lengthsSegd #-}
 
 
--- | O(1). Take the segment starting indices of a `Segd`.
+-- | O(1). Yield the segment starting indices of a `Segd`.
 indicesSegd :: Segd -> Array Int
 {-# INLINE_BACKEND indicesSegd #-}
 
 
--- | O(1). Take the total number of elements defined by a `Segd`.
+-- | O(1). Yield the total number of elements defined by a `Segd`.
 elementsSegd :: Segd -> Int
 {-# INLINE_BACKEND elementsSegd #-}
 
--- | O(max(segs,threads) . log segs). 
+-- | O(max(segs, threads) . log segs). 
 --   Add the lengths of corresponding segments in two descriptors.
 --
 --   @plusSegd [lens: 2 3 1] [lens: 3 1 1] = [lens: 5 4 2]@
@@ -891,30 +1040,27 @@ plusSegd segd1 segd2
  #-}
 
 -- Scattered Segment Descriptors ==============================================
--- | Construct a Scattered Segment Descriptor from an array of source array 
---   indices, starting indices and an existing `Segd`.
+-- | Construct a Scattered Segment Descriptor.
 --
---   A `SSegd` is an extension of a `Segd` that that allows the segments to be
---     scattered through multiple flat arrays.
+--   A `SSegd` is an extension of a `Segd` that that allows the segments to be
+--   scattered through multiple flat arrays.
 --
---   Each segment is associated with a source id that indicates what 
---     flat array it is in, along with the starting index in that flat array.
+--   Each segment is associated with a source id that indicates what 
+--   flat array it is in, along with the starting index in that flat array.
 --
 --   * The segments need not cover the entire flat array.
 --
 --   * Different segments may point to the same elements.
 --
---   * As different segments may point to the same elements, it is possible
---     for the total number of elements covered by the segment descriptor
---     to overflow a machine word.
---
-mkSSegd :: Array Int -> Array Int -> Segd -> SSegd
+mkSSegd :: Array Int    -- ^ (starts)  Starting index of each segment within its flat array.
+        -> Array Int    -- ^ (sources) Source id of flat array to get each segment from. 
+        -> Segd         -- ^ Plain segment descriptor giving the lengths
+                        --   of the segments.
+        -> SSegd
 {-# INLINE CONLIKE PHASE_BACKEND mkSSegd #-}
 
 
 -- | Check whether a `Segd` is well formed.
---
---   * This will only return `False` if there is a bug in the library.
 validSSegd :: SSegd -> Bool
 {-# NOINLINE validSSegd #-}
 --  NOINLINE because it's only used during debugging.
@@ -930,14 +1076,13 @@ singletonSSegd :: Int -> SSegd
 {-# INLINE_BACKEND singletonSSegd #-}
 
 
--- | O(max(segs,threads) . log segs). Promote a `Segd` to a `SSegd`, 
+-- | O(segs). Promote a `Segd` to a `SSegd`, 
 --   assuming all segments are contiguous and come from a single array.
 promoteSegdToSSegd :: Segd -> SSegd
 {-# INLINE_BACKEND promoteSegdToSSegd #-}
 
 
--- | O(1). True when the segment starts are identical to the segment indices
---   field and the sources are all 0's. 
+-- | O(1). True when a `SSegd` has been constructed by promoting a `SSegd`.
 --
 --   In this case all the data elements are in one contiguous flat
 --   array, and consumers can avoid looking at the real starts and
@@ -946,27 +1091,27 @@ isContiguousSSegd :: SSegd -> Bool
 {-# INLINE_BACKEND isContiguousSSegd #-}
 
 
--- | O(1). Take the length of a `SSegd`.
+-- | O(1). Yield the length of a `SSegd`.
 lengthOfSSegd :: SSegd -> Int
 {-# INLINE_BACKEND lengthOfSSegd #-}
 
 
--- | O(1). Take the segment lengths of a `SSegd`.
+-- | O(1). Yield the segment lengths of a `SSegd`.
 lengthsOfSSegd :: SSegd -> Array Int
 {-# INLINE_BACKEND lengthsOfSSegd #-}
 
 
--- | O(1). Take the segment starting indices of a `SSegd`.
+-- | O(1). Yield the indices field of a `SSegd`.
 indicesOfSSegd :: SSegd -> Array Int
 {-# INLINE_BACKEND indicesOfSSegd #-}
 
 
--- | O(1). Take the segment starting indices of a `SSegd`.
+-- | O(1). Yield the starts field of a `SSegd`.
 startsOfSSegd :: SSegd -> Array Int
 {-# INLINE_BACKEND startsOfSSegd #-}
 
 
--- | O(1). Take the source ids of a `SSegd`.
+-- | O(1). Yield the sources field of a `SSegd`.
 sourcesOfSSegd :: SSegd -> Array Int
 {-# INLINE_BACKEND sourcesOfSSegd #-}
 
@@ -983,29 +1128,32 @@ appendSSegd :: SSegd -> Int -> SSegd -> Int -> SSegd
         
 
 -- Virtual Segment descriptors ================================================
--- | Construct a Virtual Segment Descriptor from an array of virtual segment
---   ids and an existing `SSegd`.
+-- | Construct a Virtual Segment Descriptor.
 --
 --   A `VSegd` is an extension of a `SSegd` that allows data from the underlying
 --   flat array to be shared between segments. For example, you can define an array
 --   of 10 virtual segments that all have the same length and elements as a
 --   single physical segment.
 --
---   Internally, we maintain the invariant that all physical segments are 
---   reachable by some virtual segment. This is needed to ensure that operations
---   such as segmented fold have the right complexity. If you don't need the 
---   invariant then you can sidestep the code that maintains it by using the
---   redundant versions of the following operators.
+--   * Internally we maintain the invariant that all physical segments must be
+--     reachable by some virtual segment. This is needed to ensure that operations
+--     such as `fold_ss` segmented fold have the right complexity. 
+--   
+--   * If you don't need the invariant then you can sidestep the code that
+--     maintains it by using the redundant versions of the following operators, 
+--     and sometimes get faster code.
 -- 
-mkVSegd :: Array Int -> SSegd -> VSegd
+mkVSegd :: Array Int    -- ^ (vsegids) Mapping from virtual to physical segments.
+        -> SSegd        -- ^ Scattered Segment descriptor defining the 
+                        --   physical segments.
+        -> VSegd
 {-# INLINE_BACKEND mkVSegd #-}
 
 
 -- | Check whether a `Segd` is well formed.
---
---   * This will only return `False` if there is a bug in the library.
 validVSegd :: VSegd -> Bool
-{-# INLINE_BACKEND validVSegd #-}
+{-# NOINLINE validVSegd #-}
+--  NOINLINE because it's only used during debugging.
 
 
 -- | O(1). Construct an empty `SSegd`.
@@ -1019,7 +1167,7 @@ singletonVSegd :: Int -> VSegd
 
 
 -- | O(len). Construct a `VSegd` that describes an array where all virtual 
---   segmentspoint to the same physical segment.
+--   segments point to the same physical segment.
 replicatedVSegd 
         :: Int          -- ^ Length of segment.
         -> Int          -- ^ Number of times replicated.
@@ -1028,6 +1176,7 @@ replicatedVSegd
 
 
 -- | O(segs). Promote a plain `Segd` to a `VSegd`.
+--
 --   The result contains one virtual segment for every physical segment
 --   the provided `Segd`.
 promoteSegdToVSegd :: Segd -> VSegd
@@ -1035,24 +1184,25 @@ promoteSegdToVSegd :: Segd -> VSegd
 
 
 -- | O(segs). Promote a plain `SSegd` to a `VSegd`.
+--
 --   The result contains one virtual segment for every physical segment
 --   the provided `SSegd`.
 promoteSSegdToVSegd :: SSegd -> VSegd
 {-# INLINE CONLIKE PHASE_BACKEND promoteSSegdToVSegd #-}
 
 
--- | O(1). Checks whether all the segments are manifest (unshared / non-virtual).
---   If this is the case, then the vsegids field will be [0..len-1]
+-- | O(1). If true then the segments are all unshared, and the @vsegids@ field 
+--         be just @[0..len-1]@
 --
---   Consumers can check this field to avoid demanding the vsegids field.
---   This can avoid the need for it to be constructed in the first place, due to
---   lazy evaluation.
+--   Consumers can check this field to avoid demanding the @vsegids@ field.
+--   This can avoid the need for it to be constructed in the first place, 
+--   due to lazy evaluation.
 isManifestVSegd :: VSegd -> Bool
 {-# INLINE_BACKEND isManifestVSegd #-}
 
 
--- | O(1). Checks whether the starts are identical to the indices field and
---   the sourceids are all 0's. 
+-- | O(1). If true then the @starts@ field is identical to the @indices@ field
+--         and the sourceids are all 0s.
 --
 --   In this case all the data elements are in one contiguous flat array, and
 --   consumers can avoid looking at the real starts and sources fields.
@@ -1060,17 +1210,17 @@ isContiguousVSegd :: VSegd -> Bool
 {-# INLINE_BACKEND isContiguousVSegd #-}
 
 
--- | O(1). Take the length of a `VSegd`.
+-- | O(1). Yield the length of a `VSegd`.
 lengthOfVSegd :: VSegd -> Int
 {-# INLINE_BACKEND lengthOfVSegd #-}
 
 
--- | O(1). Take the vsegids of a `VSegd`.
+-- | O(1). Yield the vsegids of a `VSegd`.
 takeVSegidsOfVSegd :: VSegd -> Array Int
 {-# INLINE_BACKEND takeVSegidsOfVSegd #-}
 
 
--- | O(1). Take the vsegids of a `VSegd`, but don't require that every physical
+-- | O(1). Yield the vsegids of a `VSegd`, but don't require that every physical
 --   segment is referenced by some virtual segment.
 --
 --   If you're just performing indexing and don't need the invariant that all
@@ -1079,19 +1229,19 @@ takeVSegidsOfVSegd :: VSegd -> Array Int
 --
 --   The stated O(1) complexity assumes that the array has already been fully
 --   evalauted. If this is not the case then we can avoid demanding the result
---   of a prior computation on the vsegids, thus reducing the cost attributed
+--   of a prior computation on the @vsegids@, thus reducing the cost attributed
 --   to that prior computation.
 --
 takeVSegidsRedundantOfVSegd :: VSegd -> Array Int
 {-# INLINE_BACKEND takeVSegidsRedundantOfVSegd #-}
 
 
--- | O(1). Take the `SSegd` of a `VSegd`.
+-- | O(1). Yield the `SSegd` of a `VSegd`.
 takeSSegdOfVSegd :: VSegd -> SSegd
 {-# INLINE_BACKEND takeSSegdOfVSegd #-}
 
 
--- | O(1). Take the `SSegd` of a `VSegd`, but don't require that every physical
+-- | O(1). Yield the `SSegd` of a `VSegd`, but don't require that every physical
 --   segment is referenced by some virtual segment.
 --
 --   See the note in `takeVSegidsRedundantOfVSegd`.
@@ -1099,7 +1249,7 @@ takeSSegdRedundantOfVSegd :: VSegd -> SSegd
 {-# INLINE_BACKEND takeSSegdRedundantOfVSegd #-}
 
 
--- | O(1). Take the segment lengths of a `VSegd`.
+-- | O(1). Yield the segment lengths of a `VSegd`.
 takeLengthsOfVSegd :: VSegd -> Array Int
 {-# INLINE_BACKEND takeLengthsOfVSegd #-}
 
@@ -1109,30 +1259,33 @@ getSegOfVSegd :: VSegd -> Int -> (Int, Int, Int)
 {-# INLINE_BACKEND getSegOfVSegd #-}
 
 
--- | O(segs). Yield a `SSegd` that describes each segment of a `VSegd`
---   individually.
+-- | O(segs). 
+--   Yield a `SSegd` that describes each segment of a `VSegd` individually.
 --
 --   By doing this we lose information about which virtual segments
 --   correspond to the same physical segments.
-demoteToSSegdOfVSegd :: VSegd -> SSegd
-{-# INLINE_BACKEND demoteToSSegdOfVSegd #-}
-
-
--- | O(segs). Yield a `Segd` that describes each segment of a `VSegd`
---   individually, assuming all segments have been concatenated to 
---   remove scattering.
 --
---   /WARNING/: Trying to take the `Segd` of a nested array that has been
+--   /WARNING/: Trying to take the `SSegd` of a nested array that has been
 --   constructed with replication can cause index space overflow. This is
 --   because the virtual size of the corresponding flat data can be larger
 --   than physical memory. If this happens then indices fields and 
 --   element count in the result will be invalid.
 --
+unsafeDemoteToSSegdOfVSegd :: VSegd -> SSegd
+{-# INLINE_BACKEND unsafeDemoteToSSegdOfVSegd #-}
+
+
+-- | O(segs). Yield a `Segd` that describes each segment of a `VSegd` individually.
+--
+--   By doing this we lose information about which virtual segments
+--   correspond to the same physical segments.
+--
+--   See the warning in `unsafeDemoteToSSegdOfVSegd`.
 unsafeDemoteToSegdOfVSegd :: VSegd -> Segd
 {-# INLINE_BACKEND unsafeDemoteToSegdOfVSegd #-}
 
 
--- | Update the vsegids of a `VSegd`, and then cull the physical
+-- | Update the @vsegids@ of a `VSegd`, and then cull the physical
 --   segment descriptor so that all physical segments are reachable from
 --   some virtual segment.
 --
@@ -1140,16 +1293,16 @@ updateVSegsOfVSegd :: (Array Int -> Array Int) -> VSegd -> VSegd
 {-# INLINE_BACKEND updateVSegsOfVSegd #-}
 
 
--- | Update the vsegids  of `VSegd`, where the result is guaranteed to
+-- | Update the @vsegids@ of `VSegd`, where the result is guaranteed to
 --   cover all physical segments.
 --
---   Using this version saves performing the 'cull' operation which 
+--   Using this version avoids performing the 'cull' operation which 
 --   discards unreachable physical segments.
 --
 --   * The resulting vsegids must cover all physical segments.
 --     If they do not then there will be physical segments that are not 
 --     reachable from some virtual segment, and subsequent operations
---     like segmented fold will have the wrong work complexity.
+--     like @fold_ss@ will have the wrong work complexity.
 --
 updateVSegsReachableOfVSegd :: (Array Int -> Array Int) -> VSegd -> VSegd
 {-# INLINE_BACKEND updateVSegsReachableOfVSegd #-}
@@ -1236,12 +1389,12 @@ fromList :: Elt a => [a] -> Array a
 -- control exactly when they get inlined.
 
 dph_mod_index :: Int -> Int -> Int
-{-# INLINE_BACKEND dph_mod_index #-}
 dph_mod_index by idx = idx `GHC.Base.remInt` by
+{-# INLINE_BACKEND dph_mod_index #-}
 
 dph_plus :: Int -> Int -> Int
-{-# INLINE_BACKEND dph_plus #-}
 dph_plus x y = x Prelude.+ y
+{-# INLINE_BACKEND dph_plus #-}
 
 {-# RULES
 
@@ -1250,7 +1403,8 @@ dph_plus x y = x Prelude.+ y
 
   #-}
 
+
 tagZeroes :: Array Int -> Array Tag
-{-# INLINE CONLIKE PHASE_BACKEND tagZeroes #-}
 tagZeroes xs = map (\x -> fromBool (x==0)) xs
+{-# INLINE CONLIKE PHASE_BACKEND tagZeroes #-}
 
index c3ae417..9c793c5 100644 (file)
@@ -305,7 +305,7 @@ takeSSegdOfVSegd                = UPVSegd.takeUPSSegd
 takeSSegdRedundantOfVSegd       = UPVSegd.takeUPSSegdRedundant
 takeLengthsOfVSegd              = UPVSegd.takeLengths
 getSegOfVSegd                   = UPVSegd.getSeg
-demoteToSSegdOfVSegd            = UPVSegd.demoteToUPSSegd
+unsafeDemoteToSSegdOfVSegd      = UPVSegd.unsafeDemoteToUPSSegd
 unsafeDemoteToSegdOfVSegd       = UPVSegd.unsafeDemoteToUPSegd
 updateVSegsOfVSegd              = UPVSegd.updateVSegs
 updateVSegsReachableOfVSegd     = UPVSegd.updateVSegsReachable
index 425b53a..50fec42 100644 (file)
@@ -2,7 +2,7 @@
 -- | Read\/Show instances for segmented unlifted arrays.
 module Data.Array.Parallel.Unlifted.Parallel.Text ()
 where
-import Data.Array.Parallel.Base (showsApp)
+import Data.Array.Parallel.Base.Text (showsApp)
 import Data.Array.Parallel.Unlifted.Parallel.UPSegd (UPSegd, takeLengths)
 
 instance Show UPSegd where
index b83a7cb..6fbfc4e 100644 (file)
@@ -38,55 +38,6 @@ data UPSel2
         , upsel2_rep  :: UPSelRep2 }
 
 
--- | A `UPSelRep2` describes how to distribute the two data vectors
---   corresponding to a `UPSel2` across several PEs.
---
---   Suppose we want to perform the following combine operation:
---
--- @
--- combine [0,0,1,1,0,1,0,0,1] [A0,A1,A2,A3,A4] [B0,B1,B2,B3] 
---   = [A0,A1,B0,B1,A2,B2,A3,A4,B3]
--- @
---
---   The first array is the tags array, that says which of the data arrays to
---   get each successive element from. As `combine` is difficult to compute
---   in parallel, if we are going to perform several combines with the same
---   tag array, we can precompute a selector that tells us where to get each
---   element. The selector contains the original tags, as well as the source
---   index telling us where to get each element for the result array.
--- 
--- @
--- tags:    [0,0,1,1,0,1,0,0,1]
--- indices: [0,1,0,1,2,2,3,4,3]
--- @
---
---  Suppose we want to distribute the combine operation across 3 PEs. It's
---  easy to split the selector like so:
---
--- @
---            PE0                PE1               PE2
--- tags:    [0,0,1]            [1,0,1]           [0,0,1] 
--- indices: [0,1,0]            [1,2,2]           [3,4,3]
--- @
---
---  We now need to split the two data arrays. Each PE needs slices of the data
---  arrays that correspond to the parts of the selector that were given to it.
---  For the current example we get:
---
--- @
---            PE0                PE1               PE2
--- data_A:   [A0,A1]            [A2]              [A3,A4]
--- data_B:   [B0]               [B1,B2]           [B3]
--- @
---
---  The `UPSelRep2` contains the starting index and length of each of of these
---  slices:
---
--- @
---            PE0                PE1               PE2
---      ((0, 0), (2, 1))   ((2, 1), (1, 2))  ((3, 3), (2, 1))
---       indices   lens      indices  lens    indices  lens
--- @
 --
 type UPSelRep2
         = Dist ((Int,Int), (Int,Int))
index 56a30ae..5c20788 100644 (file)
@@ -30,7 +30,7 @@ module Data.Array.Parallel.Unlifted.Parallel.UPVSegd
         , getSeg
 
         -- * Demotion
-        , demoteToUPSSegd
+        , unsafeDemoteToUPSSegd
         , unsafeDemoteToUPSegd
 
         -- * Operators
@@ -310,8 +310,8 @@ getSeg upvsegd ix
 --   By doing this we lose information about which virtual segments
 --   correspond to the same physical segments.
 -- 
-demoteToUPSSegd :: UPVSegd -> UPSSegd
-demoteToUPSSegd upvsegd
+unsafeDemoteToUPSSegd :: UPVSegd -> UPSSegd
+unsafeDemoteToUPSSegd upvsegd
  | upvsegd_manifest upvsegd     = upvsegd_upssegd_culled upvsegd        -- TODO: take the redundant ones
  | otherwise
  = let  vsegids         = upvsegd_vsegids_culled upvsegd
@@ -321,7 +321,7 @@ demoteToUPSSegd upvsegd
         lengths'        = bpermuteUP (UPSSegd.takeLengths upssegd) vsegids
         upsegd'         = UPSegd.fromLengths lengths'
    in   UPSSegd.mkUPSSegd starts' sources' upsegd'
-{-# NOINLINE demoteToUPSSegd #-}
+{-# NOINLINE unsafeDemoteToUPSSegd #-}
 --  NOINLINE because it's complicated and won't fuse with anything.
 --  In core we want to see when VSegds are being demoted.
 
index a9d938c..1afb5d5 100644 (file)
@@ -166,7 +166,7 @@ takeSSegdOfVSegd                = UVSegd.takeUSSegd
 takeSSegdRedundantOfVSegd       = UVSegd.takeUSSegd
 takeLengthsOfVSegd              = UVSegd.takeLengths
 getSegOfVSegd                   = UVSegd.getSeg
-demoteToSSegdOfVSegd            = UVSegd.demoteToUSSegd
+unsafeDemoteToSSegdOfVSegd      = UVSegd.unsafeDemoteToUSSegd
 unsafeDemoteToSegdOfVSegd       = UVSegd.unsafeDemoteToUSegd
 updateVSegsOfVSegd              = UVSegd.updateVSegs
 updateVSegsReachableOfVSegd     = UVSegd.updateVSegsReachable
index b3f027e..0a98862 100644 (file)
@@ -1,34 +1,7 @@
--- | A selector is a description of how to perform a `combine` operation.
---
--- Suppose we are evaluating the following expression:
---
---   @combine [F,F,T,F,T,T] [1,2,3] [4,5,6] = [4,5,1,6,2,3]@
---
--- This is difficult to parallelise. For each element in the result, the
--- source array we get this element from depends on the tag values associated
--- with all previous elements.
---
--- However, if we going to perform several combines with the same tag array, 
--- we can precompute a selector that tells us where to get each element. 
--- The selector contains the original tags, as well as the source index telling
--- us where to get each element for the result array.
---
--- For example:
---
---  @
---  tagsToIndices2 [F,F,T,F,T,T]   -- tags
---               = [0,1,0,2,1,2]   -- indices
---  @
---
---  This says get the first element from index 0 in the second array, 
---   then from index 1 in the second array,
---  then index 0 in the first array ...
---  
---  The selector then consists of both the @tag@ and @indices@ arrays.
---
 {-# LANGUAGE CPP #-}
 #include "fusion-phases.h"
 
+-- | Selectors. See the docs in dph-prim-interface for how these work.
 module Data.Array.Parallel.Unlifted.Sequential.USel 
         ( -- * Types
           USel2
index db196a2..2b73c86 100644 (file)
@@ -34,7 +34,7 @@ module Data.Array.Parallel.Unlifted.Sequential.UVSegd
         , combine2
         , updateVSegs
         , updateVSegsReachable
-        , demoteToUSSegd
+        , unsafeDemoteToUSSegd
         , unsafeDemoteToUSegd)
 where
 import Data.Array.Parallel.Unlifted.Sequential.USel
@@ -305,8 +305,8 @@ getSeg uvsegd ix
 --   * This operation is used in concatPR as the first step in eliminating
 --     segmentation from a nested array.
 -- 
-demoteToUSSegd :: UVSegd -> USSegd
-demoteToUSSegd uvsegd
+unsafeDemoteToUSSegd :: UVSegd -> USSegd
+unsafeDemoteToUSSegd uvsegd
  | uvsegd_manifest uvsegd       = uvsegd_ussegd_culled uvsegd           -- TODO: take the redundant ones
  | otherwise
  = let  vsegids         = uvsegd_vsegids_culled uvsegd
@@ -316,7 +316,7 @@ demoteToUSSegd uvsegd
         lengths'        = U.bpermute (USSegd.takeLengths ussegd) vsegids
         usegd'          = USegd.fromLengths lengths'
    in   USSegd.mkUSSegd starts' sources' usegd'
-{-# NOINLINE demoteToUSSegd #-}
+{-# NOINLINE unsafeDemoteToUSSegd #-}
 --  NOINLINE because it's complicated and won't fuse with anything.