Changes between Version 2 and Version 3 of DataParallel/Replicate

Jun 15, 2011 2:31:22 PM (6 years ago)



  • DataParallel/Replicate

    v2 v3  
    1818  | otherwise
    1919  = let len     = lengthP xx
    20           half    = len `div` 2
    21           s1      = sliceP 0    half xx
    22           s2      = sliceP half half  xx           
     20        half    = len `div` 2
     21        s1      = sliceP 0    half xx
     22        s2      = sliceP half half  xx           
    2323      in concatP (mapP (treeLookup table) [: s1, s2 :])
    2525Here `table` is constant in `mapP (treeLookup table) [: s1, s2 :]`; hence, the entire `table` gets duplicated on each level of the recursion, leading to space consumption that is exponential in the depth of the recursion.
     28== What's happening here? ==
     30Replication of scalars and arrays is always a waste of time and space.  However, it is particularly problematic if the replicated structure is consumed by an indexing operation as it can change the asymptotic work complexity of the vectorised program.  This holds not only for indexing, but for any operation that consumes only a small part of its input array(s).  In other words, if a replicated structure is consumed in its entirety (for example by a fold), the asymptotic work complexity of replication matches that of consuming the structure.  For operations that only consume a small part of their input, that is not the case.  Hence, lifting, which introduces the replication, does increase asymptotic work.
     33== A plan to fix the problem ==