[Pharo-users] Dictionary removeKey: very low

Kasper Østerbye kasper.osterbye at gmail.com
Fri Feb 7 06:23:29 EST 2020


This is actually a very good issue you have raised. As far as I am able to
read the code for Dictionary and HashedCollection, the implementation is
not very well suited for deletions at all.

First, as you have discovered, the remove has an implementation which is
unsound (performance wise). Second, HashedCollections grow when you add to
them, but they do not shrink when you remove from them.

That is, in scenarios where your dictionaries grow huge, and then later
shrink, there is a potential “memory leak” in that the array is kept at its
largest size.

Btw, thanks for the shuffle function using sort.  I do believe the built-in
shuffle in SequenceableCollection is faster though (O(n·logn) vs. O(n)).

It seems from the wikipedia page on hash tables, that the there are
algorithms with efficient removal also for the "open addressing with linear
probing” implementation used in HashedCollection. But it only seems to work
if the hash table is also implementing a “shrink” function which is where
the re-hashing is done.

Interesting stuff. It would be a good programming exercise to get that to
work.

— Kasper


On 7 February 2020 at 11.17.27, LABORDE Pierre (
pierre.laborde at fr.thalesgroup.com) wrote:

Thanks Peter.



Here some informations about execution time :



*dic := Dictionary new: 10000.*



*Time microsecondsToRun:[*

*            1 to: 10000 do:[ :i |*

*                        dic at: i put: i printString.*

*            ].*

*]. "6000µs"*

*Time microsecondsToRun:[*

*            1 to: 10000 do:[ :i |*

*                        dic removeKey: i.      *

*            ].*

*]. "2683000µs, up to 447x"*



Regarding your comment, I have wrote a too simple example.

Here a new test with a better representation of my need and datas
(randomization) :



*dic := Dictionary new: 10000.*



*pool := SortedCollection new: 10000.*

*random := Random new.*

*pool sort:[ :a :b | random next < 0.5 ].*

*1 to: 10000 do:[ :i | pool add: i ].*



*Time microsecondsToRun:[*

*            pool do:[ :i |*

*                        dic at: i put: i printString.*

*            ].*

*]. "6000µs => same time, good point"*

*Time microsecondsToRun:[*

*            pool do:[ :i |*

*                        dic removeKey: i.      *

*            ].*

*]. "17000µs, up to 2,8x => huge changes !"*



It’s appear more reasonable !

I need to test it with real datas, to be continued.



Thanks for all.



Pierre



*De :* Pharo-users [mailto:pharo-users-bounces at lists.pharo.org] *De la part
de* PBKResearch
*Envoyé :* lundi 3 février 2020 12:25
*À :* 'Any question about pharo is welcome'
*Objet :* Re: [Pharo-users] Dictionary removeKey: very low



Pierre



It’s all to do with rehashing. A dictionary is stored as an Array of
Association. After a key and its corresponding association is removed, the
remaining entries are rehashed from the removal point to the end of the
array. By doing the removals in natural order, you rehash the whole of the
remaining array after each removal. Try doing the removals in reverse
order; on my machine it reduces the time from 6 seconds to 6 milliseconds.



HTH



Peter Kenny



*From:* Pharo-users <pharo-users-bounces at lists.pharo.org> *On Behalf
Of *LABORDE
Pierre
*Sent:* 03 February 2020 10:18
*To:* pharo-users at lists.pharo.org
*Subject:* [Pharo-users] Dictionary removeKey: very low



Hi all,



I have a problem with Dictionaries :



*dic := Dictionary new: 10000.*



*1 to: 10000 do:[ :i |*

*            dic at: i put: i printString.*

*].*



*1 to: 10000 do:[ :i |*

*            dic removeKey: i.      *

*]*



Removing each keys is very slooow, time execution difference between add
and remove is crazy.

Any idea for fix that ? Can I use another Dictionary implementation or
settings ?



Thanks.



Pierre
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.pharo.org/pipermail/pharo-users_lists.pharo.org/attachments/20200207/00e730de/attachment.html>


More information about the Pharo-users mailing list