Changes between Version 4 and Version 5 of DataParallel/Replicate


Ignore:
Timestamp:
Jun 20, 2011 2:15:14 PM (4 years ago)
Author:
chak
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • DataParallel/Replicate

    v4 v5  
    3333== A plan to fix the problem ==
    3434
     35Generally, 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.  So, instead of having `replicateP` allocate and fill a new array with multiple copies of the same data, we use a special array representation that stores the data (once!) together with the replication count.  This is surely the most space efficient representation for a replicated array.
     36
     37The downside of a special representation is that we now also need to modify all consumers of replicated arrays to accept this new representation and to handle it specially.  This leads to some code blow up (each array consumer needs to be able to dynamically decide between two input array representations), and we need to be careful not to disturb fusion.
     38
    3539TODO:
    36  * Special representation for replicated arrays
    3740 * Avoiding out of bounds indices
    3841 * Mention need to be careful with length