Parallelizing code -- design problem in networkish code

[Charles Hixson]

On 12/14/2012 01:50 PM, Ali Çehreli wrote:
> On 12/13/2012 08:38 PM, Charles Hixson wrote:
>
>  > Now what I was thinking of involved an array in another class (i.e., not
>  > the Cell class) defined:
>  > Cell[] cells;
>  > and the Cell class, which includes:
>  > public class Cell
>  > { ...
>  > Idno[] ups;
>  > ...
>  > }
>  > where ups is an array of Id#s which are indexes into cells. While
>  > processing a cell, it's likely that ups will be used to index into cells
>  > to adjust the weight of the similar reference down to this cell. (And
>  > yes, there's an array of downs also, which also does an indirection
>  > through cells to adjust weights of cells below it that refer to the
>  > current cell.
>
> That description makes me think that there will be data races on
> accesses to weights: Some threads will be reading while others will be
> writing. If I understood correctly, that would disqualify std.parallelism.
>
>  > This process offers several possibilities of collision when done in
>  > parallel, which was why I though that the alterations should probably be
>  > done via creating a new cell and substituting it for the original one.
>  > If this isn't necessary, it would be a real benefit.
>
> I hope others have answers to your questions. Sorry...
>
> Ali
>
Actually, data races will probably need to be accepted.  At least in the 
sense of some (external) reads getting stale data. That's no worse than 
using immutable data, and creating a new version with every change.  (At 
that point, any cell holding a pointer to the old version would be 
working with stale data.)  Any approach involving locking reads of data 
will quickly devolve into a HUGE number of pairs of node in deadly embrace.

The thing is, stale data will generally only have a minor effect.  And I 
think that an optimal solution is probably impossible.  What I'm looking 
for is a "sufficiently good" solution.  Think more of "eventual 
consistency" than of consistency.

(Note:  This reply is over 10 days after the original post, and is only 
for the benefit of later readers.)