11635: Race condition in SequenceableCollection>>shuffle
Sven suggested posting this on the list for discussion, so here you go:
Maybe this should be discussed on the list, your are going to break API.
Note that there is also #sort and #sorted with similar copy behavior.
Also, I am not sure that basic operations should use mutexes to protect themselves by default: there is a cost when you are a single threaded user. Even in Java there are synchronized and non-synchronized versions of collections. IMHO, the protection should happen in your app, and basic collections do not have to be thread safe.
Sven
#shuffle does not use Collection>>mutexForPicking as other users of #randomForPicking demonstrate. This can lead to race conditions (found in our application).
In addition, there are now #shuffle, #shuffled, #shuffleBy: and #shuffledBy: where #shuffled and #shuffledBy: shuffle a copy and answers that. This is very confusing.
I propose a fix where #shuffled and #shuffledBy: are renamed to #copyShuffle and #copyShuffledBy: and moved to the "copying" protocol. #shuffle and #copyShuffle will use the mutex to prevent race conditions.
Here is my 100% personal opinion: I don't like the copyShuffle. To me, the rules are quite clear: sort shuffle reverse etc... -> perform modification in place sorted shuffled reversed etc... -> answer a copy I hope the methods comments are clear. Does PBE tells about these conventions? It would be a good thing. And I don't like to have mutexes in base library, the less we have, the better. If a user is going to modify the same object concurrently, he/she takes care of mutual exclusion. 2013/9/23 Max Leske <maxleske@gmail.com>
Sven suggested posting this on the list for discussion, so here you go:
Maybe this should be discussed on the list, your are going to break API.
Note that there is also #sort and #sorted with similar copy behavior.
Also, I am not sure that basic operations should use mutexes to protect themselves by default: there is a cost when you are a single threaded user. Even in Java there are synchronized and non-synchronized versions of collections. IMHO, the protection should happen in your app, and basic collections do not have to be thread safe.
Sven
#shuffle does not use Collection>>mutexForPicking as other users of #randomForPicking demonstrate. This can lead to race conditions (found in our application).
In addition, there are now #shuffle, #shuffled, #shuffleBy: and #shuffledBy: where #shuffled and #shuffledBy: shuffle a copy and answers that. This is very confusing.
I propose a fix where #shuffled and #shuffledBy: are renamed to #copyShuffle and #copyShuffledBy: and moved to the "copying" protocol. #shuffle and #copyShuffle will use the mutex to prevent race conditions.
On 23 September 2013 14:17, Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com> wrote:
Here is my 100% personal opinion:
I don't like the copyShuffle. To me, the rules are quite clear: sort shuffle reverse etc... -> perform modification in place sorted shuffled reversed etc... -> answer a copy I hope the methods comments are clear. Does PBE tells about these conventions? It would be a good thing.
And I don't like to have mutexes in base library, the less we have, the better. If a user is going to modify the same object concurrently, he/she takes care of mutual exclusion.
Especially since locks don't compose. If you _really_ cared about accessing something concurrently, you'd share immutable data structures. frank
2013/9/23 Max Leske <maxleske@gmail.com>
Sven suggested posting this on the list for discussion, so here you go:
Maybe this should be discussed on the list, your are going to break API.
Note that there is also #sort and #sorted with similar copy behavior.
Also, I am not sure that basic operations should use mutexes to protect themselves by default: there is a cost when you are a single threaded user. Even in Java there are synchronized and non-synchronized versions of collections. IMHO, the protection should happen in your app, and basic collections do not have to be thread safe.
Sven
#shuffle does not use Collection>>mutexForPicking as other users of #randomForPicking demonstrate. This can lead to race conditions (found in our application).
In addition, there are now #shuffle, #shuffled, #shuffleBy: and #shuffledBy: where #shuffled and #shuffledBy: shuffle a copy and answers that. This is very confusing.
I propose a fix where #shuffled and #shuffledBy: are renamed to #copyShuffle and #copyShuffledBy: and moved to the "copying" protocol. #shuffle and #copyShuffle will use the mutex to prevent race conditions.
On 23.09.2013, at 15:20, Frank Shearar <frank.shearar@gmail.com> wrote:
On 23 September 2013 14:17, Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com> wrote:
Here is my 100% personal opinion:
I don't like the copyShuffle. To me, the rules are quite clear: sort shuffle reverse etc... -> perform modification in place sorted shuffled reversed etc... -> answer a copy I hope the methods comments are clear. Does PBE tells about these conventions? It would be a good thing.
And I don't like to have mutexes in base library, the less we have, the better. If a user is going to modify the same object concurrently, he/she takes care of mutual exclusion.
Especially since locks don't compose. If you _really_ cared about accessing something concurrently, you'd share immutable data structures.
I don't quite follow. Could you elaborate?
frank
2013/9/23 Max Leske <maxleske@gmail.com>
Sven suggested posting this on the list for discussion, so here you go:
Maybe this should be discussed on the list, your are going to break API.
Note that there is also #sort and #sorted with similar copy behavior.
Also, I am not sure that basic operations should use mutexes to protect themselves by default: there is a cost when you are a single threaded user. Even in Java there are synchronized and non-synchronized versions of collections. IMHO, the protection should happen in your app, and basic collections do not have to be thread safe.
Sven
#shuffle does not use Collection>>mutexForPicking as other users of #randomForPicking demonstrate. This can lead to race conditions (found in our application).
In addition, there are now #shuffle, #shuffled, #shuffleBy: and #shuffledBy: where #shuffled and #shuffledBy: shuffle a copy and answers that. This is very confusing.
I propose a fix where #shuffled and #shuffledBy: are renamed to #copyShuffle and #copyShuffledBy: and moved to the "copying" protocol. #shuffle and #copyShuffle will use the mutex to prevent race conditions.
On 23 September 2013 14:34, Max Leske <maxleske@gmail.com> wrote:
On 23.09.2013, at 15:20, Frank Shearar <frank.shearar@gmail.com> wrote:
On 23 September 2013 14:17, Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com> wrote:
Here is my 100% personal opinion:
I don't like the copyShuffle. To me, the rules are quite clear: sort shuffle reverse etc... -> perform modification in place sorted shuffled reversed etc... -> answer a copy I hope the methods comments are clear. Does PBE tells about these conventions? It would be a good thing.
And I don't like to have mutexes in base library, the less we have, the better. If a user is going to modify the same object concurrently, he/she takes care of mutual exclusion.
Especially since locks don't compose. If you _really_ cared about accessing something concurrently, you'd share immutable data structures.
I don't quite follow. Could you elaborate?
Hopefully it's uncontroversial to assert that locks don't compose. If you only ever have one thread of execution, you don't have any concurrency issues, and locks serve no purpose. If you do have multiple threads of execution, then you have a few choices for sharing data: * you can use a lock around mutable data (but lock-using blocks of code don't compose, so you end up with loads of bugs or deadlocks or nests of locks, or all of the above) * you can share a _copy_ of data. In the latter case, you can share an actual copy, or share a pointer to a structure that can't change. If it can't change, you can't have a reader accidentally reading something from a structure halfway through the writer writing to it. Sharing some immutable chunk of state lets you save the memory taken up by a copy, but also prevents all the race condition things you usually get with shared mutable state. frank
frank
2013/9/23 Max Leske <maxleske@gmail.com>
Sven suggested posting this on the list for discussion, so here you go:
Maybe this should be discussed on the list, your are going to break API.
Note that there is also #sort and #sorted with similar copy behavior.
Also, I am not sure that basic operations should use mutexes to protect themselves by default: there is a cost when you are a single threaded user. Even in Java there are synchronized and non-synchronized versions of collections. IMHO, the protection should happen in your app, and basic collections do not have to be thread safe.
Sven
#shuffle does not use Collection>>mutexForPicking as other users of #randomForPicking demonstrate. This can lead to race conditions (found in our application).
In addition, there are now #shuffle, #shuffled, #shuffleBy: and #shuffledBy: where #shuffled and #shuffledBy: shuffle a copy and answers that. This is very confusing.
I propose a fix where #shuffled and #shuffledBy: are renamed to #copyShuffle and #copyShuffledBy: and moved to the "copying" protocol. #shuffle and #copyShuffle will use the mutex to prevent race conditions.
On 23.09.2013, at 15:46, Frank Shearar <frank.shearar@gmail.com> wrote:
On 23 September 2013 14:34, Max Leske <maxleske@gmail.com> wrote:
On 23.09.2013, at 15:20, Frank Shearar <frank.shearar@gmail.com> wrote:
On 23 September 2013 14:17, Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com> wrote:
Here is my 100% personal opinion:
I don't like the copyShuffle. To me, the rules are quite clear: sort shuffle reverse etc... -> perform modification in place sorted shuffled reversed etc... -> answer a copy I hope the methods comments are clear. Does PBE tells about these conventions? It would be a good thing.
And I don't like to have mutexes in base library, the less we have, the better. If a user is going to modify the same object concurrently, he/she takes care of mutual exclusion.
Especially since locks don't compose. If you _really_ cared about accessing something concurrently, you'd share immutable data structures.
I don't quite follow. Could you elaborate?
Hopefully it's uncontroversial to assert that locks don't compose.
If you only ever have one thread of execution, you don't have any concurrency issues, and locks serve no purpose.
If you do have multiple threads of execution, then you have a few choices for sharing data: * you can use a lock around mutable data (but lock-using blocks of code don't compose, so you end up with loads of bugs or deadlocks or nests of locks, or all of the above) * you can share a _copy_ of data.
In the latter case, you can share an actual copy, or share a pointer to a structure that can't change. If it can't change, you can't have a reader accidentally reading something from a structure halfway through the writer writing to it.
Sharing some immutable chunk of state lets you save the memory taken up by a copy, but also prevents all the race condition things you usually get with shared mutable state.
frank
Thanks Frank, I get it now. And I agree.
frank
2013/9/23 Max Leske <maxleske@gmail.com>
Sven suggested posting this on the list for discussion, so here you go:
Maybe this should be discussed on the list, your are going to break API.
Note that there is also #sort and #sorted with similar copy behavior.
Also, I am not sure that basic operations should use mutexes to protect themselves by default: there is a cost when you are a single threaded user. Even in Java there are synchronized and non-synchronized versions of collections. IMHO, the protection should happen in your app, and basic collections do not have to be thread safe.
Sven
#shuffle does not use Collection>>mutexForPicking as other users of #randomForPicking demonstrate. This can lead to race conditions (found in our application).
In addition, there are now #shuffle, #shuffled, #shuffleBy: and #shuffledBy: where #shuffled and #shuffledBy: shuffle a copy and answers that. This is very confusing.
I propose a fix where #shuffled and #shuffledBy: are renamed to #copyShuffle and #copyShuffledBy: and moved to the "copying" protocol. #shuffle and #copyShuffle will use the mutex to prevent race conditions.
On 23.09.2013, at 15:17, Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com> wrote:
Here is my 100% personal opinion:
I don't like the copyShuffle.
Me neither :) But see below.
To me, the rules are quite clear: sort shuffle reverse etc... -> perform modification in place
agreed.
sorted shuffled reversed etc... -> answer a copy
If you're aware that this convention exists, then ok. BUT: I've been working with Pharo for over 4 years now and I wasn't aware of it. Since we want to make Pharo accessible to new users it is my oppinion that this convention isn't a good one. Especially since messages that answer a copy usually are named #copyXXX. To me, there is no semantical difference between #shuffle and #shuffled, the message names are not revealing in this case (again: personal oppion).
I hope the methods comments are clear. Does PBE tells about these conventions? It would be a good thing.
And I don't like to have mutexes in base library, the less we have, the better. If a user is going to modify the same object concurrently, he/she takes care of mutual exclusion.
Agreed. BUT: the Random object used by these methods is the same one that is used by #atRandom for instance, hence the race condition. There is no way anyone can safely use these methods without the mutex, single threaded or not. Calls to methods using that same Random object can be all over the place and also in the base system.
2013/9/23 Max Leske <maxleske@gmail.com> Sven suggested posting this on the list for discussion, so here you go:
Maybe this should be discussed on the list, your are going to break API.
Note that there is also #sort and #sorted with similar copy behavior.
Also, I am not sure that basic operations should use mutexes to protect themselves by default: there is a cost when you are a single threaded user. Even in Java there are synchronized and non-synchronized versions of collections. IMHO, the protection should happen in your app, and basic collections do not have to be thread safe.
Sven
#shuffle does not use Collection>>mutexForPicking as other users of #randomForPicking demonstrate. This can lead to race conditions (found in our application).
In addition, there are now #shuffle, #shuffled, #shuffleBy: and #shuffledBy: where #shuffled and #shuffledBy: shuffle a copy and answers that. This is very confusing.
I propose a fix where #shuffled and #shuffledBy: are renamed to #copyShuffle and #copyShuffledBy: and moved to the "copying" protocol. #shuffle and #copyShuffle will use the mutex to prevent race conditions.
On Sep 23, 2013, at 3:33 , Max Leske <maxleske@gmail.com> wrote:
If a user is going to modify the same object concurrently, he/she takes care of mutual exclusion.
Agreed. BUT: the Random object used by these methods is the same one that is used by #atRandom for instance, hence the race condition. There is no way anyone can safely use these methods without the mutex, single threaded or not. Calls to methods using that same Random object can be all over the place and also in the base system.
It seems to me an existing Random instance is used in this case mostly* for performance. One could argue that since the Random in this case is used for a bulk operation, for which the object creation cost is largely amortized for collection sizes > 20, it's acceptable to instead use Random new by default, which wouldn't suffer from the same race conditions. While still slower than a mutex-protected version for single-threaded code, it would also scale correctly if the users (and vm) are actually multi-threaded. [#(1 2 3 4 5 6 7 8 9 10 11 12) shuffle] bench '208,000 per second.' '222,000 per second.' '223,000 per second.' [#(1 2 3 4 5 6 7 8 9 10 11 12) shuffleWithMutex] bench '188,000 per second.' '186,000 per second.''184,000 per second.' [#(1 2 3 4 5 6 7 8 9 10 11 12) shuffleNewRandom] bench '167,000 per second.' '166,000 per second.' '167,000 per second.' Cheers, Henry * Low seed entropy is another issue, but if purely random shuffling is a critical requirement, one shouldn't use the default Random generator anyways...
100% agree. Do it right > do it fast. We must not turn usage of the library into something fragile for the sake of speed. We already make the code itself fragile more often than not in term of complexity (harder to understand/test/change). Especially, introduction of shared mutable states (global, class vars, singleton or any other form) should ring an alarm in reviewers head (This is some very old Squeak code in this case, so Squeakers are to blame, but we're all in same bath). 2013/9/23 Henrik Johansen <henrik.s.johansen@veloxit.no>
On Sep 23, 2013, at 3:33 , Max Leske <maxleske@gmail.com> wrote:
If a user is going to modify the same object concurrently, he/she takes
care of mutual exclusion.
Agreed. BUT: the Random object used by these methods is the same one that is used by #atRandom for instance, hence the race condition. There is no way anyone can safely use these methods without the mutex, single threaded or not. Calls to methods using that same Random object can be all over the place and also in the base system.
It seems to me an existing Random instance is used in this case mostly* for performance. One could argue that since the Random in this case is used for a bulk operation, for which the object creation cost is largely amortized for collection sizes > 20, it's acceptable to instead use Random new by default, which wouldn't suffer from the same race conditions. While still slower than a mutex-protected version for single-threaded code, it would also scale correctly if the users (and vm) are actually multi-threaded.
[#(1 2 3 4 5 6 7 8 9 10 11 12) shuffle] bench '208,000 per second.' '222,000 per second.' '223,000 per second.' [#(1 2 3 4 5 6 7 8 9 10 11 12) shuffleWithMutex] bench '188,000 per second.' '186,000 per second.''184,000 per second.' [#(1 2 3 4 5 6 7 8 9 10 11 12) shuffleNewRandom] bench '167,000 per second.' '166,000 per second.' '167,000 per second.'
Cheers, Henry
* Low seed entropy is another issue, but if purely random shuffling is a critical requirement, one shouldn't use the default Random generator anyways...
+1 Now I understand the point of max with the name sort/sorted because this is not explicit to me too :) I laways have to think. On Sep 23, 2013, at 6:28 PM, Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com> wrote:
100% agree. Do it right > do it fast. We must not turn usage of the library into something fragile for the sake of speed. We already make the code itself fragile more often than not in term of complexity (harder to understand/test/change).
Especially, introduction of shared mutable states (global, class vars, singleton or any other form) should ring an alarm in reviewers head (This is some very old Squeak code in this case, so Squeakers are to blame, but we're all in same bath).
2013/9/23 Henrik Johansen <henrik.s.johansen@veloxit.no>
On Sep 23, 2013, at 3:33 , Max Leske <maxleske@gmail.com> wrote:
If a user is going to modify the same object concurrently, he/she takes care of mutual exclusion.
Agreed. BUT: the Random object used by these methods is the same one that is used by #atRandom for instance, hence the race condition. There is no way anyone can safely use these methods without the mutex, single threaded or not. Calls to methods using that same Random object can be all over the place and also in the base system.
It seems to me an existing Random instance is used in this case mostly* for performance. One could argue that since the Random in this case is used for a bulk operation, for which the object creation cost is largely amortized for collection sizes > 20, it's acceptable to instead use Random new by default, which wouldn't suffer from the same race conditions. While still slower than a mutex-protected version for single-threaded code, it would also scale correctly if the users (and vm) are actually multi-threaded.
[#(1 2 3 4 5 6 7 8 9 10 11 12) shuffle] bench '208,000 per second.' '222,000 per second.' '223,000 per second.' [#(1 2 3 4 5 6 7 8 9 10 11 12) shuffleWithMutex] bench '188,000 per second.' '186,000 per second.''184,000 per second.' [#(1 2 3 4 5 6 7 8 9 10 11 12) shuffleNewRandom] bench '167,000 per second.' '166,000 per second.' '167,000 per second.'
Cheers, Henry
* Low seed entropy is another issue, but if purely random shuffling is a critical requirement, one shouldn't use the default Random generator anyways...
The reason why I don't like the explicit "copy", is because this is the default behaviour. In place mutation is an (evil) exception. I'm personnally fine with current conventions: - sort, shuffle, reverse, replace: are imperative, thus you are telling collection, sort yourself ! - sorted clearly sounds as a sorted copy for me. If ever a change was to be made, I would much prefer this to happen on opposite naming, sort -> inPlaceSort, or sortYourself :) It's like telling the programmer, hey - a stateful mutation is really what you want, is it? 2013/9/23 Stéphane Ducasse <stephane.ducasse@inria.fr>
+1 Now I understand the point of max with the name sort/sorted because this is not explicit to me too :) I laways have to think.
On Sep 23, 2013, at 6:28 PM, Nicolas Cellier < nicolas.cellier.aka.nice@gmail.com> wrote:
100% agree. Do it right > do it fast. We must not turn usage of the library into something fragile for the sake of speed. We already make the code itself fragile more often than not in term of complexity (harder to understand/test/change).
Especially, introduction of shared mutable states (global, class vars, singleton or any other form) should ring an alarm in reviewers head (This is some very old Squeak code in this case, so Squeakers are to blame, but we're all in same bath).
2013/9/23 Henrik Johansen <henrik.s.johansen@veloxit.no>
On Sep 23, 2013, at 3:33 , Max Leske <maxleske@gmail.com> wrote:
If a user is going to modify the same object concurrently, he/she
takes care of mutual exclusion.
Agreed. BUT: the Random object used by these methods is the same one that is used by #atRandom for instance, hence the race condition. There is no way anyone can safely use these methods without the mutex, single threaded or not. Calls to methods using that same Random object can be all over the place and also in the base system.
It seems to me an existing Random instance is used in this case mostly* for performance. One could argue that since the Random in this case is used for a bulk operation, for which the object creation cost is largely amortized for collection sizes > 20, it's acceptable to instead use Random new by default, which wouldn't suffer from the same race conditions. While still slower than a mutex-protected version for single-threaded code, it would also scale correctly if the users (and vm) are actually multi-threaded.
[#(1 2 3 4 5 6 7 8 9 10 11 12) shuffle] bench '208,000 per second.' '222,000 per second.' '223,000 per second.' [#(1 2 3 4 5 6 7 8 9 10 11 12) shuffleWithMutex] bench '188,000 per second.' '186,000 per second.''184,000 per second.' [#(1 2 3 4 5 6 7 8 9 10 11 12) shuffleNewRandom] bench '167,000 per second.' '166,000 per second.' '167,000 per second.'
Cheers, Henry
* Low seed entropy is another issue, but if purely random shuffling is a critical requirement, one shouldn't use the default Random generator anyways...
Thanks for the feedback guys. Based on the discussion I propose a different set of changes: 1. shuffle ^ self shuffleBy: Random new 2. shuffled ^ self copy shuffle 3. remove #shuffledBy: (if you're specific enough to use a custom Random instance you can also create a copy of the collection yourself if you want to) I leave the matter of renaming the methods for further discussion. Personally I'm for more intention revealing selectors; I quite like #shuffle and #shuffleInPlace. If we can agree on a different naming scheme we should then apply it to other methods aswell of course (e.g. #sort, #sortInPlace). Also open for discussion is the use of Collection>>randomForPicking and Collection>>mutexForPicking in other methods (such as #atRandom). I think it shouldn't be too big a problem to make those methods use individual Random instances and to remove the two class variables from Collection. Cheers, Max On 24.09.2013, at 02:33, btc@openInWorld.com wrote:
Nicolas Cellier wrote:
The reason why I don't like the explicit "copy", is because this is the default behaviour. In place mutation is an (evil) exception. I'm personnally fine with current conventions: - sort, shuffle, reverse, replace: are imperative, thus you are telling collection, sort yourself ! - sorted clearly sounds as a sorted copy for me. If ever a change was to be made, I would much prefer this to happen on opposite naming, sort -> inPlaceSort, or sortYourself :) It's like telling the programmer, hey - a stateful mutation is really what you want, is it?
Conventions should encourage good programming practice. Although it makes perfect sense on hearing it, I was explicitly not aware of the convention between 'sort' and 'sorted'. For me, the small difference in letters used between the two doesn't provide a wide enough distinction. Also, regarding not mutating state, I guess I knew that in the back of my head, but it has not generally been an explicit concern of mine while programming. Convention should encourage good programming. So I like the suggestion of inPlaceSort & sortYourself. As well as being more intention revealing, the less desirable methods are made less attractive by using a longer name. Perhaps another naming convention could be mutatedSort, or mutSort as a hint that the programmer should consider using these in conjunction with mutexes, or at own risk.
cheers -ben
2013/9/23 Stéphane Ducasse <stephane.ducasse@inria.fr>
+1 Now I understand the point of max with the name sort/sorted because this is not explicit to me too :) I laways have to think.
On Sep 23, 2013, at 6:28 PM, Nicolas Cellier < nicolas.cellier.aka.nice@gmail.com> wrote:
100% agree. Do it right > do it fast. We must not turn usage of the library into something fragile for the sake of speed. We already make the code itself fragile more often than not in term of complexity (harder to understand/test/change).
Especially, introduction of shared mutable states (global, class vars, singleton or any other form) should ring an alarm in reviewers head (This is some very old Squeak code in this case, so Squeakers are to blame, but we're all in same bath).
2013/9/23 Henrik Johansen <henrik.s.johansen@veloxit.no>
On Sep 23, 2013, at 3:33 , Max Leske <maxleske@gmail.com> wrote:
If a user is going to modify the same object concurrently, he/she
takes care of mutual exclusion.
Agreed. BUT: the Random object used by these methods is the same one
that is used by #atRandom for instance, hence the race condition. There is no way anyone can safely use these methods without the mutex, single threaded or not. Calls to methods using that same Random object can be all over the place and also in the base system.
It seems to me an existing Random instance is used in this case mostly* for performance. One could argue that since the Random in this case is used for a bulk operation, for which the object creation cost is largely amortized for collection sizes > 20, it's acceptable to instead use Random new by default, which wouldn't suffer from the same race conditions. While still slower than a mutex-protected version for single-threaded code, it would also scale correctly if the users (and vm) are actually multi-threaded.
[#(1 2 3 4 5 6 7 8 9 10 11 12) shuffle] bench '208,000 per second.' '222,000 per second.' '223,000 per second.' [#(1 2 3 4 5 6 7 8 9 10 11 12) shuffleWithMutex] bench '188,000 per second.' '186,000 per second.''184,000 per second.' [#(1 2 3 4 5 6 7 8 9 10 11 12) shuffleNewRandom] bench '167,000 per second.' '166,000 per second.' '167,000 per second.'
Cheers, Henry
* Low seed entropy is another issue, but if purely random shuffling is a critical requirement, one shouldn't use the default Random generator anyways...
On Sep 28, 2013, at 10:59 , Max Leske <maxleske@gmail.com> wrote:
Thanks for the feedback guys.
Based on the discussion I propose a different set of changes:
1. shuffle ^ self shuffleBy: Random new
2. shuffled ^ self copy shuffle
3. remove #shuffledBy: (if you're specific enough to use a custom Random instance you can also create a copy of the collection yourself if you want to)
I leave the matter of renaming the methods for further discussion. Personally I'm for more intention revealing selectors; I quite like #shuffle and #shuffleInPlace. If we can agree on a different naming scheme we should then apply it to other methods aswell of course (e.g. #sort, #sortInPlace).
Also open for discussion is the use of Collection>>randomForPicking and Collection>>mutexForPicking in other methods (such as #atRandom). I think it shouldn't be too big a problem to make those methods use individual Random instances and to remove the two class variables from Collection.
Cheers, Max
+1 from me on all three suggestions, as you might guess. :) As for #atRandom using Random new, the performance hit and seed quality would be much greater concerns, as the Random instance would only be used once per invocation. At this point in time there's no good alternatives to the current approach, but renaming the mutex/shared variable to reflect its singular use would be one possible improvement, I guess. Cheers, Henry
Name: SLICE-Issue-11635-Race-condition-in-SequenceableCollectionshuffle-MaxLeske.2 Author: MaxLeske Time: 30 October 2013, 1:41:57.198092 pm UUID: c3d51645-7e81-4997-b74c-545bf7ef60b0 Ancestors: Dependencies: Collections-Abstract-MaxLeske.231, Collections-Unordered-MaxLeske.175 made changes as detailed on the mailing list * shuffle ^ self shuffleBy: Random new * shuffled ^ self copy shuffle * removed #shuffledBy: * Matrix uses #shuffleBy: (on an explicit copy) instead of #shuffledBy: On 01.10.2013, at 17:06, Henrik Johansen <henrik.s.johansen@veloxit.no> wrote:
On Sep 28, 2013, at 10:59 , Max Leske <maxleske@gmail.com> wrote:
Thanks for the feedback guys.
Based on the discussion I propose a different set of changes:
1. shuffle ^ self shuffleBy: Random new
2. shuffled ^ self copy shuffle
3. remove #shuffledBy: (if you're specific enough to use a custom Random instance you can also create a copy of the collection yourself if you want to)
I leave the matter of renaming the methods for further discussion. Personally I'm for more intention revealing selectors; I quite like #shuffle and #shuffleInPlace. If we can agree on a different naming scheme we should then apply it to other methods aswell of course (e.g. #sort, #sortInPlace).
Also open for discussion is the use of Collection>>randomForPicking and Collection>>mutexForPicking in other methods (such as #atRandom). I think it shouldn't be too big a problem to make those methods use individual Random instances and to remove the two class variables from Collection.
Cheers, Max
+1 from me on all three suggestions, as you might guess. :)
As for #atRandom using Random new, the performance hit and seed quality would be much greater concerns, as the Random instance would only be used once per invocation. At this point in time there's no good alternatives to the current approach, but renaming the mutex/shared variable to reflect its singular use would be one possible improvement, I guess.
Cheers, Henry
bump...
Thanks for the feedback guys.
Based on the discussion I propose a different set of changes:
1. shuffle ^ self shuffleBy: Random new
2. shuffled ^ self copy shuffle
3. remove #shuffledBy: (if you're specific enough to use a custom Random instance you can also create a copy of the collection yourself if you want to)
I leave the matter of renaming the methods for further discussion. Personally I'm for more intention revealing selectors; I quite like #shuffle and #shuffleInPlace. If we can agree on a different naming scheme we should then apply it to other methods aswell of course (e.g. #sort, #sortInPlace).
Also open for discussion is the use of Collection>>randomForPicking and Collection>>mutexForPicking in other methods (such as #atRandom). I think it shouldn't be too big a problem to make those methods use individual Random instances and to remove the two class variables from Collection.
Cheers, Max
On 24.09.2013, at 02:33, btc@openInWorld.com wrote:
Nicolas Cellier wrote:
The reason why I don't like the explicit "copy", is because this is the default behaviour. In place mutation is an (evil) exception. I'm personnally fine with current conventions: - sort, shuffle, reverse, replace: are imperative, thus you are telling collection, sort yourself ! - sorted clearly sounds as a sorted copy for me. If ever a change was to be made, I would much prefer this to happen on opposite naming, sort -> inPlaceSort, or sortYourself :) It's like telling the programmer, hey - a stateful mutation is really what you want, is it?
Conventions should encourage good programming practice. Although it makes perfect sense on hearing it, I was explicitly not aware of the convention between 'sort' and 'sorted'. For me, the small difference in letters used between the two doesn't provide a wide enough distinction. Also, regarding not mutating state, I guess I knew that in the back of my head, but it has not generally been an explicit concern of mine while programming. Convention should encourage good programming. So I like the suggestion of inPlaceSort & sortYourself. As well as being more intention revealing, the less desirable methods are made less attractive by using a longer name. Perhaps another naming convention could be mutatedSort, or mutSort as a hint that the programmer should consider using these in conjunction with mutexes, or at own risk.
cheers -ben
2013/9/23 Stéphane Ducasse <stephane.ducasse@inria.fr>
+1 Now I understand the point of max with the name sort/sorted because this is not explicit to me too :) I laways have to think.
On Sep 23, 2013, at 6:28 PM, Nicolas Cellier < nicolas.cellier.aka.nice@gmail.com> wrote:
100% agree. Do it right > do it fast. We must not turn usage of the library into something fragile for the sake of speed. We already make the code itself fragile more often than not in term of complexity (harder to understand/test/change).
Especially, introduction of shared mutable states (global, class vars, singleton or any other form) should ring an alarm in reviewers head (This is some very old Squeak code in this case, so Squeakers are to blame, but we're all in same bath).
2013/9/23 Henrik Johansen <henrik.s.johansen@veloxit.no>
On Sep 23, 2013, at 3:33 , Max Leske <maxleske@gmail.com> wrote:
If a user is going to modify the same object concurrently, he/she
takes care of mutual exclusion.
Agreed. BUT: the Random object used by these methods is the same one
that is used by #atRandom for instance, hence the race condition. There is no way anyone can safely use these methods without the mutex, single threaded or not. Calls to methods using that same Random object can be all over the place and also in the base system.
It seems to me an existing Random instance is used in this case mostly* for performance. One could argue that since the Random in this case is used for a bulk operation, for which the object creation cost is largely amortized for collection sizes > 20, it's acceptable to instead use Random new by default, which wouldn't suffer from the same race conditions. While still slower than a mutex-protected version for single-threaded code, it would also scale correctly if the users (and vm) are actually multi-threaded.
[#(1 2 3 4 5 6 7 8 9 10 11 12) shuffle] bench '208,000 per second.' '222,000 per second.' '223,000 per second.' [#(1 2 3 4 5 6 7 8 9 10 11 12) shuffleWithMutex] bench '188,000 per second.' '186,000 per second.''184,000 per second.' [#(1 2 3 4 5 6 7 8 9 10 11 12) shuffleNewRandom] bench '167,000 per second.' '166,000 per second.' '167,000 per second.'
Cheers, Henry
* Low seed entropy is another issue, but if purely random shuffling is a critical requirement, one shouldn't use the default Random generator anyways...
On Sep 23, 2013, at 3:17 PM, Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com> wrote:
Here is my 100% personal opinion:
I don't like the copyShuffle. To me, the rules are quite clear: sort shuffle reverse etc... -> perform modification in place sorted shuffled reversed etc... -> answer a copy I hope the methods comments are clear. Does PBE tells about these conventions? It would be a good thing.
I do not remember. Because probably that we wrote it before. I will log it and see for the next release of PBE.
And I don't like to have mutexes in base library, the less we have, the better. If a user is going to modify the same object concurrently, he/she takes care of mutual exclusion.
2013/9/23 Max Leske <maxleske@gmail.com> Sven suggested posting this on the list for discussion, so here you go:
Maybe this should be discussed on the list, your are going to break API.
Note that there is also #sort and #sorted with similar copy behavior.
Also, I am not sure that basic operations should use mutexes to protect themselves by default: there is a cost when you are a single threaded user. Even in Java there are synchronized and non-synchronized versions of collections. IMHO, the protection should happen in your app, and basic collections do not have to be thread safe.
Sven
#shuffle does not use Collection>>mutexForPicking as other users of #randomForPicking demonstrate. This can lead to race conditions (found in our application).
In addition, there are now #shuffle, #shuffled, #shuffleBy: and #shuffledBy: where #shuffled and #shuffledBy: shuffle a copy and answers that. This is very confusing.
I propose a fix where #shuffled and #shuffledBy: are renamed to #copyShuffle and #copyShuffledBy: and moved to the "copying" protocol. #shuffle and #copyShuffle will use the mutex to prevent race conditions.
participants (6)
-
btc＠openinworld.com -
Frank Shearar -
Henrik Johansen -
Max Leske -
Nicolas Cellier -
Stéphane Ducasse