dph-prim-seq: more doc cleanups
authorBen Lippmeier <benl@ouroborus.net>
Fri, 3 Feb 2012 06:33:47 +0000 (17:33 +1100)
committerBen Lippmeier <benl@ouroborus.net>
Fri, 3 Feb 2012 06:33:47 +0000 (17:33 +1100)
16 files changed:
dph-prim-interface/Data/Array/Parallel/Unlifted.hs
dph-prim-interface/dph-prim-interface.cabal
dph-prim-interface/interface/DPH_Interface.h
dph-prim-par/Data/Array/Parallel/Unlifted.hs
dph-prim-par/dph-prim-par.cabal
dph-prim-seq/Data/Array/Parallel/Unlifted.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/ArrayArray.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/Sequential/USSegd.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/Sequential/USegd.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/Sequential/USel.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/Sequential/UVSegd.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/Stream.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/Stream/Elems.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/Stream/Segments.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/Vectors.hs
dph-prim-seq/dph-prim-seq.cabal

index 58cea0f..30656d2 100644 (file)
@@ -3,7 +3,7 @@
 -- | WARNING: 
 --   This is an abstract interface. All the functions will just `error` if called. 
 --
---   This module provides an API for the unlifted array primitives used by DPH.
+--   This module provides an API for the segmented array primitives used by DPH.
 --   None of the functions here have implementations.
 --
 --   Client programs should use either the @dph-prim-seq@ or @dph-prim-par@
index ce4658a..ef1411c 100644 (file)
@@ -6,7 +6,7 @@ Author:         The DPH Team
 Maintainer:     Ben Lippmeier <benl@cse.unsw.edu.au>
 Homepage:       http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell
 Category:       Data Structures
-Synopsis:       Data Parallel Haskell flat parallel arrays. (abstract interface)
+Synopsis:       Data Parallel Haskell segmented arrays. (abstract interface)
 Description:    Empty implementation of flat parallel arrays. 
                 This package exists only so that dph-prim-par and dph-prim-seq
                 can provide the same interface.
index 61e85da..ef18214 100644 (file)
@@ -949,6 +949,16 @@ tagsToSel2 tags
 --
 --   * If you don't want to cover all the elements from the flat arrary then
 --     use a `SSegd` instead.
+--
+--  Example:
+--
+--   @
+--   flat array data: [1 2 3 4 5 6 7 8]
+--     (segmentation)  --- ----- - ---
+--     segd  lengths: [2, 3, 1, 2]
+--           indices: [0, 2, 5, 6]
+--          elements: 8 
+--   @
 ---
 --   * This ensures that the indices are monotonically increasing,
 --     and all elements from the flat array are covered by some segment.
@@ -958,6 +968,7 @@ tagsToSel2 tags
 --     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.
index 9c793c5..b40c4cb 100644 (file)
@@ -1,18 +1,17 @@
 {-# LANGUAGE CPP, NoMonomorphismRestriction #-}
 {-# OPTIONS -fno-warn-missing-signatures #-}
--- | Primitive parallel combinators that work on flat, unlifted arrays.
---   Some of them don't actually have parallel implementations, so we bail out
---   to the regular sequential ones.
+-- | Parallel implementation of the segmented array API defined in @dph-prim-interface@.
+--
+--   Some of them don't yet have parallel implementations, so we fall back
+--   to the sequential ones from @dph-prim-seq@.
 --
 --   /WARNING:/ Although this library is intended to be used as a target
---   for the DPH vectoriser, it is also perfectly reasonable to use it directly
---   from non DPH programs. However, you can NOT perform further parallel
---   computations in the workers passed to higher order functions such as 
---   `map`, `zipWith`, `filter`, `fold`, etc. Doing this is nested parallelism, 
---   which this library does not support, and any attempts to do so will
---   just run sequentially. If you want to run nested parallel code then
---   you need to use the vectoriser.
-
+--   for the DPH vectoriser, it is also fine to use it directly from non
+--   DPH programs. However, this library does not support nested parallelism
+--   by itself. If you try to run further parallel computations in the workers
+--   passed to `map`, `zipWith`, `fold` etc, then they will just run
+--   sequentially.
+---
 --   This API is used by the @dph-lifted-*@ libraries, and is defined in
 --   @DPH_Header.h@ and @DPH_Interface.h@. We use header files to ensure
 --   that this API is implemented identically by both the 
@@ -46,6 +45,9 @@ import Prelude (($!))
 
 -- Basics ---------------------------------------------------------------------
 class (Unbox a,   DT a) => Elt a
+
+-- | Arrays are stored as unboxed vectors. 
+--   They have bulk-strict semantics, so demanding one element demands them all.
 type Array      = Vector
 
 
index 300288e..8f39898 100644 (file)
@@ -6,7 +6,7 @@ Author:         The DPH Team
 Maintainer:     Ben Lippmeier <benl@cse.unsw.edu.au>
 Homepage:       http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell
 Category:       Data Structures
-Synopsis:       Data Parallel Haskell flat parallel arrays.
+Synopsis:       Data Parallel Haskell segmented arrays. (production version)
 Description:    Production implementation of the flat parallel array API defined
                 in dph-prim-interface.
 
index 1afb5d5..f4ce05b 100644 (file)
@@ -1,6 +1,10 @@
 {-# LANGUAGE CPP #-}
 {-# OPTIONS -fno-warn-missing-signatures #-}
--- | Primitive sequential combinators that work on flat, unlifted arrays.
+-- | Sequential implementation of the segmented array API defined in 
+--   @dph-prim-interface@. 
+--
+--   There is a parallel implementation in @dph-prim-par@, 
+--   so you probably want that instead.
 
 --   The API is defined in @DPH_Header.h@ and @DPH_Interface.h@ to ensure that both
 --   @dph-prim-par@ and @dph-prim-seq@ really do export the same symbols.
@@ -21,6 +25,9 @@ import qualified Data.Array.Parallel.Unlifted.Vectors            as US
 
 -- Basics ---------------------------------------------------------------------
 class U.Unbox a => Elt a
+
+-- | Arrays are stored as unboxed vectors. 
+--   They have bulk-strict semantics, so demanding one element demands them all.
 type Array                      = U.Vector
 
 
index 8ce9eec..3f4e185 100644 (file)
@@ -1,6 +1,11 @@
 
--- | Nested unboxed arrays.
---  
+-- | Irregular 2D unboxed arrays.
+--
+--   The difference between this type and something like 
+--   @Data.Vector (Data.Vector.Unboxed a)@ is that the inner arrays have kind
+--   @#@ and cannot be bottom. This ensures that we can always lookup an element
+--   from an `ArrayArray#` without performing unboxings or checking for thunks.
+---
 --   TODO: move this into the Data.Primitive library.
 module Data.Array.Parallel.Unlifted.ArrayArray
         ( MutableArrayArray (..)
index 3f3a66e..a66abca 100644 (file)
@@ -2,7 +2,10 @@
 {-# OPTIONS -Wall -fno-warn-orphans #-}
 #include "fusion-phases.h"
 
--- | Scattered Segment Descriptors
+-- | Scattered Segment Descriptors.
+--
+--   See "Data.Array.Parallel.Unlifted" for how this works.
+--
 module Data.Array.Parallel.Unlifted.Sequential.USSegd 
         ( -- * Types
           USSegd(..)
@@ -39,23 +42,7 @@ here s = "Data.Array.Parallel.Unlifted.Sequential.USSegd." ++ s
 
 
 -- USSegd ---------------------------------------------------------------------
--- | Construct a Scattered Segment Descriptor from an array of source
---   array indices, starting indices and an existing `USegd`.
---
---   * A `USSegd` is an extension of a `USegd` 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.
---
---   * 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.
--- 
+-- | Scattered Segment Descriptor.
 data USSegd
         = USSegd
         { ussegd_contiguous     :: !Bool
@@ -236,8 +223,8 @@ appendWith
 --  NOINLINE because we're worried about code explosion. Might be useful though.
 
 
--- | Cull the segments in a SSegd down to only those reachable from an array
---   of vsegids, and also update the vsegids to point to the same segments
+-- | Cull the segments of a `USSegd` down to only those reachable from an array
+--   of @vsegids@, and also update the @vsegids@ to point to the same segments
 --   in the result.
 --
 cullOnVSegids :: Vector Int -> USSegd -> (Vector Int, USSegd)
index 2c33900..6e73c6b 100644 (file)
@@ -2,10 +2,13 @@
 {-# OPTIONS -fno-warn-orphans #-}
 #include "fusion-phases.h"
 
--- | Segment Descriptors
+-- | Segment Descriptors.
+--
+--   See "Data.Array.Parallel.Unlifted" for how this works.
+--
 module Data.Array.Parallel.Unlifted.Sequential.USegd 
         ( -- * Types
-          USegd
+          USegd(..)
 
           -- * Constructors
         , mkUSegd, valid
@@ -29,27 +32,7 @@ here :: String -> String
 here s = "Data.Array.Parallel.Unlifted.Sequential.USegd." ++ s
 
 
--- | 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 flU.at array.
---
---   /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 parallel implementations 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`.
---
---   @
---   flat array data: [1 2 3 4 5 6 7 8]
---     (segmentation)  --- ----- - ---
---     segd  lengths: [2, 3, 1, 2]
---           indices: [0, 2, 5, 6]
---          elements: 8 
---   @
---
+-- | Segment descriptor. 
 data USegd 
         = USegd 
         { usegd_lengths  :: !(Vector Int)  -- ^ Length of each segment.
index 0a98862..e35be93 100644 (file)
@@ -1,10 +1,13 @@
 {-# LANGUAGE CPP #-}
 #include "fusion-phases.h"
 
--- | Selectors. See the docs in dph-prim-interface for how these work.
+-- | Selectors. 
+--
+--   See "Data.Array.Parallel.Unlifted" for how this works.
+--
 module Data.Array.Parallel.Unlifted.Sequential.USel 
         ( -- * Types
-          USel2
+          USel2(..)
 
           -- * Operations on selectors
         , mkUSel2
@@ -19,8 +22,7 @@ import Data.Vector.Fusion.Stream.Monadic                ( Stream(..) )
 import Data.Array.Parallel.Base                         (Tag)
 
 
--- | Abstract selector. 
---   Contains both the @tags@ and @indices@ arrays outlined above.
+-- | Selector.
 data USel2 
         = USel2
         { usel2_tags      :: !(Vector Tag)
index 2b73c86..c6b1c5b 100644 (file)
@@ -2,7 +2,10 @@
 {-# OPTIONS -Wall -fno-warn-orphans -fno-warn-missing-signatures #-}
 #include "fusion-phases.h"
 
--- | Segment descriptors for virtual arrays.
+-- | Virtual Segment Descriptors.
+--
+--   See "Data.Array.Parallel.Unlifted" for how this works.
+--
 module Data.Array.Parallel.Unlifted.Sequential.UVSegd
         ( -- * Types
           UVSegd(..)
@@ -52,10 +55,8 @@ here s = "Data.Array.Parallel.Unlifted.Sequential.UVSegd." ++ s
 
 
 -- UVSegd ---------------------------------------------------------------------
--- | Virtual segment descriptors. 
---   Represents an index space transformation between indices for the nested
---   array and indices for the physical data.
---   
+-- | Virtual segment descriptor.
+----   
 --   * TODO: It would probably be better to represent the vsegids as a lens (function)
 --           instead of a vector of segids. Much of the time the vsegids are just @[0..n]@
 --
@@ -110,7 +111,7 @@ instance PprPhysical UVSegd where
 
 
 -- | O(1). Check the internal consistency of a virutal segmentation descriptor.
---
+---
 --   * TODO: check that all vsegs point to a valid pseg
 valid :: UVSegd -> Bool
 valid (UVSegd _ _ vsegids _ ussegd)
@@ -123,9 +124,9 @@ valid (UVSegd _ _ vsegids _ ussegd)
 -- | O(1). Construct a new virtual segment descriptor.
 --   All the provided arrays must have the same lengths.
 mkUVSegd
-        :: Vector Int   -- ^ Array saying which physical segment to use for each
-                        --   virtual segment.
-        -> USSegd       -- ^ Slice segment descriptor describing physical segments.
+        :: Vector Int   -- ^ (vsegids) Mapping from virtual to physical segments.
+        -> USSegd       -- ^ Scattered Segment descriptor defining the 
+                        --   physical segments.
         -> UVSegd
 
 mkUVSegd vsegids ussegd
@@ -133,10 +134,10 @@ mkUVSegd vsegids ussegd
 {-# INLINE mkUVSegd #-}
 
 
--- | O(segs). Promote a plain `USSegd` to a `UVSegd`
---   The result contains one virtual segment for every physical segment
---   the provided `USSegd`.
+-- | O(segs). Promote a plain `USegd` to a `UVSegd`.
 --
+--   The result contains one virtual segment for every physical segment
+--   the provided `Segd`.
 fromUSSegd :: USSegd -> UVSegd
 fromUSSegd ussegd
  = let  vsegids = U.enumFromTo 0 (USSegd.length ussegd - 1)
@@ -144,11 +145,10 @@ fromUSSegd ussegd
 {-# INLINE_U fromUSSegd #-}
 
 
--- | O(segs). Promote a plain `USegd` to a `UVSegd`.
---   All segments are assumed to come from a flat array with sourceid 0.
---   The result contains one virtual segment for every physical segment
---   the provided USegd.
+-- | O(segs). Promote a plain `Segd` to a `VSegd`.
 --
+--   The result contains one virtual segment for every physical segment
+--   the provided `SSegd`.
 fromUSegd :: USegd -> UVSegd
 fromUSegd
         = fromUSSegd . USSegd.fromUSegd
index 925abb6..5df8c3d 100644 (file)
@@ -1,8 +1,15 @@
 
 module Data.Array.Parallel.Unlifted.Stream
-        ( module Data.Array.Parallel.Unlifted.Stream.Segmented
+        ( -- * Segmented streams
+          module Data.Array.Parallel.Unlifted.Stream.Segmented
+
+          -- * Stream through segment descriptors
         , module Data.Array.Parallel.Unlifted.Stream.Ixs
+
+          -- * Streams of scattered elements
         , module Data.Array.Parallel.Unlifted.Stream.Elems
+
+          -- * Streams of scattered segments
         , module Data.Array.Parallel.Unlifted.Stream.Segments)
 where
 import Data.Array.Parallel.Unlifted.Stream.Segmented
index 53a7df0..c69a0ad 100644 (file)
@@ -14,7 +14,9 @@ import qualified Data.Array.Parallel.Unlifted.Sequential.Vector  as U
 import qualified Data.Array.Parallel.Unlifted.Vectors            as US
 import qualified Data.Array.Parallel.Unlifted.Sequential.UVSegd  as UVSegd
 
-
+-- | Take a stream of indices, 
+--    look them up from a vector, 
+--    and produce a stream of elements.
 streamElemsFromVector
         :: (Monad m, Unbox a)
         => Vector a -> Stream m Int -> Stream m a
@@ -35,8 +37,9 @@ streamElemsFromVector vector (Stream mkStep s0 size0)
 {-# INLINE_STREAM streamElemsFromVector #-}
 
 
--- | Take a stream of chunk and chunk element indices, look them up from
---   some vectors, and produce a stream of elements.
+-- | Take a stream of chunk and chunk element indices, 
+--    look them up from some vectors, 
+--    and produce a stream of elements.
 streamElemsFromVectors 
         :: (Monad m, Unboxes a) 
         => Vectors a -> Stream m (Int, Int) -> Stream m a
index d3a36b8..48a0b0b 100644 (file)
@@ -23,7 +23,7 @@ import System.IO.Unsafe
 
 -- Nested -----------------------------------------------------------------------------------------
 -- | Stream some physical segments from many data arrays.
--- 
+--- 
 --   * TODO: make this more efficient, and fix fusion.
 --           We should be able to eliminate a lot of the indexing happening in the 
 --           inner loop by being cleverer about the loop state.
index 37b137c..c234546 100644 (file)
@@ -2,7 +2,7 @@
 #include "fusion-phases.h"
 
 -- | Irregular two dimensional arrays.
---
+---
 --   * TODO: The inner arrays should be unboxed so we don't get an unboxing overhead
 --           for every call to unsafeIndex2. This might need an extension to the GHC
 --           runtime if we alwo want to convert a U.Vector directly to this form.
@@ -135,11 +135,9 @@ unsafeIndexUnpack (Vectors _ starts lens arrs) ix
 {-# INLINE_U unsafeIndexUnpack #-}
 
 
--- | Append two `Vectors`.
---
---   * Important: appending two `Vectors` involes work proportional to
---     the length of the outer arrays, not the size of the inner ones.
-append :: (Unboxes a, Unbox a, Show a) => Vectors a -> Vectors a -> Vectors a
+-- | Appending two `Vectors` uses work proportional to
+--   the length of the outer arrays.
+append :: (Unboxes a, Unbox a) => Vectors a -> Vectors a -> Vectors a
 append  (Vectors len1 starts1 lens1 chunks1)
         (Vectors len2 starts2 lens2 chunks2)
  = runST
index 1fd157d..f88a524 100644 (file)
@@ -6,11 +6,10 @@ Author:         The DPH Team
 Maintainer:     Ben Lippmeier <benl@cse.unsw.edu.au>
 Homepage:       http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell
 Category:       Data Structures
-Synopsis:       Data Parallel Haskell flat parallel arrays. (sequential reference implementation)
-Description:    Sequential implementation of the flat parallel array API defined
-                in dph-prim-interface.
-                This is normall only used during debugging.
-                You probably want dph-prim-par instead.
+Synopsis:       Data Parallel Haskell segmented arrays. (sequential implementation)
+Description:    Sequential array data type and stream fuctions, along with a
+                sequential reference implementation of the segmented array
+                API defined in @dph-prim-interface@.
 
 Cabal-Version:  >= 1.6
 Build-Type:     Simple