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%20Typ... 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@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@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- =========================================================================== John M. McIntosh <johnmci@smalltalkconsulting.com> Twitter: squeaker68882 Corporate Smalltalk Consulting Ltd. http://www.smalltalkconsulting.com ===========================================================================
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project