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
