October 2010 - Pharo-dev - lists.pharo.org

Re: [Pharo-project] call for scripting idea

by StÃ©phane Ducasse

why not :) could you send them to the list so that we can see them? On Oct 18, 2010, at 10:15 PM, Tudor Girba wrote: > How about getting the scripts from the Hudson integration (builder) of Lukas and translating them into Smalltalk? > > Cheers, > Doru > > > On 18 Oct 2010, at 21:52, stephane ducasse wrote: > >> Hi >> >> we would like to exercise a bit our scripting engine :) so if you have ideas of scripts that we should be able to write let us know. >> >> Stef >> _______________________________________________ >> Pharo-project mailing list >> Pharo-project(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > -- > www.tudorgirba.com > > "No matter how many recipes we know, we still value a chef." > > > > > > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Oct. 19, 2010

Re: [Pharo-project] Stack should be reimplemented with Array

by Levente Uzonyi

On Tue, 19 Oct 2010, Igor Stasenko wrote: > On 19 October 2010 02:51, Levente Uzonyi <leves(a)elte.hu> wrote: >> On Tue, 19 Oct 2010, Igor Stasenko wrote: >> >>> On 19 October 2010 00:25, Levente Uzonyi <leves(a)elte.hu> wrote: >>>> >>>> On Mon, 18 Oct 2010, Igor Stasenko wrote: >>>> >>>>> Stephane, i could say more: >>>>> - i don't like how LinkedList implemented. >>>>> >>>>> I don't see why it should mimic things like #at: #at:put: at all.. >>>> >>>> It's not mimicing those methods. A list usually support things like this, >>>> but the user should know the consequences. >>>> >>> >>> The consequences of such approach is much more far-reaching: leads to >>> bad design practices, crappy application performance, >>> and then tons of bugs and workarounds. >> >> Are programmers idiots? If not, then we shouldn't treat them like idiots. >> > No, of course not. > And that's why as non-idiot (i hope), i was wondering, what things > like #at: #at:put: doing in classes like Stack, > or LikedList. Okay, it's not nice if a Stack allows indexing, but most linked list implementations support it. > You know, its like you driving the car and along the road you see a > beatiful park with pool and attractions for the kids to play to the > right side, and a toxic waste dump to the left side of road.. And you > keep driving, thinking about a diner and wife, which waits you at > home, but at some moment your attention gets back to that place and > you have a gut feeling that there was something wrong with a picture > you just seen, and then you got it: they are close to each other, just > across the road! > >>> >>>>> IMO this protocol should be pruned from it, to not provoke uses which >>>>> completely do not fit for given data structure. >>>> >>>> I'm not sure if it's okay to remove features, because users lacking >>>> really >>>> basic CS knowledge may use them the wrong way. >>>> >>> >>> Imo, we should prohibit this from the beginning. Standard, core >>> classes should not contain an API, which could lead to >>> careless, abusive programming techniques. >> >> So we should get rid of SortedCollection, remove #includes: #indexOf: from >> ArrayedCollections, get rid of OrderedCollection >> #remove:, etc. Am I >> right? >> > Roughly speaking, yes. But they are inherited.. this is a little another story. > And should be handled in a way like Array>>add: does. Array >> #add: is different, because Arrays are not resizable. You could say that one could use #become: to grow the array, but then I'd say that following your suggestions we have to remove #become: from the system, because it's slow and people may use it to write slow code. > >>> IMO, a kernel APIs should serve not only as an implementation of basic >>> system funcionality, it also must serve as guide, >>> how to best use these facilities, so people will learn what is the >>> right way to use it. >> >> That's right, but there's no need to remove useful features to achieve this. >> > you should convince me first, that things like LinkedList>>at: is userful. Ok. Here's an example: What happens if you remove OrderedCollection >> #remove: from the system? People will write code like this (or worse): gotIt := false. 1 to: o size do: [ :index | gotIt ifTrue: [ o at: index - 1 put: (o at: index) ] ifFalse: [ (o at: index) = myObject ifTrue: [ gotIt := true ] ]. gotIt ifTrue: [ o removeLast ]. This kind of code is a lot worse than using #remove:, because it's harder to understand, harder to debug, really easy to mess up. And it will be reimplemented several times. Levente > >>> >>> We should teach users to use right tools for things they need. >>> >>> >>>>> >>>>> Removing/inserting into the middle of list is quite ineffective >>>>> operation (O(n)), >>>> >>>> As long as you don't give away the link objects, it's O(n), otherwise it >>>> can >>>> be O(1). >>> >>> giving away link objects... oh, that's the worst thing, which could >>> possibly happen :) >> >> No. It's the user's responsibility to use it wisely. If you don't need to >> access a internal nodes, just adding/removing elements to/from the list, >> then you probably shouldn't use a list at all. >> > > I prefer making own lists and own classes for list items, because > implementation of > LinkedList raising many questions starting from being optimal, and up > to concerns i presented above. > > >>> >>>> >>>>> while inserting at the begginning/end of list is O(1). >>>>> >>>>> Lists are sequenceable.. but sequenceable ~~ indexable. Period. >>>> >>>> Sequenceable is indexable, but good performance is not guaranteed. >>>> >>> Unless you representing an infinite collection(s). >>> Streams are good example of sequenceable, however non-indexable >>> containers. >> >> Streams are more like external iterators, than containers IMHO. But you can >> get/set the position of most streams. >> >> >> Levente >> >>> >>> >>>> >>>> Levente >>>> >>>>> >>>>> -- >>>>> Best regards, >>>>> Igor Stasenko AKA sig. >>>>> >>>>> _______________________________________________ >>>>> Pharo-project mailing list >>>>> Pharo-project(a)lists.gforge.inria.fr >>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>>>> >>>> >>>> _______________________________________________ >>>> Pharo-project mailing list >>>> Pharo-project(a)lists.gforge.inria.fr >>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>>> >>> >>> >>> >>> -- >>> Best regards, >>> Igor Stasenko AKA sig. >>> >>> _______________________________________________ >>> Pharo-project mailing list >>> Pharo-project(a)lists.gforge.inria.fr >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>> >> >> _______________________________________________ >> Pharo-project mailing list >> Pharo-project(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > > > -- > Best regards, > Igor Stasenko AKA sig. > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Oct. 19, 2010

Re: [Pharo-project] [squeak-dev] SharedQueue does scale (was: Re: SharedQueue doesn't scale)

by Igor Stasenko

On 19 October 2010 06:29, Levente Uzonyi <leves(a)elte.hu> wrote: > On Tue, 19 Oct 2010, Igor Stasenko wrote: > >> On 19 October 2010 03:42, Levente Uzonyi <leves(a)elte.hu> wrote: >>> >>> On Tue, 19 Oct 2010, Igor Stasenko wrote: >>> >>>> On 19 October 2010 02:06, Levente Uzonyi <leves(a)elte.hu> wrote: >>>>> >>>>> On Mon, 18 Oct 2010, Igor Stasenko wrote: >>>>> >>>>> snip >>>>> >>>>>> >>>>> >>>>> Thanks, Levente for giving a feedback. >>>>> Please, feel free to shape my classes in more complete from (such as >>>>> proper naming), >>>>> to make them ready for inclusion in both Squeak's and Pharo cores. >>>>> I propose the following names: >>>>> AtomicQueue (base class) -> AtomicCollection >>>>> FIFOQueue -> AtomicQueue >>>>> LIFOQueue -> AtomicStack >>>>> If you, or anyone else having better suggestions, speak now :) >>>>> >>>>> >>>>> >>>>> I think these should be the names: >>>>> >>>>> FIFOQueue -> SharedQueue >>>> >>>> this name already used by Kernel. >>>> So, unless my class will fully replace it, i see no way how i could >>>> use this name in separate package. >>> >>> Yes, it would be good to replace the implementation IMHO. The API seems >>> to >>> be complete to me (except for copying ;)). >>> >> You mean this: >> >> copy >> Â Â Â Â ^ self errorDontCopy >> >> errorDontCopy >> Â Â Â Â "copying a structure, involved in concurrent operations is a bad >> idea" >> Â Â Â Â ^ self error: 'Copying not available' >> >> :) >> >> See how Squeak's EventSensor doing right thing to make a 'copy': >> >> EventSensor>>flushAllButDandDEvents >> Â Â Â Â | newQueue oldQueue Â | >> >> Â Â Â Â newQueue := SharedQueue new. >> Â Â Â Â self eventQueue ifNil: >> Â Â Â Â Â Â Â Â [eventQueue := newQueue. >> Â Â Â Â Â Â Â Â ^self]. >> Â Â Â Â oldQueue := self eventQueue. >> Â Â Â Â [oldQueue size > 0] whileTrue: >> Â Â Â Â Â Â Â Â [| item type | >> Â Â Â Â Â Â Â Â item := oldQueue next. >> Â Â Â Â Â Â Â Â type := item at: 1. >> Â Â Â Â Â Â Â Â type = EventTypeDragDropFiles ifTrue: [ newQueue nextPut: >> item]]. >> Â Â Â Â eventQueue := newQueue. >> >> Well, you might be right, that #copy can be implemented as: >> >> copy >> Â | copy | >> Â copy := self class new. >> Â [ copy put: (self nextIfNone: [ ^ copy ] ) ] repeat >> >> if it makes any sense, to anyone.. >> >> Its hard to imagine a situation where one may need to copy existing queue, >> because he simply can keep using it. > > I didn't say that I find copying useful, but the API is different. > Why? #copy is implemented.. it just behaves differently :) >> >> >>>> >>>> Also, i must stress, that behavior of FIFOQueue only attempts to >>>> closely resemble the SharedQueue behavior. >>>> However, there is a situations (related to how scheduling works and >>>> use of #yield), where using them could lead to deadlocks. >>>> In this regard, an AtomicSharedQueue (a subclass of FIFOQueue) is much >>>> better analogy to current SharedQueue. >>> >>> If you mean the case: "if process A tries to read from an empty queue, >>> later >>> process B tries to do the same, then process A is guaranteed to read >>> before >>> process B", then that shouldn't be a problem. It would require an >>> external >>> synchronization step to make use of this feature with the current >>> implementation. I doubt that anyone wrote such code ever. >>> >> No. The problems is not in that. The problem related to scheduling and >> how #yield primitive works. >> >> Here the VM's primitiveYield: >> >> primitiveYield >> "primitively do the equivalent of Process>yield" >> Â Â Â Â | activeProc priority processLists processList | >> Â Â Â Â activeProc := self fetchPointer: ActiveProcessIndex >> Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â ofObject: self >> schedulerPointer. >> Â Â Â Â priority := self quickFetchInteger: PriorityIndex ofObject: >> activeProc. >> Â Â Â Â processLists := self fetchPointer: ProcessListsIndex ofObject: self >> schedulerPointer. >> Â Â Â Â processList := self fetchPointer: priority - 1 ofObject: >> processLists. >> >> Â Â Â Â (self isEmptyList: processList) ifFalse:[ >> Â Â Â Â Â Â Â Â self addLastLink: activeProc toList: processList. >> Â Â Â Â Â Â Â Â self transferTo: self wakeHighestPriority] >> >> Note #wakeHighestPriority. >> >> So, a fetcher (which using #yield in spin loop) with priority higher >> than pusher process, will loop infinitely >> blocking pusher and all lower priority processes from advancing. >> >> To avoid this problem, one should make sure that process which pushing >> new items to queue >> having either higher or same priority as any fetching process(es) >> using same queue. >> Or use wait-free access to queue (avoid use #next, use #nextOrNil >> instead). >> >> That's why in subclass - AtomicSharedQueue, i using semaphore to >> workaround this issue. > > Okay. So AtomicSharedQueue is the class which can be used to replace > SharedQueue. So the names could be: > > LIFOQueue -> AtomicStack > FIFOQueue -> AtomicQueue > AtomicSharedQueue -> SharedQueue > Right, and i think i'll move all non wait-free methods (like #next ) into SharedQueue, so AtomicQueue will not contain #next in its protocol, and will be purely a wait-free based implementation. >> >> And potentially, it would be good some day to have a way to say to >> scheduler: >> please stop current process and see if you can run anything with lower >> priority. > > That would break the current scheduling policy. > I prefer an 'alter' word as in 'alternative' :) > > Levente > -- Best regards, Igor Stasenko AKA sig.

Oct. 19, 2010

Re: [Pharo-project] [squeak-dev] SharedQueue does scale (was: Re: SharedQueue doesn't scale)

by Levente Uzonyi

On Tue, 19 Oct 2010, Igor Stasenko wrote: > On 19 October 2010 03:42, Levente Uzonyi <leves(a)elte.hu> wrote: >> On Tue, 19 Oct 2010, Igor Stasenko wrote: >> >>> On 19 October 2010 02:06, Levente Uzonyi <leves(a)elte.hu> wrote: >>>> >>>> On Mon, 18 Oct 2010, Igor Stasenko wrote: >>>> >>>> snip >>>> >>>>> >>>> >>>> Thanks, Levente for giving a feedback. >>>> Please, feel free to shape my classes in more complete from (such as >>>> proper naming), >>>> to make them ready for inclusion in both Squeak's and Pharo cores. >>>> I propose the following names: >>>> AtomicQueue (base class) -> AtomicCollection >>>> FIFOQueue -> AtomicQueue >>>> LIFOQueue -> AtomicStack >>>> If you, or anyone else having better suggestions, speak now :) >>>> >>>> >>>> >>>> I think these should be the names: >>>> >>>> FIFOQueue -> SharedQueue >>> >>> this name already used by Kernel. >>> So, unless my class will fully replace it, i see no way how i could >>> use this name in separate package. >> >> Yes, it would be good to replace the implementation IMHO. The API seems to >> be complete to me (except for copying ;)). >> > You mean this: > > copy > ^ self errorDontCopy > > errorDontCopy > "copying a structure, involved in concurrent operations is a bad idea" > ^ self error: 'Copying not available' > > :) > > See how Squeak's EventSensor doing right thing to make a 'copy': > > EventSensor>>flushAllButDandDEvents > | newQueue oldQueue | > > newQueue := SharedQueue new. > self eventQueue ifNil: > [eventQueue := newQueue. > ^self]. > oldQueue := self eventQueue. > [oldQueue size > 0] whileTrue: > [| item type | > item := oldQueue next. > type := item at: 1. > type = EventTypeDragDropFiles ifTrue: [ newQueue nextPut: item]]. > eventQueue := newQueue. > > Well, you might be right, that #copy can be implemented as: > > copy > | copy | > copy := self class new. > [ copy put: (self nextIfNone: [ ^ copy ] ) ] repeat > > if it makes any sense, to anyone.. > > Its hard to imagine a situation where one may need to copy existing queue, > because he simply can keep using it. I didn't say that I find copying useful, but the API is different. > > >>> >>> Also, i must stress, that behavior of FIFOQueue only attempts to >>> closely resemble the SharedQueue behavior. >>> However, there is a situations (related to how scheduling works and >>> use of #yield), where using them could lead to deadlocks. >>> In this regard, an AtomicSharedQueue (a subclass of FIFOQueue) is much >>> better analogy to current SharedQueue. >> >> If you mean the case: "if process A tries to read from an empty queue, later >> process B tries to do the same, then process A is guaranteed to read before >> process B", then that shouldn't be a problem. It would require an external >> synchronization step to make use of this feature with the current >> implementation. I doubt that anyone wrote such code ever. >> > No. The problems is not in that. The problem related to scheduling and > how #yield primitive works. > > Here the VM's primitiveYield: > > primitiveYield > "primitively do the equivalent of Process>yield" > | activeProc priority processLists processList | > activeProc := self fetchPointer: ActiveProcessIndex > ofObject: self schedulerPointer. > priority := self quickFetchInteger: PriorityIndex ofObject: activeProc. > processLists := self fetchPointer: ProcessListsIndex ofObject: self > schedulerPointer. > processList := self fetchPointer: priority - 1 ofObject: processLists. > > (self isEmptyList: processList) ifFalse:[ > self addLastLink: activeProc toList: processList. > self transferTo: self wakeHighestPriority] > > Note #wakeHighestPriority. > > So, a fetcher (which using #yield in spin loop) with priority higher > than pusher process, will loop infinitely > blocking pusher and all lower priority processes from advancing. > > To avoid this problem, one should make sure that process which pushing > new items to queue > having either higher or same priority as any fetching process(es) > using same queue. > Or use wait-free access to queue (avoid use #next, use #nextOrNil instead). > > That's why in subclass - AtomicSharedQueue, i using semaphore to > workaround this issue. Okay. So AtomicSharedQueue is the class which can be used to replace SharedQueue. So the names could be: LIFOQueue -> AtomicStack FIFOQueue -> AtomicQueue AtomicSharedQueue -> SharedQueue > > And potentially, it would be good some day to have a way to say to scheduler: > please stop current process and see if you can run anything with lower priority. That would break the current scheduling policy. Levente > (Another reason to move scheduling to language side, so we are free to > modify it in a way we like ;). > >>> >>> As i noted in another mail, i see that we might also provide a >>> separate wait-free interface. So we can guarantee, >>> that if you using only wait-free interface, a queue can never be the >>> cause of deadlock. >> >> That's great, and it can be a future addition even if we push the current >> implementation to the Trunk. >> > > Yes. I think that for most cases in concurrent environment, a > wait-free access is preferable way to work with queues. > > >> >> Levente >> > > > > -- > Best regards, > Igor Stasenko AKA sig. > >

Oct. 19, 2010

Re: [Pharo-project] Stack should be reimplemented with Array

by Igor Stasenko

On 19 October 2010 02:51, Levente Uzonyi <leves(a)elte.hu> wrote: > On Tue, 19 Oct 2010, Igor Stasenko wrote: > >> On 19 October 2010 00:25, Levente Uzonyi <leves(a)elte.hu> wrote: >>> >>> On Mon, 18 Oct 2010, Igor Stasenko wrote: >>> >>>> Stephane, i could say more: >>>> - i don't like how LinkedList implemented. >>>> >>>> I don't see why it should mimic things like #at: #at:put: at all.. >>> >>> It's not mimicing those methods. A list usually support things like this, >>> but the user should know the consequences. >>> >> >> The consequences of such approach is much more far-reaching: leads to >> bad design practices, crappy application performance, >> and then tons of bugs and workarounds. > > Are programmers idiots? If not, then we shouldn't treat them like idiots. > No, of course not. And that's why as non-idiot (i hope), i was wondering, what things like #at: #at:put: doing in classes like Stack, or LikedList. You know, its like you driving the car and along the road you see a beatiful park with pool and attractions for the kids to play to the right side, and a toxic waste dump to the left side of road.. And you keep driving, thinking about a diner and wife, which waits you at home, but at some moment your attention gets back to that place and you have a gut feeling that there was something wrong with a picture you just seen, and then you got it: they are close to each other, just across the road! >> >>>> IMO this protocol should be pruned from it, to not provoke uses which >>>> completely do not fit for given data structure. >>> >>> I'm not sure if it's okay to remove features, because users lacking >>> really >>> basic CS knowledge may use them the wrong way. >>> >> >> Imo, we should prohibit this from the beginning. Standard, core >> classes should not contain an API, which could lead to >> careless, abusive programming techniques. > > So we should get rid of SortedCollection, remove #includes: #indexOf: from > ArrayedCollections, get rid of OrderedCollection >> #remove:, etc. Am I > right? > Roughly speaking, yes. But they are inherited.. this is a little another story. And should be handled in a way like Array>>add: does. >> IMO, a kernel APIs should serve not only as an implementation of basic >> system funcionality, it also must serve as guide, >> how to best use these facilities, so people will learn what is the >> right way to use it. > > That's right, but there's no need to remove useful features to achieve this. > you should convince me first, that things like LinkedList>>at: is userful. >> >> We should teach users to use right tools for things they need. >> >> >>>> >>>> Removing/inserting into the middle of list is quite ineffective >>>> operation (O(n)), >>> >>> As long as you don't give away the link objects, it's O(n), otherwise it >>> can >>> be O(1). >> >> giving away link objects... oh, that's the worst thing, which could >> possibly happen :) > > No. It's the user's responsibility to use it wisely. If you don't need to > access a internal nodes, just adding/removing elements to/from the list, > then you probably shouldn't use a list at all. > I prefer making own lists and own classes for list items, because implementation of LinkedList raising many questions starting from being optimal, and up to concerns i presented above. >> >>> >>>> while inserting at the begginning/end of list is O(1). >>>> >>>> Lists are sequenceable.. but sequenceable ~~ indexable. Period. >>> >>> Sequenceable is indexable, but good performance is not guaranteed. >>> >> Unless you representing an infinite collection(s). >> Streams are good example of sequenceable, however non-indexable >> containers. > > Streams are more like external iterators, than containers IMHO. But you can > get/set the position of most streams. > > > Levente > >> >> >>> >>> Levente >>> >>>> >>>> -- >>>> Best regards, >>>> Igor Stasenko AKA sig. >>>> >>>> _______________________________________________ >>>> Pharo-project mailing list >>>> Pharo-project(a)lists.gforge.inria.fr >>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>>> >>> >>> _______________________________________________ >>> Pharo-project mailing list >>> Pharo-project(a)lists.gforge.inria.fr >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>> >> >> >> >> -- >> Best regards, >> Igor Stasenko AKA sig. >> >> _______________________________________________ >> Pharo-project mailing list >> Pharo-project(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > -- Best regards, Igor Stasenko AKA sig.

Oct. 19, 2010

Re: [Pharo-project] bad bracket autocompletion in Pharo Core 1.2

by Igor Stasenko

On 18 October 2010 21:44, StÃ©phane Ducasse <stephane.ducasse(a)inria.fr> wrote: >> >> > On Sun, Oct 17, 2010 at 10:51 AM, StÃ©phane Ducasse <stephane.ducasse(a)inria.fr> wrote: >> > I have a question: >> > Â Â Â Â does shout support closing parenthesis behavior? >> > >> > >> > >> > I wonder the same. I don't see the difference between this and shout smart characters. >> >> so may be we could remove this and keep smart characters. >> Now that there is a setting we could try and see. >> >> Do you know where/why/who added this? Â because I guess there is a reason that we don't see. > > In fact I do not understand :) since ithought that the code was coming from cuis and cuis does not > implement it at all. may this is evil autogenerating code :) > Maybe Pharo runs some hidden AI process, which refactors and changes things under the hood? :) > Stef > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > -- Best regards, Igor Stasenko AKA sig.

Oct. 19, 2010

Re: [Pharo-project] [squeak-dev] SharedQueue does scale (was: Re: SharedQueue doesn't scale)

by Igor Stasenko

On 19 October 2010 03:42, Levente Uzonyi <leves(a)elte.hu> wrote: > On Tue, 19 Oct 2010, Igor Stasenko wrote: > >> On 19 October 2010 02:06, Levente Uzonyi <leves(a)elte.hu> wrote: >>> >>> On Mon, 18 Oct 2010, Igor Stasenko wrote: >>> >>> snip >>> >>>> >>> >>> Thanks, Levente for giving a feedback. >>> Please, feel free to shape my classes in more complete from (such as >>> proper naming), >>> to make them ready for inclusion in both Squeak's and Pharo cores. >>> I propose the following names: >>> AtomicQueue (base class) -> AtomicCollection >>> FIFOQueue -> AtomicQueue >>> LIFOQueue -> AtomicStack >>> If you, or anyone else having better suggestions, speak now :) >>> >>> >>> >>> I think these should be the names: >>> >>> FIFOQueue -> SharedQueue >> >> this name already used by Kernel. >> So, unless my class will fully replace it, i see no way how i could >> use this name in separate package. > > Yes, it would be good to replace the implementation IMHO. The API seems to > be complete to me (except for copying ;)). > You mean this: copy ^ self errorDontCopy errorDontCopy "copying a structure, involved in concurrent operations is a bad idea" ^ self error: 'Copying not available' :) See how Squeak's EventSensor doing right thing to make a 'copy': EventSensor>>flushAllButDandDEvents | newQueue oldQueue | newQueue := SharedQueue new. self eventQueue ifNil: [eventQueue := newQueue. ^self]. oldQueue := self eventQueue. [oldQueue size > 0] whileTrue: [| item type | item := oldQueue next. type := item at: 1. type = EventTypeDragDropFiles ifTrue: [ newQueue nextPut: item]]. eventQueue := newQueue. Well, you might be right, that #copy can be implemented as: copy | copy | copy := self class new. [ copy put: (self nextIfNone: [ ^ copy ] ) ] repeat if it makes any sense, to anyone.. Its hard to imagine a situation where one may need to copy existing queue, because he simply can keep using it. >> >> Also, i must stress, that behavior of FIFOQueue only attempts to >> closely resemble the SharedQueue behavior. >> However, there is a situations (related to how scheduling works and >> use of #yield), where using them could lead to deadlocks. >> In this regard, an AtomicSharedQueue (a subclass of FIFOQueue) is much >> better analogy to current SharedQueue. > > If you mean the case: "if process A tries to read from an empty queue, later > process B tries to do the same, then process A is guaranteed to read before > process B", then that shouldn't be a problem. It would require an external > synchronization step to make use of this feature with the current > implementation. I doubt that anyone wrote such code ever. > No. The problems is not in that. The problem related to scheduling and how #yield primitive works. Here the VM's primitiveYield: primitiveYield "primitively do the equivalent of Process>yield" | activeProc priority processLists processList | activeProc := self fetchPointer: ActiveProcessIndex ofObject: self schedulerPointer. priority := self quickFetchInteger: PriorityIndex ofObject: activeProc. processLists := self fetchPointer: ProcessListsIndex ofObject: self schedulerPointer. processList := self fetchPointer: priority - 1 ofObject: processLists. (self isEmptyList: processList) ifFalse:[ self addLastLink: activeProc toList: processList. self transferTo: self wakeHighestPriority] Note #wakeHighestPriority. So, a fetcher (which using #yield in spin loop) with priority higher than pusher process, will loop infinitely blocking pusher and all lower priority processes from advancing. To avoid this problem, one should make sure that process which pushing new items to queue having either higher or same priority as any fetching process(es) using same queue. Or use wait-free access to queue (avoid use #next, use #nextOrNil instead). That's why in subclass - AtomicSharedQueue, i using semaphore to workaround this issue. And potentially, it would be good some day to have a way to say to scheduler: please stop current process and see if you can run anything with lower priority. (Another reason to move scheduling to language side, so we are free to modify it in a way we like ;). >> >> As i noted in another mail, i see that we might also provide a >> separate wait-free interface. So we can guarantee, >> that if you using only wait-free interface, a queue can never be the >> cause of deadlock. > > That's great, and it can be a future addition even if we push the current > implementation to the Trunk. > Yes. I think that for most cases in concurrent environment, a wait-free access is preferable way to work with queues. > > Levente > -- Best regards, Igor Stasenko AKA sig.

Oct. 19, 2010

Re: [Pharo-project] [squeak-dev] SharedQueue does scale (was: Re: SharedQueue doesn't scale)

by Levente Uzonyi

On Tue, 19 Oct 2010, Igor Stasenko wrote: > On 19 October 2010 02:06, Levente Uzonyi <leves(a)elte.hu> wrote: >> On Mon, 18 Oct 2010, Igor Stasenko wrote: >> >> snip >> >>> >> >> Thanks, Levente for giving a feedback. >> Please, feel free to shape my classes in more complete from (such as >> proper naming), >> to make them ready for inclusion in both Squeak's and Pharo cores. >> I propose the following names: >> AtomicQueue (base class) -> AtomicCollection >> FIFOQueue -> AtomicQueue >> LIFOQueue -> AtomicStack >> If you, or anyone else having better suggestions, speak now :) >> >> >> >> I think these should be the names: >> >> FIFOQueue -> SharedQueue > > this name already used by Kernel. > So, unless my class will fully replace it, i see no way how i could > use this name in separate package. Yes, it would be good to replace the implementation IMHO. The API seems to be complete to me (except for copying ;)). > > Also, i must stress, that behavior of FIFOQueue only attempts to > closely resemble the SharedQueue behavior. > However, there is a situations (related to how scheduling works and > use of #yield), where using them could lead to deadlocks. > In this regard, an AtomicSharedQueue (a subclass of FIFOQueue) is much > better analogy to current SharedQueue. If you mean the case: "if process A tries to read from an empty queue, later process B tries to do the same, then process A is guaranteed to read before process B", then that shouldn't be a problem. It would require an external synchronization step to make use of this feature with the current implementation. I doubt that anyone wrote such code ever. > > As i noted in another mail, i see that we might also provide a > separate wait-free interface. So we can guarantee, > that if you using only wait-free interface, a queue can never be the > cause of deadlock. That's great, and it can be a future addition even if we push the current implementation to the Trunk. Levente > >> LIFOQueue -> SharedStack >> >> I don't know a really good name for AtomicQueue, maybe SharedList, >> SharedCollection or SharedListStub. >> >> >> Levente >> >> >> >> In any case, i'm am open to discuss further details and possible >> caveats of using new classes >> to anyone interested in using them. >> >> P.S. As a side note, i now can explain (to myself at first place), why >> i intuitively choosed to used atomic swap >> instead of CAS. >> Because it fits better fits with smalltalk language semantics: >> >> A swap operation in smalltalk implemented as two assignments: >> x := y. y := z. >> An assignments is basic operation, which have nothing to do with >> late-bound nature of language. >> Unless we going to introduce a meta-object protocol(s), which could >> turn a simple assignment >> into some message sends under the hood, it will remain a basic, >> early-bound operation. >> And even if we do, it is highly unlikely, that even then we will throw >> away the old, >> simple assignment, which identifies an assignment source & target at >> compile time. >> >> In contrast, a CAS operation , if written in smalltalk looks like: >> >> (a == b ) ifTrue: [ a := c ] >> >> so, it having two message sends (#== , #ifTrue:), and from strict, >> pure language perspective, >> this using a late-bound semantics (a message sends), >> and as any message send, the message result and behavior cannot be >> predicted at compile time >> and therefore its wrong to assume that such statement could be an >> atomic operation. >> >> Unless, of course, we introduce a new language syntax which will >> denote a CAS operation explicitly. >> >>> >>> Levente >>> >>> >>> snip >>> >> >> >> -- >> Best regards, >> Igor Stasenko AKA sig. >> >> _______________________________________________ >> Pharo-project mailing list >> Pharo-project(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> >> > > > > -- > Best regards, > Igor Stasenko AKA sig. > >

Oct. 19, 2010

Re: [Pharo-project] Stack should be reimplemented with Array

by Levente Uzonyi

On Tue, 19 Oct 2010, Igor Stasenko wrote: > On 19 October 2010 00:25, Levente Uzonyi <leves(a)elte.hu> wrote: >> On Mon, 18 Oct 2010, Igor Stasenko wrote: >> >>> Stephane, i could say more: >>> - i don't like how LinkedList implemented. >>> >>> I don't see why it should mimic things like #at: #at:put: at all.. >> >> It's not mimicing those methods. A list usually support things like this, >> but the user should know the consequences. >> > > The consequences of such approach is much more far-reaching: leads to > bad design practices, crappy application performance, > and then tons of bugs and workarounds. Are programmers idiots? If not, then we shouldn't treat them like idiots. > >>> IMO this protocol should be pruned from it, to not provoke uses which >>> completely do not fit for given data structure. >> >> I'm not sure if it's okay to remove features, because users lacking really >> basic CS knowledge may use them the wrong way. >> > > Imo, we should prohibit this from the beginning. Standard, core > classes should not contain an API, which could lead to > careless, abusive programming techniques. So we should get rid of SortedCollection, remove #includes: #indexOf: from ArrayedCollections, get rid of OrderedCollection >> #remove:, etc. Am I right? > IMO, a kernel APIs should serve not only as an implementation of basic > system funcionality, it also must serve as guide, > how to best use these facilities, so people will learn what is the > right way to use it. That's right, but there's no need to remove useful features to achieve this. > > We should teach users to use right tools for things they need. > > >>> >>> Removing/inserting into the middle of list is quite ineffective >>> operation (O(n)), >> >> As long as you don't give away the link objects, it's O(n), otherwise it can >> be O(1). > > giving away link objects... oh, that's the worst thing, which could > possibly happen :) No. It's the user's responsibility to use it wisely. If you don't need to access a internal nodes, just adding/removing elements to/from the list, then you probably shouldn't use a list at all. > >> >>> while inserting at the begginning/end of list is O(1). >>> >>> Lists are sequenceable.. but sequenceable ~~ indexable. Period. >> >> Sequenceable is indexable, but good performance is not guaranteed. >> > Unless you representing an infinite collection(s). > Streams are good example of sequenceable, however non-indexable containers. Streams are more like external iterators, than containers IMHO. But you can get/set the position of most streams. Levente > > >> >> Levente >> >>> >>> -- >>> Best regards, >>> Igor Stasenko AKA sig. >>> >>> _______________________________________________ >>> Pharo-project mailing list >>> Pharo-project(a)lists.gforge.inria.fr >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>> >> >> _______________________________________________ >> Pharo-project mailing list >> Pharo-project(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > > > -- > Best regards, > Igor Stasenko AKA sig. > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Oct. 18, 2010

Re: [Pharo-project] [squeak-dev] SharedQueue does scale (was: Re: SharedQueue doesn't scale)

by Igor Stasenko

On 19 October 2010 02:06, Levente Uzonyi <leves(a)elte.hu> wrote: > On Mon, 18 Oct 2010, Igor Stasenko wrote: > > snip > >> > > Thanks, Levente for giving a feedback. > Please, feel free to shape my classes in more complete from (such as > proper naming), > to make them ready for inclusion in both Squeak's and Pharo cores. > I propose the following names: > AtomicQueue (base class) -> AtomicCollection > FIFOQueue -> AtomicQueue > LIFOQueue -> AtomicStack > If you, or anyone else having better suggestions, speak now :) > > > > I think these should be the names: > > FIFOQueue -> SharedQueue this name already used by Kernel. So, unless my class will fully replace it, i see no way how i could use this name in separate package. Also, i must stress, that behavior of FIFOQueue only attempts to closely resemble the SharedQueue behavior. However, there is a situations (related to how scheduling works and use of #yield), where using them could lead to deadlocks. In this regard, an AtomicSharedQueue (a subclass of FIFOQueue) is much better analogy to current SharedQueue. As i noted in another mail, i see that we might also provide a separate wait-free interface. So we can guarantee, that if you using only wait-free interface, a queue can never be the cause of deadlock. > LIFOQueue -> SharedStack > > I don't know a really good name for AtomicQueue, maybe SharedList, > SharedCollection or SharedListStub. > > > Levente > > > > In any case, i'm am open to discuss further details and possible > caveats of using new classes > to anyone interested in using them. > > P.S. As a side note, i now can explain (to myself at first place), why > i intuitively choosed to used atomic swap > instead of CAS. > Because it fits better fits with smalltalk language semantics: > > A swap operation in smalltalk implemented as two assignments: > x := y. y := z. > An assignments is basic operation, which have nothing to do with > late-bound nature of language. > Unless we going to introduce a meta-object protocol(s), which could > turn a simple assignment > into some message sends under the hood, it will remain a basic, > early-bound operation. > And even if we do, it is highly unlikely, that even then we will throw > away the old, > simple assignment, which identifies an assignment source & target at > compile time. > > In contrast, a CAS operation , if written in smalltalk looks like: > > (a == b ) ifTrue: [ a := c ] > > so, it having two message sends (#== , #ifTrue:), and from strict, > pure language perspective, > this using a late-bound semantics (a message sends), > and as any message send, the message result and behavior cannot be > predicted at compile time > and therefore its wrong to assume that such statement could be an > atomic operation. > > Unless, of course, we introduce a new language syntax which will > denote a CAS operation explicitly. > >> >> Levente >> >> >> snip >> > > > -- > Best regards, > Igor Stasenko AKA sig. > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > -- Best regards, Igor Stasenko AKA sig.

Oct. 18, 2010