this is interesting to see that this is still a guess game. Even with these numbers I cannot evaluate what could be a slowdown/pseed up impact on the complete system. I imgain that the ietration slow down should be minimal and compensated by the creation speed up. May be in the future when system will have a better knowledge of themselves we may end up having better tools...
> I posted these numbers a while ago. > > In my image the average length of a Dictionary is 10, the average > length of a Set is 1.2. > > Lukas > > > 2009/12/4 Stéphane Ducasse <[email protected]>: >> I would be curious to see the average length of dictionary keys (except >> Smalltalk) >> and see the performance penalty between set and array for the do: >> >> Stef >> >>> 2009/12/4 Lukas Renggli <[email protected]>: >>>> Actually the code can be further optimized: >>>> >>>> Dictionary>>keys >>>> "Answer a Set containing the receiver's keys." >>>> >>>> | result container | >>>> result := Set basicNew setTally: tally array: array copy. >>>> container := result array. >>>> 1 to: container size do: [ :index | >>>> (container at: index) >>>> ifNotNil: [ :assoc | container at: index put: assoc >>>> key ] ]. >>>> ^ result >>>> >>>> This is roughly 22 times faster than the current implementation, and 5 >>>> times faster than the squeak implementation. >>>> >>>> The system doesn't seem to break with this change :-) >>>> >>>> Lukas >>>> >>> >>> Yes Levente considered this implementation as keysAsSet, but did not >>> pushed it in trunk so far. >>> You must also consider that each further usage of a Set will add a >>> performance penalty vs an Array, especially do: >>> >>> Nicolas >>> >>>> 2009/12/4 Lukas Renggli <[email protected]>: >>>>> I wonder if ever something along the following lines was considered? >>>>> >>>>> Dictionary>>keys >>>>> "Answer a Set containing the receiver's keys." >>>>> >>>>> | result | >>>>> result := Set basicNew. >>>>> result setTally: tally array: (array collect: [ :each | >>>>> each isNil ifFalse: [ each key ] ]). >>>>> ^ result >>>>> >>>>> This returns a Set, so it wouldn't break any semantics. In my >>>>> benchmark this is roughly 8x faster than the current implementation, >>>>> and 2x faster than the optimized Squeak implementation. >>>>> >>>>> The drawback is that it makes some heavy assumptions on the internal >>>>> structure of Dictionary, Association and Set. >>>>> >>>>> Lukas >>>>> >>>>> 2009/12/4 Henrik Sperre Johansen <[email protected]>: >>>>>> A small addendum ;) >>>>>> On 03.12.2009 22:13, Nicolas Cellier wrote: >>>>>>> 3) identify thise sending a potential inefficient message (includes:) >>>>>>> insert keys asSet in this case (only if includes: is in a loop!) >>>>>>> >>>>>>> >>>>>> 3b. If the keys collection isn't used for anything else, change to use >>>>>> includesKey: instead. >>>>>> >>>>>> Cheers, >>>>>> Henry >>>>>> >>>>>> _______________________________________________ >>>>>> Pharo-project mailing list >>>>>> [email protected] >>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> Lukas Renggli >>>>> http://www.lukas-renggli.ch >>>>> >>>> >>>> >>>> >>>> -- >>>> Lukas Renggli >>>> http://www.lukas-renggli.ch >>>> >>>> _______________________________________________ >>>> Pharo-project mailing list >>>> [email protected] >>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>>> >>> >>> _______________________________________________ >>> Pharo-project mailing list >>> [email protected] >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> >> >> _______________________________________________ >> Pharo-project mailing list >> [email protected] >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > > > -- > Lukas Renggli > http://www.lukas-renggli.ch > > _______________________________________________ > Pharo-project mailing list > [email protected] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project _______________________________________________ Pharo-project mailing list [email protected] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
