- Pharo-dev - lists.pharo.org

Re: [Pharo-project] Collection

by Stephan Eggermont

Igor wrote: >Yes. Use right tool for to do job. >An OrderedCollection can't satisfy every possible combination of >tasks, which developer facing. So, these collections are currently missing. And as all current code is bound to the current implementations, switching implementation on size is the prefered approach. Stephan

March 13, 2010

Re: [Pharo-project] collections

by Igor Stasenko

On 13 March 2010 12:20, Stephan Eggermont <stephan(a)stack.nl> wrote: > 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. > Yes. Use right tool for to do job. An OrderedCollection can't satisfy every possible combination of tasks, which developer facing. >From this point, i barely see how we can achieve a substantial improvements in current implementation. And i think if we talk about collections, we should be focused more on a refactoring (use traits) for better library design, which will make implemetation more compact and cleaner. > Stephan > > _______________________________________________ > 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.

March 13, 2010

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