Re: [Pharo-dev] OrderedCollection protocols are broken: a potential fix

[Ben Coman]

Clément Bera wrote: 2014-09-10 10:16 GMT+02:00 Sven Van Caekenberghe <s...@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. It would be interesting if there was something like SmallLint for optimization - <dreaming> that ran automatically in the background to display an icon that you could hover over or click </dreaming> to get info on how to transform common patterns into an optimisable form - like copy inst var values into a local variable before the loop. cheers -ben 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.clem...@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 <s...@stfx.eu>: > I added a slice for https://pharo.fogbugz.com/f/cases/13985/OrderedCollection-do-and-reverseDo-are-not-consistent-with-the-other-enumerations > > On 09 Sep 2014, at 12:53, Nicolai Hess <nicolaih...@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 <steph...@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.ter...@gmail.com>: > >> > >> On 3 sept. 2014, at 11:42, Clément Bera <bera.clem...@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 > >> > > >> > >> > >> > > > > > > >