Faster dictionaries?

Adrian Lienhard adi at netstyle.ch
Fri Jul 20 14:33:42 UTC 2007


On Jul 19, 2007, at 22:53 , sig wrote:
>>
>> Time it takes to add 100k consecutive integers as keys of a  
>> dictionary.
>>
> | sd md r |
> Transcript clear.
> r := OrderedCollection new.
> 1 to: 100000 do: [:each | r add: each ].
> sd := BDictionary new.
> Smalltalk garbageCollect.
> Transcript cr; show: 'time to add all strings to bd: ',
> 	[ r do: [:each | sd at: each put: each ] ] timeToRun printString.
> sd := Dictionary new.
> Smalltalk garbageCollect.
> Transcript cr; show: 'time to add all strings to sd: ',
> 	[ r do: [:each | sd at: each put: each ] ] timeToRun printString.
>
>
> time to add all strings to bd: 719
> time to add all strings to sd: 870

However, accessing the integer keys is faster with the Smalltalk  
Dictionary!

I got the folllowing numbers:

time to add to bd: 298
time to add to sd: 347

time to access bd: 207
time to access sd: 110

| sd r |
r := OrderedCollection new.
1 to: 100000 do: [:each | r add: each ].
bd := BDictionary new.
Smalltalk garbageCollect.
Transcript cr; show: 'time to add to bd: ',
	[ r do: [:each | bd at: each put: each ] ] timeToRun printString.
sd := Dictionary new.
Smalltalk garbageCollect.
Transcript cr; show: 'time to add to sd: ',
	[ r do: [:each | sd at: each put: each ] ] timeToRun printString.
r := r shuffled.
Smalltalk garbageCollect.
Transcript cr; show: 'time to access bd: ',
	[ r do: [:each | bd at: each ] ] timeToRun printString.
Smalltalk garbageCollect.
Transcript cr; show: 'time to access sd: ',
	[ r do: [:each | sd at: each ] ] timeToRun printString.


On Jul 20, 2007, at 12:35 , sig wrote:
>>
> SpaceTally new spaceForInstancesOf: Association withInstanceCount: 1
> returns 12
>
> SpaceTally new spaceForInstancesOf: BAssociation withInstanceCount: 1
> returns 20

ok, the additional memory consumption seems reasonable as there is  
only one additional instance variable in BAssociation (note,  
Association is a compact class and hence its header is only 4 bytes  
compared to 8 bytes of the header of BAssociation; but BAssocitaion  
could also be made a compact class).

As far as I can tell, your implementation performs very well for  
objects with no reasonable hash, like the identityHash of  Squeak  
(which is way too small). Else, this does not seem to be the case.

Cheers,
Adrian

___________________
Adrian Lienhard
www.adrian-lienhard.ch




More information about the Squeak-dev mailing list