Re: some ideas for multithreading support

Sam Steingold writes:
 > > * Don Cohen <[email protected]> [2017-12-20 20:06:46 +0000]:
 > >
 > > Suppose an iteration over a table starts in a state with the table
 > > empty, and another thread performs the following operations in the
 > > following order:
 > >  operation     resulting state
 > >  add A => 1    (A=>1)
 > >  add B => 2    (A=>1,B=>2)
 > >  remove A      (B=>2)
 > >  add A => 3    (B=>2,A=>3)  
 > >  remove B      (A=>3)
 > >  add B => 4    (A=>3,B=>4)
 > > and now the iteration returns.  
 > > Suppose the iteration simply collects and returns a list of all the
 > > keys and values in the order visited.
 > > The following results from the iteration are allowable:
 > >  NIL - the iteration could have finished before the first add
 > >  all of the resulting states listed above are allowed when 
 > >    interpreted as iterations results, since the entire iteration
 > >    could have been performed in that state
 > >  (A=>1,B=>4), even though the table was never in such a state,
 > >    because it could visit A right after A was added and B just
 > >    before the end)
 > >  (B=>4) is allowed because A might have been visited during the
 > >    time it was not present, and then B visited at the end.
 > >
 > > However (B=>4,A=>1) is NOT allowed, because after B became
 > > related to 4, A was never related to 1.
 > 
 > I cannot imagine how you can prevent this.
 > Suppose the iteration collected A=>1 (after 1st or 2nd step) but, before
 > it could terminate, the 1st thread did all its work.
 > Now iteration sees that the key vector has length 2, it saw the 1st
 > element and now it processes the second element which is B which points
 > to 4.
 > Thus iteration will collect B=>4,A=>1.

You're missing the point that the result is being returned in 
visited order.
If it visits A first and gets A=>1, then later visits B and gets B=>4
it returns the list (A=>1,B=>4), NOT the list (B=>4,A=>1).
In order to return (B=>4,A=>1) it would have to first visit B and find
4 as the value, and then later visit A and find 1 as the value.
And this is incompatible with the history of states.

Notice that the "state" descriptions are unordered sets of key/value
pairs, but the iteration results are ordered.
 > >  all of the resulting states listed above are allowed when 
 > >    interpreted as iterations results, since the entire iteration
The "interpreted as" above means that the unordered state (A=>3,B=>4)
is interpreted as the result of first visiting A and then B.
In fact, any of the orderings of any of the actual states would be 
allowed as iteration results since the entire iteration could be
done in that state in any order.
However (A=>1,B=>4) is outside of that class.  

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
clisp-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/clisp-devel