OrderedCollection protocols are broken: a potential fix
Hello guys, I was looking into the OrderedCollection protocols recently to see how well the sista optimizer perform with it methods, and I realized that this is completely broken. For example: col := #(1 2 3 4 5) asOrderedCollection. col do: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]]. => '12345678' However: col := #(1 2 3 4 5) asOrderedCollection. col collect: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]]. => '12345' This means that #do: and #reverseDo: iterate over all the elements of the collection,*including* the ones that you are adding while iterating over the collection, whereas all the other OrderedCollection protocols, such as #collect:, #select:, iterates over all the elements of the collection, *excluding* the ones you are adding while iterating over the collection. Marcus argued that one should not edit a collection while iterating over it, however this point is not valid as the World menu relies on this feature, using #do: to iterate over the elements of the OrderedCollection including the one it is adding while iterating over the collection. Changing the implementation makes the world menu display half of its items. I don't like this difference because it is inconsistent. For example, refactoring a #do: into a #collect: can simply not work because they do not iterate over the same elements if you are editing the collection while iterating over it. In VW, the protocols are consistent and iterating over a collection never iterates over the elements one is adding while iterating over it. Therefore, I believe most frameworks should expect this behavior (at least the ones cross smalltalk) which sounds the most correct. I think we should fix the world menu implementation and make the protocols consistent. Alternatively, we can let VW be a much more consistent Smalltalk environment than Pharo. What do you think ? Clement
Clement, I am not sure, but could this not be a compiler issue ? Not with Opal but with the old compiler ?! I mean, if you look at the implementations of OrderedCollection>>#do: and OrderedCollection>>#collect: they basically do the same thing, going from firstIndex to lastIndex, both of which are instance variables, but in the first case, the #do:, the end test is evaluated on each iteration, while in the second case, the #to:do:, the end test should be evaluated only once. Since lastIndex changes while iterating, one iteration sees it, the other not. Looking at the byte codes seems to confirm that: the compilation of the #:to:do is different: Opal correctly moves both instance variables to temps, while the old compiler keeps on referring to the second instance variable (lastIndex) directly on each loop - which is plain wrong IMHO. I am with Marcus that you should not modify a collection that you iterate over. What if you would be inserting values at arbitrary places ? I am with you that both (all) enumerations should be consistent. Like in VW, delegating to the simplest #do: seems best. Sven On 03 Sep 2014, at 11:42, Clément Bera <bera.clement@gmail.com> wrote:
Hello guys,
I was looking into the OrderedCollection protocols recently to see how well the sista optimizer perform with it methods, and I realized that this is completely broken.
For example:
col := #(1 2 3 4 5) asOrderedCollection. col do: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345678'
However:
col := #(1 2 3 4 5) asOrderedCollection. col collect: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345'
This means that #do: and #reverseDo: iterate over all the elements of the collection,*including* the ones that you are adding while iterating over the collection, whereas all the other OrderedCollection protocols, such as #collect:, #select:, iterates over all the elements of the collection, *excluding* the ones you are adding while iterating over the collection.
Marcus argued that one should not edit a collection while iterating over it, however this point is not valid as the World menu relies on this feature, using #do: to iterate over the elements of the OrderedCollection including the one it is adding while iterating over the collection. Changing the implementation makes the world menu display half of its items.
I don't like this difference because it is inconsistent. For example, refactoring a #do: into a #collect: can simply not work because they do not iterate over the same elements if you are editing the collection while iterating over it.
In VW, the protocols are consistent and iterating over a collection never iterates over the elements one is adding while iterating over it. Therefore, I believe most frameworks should expect this behavior (at least the ones cross smalltalk) which sounds the most correct.
I think we should fix the world menu implementation and make the protocols consistent. Alternatively, we can let VW be a much more consistent Smalltalk environment than Pharo. What do you think ?
Clement
I think we should change OrderedCollection>>#do: aBlock "Override the superclass for performance reasons." firstIndex to: lastIndex do: [ :index | aBlock value: (array at: index) ] Clement, Do you happen to know exactly where the world menu building goes wrong ? Sven On 03 Sep 2014, at 13:51, Sven Van Caekenberghe <sven@stfx.eu> wrote:
Clement,
I am not sure, but could this not be a compiler issue ? Not with Opal but with the old compiler ?!
I mean, if you look at the implementations of OrderedCollection>>#do: and OrderedCollection>>#collect: they basically do the same thing, going from firstIndex to lastIndex, both of which are instance variables, but in the first case, the #do:, the end test is evaluated on each iteration, while in the second case, the #to:do:, the end test should be evaluated only once. Since lastIndex changes while iterating, one iteration sees it, the other not.
Looking at the byte codes seems to confirm that: the compilation of the #:to:do is different: Opal correctly moves both instance variables to temps, while the old compiler keeps on referring to the second instance variable (lastIndex) directly on each loop - which is plain wrong IMHO.
I am with Marcus that you should not modify a collection that you iterate over. What if you would be inserting values at arbitrary places ?
I am with you that both (all) enumerations should be consistent. Like in VW, delegating to the simplest #do: seems best.
Sven
On 03 Sep 2014, at 11:42, Clément Bera <bera.clement@gmail.com> wrote:
Hello guys,
I was looking into the OrderedCollection protocols recently to see how well the sista optimizer perform with it methods, and I realized that this is completely broken.
For example:
col := #(1 2 3 4 5) asOrderedCollection. col do: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345678'
However:
col := #(1 2 3 4 5) asOrderedCollection. col collect: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345'
This means that #do: and #reverseDo: iterate over all the elements of the collection,*including* the ones that you are adding while iterating over the collection, whereas all the other OrderedCollection protocols, such as #collect:, #select:, iterates over all the elements of the collection, *excluding* the ones you are adding while iterating over the collection.
Marcus argued that one should not edit a collection while iterating over it, however this point is not valid as the World menu relies on this feature, using #do: to iterate over the elements of the OrderedCollection including the one it is adding while iterating over the collection. Changing the implementation makes the world menu display half of its items.
I don't like this difference because it is inconsistent. For example, refactoring a #do: into a #collect: can simply not work because they do not iterate over the same elements if you are editing the collection while iterating over it.
In VW, the protocols are consistent and iterating over a collection never iterates over the elements one is adding while iterating over it. Therefore, I believe most frameworks should expect this behavior (at least the ones cross smalltalk) which sounds the most correct.
I think we should fix the world menu implementation and make the protocols consistent. Alternatively, we can let VW be a much more consistent Smalltalk environment than Pharo. What do you think ?
Clement
2014-09-03 14:44 GMT+02:00 Sven Van Caekenberghe <sven@stfx.eu>:
I think we should change
OrderedCollection>>#do: aBlock "Override the superclass for performance reasons."
firstIndex to: lastIndex do: [ :index | aBlock value: (array at: index) ]
I agree. It's easier to read. But if you do that world menu does not work any more :-/
Clement,
Do you happen to know exactly where the world menu building goes wrong ?
I think so. The problem is in methods such as menuCommandOn: aBuilder <worldMenu> (aBuilder group: #SystemChanges) parent: #Tools; order: 0.51; with: [ (aBuilder item: #'Change Sorter') action:[self open]; icon: self taskbarIcon. (aBuilder item: #'Recover lost changes...') icon: Smalltalk ui icons recoverLostChangesIcon; action: [Smalltalk tools changeList browseRecentLog].]. aBuilder withSeparatorAfter. Here you have a with block which add other items to the menu. Then in the method PragmaMenuBuilder>>#interpretRegistration:, while iterating other the registrations, The code "node with: block" line 12 calls PragmaMenuBuilder>>#currentRoot:while: which activates the block, adding new elements to the collection it iterates from in PragmaMenuBuilder>>#interpretRegistration:. Be ready to use haltOnce / inspectOnce to debug these cases :-).
Sven
On 03 Sep 2014, at 13:51, Sven Van Caekenberghe <sven@stfx.eu> wrote:
Clement,
I am not sure, but could this not be a compiler issue ? Not with Opal but with the old compiler ?!
I mean, if you look at the implementations of OrderedCollection>>#do: and OrderedCollection>>#collect: they basically do the same thing, going from firstIndex to lastIndex, both of which are instance variables, but in the first case, the #do:, the end test is evaluated on each iteration, while in the second case, the #to:do:, the end test should be evaluated only once. Since lastIndex changes while iterating, one iteration sees it, the other not.
Looking at the byte codes seems to confirm that: the compilation of the #:to:do is different: Opal correctly moves both instance variables to temps, while the old compiler keeps on referring to the second instance variable (lastIndex) directly on each loop - which is plain wrong IMHO.
I am with Marcus that you should not modify a collection that you iterate over. What if you would be inserting values at arbitrary places ?
I am with you that both (all) enumerations should be consistent. Like in VW, delegating to the simplest #do: seems best.
Sven
On 03 Sep 2014, at 11:42, Clément Bera <bera.clement@gmail.com> wrote:
Hello guys,
I was looking into the OrderedCollection protocols recently to see how well the sista optimizer perform with it methods, and I realized that this is completely broken.
For example:
col := #(1 2 3 4 5) asOrderedCollection. col do: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345678'
However:
col := #(1 2 3 4 5) asOrderedCollection. col collect: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345'
This means that #do: and #reverseDo: iterate over all the elements of the collection,*including* the ones that you are adding while iterating over the collection, whereas all the other OrderedCollection protocols, such as #collect:, #select:, iterates over all the elements of the collection, *excluding* the ones you are adding while iterating over the collection.
Marcus argued that one should not edit a collection while iterating over it, however this point is not valid as the World menu relies on this feature, using #do: to iterate over the elements of the OrderedCollection including the one it is adding while iterating over the collection. Changing the implementation makes the world menu display half of its items.
I don't like this difference because it is inconsistent. For example, refactoring a #do: into a #collect: can simply not work because they do not iterate over the same elements if you are editing the collection while iterating over it.
In VW, the protocols are consistent and iterating over a collection never iterates over the elements one is adding while iterating over it. Therefore, I believe most frameworks should expect this behavior (at least the ones cross smalltalk) which sounds the most correct.
I think we should fix the world menu implementation and make the protocols consistent. Alternatively, we can let VW be a much more consistent Smalltalk environment than Pharo. What do you think ?
Clement
On Wed, 3 Sep 2014, Clément Bera wrote:
Hello guys, I was looking into the OrderedCollection protocols recently to see how well the sista optimizer perform with it methods, and I realized that this is completely broken.
For example:
col := #(1 2 3 4 5) asOrderedCollection. col do: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345678'
However:
col := #(1 2 3 4 5) asOrderedCollection. col collect: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345'
This means that #do: and #reverseDo: iterate over all the elements of the collection,*including* the ones that you are adding while iterating over the collection, whereas all the other OrderedCollection protocols, such as #collect:, #select:, iterates over all the elements of the collection, *excluding* the ones you are adding while iterating over the collection.
In case of #select and #collect: this is only true for elements added with #addLast:, #addFirst:, or #add:, but there are other methods which can have (even worse) side effects (#add:after:, #add:before:, etc). Levente
Marcus argued that one should not edit a collection while iterating over it, however this point is not valid as the World menu relies on this feature, using #do: to iterate over the elements of the OrderedCollection including the one it is adding while iterating over the collection. Changing the implementation makes the world menu display half of its items.
I don't like this difference because it is inconsistent. For example, refactoring a #do: into a #collect: can simply not work because they do not iterate over the same elements if you are editing the collection while iterating over it.
In VW, the protocols are consistent and iterating over a collection never iterates over the elements one is adding while iterating over it. Therefore, I believe most frameworks should expect this behavior (at least the ones cross smalltalk) which sounds the most correct.
I think we should fix the world menu implementation and make the protocols consistent. Alternatively, we can let VW be a much more consistent Smalltalk environment than Pharo. What do you think ?
Clement
On 3 sept. 2014, at 11:42, Clément Bera <bera.clement@gmail.com> wrote:
Hello guys,
I was looking into the OrderedCollection protocols recently to see how well the sista optimizer perform with it methods, and I realized that this is completely broken.
For example:
col := #(1 2 3 4 5) asOrderedCollection. col do: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345678'
However:
col := #(1 2 3 4 5) asOrderedCollection. col collect: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345'
This means that #do: and #reverseDo: iterate over all the elements of the collection,*including* the ones that you are adding while iterating over the collection, whereas all the other OrderedCollection protocols, such as #collect:, #select:, iterates over all the elements of the collection, *excluding* the ones you are adding while iterating over the collection.
Marcus argued that one should not edit a collection while iterating over it, however this point is not valid as the World menu relies on this feature, using #do: to iterate over the elements of the OrderedCollection including the one it is adding while iterating over the collection. Changing the implementation makes the world menu display half of its items.
I don't like this difference because it is inconsistent. For example, refactoring a #do: into a #collect: can simply not work because they do not iterate over the same elements if you are editing the collection while iterating over it.
In VW, the protocols are consistent and iterating over a collection never iterates over the elements one is adding while iterating over it. Therefore, I believe most frameworks should expect this behavior (at least the ones cross smalltalk) which sounds the most correct.
I think we should fix the world menu implementation and make the protocols consistent. Alternatively, we can let VW be a much more consistent Smalltalk environment than Pharo. What do you think ?
The thing is to find alternative implementations that are efficient enough (no copy). Maybe we can get some inspirations from VW for that (how do they do BTW?). You should also check with other kinds of collection because they may act differently than OrderedCollection. So in the end it depends on the amount of effort needed to make all collections consistent with this new requirement and on the resulting overhead. If it's too much, I think that following the old advice "don't modify a collection while iterating it" is enough. If one really needs to do such kind of things he should consider an alternative design like using a zipper for example. Camille
Clement
Hello, Sven you are right, the old compiler was consistent in the sense that it always iterated over all the elements, including the ones added with #add: and #addLast: while iterating over the collection. On the other hand, VW is consistent with the Opal implementation for #to:do: in the sense that they iterate only on the elements of the collection excluding the ones added while iterating. #add:after: and co do not work well if you edit the collection while iterating over it for sure :). It's too late for "don't modify a collection while iterating it" because the system does it, for example, to build the world menu. So I think the solution is in two steps: - removing code which edit the collection while iterating over it. As most frameworks work both on Pharo and VW and that the behavior is different I think there shouldn't be that much, so fixing the Pharo image may be enough. - be consistent in our collection protocol, basically by rewriting do: and reverseDo: like that: FROM: do: aBlock "Override the superclass for performance reasons." | index | index := firstIndex. [index <= lastIndex] whileTrue: [aBlock value: (array at: index). index := index + 1] TO: do: aBlock "Override the superclass for performance reasons." firstIndex to: lastIndex do: [ :index | aBlock value: (array at: index) ] 2014-09-03 14:05 GMT+02:00 Camille Teruel <camille.teruel@gmail.com>:
On 3 sept. 2014, at 11:42, Clément Bera <bera.clement@gmail.com> wrote:
Hello guys,
I was looking into the OrderedCollection protocols recently to see how well the sista optimizer perform with it methods, and I realized that this is completely broken.
For example:
col := #(1 2 3 4 5) asOrderedCollection. col do: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345678'
However:
col := #(1 2 3 4 5) asOrderedCollection. col collect: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345'
This means that #do: and #reverseDo: iterate over all the elements of the collection,*including* the ones that you are adding while iterating over the collection, whereas all the other OrderedCollection protocols, such as #collect:, #select:, iterates over all the elements of the collection, *excluding* the ones you are adding while iterating over the collection.
Marcus argued that one should not edit a collection while iterating over it, however this point is not valid as the World menu relies on this feature, using #do: to iterate over the elements of the OrderedCollection including the one it is adding while iterating over the collection. Changing the implementation makes the world menu display half of its items.
I don't like this difference because it is inconsistent. For example, refactoring a #do: into a #collect: can simply not work because they do not iterate over the same elements if you are editing the collection while iterating over it.
In VW, the protocols are consistent and iterating over a collection never iterates over the elements one is adding while iterating over it. Therefore, I believe most frameworks should expect this behavior (at least the ones cross smalltalk) which sounds the most correct.
I think we should fix the world menu implementation and make the protocols consistent. Alternatively, we can let VW be a much more consistent Smalltalk environment than Pharo. What do you think ?
The thing is to find alternative implementations that are efficient enough (no copy). Maybe we can get some inspirations from VW for that (how do they do BTW?). You should also check with other kinds of collection because they may act differently than OrderedCollection. So in the end it depends on the amount of effort needed to make all collections consistent with this new requirement and on the resulting overhead. If it's too much, I think that following the old advice "don't modify a collection while iterating it" is enough. If one really needs to do such kind of things he should consider an alternative design like using a zipper for example.
Camille
Clement
Clement we should fix the code of the menu :) Stef On 3/9/14 15:25, Clément Bera wrote:
Hello,
Sven you are right, the old compiler was consistent in the sense that it always iterated over all the elements, including the ones added with #add: and #addLast: while iterating over the collection. On the other hand, VW is consistent with the Opal implementation for #to:do: in the sense that they iterate only on the elements of the collection excluding the ones added while iterating.
#add:after: and co do not work well if you edit the collection while iterating over it for sure :).
It's too late for "don't modify a collection while iterating it" because the system does it, for example, to build the world menu. So I think the solution is in two steps: - removing code which edit the collection while iterating over it. As most frameworks work both on Pharo and VW and that the behavior is different I think there shouldn't be that much, so fixing the Pharo image may be enough. - be consistent in our collection protocol, basically by rewriting do: and reverseDo: like that:
FROM: do: aBlock "Override the superclass for performance reasons." | index | index := firstIndex. [index <= lastIndex] whileTrue: [aBlock value: (array at: index). index := index + 1] TO: do: aBlock "Override the superclass for performance reasons." firstIndex to: lastIndex do: [ :index | aBlock value: (array at: index) ]
2014-09-03 14:05 GMT+02:00 Camille Teruel <camille.teruel@gmail.com <mailto:camille.teruel@gmail.com>>:
On 3 sept. 2014, at 11:42, Clément Bera <bera.clement@gmail.com <mailto:bera.clement@gmail.com>> wrote:
> Hello guys, > > I was looking into the OrderedCollection protocols recently to see how well the sista optimizer perform with it methods, and I realized that this is completely broken. > > For example: > > col := #(1 2 3 4 5) asOrderedCollection. > col do: [ :elem | elem trace . > elem < 4 ifTrue: [ col add: col size + 1 ]]. > > => '12345678' > > However: > > col := #(1 2 3 4 5) asOrderedCollection. > col collect: [ :elem | elem trace . > elem < 4 ifTrue: [ col add: col size + 1 ]]. > > => '12345' > > This means that #do: and #reverseDo: iterate over all the elements of the collection,*including* the ones that you are adding while iterating over the collection, whereas all the other OrderedCollection protocols, such as #collect:, #select:, iterates over all the elements of the collection, *excluding* the ones you are adding while iterating over the collection. > > Marcus argued that one should not edit a collection while iterating over it, however this point is not valid as the World menu relies on this feature, using #do: to iterate over the elements of the OrderedCollection including the one it is adding while iterating over the collection. Changing the implementation makes the world menu display half of its items. > > I don't like this difference because it is inconsistent. For example, refactoring a #do: into a #collect: can simply not work because they do not iterate over the same elements if you are editing the collection while iterating over it. > > In VW, the protocols are consistent and iterating over a collection never iterates over the elements one is adding while iterating over it. Therefore, I believe most frameworks should expect this behavior (at least the ones cross smalltalk) which sounds the most correct. > > I think we should fix the world menu implementation and make the protocols consistent. Alternatively, we can let VW be a much more consistent Smalltalk environment than Pharo. What do you think ?
The thing is to find alternative implementations that are efficient enough (no copy). Maybe we can get some inspirations from VW for that (how do they do BTW?). You should also check with other kinds of collection because they may act differently than OrderedCollection. So in the end it depends on the amount of effort needed to make all collections consistent with this new requirement and on the resulting overhead. If it's too much, I think that following the old advice "don't modify a collection while iterating it" is enough. If one really needs to do such kind of things he should consider an alternative design like using a zipper for example.
Camille
> > Clement >
fogbugz entry for fixing the menu builder 13979 <https://pharo.fogbugz.com/default.asp?13979> PragmaMenuBuilder relies on modifying a collection while iterating over it. 2014-09-03 22:59 GMT+02:00 stepharo <stepharo@free.fr>:
Clement we should fix the code of the menu :)
Stef
On 3/9/14 15:25, Clément Bera wrote:
Hello,
Sven you are right, the old compiler was consistent in the sense that it always iterated over all the elements, including the ones added with #add: and #addLast: while iterating over the collection. On the other hand, VW is consistent with the Opal implementation for #to:do: in the sense that they iterate only on the elements of the collection excluding the ones added while iterating.
#add:after: and co do not work well if you edit the collection while iterating over it for sure :).
It's too late for "don't modify a collection while iterating it" because the system does it, for example, to build the world menu. So I think the solution is in two steps: - removing code which edit the collection while iterating over it. As most frameworks work both on Pharo and VW and that the behavior is different I think there shouldn't be that much, so fixing the Pharo image may be enough. - be consistent in our collection protocol, basically by rewriting do: and reverseDo: like that:
FROM: do: aBlock "Override the superclass for performance reasons." | index | index := firstIndex. [index <= lastIndex] whileTrue: [aBlock value: (array at: index). index := index + 1] TO: do: aBlock "Override the superclass for performance reasons." firstIndex to: lastIndex do: [ :index | aBlock value: (array at: index) ]
2014-09-03 14:05 GMT+02:00 Camille Teruel <camille.teruel@gmail.com>:
On 3 sept. 2014, at 11:42, Clément Bera <bera.clement@gmail.com> wrote:
Hello guys,
I was looking into the OrderedCollection protocols recently to see how well the sista optimizer perform with it methods, and I realized that this is completely broken.
For example:
col := #(1 2 3 4 5) asOrderedCollection. col do: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345678'
However:
col := #(1 2 3 4 5) asOrderedCollection. col collect: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345'
This means that #do: and #reverseDo: iterate over all the elements of the collection,*including* the ones that you are adding while iterating over the collection, whereas all the other OrderedCollection protocols, such as #collect:, #select:, iterates over all the elements of the collection, *excluding* the ones you are adding while iterating over the collection.
Marcus argued that one should not edit a collection while iterating over it, however this point is not valid as the World menu relies on this feature, using #do: to iterate over the elements of the OrderedCollection including the one it is adding while iterating over the collection. Changing the implementation makes the world menu display half of its items.
I don't like this difference because it is inconsistent. For example, refactoring a #do: into a #collect: can simply not work because they do not iterate over the same elements if you are editing the collection while iterating over it.
In VW, the protocols are consistent and iterating over a collection never iterates over the elements one is adding while iterating over it. Therefore, I believe most frameworks should expect this behavior (at least the ones cross smalltalk) which sounds the most correct.
I think we should fix the world menu implementation and make the protocols consistent. Alternatively, we can let VW be a much more consistent Smalltalk environment than Pharo. What do you think ?
The thing is to find alternative implementations that are efficient enough (no copy). Maybe we can get some inspirations from VW for that (how do they do BTW?). You should also check with other kinds of collection because they may act differently than OrderedCollection. So in the end it depends on the amount of effort needed to make all collections consistent with this new requirement and on the resulting overhead. If it's too much, I think that following the old advice "don't modify a collection while iterating it" is enough. If one really needs to do such kind of things he should consider an alternative design like using a zipper for example.
Camille
Clement
I added a slice for https://pharo.fogbugz.com/f/cases/13985/OrderedCollection-do-and-reverseDo-a... On 09 Sep 2014, at 12:53, Nicolai Hess <nicolaihess@web.de> wrote:
fogbugz entry for fixing the menu builder 13979 PragmaMenuBuilder relies on modifying a collection while iterating over it.
2014-09-03 22:59 GMT+02:00 stepharo <stepharo@free.fr>: Clement we should fix the code of the menu :)
Stef
On 3/9/14 15:25, Clément Bera wrote:
Hello,
Sven you are right, the old compiler was consistent in the sense that it always iterated over all the elements, including the ones added with #add: and #addLast: while iterating over the collection. On the other hand, VW is consistent with the Opal implementation for #to:do: in the sense that they iterate only on the elements of the collection excluding the ones added while iterating.
#add:after: and co do not work well if you edit the collection while iterating over it for sure :).
It's too late for "don't modify a collection while iterating it" because the system does it, for example, to build the world menu. So I think the solution is in two steps: - removing code which edit the collection while iterating over it. As most frameworks work both on Pharo and VW and that the behavior is different I think there shouldn't be that much, so fixing the Pharo image may be enough. - be consistent in our collection protocol, basically by rewriting do: and reverseDo: like that:
FROM: do: aBlock "Override the superclass for performance reasons." | index | index := firstIndex. [index <= lastIndex] whileTrue: [aBlock value: (array at: index). index := index + 1] TO: do: aBlock "Override the superclass for performance reasons." firstIndex to: lastIndex do: [ :index | aBlock value: (array at: index) ]
2014-09-03 14:05 GMT+02:00 Camille Teruel <camille.teruel@gmail.com>:
On 3 sept. 2014, at 11:42, Clément Bera <bera.clement@gmail.com> wrote:
Hello guys,
I was looking into the OrderedCollection protocols recently to see how well the sista optimizer perform with it methods, and I realized that this is completely broken.
For example:
col := #(1 2 3 4 5) asOrderedCollection. col do: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345678'
However:
col := #(1 2 3 4 5) asOrderedCollection. col collect: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345'
This means that #do: and #reverseDo: iterate over all the elements of the collection,*including* the ones that you are adding while iterating over the collection, whereas all the other OrderedCollection protocols, such as #collect:, #select:, iterates over all the elements of the collection, *excluding* the ones you are adding while iterating over the collection.
Marcus argued that one should not edit a collection while iterating over it, however this point is not valid as the World menu relies on this feature, using #do: to iterate over the elements of the OrderedCollection including the one it is adding while iterating over the collection. Changing the implementation makes the world menu display half of its items.
I don't like this difference because it is inconsistent. For example, refactoring a #do: into a #collect: can simply not work because they do not iterate over the same elements if you are editing the collection while iterating over it.
In VW, the protocols are consistent and iterating over a collection never iterates over the elements one is adding while iterating over it. Therefore, I believe most frameworks should expect this behavior (at least the ones cross smalltalk) which sounds the most correct.
I think we should fix the world menu implementation and make the protocols consistent. Alternatively, we can let VW be a much more consistent Smalltalk environment than Pharo. What do you think ?
The thing is to find alternative implementations that are efficient enough (no copy). Maybe we can get some inspirations from VW for that (how do they do BTW?). You should also check with other kinds of collection because they may act differently than OrderedCollection. So in the end it depends on the amount of effort needed to make all collections consistent with this new requirement and on the resulting overhead. If it's too much, I think that following the old advice "don't modify a collection while iterating it" is enough. If one really needs to do such kind of things he should consider an alternative design like using a zipper for example.
Camille
Clement
I like your slice Sven. The code is easier to read now in OrderedCollection and my optimizer can perform better. Thanks :) 2014-09-10 9:04 GMT+02:00 Sven Van Caekenberghe <sven@stfx.eu>:
I added a slice for https://pharo.fogbugz.com/f/cases/13985/OrderedCollection-do-and-reverseDo-a...
On 09 Sep 2014, at 12:53, Nicolai Hess <nicolaihess@web.de> wrote:
fogbugz entry for fixing the menu builder 13979 PragmaMenuBuilder relies on modifying a collection while iterating over it.
2014-09-03 22:59 GMT+02:00 stepharo <stepharo@free.fr>: Clement we should fix the code of the menu :)
Stef
On 3/9/14 15:25, Clément Bera wrote:
Hello,
Sven you are right, the old compiler was consistent in the sense that it always iterated over all the elements, including the ones added with #add: and #addLast: while iterating over the collection. On the other hand, VW is consistent with the Opal implementation for #to:do: in the sense that they iterate only on the elements of the collection excluding the ones added while iterating.
#add:after: and co do not work well if you edit the collection while iterating over it for sure :).
It's too late for "don't modify a collection while iterating it" because the system does it, for example, to build the world menu. So I think the solution is in two steps: - removing code which edit the collection while iterating over it. As most frameworks work both on Pharo and VW and that the behavior is different I think there shouldn't be that much, so fixing the Pharo image may be enough. - be consistent in our collection protocol, basically by rewriting do: and reverseDo: like that:
FROM: do: aBlock "Override the superclass for performance reasons." | index | index := firstIndex. [index <= lastIndex] whileTrue: [aBlock value: (array at: index). index := index + 1] TO: do: aBlock "Override the superclass for performance reasons." firstIndex to: lastIndex do: [ :index | aBlock value: (array at: index) ]
2014-09-03 14:05 GMT+02:00 Camille Teruel <camille.teruel@gmail.com>:
On 3 sept. 2014, at 11:42, Clément Bera <bera.clement@gmail.com> wrote:
Hello guys,
I was looking into the OrderedCollection protocols recently to see how well the sista optimizer perform with it methods, and I realized that this is completely broken.
For example:
col := #(1 2 3 4 5) asOrderedCollection. col do: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345678'
However:
col := #(1 2 3 4 5) asOrderedCollection. col collect: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345'
This means that #do: and #reverseDo: iterate over all the elements of the collection,*including* the ones that you are adding while iterating over the collection, whereas all the other OrderedCollection protocols, such as #collect:, #select:, iterates over all the elements of the collection, *excluding* the ones you are adding while iterating over the collection.
Marcus argued that one should not edit a collection while iterating over it, however this point is not valid as the World menu relies on this feature, using #do: to iterate over the elements of the OrderedCollection including the one it is adding while iterating over the collection. Changing the implementation makes the world menu display half of its items.
I don't like this difference because it is inconsistent. For example, refactoring a #do: into a #collect: can simply not work because they do not iterate over the same elements if you are editing the collection while iterating over it.
In VW, the protocols are consistent and iterating over a collection never iterates over the elements one is adding while iterating over it. Therefore, I believe most frameworks should expect this behavior (at least the ones cross smalltalk) which sounds the most correct.
I think we should fix the world menu implementation and make the protocols consistent. Alternatively, we can let VW be a much more consistent Smalltalk environment than Pharo. What do you think ?
The thing is to find alternative implementations that are efficient enough (no copy). Maybe we can get some inspirations from VW for that (how do they do BTW?). You should also check with other kinds of collection because they may act differently than OrderedCollection. So in the end it depends on the amount of effort needed to make all collections consistent with this new requirement and on the resulting overhead. If it's too much, I think that following the old advice "don't modify a collection while iterating it" is enough. If one really needs to do such kind of things he should consider an alternative design like using a zipper for example.
Camille
Clement
Thanks Clément, but it was really easy and trivial - Nicolai did the hard work with the pragma builder. I was wondering, does the optimiser also deal with #to:do:by as well as #to:do: ? On 10 Sep 2014, at 10:13, Clément Bera <bera.clement@gmail.com> wrote:
I like your slice Sven. The code is easier to read now in OrderedCollection and my optimizer can perform better.
Thanks :)
2014-09-10 9:04 GMT+02:00 Sven Van Caekenberghe <sven@stfx.eu>: I added a slice for https://pharo.fogbugz.com/f/cases/13985/OrderedCollection-do-and-reverseDo-a...
On 09 Sep 2014, at 12:53, Nicolai Hess <nicolaihess@web.de> wrote:
fogbugz entry for fixing the menu builder 13979 PragmaMenuBuilder relies on modifying a collection while iterating over it.
2014-09-03 22:59 GMT+02:00 stepharo <stepharo@free.fr>: Clement we should fix the code of the menu :)
Stef
On 3/9/14 15:25, Clément Bera wrote:
Hello,
Sven you are right, the old compiler was consistent in the sense that it always iterated over all the elements, including the ones added with #add: and #addLast: while iterating over the collection. On the other hand, VW is consistent with the Opal implementation for #to:do: in the sense that they iterate only on the elements of the collection excluding the ones added while iterating.
#add:after: and co do not work well if you edit the collection while iterating over it for sure :).
It's too late for "don't modify a collection while iterating it" because the system does it, for example, to build the world menu. So I think the solution is in two steps: - removing code which edit the collection while iterating over it. As most frameworks work both on Pharo and VW and that the behavior is different I think there shouldn't be that much, so fixing the Pharo image may be enough. - be consistent in our collection protocol, basically by rewriting do: and reverseDo: like that:
FROM: do: aBlock "Override the superclass for performance reasons." | index | index := firstIndex. [index <= lastIndex] whileTrue: [aBlock value: (array at: index). index := index + 1] TO: do: aBlock "Override the superclass for performance reasons." firstIndex to: lastIndex do: [ :index | aBlock value: (array at: index) ]
2014-09-03 14:05 GMT+02:00 Camille Teruel <camille.teruel@gmail.com>:
On 3 sept. 2014, at 11:42, Clément Bera <bera.clement@gmail.com> wrote:
Hello guys,
I was looking into the OrderedCollection protocols recently to see how well the sista optimizer perform with it methods, and I realized that this is completely broken.
For example:
col := #(1 2 3 4 5) asOrderedCollection. col do: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345678'
However:
col := #(1 2 3 4 5) asOrderedCollection. col collect: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345'
This means that #do: and #reverseDo: iterate over all the elements of the collection,*including* the ones that you are adding while iterating over the collection, whereas all the other OrderedCollection protocols, such as #collect:, #select:, iterates over all the elements of the collection, *excluding* the ones you are adding while iterating over the collection.
Marcus argued that one should not edit a collection while iterating over it, however this point is not valid as the World menu relies on this feature, using #do: to iterate over the elements of the OrderedCollection including the one it is adding while iterating over the collection. Changing the implementation makes the world menu display half of its items.
I don't like this difference because it is inconsistent. For example, refactoring a #do: into a #collect: can simply not work because they do not iterate over the same elements if you are editing the collection while iterating over it.
In VW, the protocols are consistent and iterating over a collection never iterates over the elements one is adding while iterating over it. Therefore, I believe most frameworks should expect this behavior (at least the ones cross smalltalk) which sounds the most correct.
I think we should fix the world menu implementation and make the protocols consistent. Alternatively, we can let VW be a much more consistent Smalltalk environment than Pharo. What do you think ?
The thing is to find alternative implementations that are efficient enough (no copy). Maybe we can get some inspirations from VW for that (how do they do BTW?). You should also check with other kinds of collection because they may act differently than OrderedCollection. So in the end it depends on the amount of effort needed to make all collections consistent with this new requirement and on the resulting overhead. If it's too much, I think that following the old advice "don't modify a collection while iterating it" is enough. If one really needs to do such kind of things he should consider an alternative design like using a zipper for example.
Camille
Clement
2014-09-10 10:16 GMT+02:00 Sven Van Caekenberghe <sven@stfx.eu>:
Thanks Clément, but it was really easy and trivial - Nicolai did the hard work with the pragma builder.
Ok I thought you did both. Thanks Nicolai too then.
I was wondering, does the optimiser also deal with #to:do:by as well as #to:do: ?
Yes. To have the optimizer working you need a comparison to escape the loop with < <= > or >= as selector, the comparison needs to compare a temp holding a smallinteger (the loop iterator) against another temp or self, and then you need an operation in the loop body that increments or decrements the loop iterator by a smallinteger constant. If all the conditions are met then the smallintegers operations and the array access have their overflow and bounds checks moved ahead of the loop body instead of at each iteration (and even removed if possible) based on the ranges the variables can have. The current problem was that with #whileTrue: the loop comparison was against an instance variable. Instance variables are problematic because then can be changed from other methods called by the loop body. Basically the optimizer can optimize mostly the receiver and the temporary variables, because to edit them from the outside of the method you need to do #become: or context access, and both cases are handled specifically. But we're at least a year from production so don't expect too much now :/.
On 10 Sep 2014, at 10:13, Clément Bera <bera.clement@gmail.com> wrote:
I like your slice Sven. The code is easier to read now in OrderedCollection and my optimizer can perform better.
Thanks :)
2014-09-10 9:04 GMT+02:00 Sven Van Caekenberghe <sven@stfx.eu>: I added a slice for https://pharo.fogbugz.com/f/cases/13985/OrderedCollection-do-and-reverseDo-a...
On 09 Sep 2014, at 12:53, Nicolai Hess <nicolaihess@web.de> wrote:
fogbugz entry for fixing the menu builder 13979 PragmaMenuBuilder relies on modifying a collection while iterating over it.
2014-09-03 22:59 GMT+02:00 stepharo <stepharo@free.fr>: Clement we should fix the code of the menu :)
Stef
On 3/9/14 15:25, Clément Bera wrote:
Hello,
Sven you are right, the old compiler was consistent in the sense that it always iterated over all the elements, including the ones added with #add: and #addLast: while iterating over the collection. On the other hand, VW is consistent with the Opal implementation for #to:do: in the sense that they iterate only on the elements of the collection excluding the ones added while iterating.
#add:after: and co do not work well if you edit the collection while iterating over it for sure :).
It's too late for "don't modify a collection while iterating it" because the system does it, for example, to build the world menu. So I think the solution is in two steps: - removing code which edit the collection while iterating over it. As most frameworks work both on Pharo and VW and that the behavior is different I think there shouldn't be that much, so fixing the Pharo image may be enough. - be consistent in our collection protocol, basically by rewriting do: and reverseDo: like that:
FROM: do: aBlock "Override the superclass for performance reasons." | index | index := firstIndex. [index <= lastIndex] whileTrue: [aBlock value: (array at: index). index := index + 1] TO: do: aBlock "Override the superclass for performance reasons." firstIndex to: lastIndex do: [ :index | aBlock value: (array at: index) ]
2014-09-03 14:05 GMT+02:00 Camille Teruel <camille.teruel@gmail.com>:
On 3 sept. 2014, at 11:42, Clément Bera <bera.clement@gmail.com> wrote:
Hello guys,
I was looking into the OrderedCollection protocols recently to see how well the sista optimizer perform with it methods, and I realized that this is completely broken.
For example:
col := #(1 2 3 4 5) asOrderedCollection. col do: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345678'
However:
col := #(1 2 3 4 5) asOrderedCollection. col collect: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345'
This means that #do: and #reverseDo: iterate over all the elements of the collection,*including* the ones that you are adding while iterating over the collection, whereas all the other OrderedCollection protocols, such as #collect:, #select:, iterates over all the elements of the collection, *excluding* the ones you are adding while iterating over the collection.
Marcus argued that one should not edit a collection while iterating over it, however this point is not valid as the World menu relies on this feature, using #do: to iterate over the elements of the OrderedCollection including the one it is adding while iterating over the collection. Changing the implementation makes the world menu display half of its items.
I don't like this difference because it is inconsistent. For example, refactoring a #do: into a #collect: can simply not work because they do not iterate over the same elements if you are editing the collection while iterating over it.
In VW, the protocols are consistent and iterating over a collection never iterates over the elements one is adding while iterating over it. Therefore, I believe most frameworks should expect this behavior (at least the ones cross smalltalk) which sounds the most correct.
I think we should fix the world menu implementation and make the protocols consistent. Alternatively, we can let VW be a much more consistent Smalltalk environment than Pharo. What do you think ?
The thing is to find alternative implementations that are efficient enough (no copy). Maybe we can get some inspirations from VW for that (how do they do BTW?). You should also check with other kinds of collection because they may act differently than OrderedCollection. So in the end it depends on the amount of effort needed to make all collections consistent with this new requirement and on the resulting overhead. If it's too much, I think that following the old advice "don't modify a collection while iterating it" is enough. If one really needs to do such kind of things he should consider an alternative design like using a zipper for example.
Camille
Clement
On 3 September 2014 11:42, Clément Bera <bera.clement@gmail.com> wrote:
Hello guys,
I was looking into the OrderedCollection protocols recently to see how well the sista optimizer perform with it methods, and I realized that this is completely broken.
For example:
col := #(1 2 3 4 5) asOrderedCollection. col do: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345678'
However:
col := #(1 2 3 4 5) asOrderedCollection. col collect: [ :elem | elem trace . elem < 4 ifTrue: [ col add: col size + 1 ]].
=> '12345'
This means that #do: and #reverseDo: iterate over all the elements of the collection,*including* the ones that you are adding while iterating over the collection, whereas all the other OrderedCollection protocols, such as #collect:, #select:, iterates over all the elements of the collection, *excluding* the ones you are adding while iterating over the collection.
Marcus argued that one should not edit a collection while iterating over it, however this point is not valid as the World menu relies on this feature, using #do: to iterate over the elements of the OrderedCollection including the one it is adding while iterating over the collection. Changing the implementation makes the world menu display half of its items.
I don't like this difference because it is inconsistent. For example, refactoring a #do: into a #collect: can simply not work because they do not iterate over the same elements if you are editing the collection while iterating over it.
An arbitrary rule. The whole world does not defines what to expect from collection when you modifying it during iterating over it.. You can introduce any rule.. but don't expect this won't surprise the users.. because there's no obvious / 'least surprising' behavior can be defined.
In VW, the protocols are consistent and iterating over a collection never iterates over the elements one is adding while iterating over it. Therefore, I believe most frameworks should expect this behavior (at least the ones cross smalltalk) which sounds the most correct.
I think we should fix the world menu implementation and make the protocols consistent. Alternatively, we can let VW be a much more consistent Smalltalk environment than Pharo. What do you think ?
Wrong wrong wrong.. you either iterate over collection, or modify it.. not both. We must fix wrong uses of collections.. not collection. It is all right with collection implementation. You put expectations into a place where should be none: the behavior of iterating over collection while modifying it is *undefined* That's the only rule which should be there. Period.
Clement
-- Best regards, Igor Stasenko.
On 03 Sep 2014, at 14:43, Igor Stasenko <siguctua@gmail.com> wrote:
In VW, the protocols are consistent and iterating over a collection never iterates over the elements one is adding while iterating over it. Therefore, I believe most frameworks should expect this behavior (at least the ones cross smalltalk) which sounds the most correct.
I think we should fix the world menu implementation and make the protocols consistent. Alternatively, we can let VW be a much more consistent Smalltalk environment than Pharo. What do you think ?
Wrong wrong wrong.. you either iterate over collection, or modify it.. not both.
So you actually agree :-) Marcus
:) On Wed, Sep 3, 2014 at 2:47 PM, Marcus Denker <marcus.denker@inria.fr> wrote:
On 03 Sep 2014, at 14:43, Igor Stasenko <siguctua@gmail.com> wrote:
In VW, the protocols are consistent and iterating over a collection never iterates over the elements one is adding while iterating over it. Therefore, I believe most frameworks should expect this behavior (at least the ones cross smalltalk) which sounds the most correct.
I think we should fix the world menu implementation and make the protocols consistent. Alternatively, we can let VW be a much more consistent Smalltalk environment than Pharo. What do you think ?
Wrong wrong wrong.. you either iterate over collection, or modify it.. not both.
So you actually agree :-)
Marcus
-- www.tudorgirba.com "Every thing has its own flow"
On 3 September 2014 14:47, Marcus Denker <marcus.denker@inria.fr> wrote:
On 03 Sep 2014, at 14:43, Igor Stasenko <siguctua@gmail.com> wrote:
In VW, the protocols are consistent and iterating over a collection never iterates over the elements one is adding while iterating over it. Therefore, I believe most frameworks should expect this behavior (at least the ones cross smalltalk) which sounds the most correct.
I think we should fix the world menu implementation and make the protocols consistent. Alternatively, we can let VW be a much more consistent Smalltalk environment than Pharo. What do you think ?
Wrong wrong wrong.. you either iterate over collection, or modify it.. not both.
So you actually agree :-)
I didn't read carefully enough.. but people start the discussion about 'how to fix OrderedColletion' which, as to me, bad signal since it goes wrong way. I am violently against it. You don't 'fix' core classes to make some abuses work. Fix abuses instead. Making abuses work, is opening can of worms, because today you pleased one abuse, tomorrow you will be forced to please another one.. and the finale of it will be complete loss of so beloved consistency.
Marcus
-- Best regards, Igor Stasenko.
participants (10)
-
Ben Coman -
Camille Teruel -
Clément Bera -
Igor Stasenko -
Levente Uzonyi -
Marcus Denker -
Nicolai Hess -
stepharo -
Sven Van Caekenberghe -
Tudor Girba