On Fri, 16 Dec 2011, Henrik Sperre Johansen wrote:
On 16.12.2011 00:40, Henrik Sperre Johansen wrote:
On 15.12.2011 23:35, Mariano Martinez Peck wrote:
Well...it is much slower :( it seems that the cost of (aKey identityHash + ( aKey mareaClass identityHash bitShift: 12) + (aKey basicSize bitShift: 24) is bigger than the colisions. Anyway, thanks for the nice thread. I learned.
Cheers
Well, first of all, that always creates a largeInteger, since identityHash is already shifted by 22... You'd want to be using basicIdentityHash. 2nd off, basicSize is useless for non-variable classes, which I guess is the common case. 3rd, putting class hash in the high bits won't really help much if you're serializing many instances of the same class, as they will all occupy a sequential hash range.
So if I were you, I'd try with something like obj basicIdentityHash << 12 + (obj class basicIdentityHash) before discarding it outright due to computation cost.
Cheers, Henry
A few more points: 1) don't use PluggableSets. Block activations are costly, and you REALLY need specialized data/hash functions for it to be worth using. 2) Even with a subclass of IdentitySet, it's hardly worth it:
PluggableSet: n := 1000000. set := PluggableSet new: n. set hashBlock: [:obj | obj basicIdentityHash << 12 + (obj class basicIdentityHash) ]. set equalBlock: [ :a :b | a == b ]. Time millisecondsToRun: [1 to: n do: [:waste | set add: Object new.]] 18828
The one I suggested in a custom subclass: n := 1000000. set := PseudoIdentitySet new: n. Time millisecondsToRun: [1 to: n do: [:waste | set add: Object new.]] 14182
Usual identitySet: n := 1000000. set := IdentitySet new: n. Time millisecondsToRun: [1 to: n do: [:waste | set add: Object new.]] 4595
Custom subclass with a slightly modified hash (anObject identityHash + (anObject class basicIdentityHash bitShift: 6)): n := 1000000. set := PseudoIdentitySet2 new: n. Time millisecondsToRun: [1 to: n do: [:waste | set add: Object new.]] 3694 Why 6 you ask? Because I'm worth it.
Not really enough to justify the extra compexity, imho.
How about my numbers? :) "Preallocate objects, so we won't count gc time." n := 1000000. objects := Array new: n streamContents: [ :stream | n timesRepeat: [ stream nextPut: Object new ] ]. set := IdentitySet new: n. Smalltalk garbageCollect. [1 to: n do: [ :i | set add: (objects at: i) ] ] timeToRun. "4949" set := LargeIdentitySet new. Smalltalk garbageCollect. [1 to: n do: [ :i | set add: (objects at: i) ] ] timeToRun. "331" set := (PluggableSet new: n) hashBlock: [ :object | object identityHash * 4096 + object class identityHash * 64 ]; "Change this to #basicIdentityHash in Pharo" equalBlock: [ :a :b | a == b ]; yourself. Smalltalk garbageCollect. [1 to: n do: [ :i | set add: (objects at: i) ] ] timeToRun. "5511" I also have a LargeIdentityDictionary, which is relatively fast, but not as fast as LargeIdentitySet, because (for some unknown reason) we don't have a primitive that could support it. If we had a primitive like primitive 132 which would return the index of the element if found or 0 if not, then we could have a really fast LargeIdentityDictionary. Levente
Cheers, Henry