GHC Trac Home
GHC Git Repos
Report a bug
Mailing Lists & IRC
The GHC Team
GHC Status Info
Tickets I Created
Patches for review
New Feature Req
side by side
lines around each change
Show the changes in full context
White space changes
Aug 7, 2011 12:29:29 PM (
Replication 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.
A plan to fix the problem
Fixing the problem: Plan A (Repeated Segments)
Generally, we don't want to copy replicated data — it's a waste of space! We definitely don't want to do it for large data structures, and in particular, we don't want to do it for arrays. After all, that can change the asymptotic work complexity of a program. To keep it simple, we are for the moment focusing on avoiding replicating arrays, as this is were our practical problems are coming from at the moment. (Some cases of replicated scalars are also eliminated by fusion.)
TODO: What if we have segment descriptors on top of one with repeated segments?
== Fixing the problem: Plan B (Lifted Application) ==
The applications of `replicatePA` and `expandPA` that introduce segmented arrays with repeated segments in Plan A are in the definition of `mapP`, specifically `replicatePA` is used in `mapP_S` and `expandPA` in `mapP_L` (see Page 403 of HtM):
mapP_S :: (a :-> b) -> PA a :-> PA b
mapP_S (Clo env _ fl) xss
= fl (replicatePA (lengthPA xss) env) xss
mapP_L :: PA (a :-> b) -> PA (PA a) -> PA (PA b)
mapP_L (AClo env _ fl) xss
= unconcatPA xss (fl (expandPA xss env) (concatPA xss))
In both cases, we replicate the environment of a closure before we apply the lifted version of the function represented by the closure.
The idea behind Plan A is that `replicatePA` and `expandPA` produce a segmented array that encodes the replication without unnecessarily copying data and that the consumer —the lifted function `fl`— processes segmented arrays with encoded replication in a special manner.
== Related work ==