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

Re: [Pharo-project] collections

by Stephan Eggermont

Levente wrote: >How bad do they perform? Do you have benchmarks? With a coll := OrderedCollection new. 1 to: 10000000 do: [:i | coll add: i]. a profile of: 1 to: 100 do: [:i | coll add: i beforeIndex: 10] here takes 1438 ms. Moving memory gets to be slow. All operations that start taking O(#elements) time are no longer funny. The usual thing to do is to start using multiple blocks of memory (like a BTree). Doubling size when growing is also not an acceptable strategy when getting close to total ram capacity. Stephan

March 13, 2010

[Pharo-project] Smalltalk -> SmalltalkImage

by StÃ©phane Ducasse

http://code.google.com/p/pharo/issues/detail?id=2136 any code is welcome :) Stef

March 13, 2010

Re: [Pharo-project] Collection

by StÃ©phane Ducasse

I think that this is great. We need to optimize as much as it makes sense without breaking our nice apis. Stef On Mar 13, 2010, at 1:23 AM, Levente Uzonyi wrote: > On Thu, 11 Mar 2010, stephane ducasse wrote: > >> Hi guys >> >> tristan is a new student here and he would like to work on collection optimization and implementation. >> I would like the get some ideas from you. >> - are there some collections that would be cool to improve? > > Here's the list I plan to improve is Squeak: > - OrderedCollection: fix the growing behavior, adding n elements takes O(n^2) time in some cases > - SortedCollection: just deprecate it (or replace it's crappy quicksort implementation if you really want to improve it. But I think it's useless) > - TextStream: adding n characters with different attributes has O(n^2) runtime > - StandardFileStream >> #upTo: (the recursive call + concatenation requires O(n^2) runtime and O(n^2) memory for large chunks of data) > > > Levente > >> - are there some collections that would be cool to have and that we do not have yet? >> If you have any idea related to optimizations let me know. >> >> Stef >> _______________________________________________ >> 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

March 13, 2010

Re: [Pharo-project] Collection

by Levente Uzonyi

On Fri, 12 Mar 2010, John M McIntosh wrote: > 10 or 15 years back I look a look at the SortedCollection logic with an eye to improve it. > Oddly I found the folks who wrote it had a good understanding of how the code becomes bytecodes and > how that impacts performance. My attempts made things worst, so good luck. Quicksort has worse performance than merge sort in dynamic languages (and in general when comparison costs more than minimal), because it makes more comparisons. The simple quicksort performs really bad (O(n^2)) if there are only a few different elements. A 3-way partitioning algorithm could perform much better in general, but I think it'd be still slower than merge sort. Here is a bug report which is pretty naive, but shows the effect of the few different elements case: http://code.google.com/p/pharo/issues/detail?id=1718&q=sort&colspec=ID%20Ty… Squeak/Pharo's merge sort implementation is highly optimized. The merge algorithm compiles to pure bytecodes and primitive sends. Levente > > Personally I'd choose the font rendering path, since there is lots of *stuff* required to run to splash a > character glyph to Display. > > On 2010-03-12, at 4:46 PM, Julian Fitzell wrote: > >> On Sat, Mar 13, 2010 at 12:23 AM, Levente Uzonyi <leves(a)elte.hu> wrote: >>> - SortedCollection: just deprecate it (or replace it's crappy quicksort >>> implementation if you really want to improve it. But I think it's useless) >> >> You shouldn't deprecate it... it's ANSI. :) >> >> But it's implementation could certainly be improved... >> >> Julian >> >> _______________________________________________ >> Pharo-project mailing list >> Pharo-project(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > -- > =========================================================================== > John M. McIntosh <johnmci(a)smalltalkconsulting.com> Twitter: squeaker68882 > Corporate Smalltalk Consulting Ltd. http://www.smalltalkconsulting.com > =========================================================================== > > > > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

March 13, 2010

Re: [Pharo-project] Collection

by John M McIntosh

10 or 15 years back I look a look at the SortedCollection logic with an eye to improve it. Oddly I found the folks who wrote it had a good understanding of how the code becomes bytecodes and how that impacts performance. My attempts made things worst, so good luck. Personally I'd choose the font rendering path, since there is lots of *stuff* required to run to splash a character glyph to Display. On 2010-03-12, at 4:46 PM, Julian Fitzell wrote: > On Sat, Mar 13, 2010 at 12:23 AM, Levente Uzonyi <leves(a)elte.hu> wrote: >> - SortedCollection: just deprecate it (or replace it's crappy quicksort >> implementation if you really want to improve it. But I think it's useless) > > You shouldn't deprecate it... it's ANSI. :) > > But it's implementation could certainly be improved... > > Julian > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project -- =========================================================================== John M. McIntosh <johnmci(a)smalltalkconsulting.com> Twitter: squeaker68882 Corporate Smalltalk Consulting Ltd. http://www.smalltalkconsulting.com ===========================================================================

March 13, 2010

Re: [Pharo-project] Collection

by Levente Uzonyi

On Sat, 13 Mar 2010, Julian Fitzell wrote: > On Sat, Mar 13, 2010 at 12:23 AM, Levente Uzonyi <leves(a)elte.hu> wrote: >> - SortedCollection: just deprecate it (or replace it's crappy quicksort >> implementation if you really want to improve it. But I think it's useless) > > You shouldn't deprecate it... it's ANSI. :) That's why I suggested deprecating instead of removing. :) > > But it's implementation could certainly be improved... > IMHO it shouldn't be used at all. Levente > Julian > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

March 13, 2010

Re: [Pharo-project] Collection

by Levente Uzonyi

On Sat, 13 Mar 2010, Henrik Sperre Johansen wrote: > On 13.03.2010 01:23, Levente Uzonyi wrote: >> On Thu, 11 Mar 2010, stephane ducasse wrote: >> >>> Hi guys >>> >>> tristan is a new student here and he would like to work on collection >>> optimization and implementation. >>> I would like the get some ideas from you. >>> - are there some collections that would be cool to improve? >> >> Here's the list I plan to improve is Squeak: >> - OrderedCollection: fix the growing behavior, adding n elements takes >> O(n^2) time in some cases > If you're talking about alternate addFirst: addLast: adds, is that really a > usecase worth optimizing for? > makeRoomAtFirst:/Last: can definately be sped up using > replaceFrom:to:with:startingAt: though. My ideas would result in a general minor speedup, while mixed use of #addFirst: and #addLast: wouldn't suffer the performance penalty at all. So we can win something without losing anything. #replaceFrom:to:with:startingAt: can only be used to move elements to a position with lower index, otherwise overlapping areas will be overwritten. >> - SortedCollection: just deprecate it (or replace it's crappy quicksort >> implementation if you really want to improve it. But I think it's useless) > +1 >> >> - StandardFileStream >> #upTo: (the recursive call + concatenation requires >> O(n^2) runtime and O(n^2) memory for large chunks of data) >> > I did a different implementation some time ago, didn't notice enough of a > speedup to consider posting it though. Hope you have better luck :) > I don't have an implementation yet, but I expect ~3-5% speedup if reading all the sources. This may seem insignificant, but if other bottlenecks are out of the way, this may be 15-25%. And my opinion is still that "library functions" should be optimized for most usecases, so this should be fixed. Levente > Cheers, > Henry > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

March 13, 2010

Re: [Pharo-project] Collection

by Julian Fitzell

On Sat, Mar 13, 2010 at 12:23 AM, Levente Uzonyi <leves(a)elte.hu> wrote: > - SortedCollection: just deprecate it (or replace it's crappy quicksort > implementation if you really want to improve it. But I think it's useless) You shouldn't deprecate it... it's ANSI. :) But it's implementation could certainly be improved... Julian

March 13, 2010

[Pharo-project] String widgets for GUIs built using ToolBuilder

by Ralph Boland

I originally posted this on Squeak-Dev but I didn't get a response so I am hoping someone on this list can help. I will release the code I am working on to SqueakSource. I assume it will work in Pharo as well. If it doesn't let me know and I will clean up the problems. ================================= I am trying to subclass TestBuilder (SUnitGUI) for my own testing facility. TestBuilder builds a GUI using ToolBuilder and I am trying to build my GUI using ToolBuilder as well. I need to use an input field and want to add a StringMorph like widget to label the input field. The only way I can see to do this using ToolBuilder is to use another input field for my input field label string. There has to be a better, standard, way of doing this. Can someone tell me what the standard way, or some reasonable way, of labeling my input field is when using ToolBuilder? Regards, Ralph Boland -- Had a wife and kids in Florida, Jack (Nicklaus) Went out for a "ride" but I couldn't get back As a ten timer being hunted down OR When the wife found out who I was knowing (biblically speaking) I hit a hydrant and I just kept going (till I hit a tree). ...

March 13, 2010

Re: [Pharo-project] Collection

by Henrik Sperre Johansen

On 13.03.2010 01:23, Levente Uzonyi wrote: > On Thu, 11 Mar 2010, stephane ducasse wrote: > >> Hi guys >> >> tristan is a new student here and he would like to work on collection >> optimization and implementation. >> I would like the get some ideas from you. >> - are there some collections that would be cool to improve? > > Here's the list I plan to improve is Squeak: > - OrderedCollection: fix the growing behavior, adding n elements takes > O(n^2) time in some cases If you're talking about alternate addFirst: addLast: adds, is that really a usecase worth optimizing for? makeRoomAtFirst:/Last: can definately be sped up using replaceFrom:to:with:startingAt: though. > - SortedCollection: just deprecate it (or replace it's crappy > quicksort implementation if you really want to improve it. But I think > it's useless) +1 > > - StandardFileStream >> #upTo: (the recursive call + concatenation > requires O(n^2) runtime and O(n^2) memory for large chunks of data) > I did a different implementation some time ago, didn't notice enough of a speedup to consider posting it though. Hope you have better luck :) Cheers, Henry

March 13, 2010