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
