Add UPVSegd
authorBen Lippmeier <benl@ouroborus.net>
Thu, 6 Oct 2011 06:00:16 +0000 (17:00 +1100)
committerBen Lippmeier <benl@ouroborus.net>
Tue, 11 Oct 2011 04:11:42 +0000 (15:11 +1100)
dph-prim-interface/Data/Array/Parallel/Unlifted.hs
dph-prim-interface/interface/DPH_Header.h
dph-prim-par/Data/Array/Parallel/Unlifted.hs
dph-prim-par/Data/Array/Parallel/Unlifted/Parallel/UPSSegd.hs
dph-prim-par/Data/Array/Parallel/Unlifted/Parallel/UPVSegd.hs [new file with mode: 0644]
dph-prim-par/dph-prim-par.cabal
dph-prim-seq/Data/Array/Parallel/Unlifted.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/Sequential/UVSegd.hs

index 8db428e..be0ce1f 100644 (file)
@@ -202,18 +202,18 @@ data VSegd
         , vsegd_ssegd   :: SSegd }
 
 mkVSegd                 = VSegd
-emptyVSegd              = VSegd [] emptySSegd
-singletonVSegd          = notImplemented "singletonVSegd"
 validVSegd              = notImplemented "validSSegd"       
 promoteSegdToVSegd      = notImplemented "promoteSegdToVSegd"
-unsafeMaterializeVSegd  = notImplemented "unsafeMaterializeVSegd"
 promoteSSegdToVSegd     = notImplemented "promoteSSegdToVSegd"
-demoteVSegdToSSegd      = notImplemented "demoteVSegdToSSegd"
-vsegidsVSegd            = vsegd_vsegids
-ssegdVSegd              = vsegd_ssegd
-lengthVSegd             = notImplemented "lengthVSegd"
-lengthsVSegd            = notImplemented "lengthsVSegd"
+emptyVSegd              = VSegd [] emptySSegd
+singletonVSegd          = notImplemented "singletonVSegd"
+lengthOfVSegd           = notImplemented "lengthOfVSegd"
+takeVSegidsOfVSegd      = vsegd_vsegids
+takeSSegdOfVSegd        = vsegd_ssegd
+takeLengthsOfVSegd      = notImplemented "takeLengthsOfVSegd"
 getSegOfVSegd           = notImplemented "getSegOfVSegd"
+demoteToSSegdOfVSegd    = notImplemented "demoteToSSegdOfVSegd"
+demoteToSegdOfVSegd     = notImplemented "demoteToSegdOfVSegd"
 updateVSegsOfVSegd      = notImplemented "updateVSegsOfVSegd"
 appendVSegd             = notImplemented "appendVSegd"
 combine2VSegd           = notImplemented "combine2VSegd"
index 312f281..47e6548 100644 (file)
@@ -73,15 +73,23 @@ module Data.Array.Parallel.Unlifted (
   appendSSegd,
   
   -- * Virtual Segment Descriptors
-  VSegd, mkVSegd, validVSegd,
-  emptyVSegd, singletonVSegd,
-  promoteSegdToVSegd,  unsafeMaterializeVSegd,
-  promoteSSegdToVSegd, demoteVSegdToSSegd,
-  vsegidsVSegd, ssegdVSegd,
-  lengthVSegd, lengthsVSegd,
+  VSegd,
+  mkVSegd,
+  validVSegd,
+  promoteSegdToVSegd,
+  promoteSSegdToVSegd,
+  emptyVSegd,
+  singletonVSegd,
+  lengthOfVSegd,
+  takeVSegidsOfVSegd,
+  takeSSegdOfVSegd,
+  takeLengthsOfVSegd,
   getSegOfVSegd,
+  demoteToSSegdOfVSegd,
+  demoteToSegdOfVSegd,
   updateVSegsOfVSegd,
-  appendVSegd, combine2VSegd,
+  appendVSegd,
+  combine2VSegd,
   
   -- * Selectors
   Sel2, mkSel2, 
index 9a7116f..deff36c 100644 (file)
@@ -21,7 +21,7 @@ import Data.Array.Parallel.Unlifted.Distributed ( DT )
 import Data.Array.Parallel.Unlifted.Parallel.UPSel
 import qualified Data.Array.Parallel.Unlifted.Parallel.UPSegd           as UPSegd
 import qualified Data.Array.Parallel.Unlifted.Parallel.UPSSegd          as UPSSegd
-import qualified Data.Array.Parallel.Unlifted.Sequential.UVSegd         as UVSegd
+import qualified Data.Array.Parallel.Unlifted.Parallel.UPVSegd          as UPVSegd
 import qualified Data.Array.Parallel.Unlifted.Sequential.Vector         as Seq
 import qualified Data.Array.Parallel.Unlifted.Sequential.Combinators    as Seq
 
@@ -249,10 +249,10 @@ elementsSegd            = UPSegd.takeElements
 -- Scattered Segment Descriptors ----------------------------------------------
 type SSegd              = UPSSegd.UPSSegd
 mkSSegd                 = UPSSegd.mkUPSSegd
+promoteSegdToSSegd      = UPSSegd.fromUPSegd
 validSSegd              = UPSSegd.valid
 emptySSegd              = UPSSegd.empty
 singletonSSegd          = UPSSegd.singleton
-promoteSegdToSSegd      = UPSSegd.fromUPSegd
 lengthSSegd             = UPSSegd.length
 lengthsSSegd            = UPSSegd.takeLengths
 indicesSSegd            = UPSSegd.takeIndices
@@ -264,23 +264,23 @@ appendSSegd             = UPSSegd.appendWith
 
 -- Virtual Segment Descriptors ------------------------------------------------
 -- TODO: these point to sequential segd ops.
-type VSegd              = UVSegd.UVSegd
-mkVSegd                 = UVSegd.mkUVSegd
-validVSegd              = UVSegd.valid
-emptyVSegd              = UVSegd.empty
-singletonVSegd          = UVSegd.singleton
-promoteSegdToVSegd      = UVSegd.fromUSegd
-unsafeMaterializeVSegd  = UVSegd.unsafeMaterialize
-promoteSSegdToVSegd     = UVSegd.fromUSSegd
-demoteVSegdToSSegd      = UVSegd.toUSSegd
-vsegidsVSegd            = UVSegd.takeVSegids
-ssegdVSegd              = UVSegd.takeUSSegd
-lengthVSegd             = UVSegd.length
-lengthsVSegd            = UVSegd.takeLengths
-getSegOfVSegd           = UVSegd.getSeg
-updateVSegsOfVSegd      = UVSegd.updateVSegs
-appendVSegd             = UVSegd.append
-combine2VSegd           = UVSegd.combine2
+type VSegd              = UPVSegd.UPVSegd
+mkVSegd                 = UPVSegd.mkUPVSegd
+validVSegd              = UPVSegd.valid
+promoteSegdToVSegd      = UPVSegd.fromUPSegd
+promoteSSegdToVSegd     = UPVSegd.fromUPSSegd
+emptyVSegd              = UPVSegd.empty
+singletonVSegd          = UPVSegd.singleton
+lengthOfVSegd           = UPVSegd.length
+takeVSegidsOfVSegd      = UPVSegd.takeVSegids
+takeSSegdOfVSegd        = UPVSegd.takeUPSSegd
+takeLengthsOfVSegd      = UPVSegd.takeLengths
+getSegOfVSegd           = UPVSegd.getSeg
+demoteToSSegdOfVSegd    = UPVSegd.demoteToUPSSegd
+demoteToSegdOfVSegd     = UPVSegd.unsafeDemoteToUPSegd
+updateVSegsOfVSegd      = UPVSegd.updateVSegs
+appendVSegd             = UPVSegd.appendWith
+combine2VSegd           = UPVSegd.combine2
 
 
 -- Selectors ------------------------------------------------------------------
index d6ec7a9..c909014 100644 (file)
@@ -84,16 +84,16 @@ valid _ = True
 
 
 -- Constructors ---------------------------------------------------------------
--- | O(1). Construct a new segment descriptor.
+-- | Construct a new segment descriptor.
 mkUPSSegd 
         :: Vector Int   -- ^ Starting index of each segment in its flat array.
         -> Vector Int   -- ^ Source id of the flat array to tach each segment from.
-        -> USegd        -- ^ Contiguous (unscattered) segment descriptor.
+        -> UPSegd       -- ^ Contiguous (unscattered) segment descriptor.
         -> UPSSegd
 
 {-# INLINE mkUPSSegd #-}
-mkUPSSegd starts sources usegd
-        = fromUSSegd (USSegd.mkUSSegd starts sources usegd)
+mkUPSSegd starts sources upsegd
+        = fromUSSegd (USSegd.mkUSSegd starts sources (UPSegd.takeUSegd upsegd))
 
 
 -- | Promote a global `USSegd` to a parallel `UPSSegd` by distributing
diff --git a/dph-prim-par/Data/Array/Parallel/Unlifted/Parallel/UPVSegd.hs b/dph-prim-par/Data/Array/Parallel/Unlifted/Parallel/UPVSegd.hs
new file mode 100644 (file)
index 0000000..d1f5be6
--- /dev/null
@@ -0,0 +1,293 @@
+{-# LANGUAGE CPP #-}
+#include "fusion-phases.h"
+
+{-# OPTIONS -Wall -fno-warn-orphans -fno-warn-missing-signatures #-}
+
+-- | Parallel virtual segment descriptors.
+module Data.Array.Parallel.Unlifted.Parallel.UPVSegd (
+        -- * Types
+        UPVSegd,
+
+        -- * Consistency check
+        valid,
+        
+        -- * Constructors
+        mkUPVSegd,
+        fromUPSegd,
+        fromUPSSegd,
+        empty,
+        singleton,
+        
+        -- * Projections
+        length,
+        takeVSegids,
+        takeUPSSegd,
+        takeLengths,
+        getSeg,
+
+        -- * Demotion
+        demoteToUPSSegd,
+        unsafeDemoteToUPSegd,
+
+        -- * Operators
+        updateVSegs,
+        appendWith,
+        combine2,
+) where
+import Data.Array.Parallel.Unlifted.Parallel.Permute
+import Data.Array.Parallel.Unlifted.Parallel.UPSel              (UPSel2)
+import Data.Array.Parallel.Unlifted.Parallel.UPSSegd            (UPSSegd)
+import Data.Array.Parallel.Unlifted.Parallel.UPSegd             (UPSegd)
+import Data.Array.Parallel.Unlifted.Sequential.Vector           (Vector)
+import Data.Array.Parallel.Pretty                               hiding (empty)
+import Prelude                                                  hiding (length)
+
+import qualified Data.Array.Parallel.Unlifted.Sequential.USSegd as USSegd
+import qualified Data.Array.Parallel.Unlifted.Sequential.Vector as V
+import qualified Data.Array.Parallel.Unlifted.Parallel.UPSel    as UPSel
+import qualified Data.Array.Parallel.Unlifted.Parallel.UPSegd   as UPSegd
+import qualified Data.Array.Parallel.Unlifted.Parallel.UPSSegd  as UPSSegd
+
+
+-- UPVSegd ---------------------------------------------------------------------
+-- | A parallel virtual segment descriptor is an extension of `UPSSegd`
+--   that explicitly represents sharing of data between multiple segments.
+--   
+--   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] 
+--
+data UPVSegd 
+        = UPVSegd 
+        { _upvsegd_vsegids       :: !(Vector Int)
+        , _upvsegd_upssegd       :: !UPSSegd }
+        deriving (Show)
+
+
+-- | Pretty print the physical representation of a `UVSegd`
+instance PprPhysical UPVSegd where
+ pprp (UPVSegd vsegids upssegd)
+  = vcat
+  [ text "UPVSegd" $$ (nest 7 $ text "vsegids: " <+> (text $ show $ V.toList vsegids))
+  , pprp upssegd ]
+
+
+-- | O(1). Check the internal consistency of a virutal segmentation descriptor.
+--
+--   * TODO: this doesn't do any checks yet.
+--\b
+valid :: UPVSegd -> Bool
+{-# INLINE valid #-}
+valid (UPVSegd _ _)
+        = True
+
+-- Constructors ---------------------------------------------------------------
+-- | O(1). Construct a new virtual segment descriptor.
+mkUPVSegd
+        :: Vector Int   -- ^ Array saying which physical segment to use for each virtual segment.
+        -> UPSSegd      -- ^ Scattered segment descriptor defining the physical segments.
+        -> UPVSegd
+
+{-# INLINE mkUPVSegd #-}
+mkUPVSegd = UPVSegd
+
+
+-- | O(segs). Promote a `UPSSegd` to a `UPVSegd`.
+--   The result contains one virtual segment for every physical segment
+--   defined by the `UPSSegd`.
+--
+--   TODO: make this parallel, use parallel version of enumFromTo.
+--
+fromUPSSegd :: UPSSegd -> UPVSegd
+{-# INLINE fromUPSSegd #-}
+fromUPSSegd upssegd
+        = UPVSegd 
+                (V.enumFromTo 0 (UPSSegd.length upssegd - 1))
+                upssegd
+
+-- | O(segs). Promote a `UPSegd` to a `UPVSegd`.
+--   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 `UPSegd`.
+--
+fromUPSegd :: UPSegd -> UPVSegd
+{-# INLINE fromUPSegd #-}
+fromUPSegd
+        = fromUPSSegd . UPSSegd.fromUPSegd
+
+
+-- | O(1). Yield an empty segment descriptor, with no elements or segments.
+empty :: UPVSegd
+{-# INLINE empty #-}
+empty   = UPVSegd V.empty UPSSegd.empty
+
+
+-- | O(1). Yield a singleton segment descriptor.
+--   The single segment covers the given number of elements in a flat array
+--   with sourceid 0.
+singleton :: Int -> UPVSegd
+{-# INLINE singleton #-}
+singleton n 
+        = UPVSegd (V.singleton 0) (UPSSegd.singleton n)
+
+
+-- Projections ----------------------------------------------------------------
+-- | O(1). Yield the overall number of segments.
+length :: UPVSegd -> Int
+{-# INLINE length #-}
+length (UPVSegd vsegids _)
+        = V.length vsegids
+
+
+-- | O(1). Yield the virtual segment ids of `UPVSegd`.
+takeVSegids :: UPVSegd -> Vector Int
+{-# INLINE takeVSegids #-}
+takeVSegids (UPVSegd vsegids _)
+        = vsegids
+
+
+-- | O(1). Yield the `UPSSegd` of `UPVSegd`.
+takeUPSSegd :: UPVSegd -> UPSSegd
+{-# INLINE takeUPSSegd #-}
+takeUPSSegd (UPVSegd _ upssegd)
+        = upssegd
+
+
+-- | O(segs). Yield the lengths of the segments described by a `UPVSegd`.
+takeLengths :: UPVSegd -> Vector Int
+{-# INLINE takeLengths #-}
+takeLengths (UPVSegd vsegids upssegd)
+        = V.map (UPSSegd.takeLengths upssegd V.!) vsegids
+
+
+-- | O(1). Get the length, starting index, and source id of a segment.
+--
+--  NOTE: We don't return the segment index field from the USSegd as this refers
+--        to the flat index relative to the SSegd array, rather than 
+--        relative to the UVSegd array. If we tried to promote the USSegd index
+--        to a UVSegd index it could overflow.
+--
+getSeg :: UPVSegd -> Int -> (Int, Int, Int)
+{-# INLINE getSeg #-}
+getSeg (UPVSegd vsegids upssegd) ix
+ = let  (len, _index, start, source) = UPSSegd.getSeg upssegd (vsegids V.! ix)
+   in   (len, start, source)
+
+
+-- Demotion -------------------------------------------------------------------
+-- | O(segs). Yield a `UPSSegd` that describes each segment of a `UPVSegd`
+--   individually.
+--
+--   * By doing this we lose information about virtual segments corresponding
+--     to the same physical segments.
+-- 
+--   * This operation is used in concatPR as the first step in eliminating
+--     segmentation from a nested array.
+-- 
+demoteToUPSSegd :: UPVSegd -> UPSSegd
+{-# INLINE demoteToUPSSegd #-}
+demoteToUPSSegd (UPVSegd vsegids upssegd)
+ = let  starts'         = bpermuteUP (UPSSegd.takeStarts  upssegd) vsegids
+        sources'        = bpermuteUP (UPSSegd.takeSources upssegd) vsegids
+        lengths'        = bpermuteUP (UPSSegd.takeLengths upssegd) vsegids
+        upsegd'         = UPSegd.fromLengths lengths'
+   in   UPSSegd.mkUPSSegd starts' sources' upsegd'
+
+
+-- | O(segs). Given an virtual segment descriptor, produce a `UPSegd` that
+--   that describes the entire array.
+--
+--   WARNING:
+--   Trying to take the `UPSegd` of a nested array that has been constructed with
+--   replication can cause index overflow. This is because the virtual size of
+--   the corresponding flat data can be larger than physical memory.
+-- 
+--   You should only apply this function to a nested array when you're about
+--   about to construct something with the same size as the corresponding
+--   flat array. In this case the index overflow doesn't matter too much
+--   because the program would OOM anyway.
+--
+unsafeDemoteToUPSegd :: UPVSegd -> UPSegd
+{-# INLINE unsafeDemoteToUPSegd #-}
+unsafeDemoteToUPSegd (UPVSegd vsegids upssegd)
+        = UPSegd.fromLengths
+        $ bpermuteUP (UPSSegd.takeLengths upssegd) vsegids
+
+
+-- Operators ------------------------------------------------------------------
+-- | Update the virtual segment ids of a UPVSegd and force out unreachable
+--   physical segments from the contained UPSSegd.
+--
+--   * TODO: make this parallel. It runs the sequential 'cull' then reconstructs
+--     the UPSSegd.
+-- 
+updateVSegs :: (Vector Int -> Vector Int) -> UPVSegd -> UPVSegd
+{-# INLINE updateVSegs #-}
+updateVSegs f (UPVSegd vsegids upssegd)
+ = let  (vsegids', ussegd') 
+                = USSegd.cullOnVSegids (f vsegids) 
+                $ UPSSegd.takeUSSegd upssegd
+
+   in   UPVSegd vsegids' (UPSSegd.fromUSSegd ussegd')
+
+
+-- Append ---------------------------------------------------------------------
+-- | Produce a segment descriptor that describes the result of appending two arrays.
+-- 
+--   * TODO: make this parallel.
+--
+appendWith
+        :: UPVSegd -> Int  -- ^ uvsegd of array, and number of physical data arrays
+        -> UPVSegd -> Int  -- ^ uvsegd of array, and number of physical data arrays
+        -> UPVSegd
+
+{-# INLINE appendWith #-}
+appendWith
+        (UPVSegd vsegids1 upssegd1) pdatas1
+        (UPVSegd vsegids2 upssegd2) pdatas2
+
+ = let  -- vsegids releative to appended psegs
+        vsegids1' = vsegids1
+        vsegids2' = V.map (+ UPSSegd.length upssegd1) vsegids2
+        
+        -- append the vsegids
+        vsegids'  = vsegids1' V.++ vsegids2'
+
+        -- All data from the source arrays goes into the result
+        upssegd'  = UPSSegd.appendWith
+                                upssegd1 pdatas1
+                                upssegd2 pdatas2
+                                 
+   in   UPVSegd vsegids' upssegd'
+
+
+-- Combine --------------------------------------------------------------------
+-- | Combine two virtual segment descriptors.
+--
+--   * TODO: make this parallel. 
+--
+combine2
+        :: UPSel2
+        -> UPVSegd -> Int   -- ^ uvsegd of array, and number of physical data arrays
+        -> UPVSegd -> Int   -- ^ uvsegd of array, and number of physical data arrays
+        -> UPVSegd
+        
+{-# INLINE combine2 #-}
+combine2
+        upsel2
+        (UPVSegd vsegids1 upssegd1) pdatas1
+        (UPVSegd vsegids2 upssegd2) pdatas2
+
+ = let  -- vsegids relative to combined psegs
+        vsegids1' = vsegids1
+        vsegids2' = V.map (+ (V.length vsegids1)) vsegids2
+
+        -- combine the vsegids
+        vsegids'  = V.combine2ByTag (UPSel.tagsUPSel2 upsel2)
+                                    vsegids1' vsegids2'
+
+         -- All data from the source arrays goes into the result
+        upssegd'  = UPSSegd.appendWith
+                                upssegd1 pdatas1
+                                upssegd2 pdatas2
+                                  
+   in   UPVSegd vsegids' upssegd'
index 7480a9b..b195bdf 100644 (file)
@@ -19,6 +19,7 @@ Library
         Data.Array.Parallel.Unlifted.Parallel
         Data.Array.Parallel.Unlifted.Parallel.UPSegd
         Data.Array.Parallel.Unlifted.Parallel.UPSSegd
+        Data.Array.Parallel.Unlifted.Parallel.UPVSegd
         Data.Array.Parallel.Unlifted.Parallel.UPSel
         Data.Array.Parallel.Unlifted
 
index 460c4d2..3316c5f 100644 (file)
@@ -145,17 +145,17 @@ appendSSegd             = USSegd.append
 type VSegd              = UVSegd.UVSegd
 mkVSegd                 = UVSegd.mkUVSegd
 validVSegd              = UVSegd.valid
-emptyVSegd              = UVSegd.empty
-singletonVSegd          = UVSegd.singleton
 promoteSegdToVSegd      = UVSegd.fromUSegd
-unsafeMaterializeVSegd  = UVSegd.unsafeMaterialize
 promoteSSegdToVSegd     = UVSegd.fromUSegd
-demoteVSegdToSSegd      = UVSegd.toUSSegd
-vsegidsVSegd            = UVSegd.takeVSegids
-ssegdVSegd              = UVSegd.takeUSSegd
-lengthVSegd             = UVSegd.length
-lengthsVSegd            = UVSegd.takeLengths
+emptyVSegd              = UVSegd.empty
+singletonVSegd          = UVSegd.singleton
+lengthOfVSegd           = UVSegd.length
+takeVSegidsOfVSegd      = UVSegd.takeVSegids
+takeSSegdOfVSegd        = UVSegd.takeUSSegd
+takeLengthsOfVSegd      = UVSegd.takeLengths
 getSegOfVSegd           = UVSegd.getSeg
+demoteToSSegdOfVSegd    = UVSegd.toUSSegd
+demoteToSegdOfVSegd     = UVSegd.unsafeMaterialize
 updateVSegsOfVSegd      = UVSegd.updateVSegs
 appendVSegd             = UVSegd.append
 combine2VSegd           = UVSegd.combine2
index 96c3a5e..ab32316 100644 (file)
@@ -1,4 +1,5 @@
 {-# OPTIONS -Wall -fno-warn-orphans -fno-warn-missing-signatures #-}
+
 -- | Segment descriptors for virtual arrays.
 module Data.Array.Parallel.Unlifted.Sequential.UVSegd (
         -- * Types
@@ -9,10 +10,10 @@ module Data.Array.Parallel.Unlifted.Sequential.UVSegd (
         
         -- * Constructors
         mkUVSegd,
-        empty,
-        singleton,
         fromUSegd,
         fromUSSegd,
+        empty,
+        singleton,
         
         -- * Projections
         length,
@@ -67,6 +68,16 @@ instance PprPhysical UVSegd where
   , pprp ussegd ]
 
 
+
+-- | O(1).
+--   Check the internal consistency of a virutal segmentation descriptor.
+--   TODO: check that all vsegs point to a valid pseg
+valid :: UVSegd -> Bool
+{-# INLINE valid #-}
+valid (UVSegd vsegids ussegd)
+        = V.length vsegids == USSegd.length ussegd
+
+
 -- Constructors ---------------------------------------------------------------
 -- | O(1). 
 --   Construct a new virtual segment descriptor.
@@ -81,32 +92,6 @@ mkUVSegd
 mkUVSegd = UVSegd
 
 
--- | O(1).
---   Check the internal consistency of a virutal segmentation descriptor.
---   TODO: check that all vsegs point to a valid pseg
-valid :: UVSegd -> Bool
-{-# INLINE valid #-}
-valid (UVSegd vsegids ussegd)
-        = V.length vsegids == USSegd.length ussegd
-
-
--- | O(1).
---  Yield an empty segment descriptor, with no elements or segments.
-empty :: UVSegd
-{-# INLINE empty #-}
-empty = UVSegd V.empty USSegd.empty
-
-
--- | O(1).
---   Yield a singleton segment descriptor.
---   The single segment covers the given number of elements in a flat array
---   with sourceid 0.
-singleton :: Int -> UVSegd
-{-# INLINE singleton #-}
-singleton n 
-        = UVSegd (V.singleton 0) (USSegd.singleton n)
-
-
 -- | O(segs). 
 --   Promote a plain USSegd to a UVSegd
 --   The result contains one virtual segment for every physical segment
@@ -127,8 +112,25 @@ fromUSSegd ussegd
 fromUSegd :: USegd -> UVSegd
 {-# INLINE fromUSegd #-}
 fromUSegd
-        = fromUSSegd
-        . USSegd.fromUSegd
+        = fromUSSegd . USSegd.fromUSegd
+
+
+-- | O(1).
+--  Yield an empty segment descriptor, with no elements or segments.
+empty :: UVSegd
+{-# INLINE empty #-}
+empty   = UVSegd V.empty USSegd.empty
+
+
+-- | O(1).
+--   Yield a singleton segment descriptor.
+--   The single segment covers the given number of elements in a flat array
+--   with sourceid 0.
+singleton :: Int -> UVSegd
+{-# INLINE singleton #-}
+singleton n 
+        = UVSegd (V.singleton 0) (USSegd.singleton n)
+
         
 
 -- Projections ----------------------------------------------------------------
@@ -136,27 +138,27 @@ takeVSegids :: UVSegd -> Vector Int
 {-# INLINE takeVSegids #-}
 takeVSegids (UVSegd vsegids _)
         = vsegids
+
         
 takeUSSegd :: UVSegd -> USSegd
 {-# INLINE takeUSSegd #-}
 takeUSSegd (UVSegd _ ussegd)
         = ussegd
 
+
 length :: UVSegd -> Int
 {-# INLINE length #-}
 length (UVSegd vsegids _)
         = V.length vsegids
 
--- | O(segs).
---   Yield the lengths of the segments described by a `UVSegd`.
+-- | O(segs). Yield the lengths of the segments described by a `UVSegd`.
 takeLengths :: UVSegd -> Vector Int
 {-# INLINE takeLengths #-}
 takeLengths (UVSegd vsegids ussegd)
         = V.map (USSegd.takeLengths ussegd V.!) vsegids
 
 
--- | O(1).
---  Get the length, starting index, and source id of a segment.
+-- | O(1). Get the length, starting index, and source id of a segment.
 --
 --  NOTE: We don't return the segment index field from the USSegd as this refers
 --        to the flat index relative to the SSegd array, rather than