Re: [Pharo-project] IdentitySet but using #hash rather than #identityHash ?
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. Cheers, Henry
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
On 16.12.2011 03:26, Levente Uzonyi wrote:
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
Hehe yes, if writing a version fully exploiting the limited range, that's probably the approach I would go for as well. (IAssuming it's the version at http://leves.web.elte.hu/squeak/LargeIdentitySet.st) Mariano commented in the version at http://www.squeaksource.com/FuelExperiments that it's slow for them, which I guess is due to not adopting #identityHash calls to #basicIdentityHash calls for Pharo: ((0 to: 4095) collect: [:each | each << 22 \\ 4096 ]) asSet size -> 1 So it basically uses 1 bucket instead of 4096... Whoops. :) Uploaded a new version to the MC repository which is adapted for Pharo, on the same machine my numbers were taken from, it does the same test as I used above in 871 ms. (181 with preallocation). Cheers, Henry
On Fri, 16 Dec 2011, Henrik Sperre Johansen wrote:
On 16.12.2011 03:26, Levente Uzonyi wrote:
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
Hehe yes, if writing a version fully exploiting the limited range, that's probably the approach I would go for as well. (IAssuming it's the version at http://leves.web.elte.hu/squeak/LargeIdentitySet.st)
Mariano commented in the version at http://www.squeaksource.com/FuelExperiments that it's slow for them, which I guess is due to not adopting #identityHash calls to #basicIdentityHash calls for Pharo: ((0 to: 4095) collect: [:each | each << 22 \\ 4096 ]) asSet size -> 1 So it basically uses 1 bucket instead of 4096... Whoops. :)
Uploaded a new version to the MC repository which is adapted for Pharo, on the same machine my numbers were taken from, it does the same test as I used above in 871 ms. (181 with preallocation).
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it. Levente
Cheers, Henry
Wow...... Henrik: thank you so much for teaching me :) Indeed, I didn't notice that in that case I use using a LargePositiveInteger, and indeed I had removed the basicSize since I also noticed it wouldn't make much sense. Second, thanks a LOT for finding Levente's LargeIdentitySet in Fuel repo with our small adaptation (#addIfNotPresent: anObject ifPresentDo: aBlock). Thanks for fixing it and commiting a new version. All I can say is that I am impressed by the numbers it is really much faster. I still don't understand why I send this email with a subject say IdentitySet because what I really need is a fast/large IdentityDictionary :( Anyway, there's a place where we can use this LargeIdentitySet in Fuel I think). So Levente, you say this is not possible to adapt this for dictionary? can we contact Eliot to provide such a primitive? thanks On Fri, Dec 16, 2011 at 3:28 PM, Levente Uzonyi <leves@elte.hu> wrote:
On Fri, 16 Dec 2011, Henrik Sperre Johansen wrote:
On 16.12.2011 03:26, Levente Uzonyi wrote:
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
Hehe yes, if writing a version fully exploiting the limited range, that's probably the approach I would go for as well. (IAssuming it's the version at http://leves.web.elte.hu/** squeak/LargeIdentitySet.st<http://leves.web.elte.hu/squeak/LargeIdentitySet.st> )
Mariano commented in the version at http://www.squeaksource.com/** FuelExperiments <http://www.squeaksource.com/FuelExperiments> that it's slow for them, which I guess is due to not adopting #identityHash calls to #basicIdentityHash calls for Pharo: ((0 to: 4095) collect: [:each | each << 22 \\ 4096 ]) asSet size -> 1 So it basically uses 1 bucket instead of 4096... Whoops. :)
Uploaded a new version to the MC repository which is adapted for Pharo, on the same machine my numbers were taken from, it does the same test as I used above in 871 ms. (181 with preallocation).
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
Cheers, Henry
-- Mariano http://marianopeck.wordpress.com
Levente, one more question: is there a case (small sets?) where LargeIdentitySet is not recommended? my question is, should I ONLY use it for places where I know I can have large sets or should it also work for small sets as well? from my tests it seems to work well also with small ones...but just wondering. Thanks On Fri, Dec 16, 2011 at 8:43 PM, Mariano Martinez Peck < marianopeck@gmail.com> wrote:
Wow......
Henrik: thank you so much for teaching me :) Indeed, I didn't notice that in that case I use using a LargePositiveInteger, and indeed I had removed the basicSize since I also noticed it wouldn't make much sense. Second, thanks a LOT for finding Levente's LargeIdentitySet in Fuel repo with our small adaptation (#addIfNotPresent: anObject ifPresentDo: aBlock). Thanks for fixing it and commiting a new version.
All I can say is that I am impressed by the numbers it is really much faster. I still don't understand why I send this email with a subject say IdentitySet because what I really need is a fast/large IdentityDictionary :( Anyway, there's a place where we can use this LargeIdentitySet in Fuel I think).
So Levente, you say this is not possible to adapt this for dictionary? can we contact Eliot to provide such a primitive?
thanks
On Fri, Dec 16, 2011 at 3:28 PM, Levente Uzonyi <leves@elte.hu> wrote:
On Fri, 16 Dec 2011, Henrik Sperre Johansen wrote:
On 16.12.2011 03:26, Levente Uzonyi wrote:
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
Hehe yes, if writing a version fully exploiting the limited range, that's probably the approach I would go for as well. (IAssuming it's the version at http://leves.web.elte.hu/** squeak/LargeIdentitySet.st<http://leves.web.elte.hu/squeak/LargeIdentitySet.st> )
Mariano commented in the version at http://www.squeaksource.com/** FuelExperiments <http://www.squeaksource.com/FuelExperiments> that it's slow for them, which I guess is due to not adopting #identityHash calls to #basicIdentityHash calls for Pharo: ((0 to: 4095) collect: [:each | each << 22 \\ 4096 ]) asSet size -> 1 So it basically uses 1 bucket instead of 4096... Whoops. :)
Uploaded a new version to the MC repository which is adapted for Pharo, on the same machine my numbers were taken from, it does the same test as I used above in 871 ms. (181 with preallocation).
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
Cheers, Henry
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
On Fri, 16 Dec 2011, Mariano Martinez Peck wrote:
Levente, one more question: is there a case (small sets?) where LargeIdentitySet is not recommended? my question is, should I ONLY use it for places where I know I can have large sets or should it also work for small sets as well? from my tests it seems to work well also with small ones...but just wondering.
One drawback of this implementation is that it allocates an array with 4096 slots even if it's empty. So it has an overhead about 16kB compared to IdentitySet. This number doubles for LargeIdentityDictionary. So if you're using only a few of these collections, then they won't cause any problem. Levente
Thanks
On Fri, Dec 16, 2011 at 8:43 PM, Mariano Martinez Peck < marianopeck@gmail.com> wrote:
Wow......
Henrik: thank you so much for teaching me :) Indeed, I didn't notice that in that case I use using a LargePositiveInteger, and indeed I had removed the basicSize since I also noticed it wouldn't make much sense. Second, thanks a LOT for finding Levente's LargeIdentitySet in Fuel repo with our small adaptation (#addIfNotPresent: anObject ifPresentDo: aBlock). Thanks for fixing it and commiting a new version.
All I can say is that I am impressed by the numbers it is really much faster. I still don't understand why I send this email with a subject say IdentitySet because what I really need is a fast/large IdentityDictionary :( Anyway, there's a place where we can use this LargeIdentitySet in Fuel I think).
So Levente, you say this is not possible to adapt this for dictionary? can we contact Eliot to provide such a primitive?
thanks
On Fri, Dec 16, 2011 at 3:28 PM, Levente Uzonyi <leves@elte.hu> wrote:
On Fri, 16 Dec 2011, Henrik Sperre Johansen wrote:
On 16.12.2011 03:26, Levente Uzonyi wrote:
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
Hehe yes, if writing a version fully exploiting the limited range, that's probably the approach I would go for as well. (IAssuming it's the version at http://leves.web.elte.hu/** squeak/LargeIdentitySet.st<http://leves.web.elte.hu/squeak/LargeIdentitySet.st> )
Mariano commented in the version at http://www.squeaksource.com/** FuelExperiments <http://www.squeaksource.com/FuelExperiments> that it's slow for them, which I guess is due to not adopting #identityHash calls to #basicIdentityHash calls for Pharo: ((0 to: 4095) collect: [:each | each << 22 \\ 4096 ]) asSet size -> 1 So it basically uses 1 bucket instead of 4096... Whoops. :)
Uploaded a new version to the MC repository which is adapted for Pharo, on the same machine my numbers were taken from, it does the same test as I used above in 871 ms. (181 with preallocation).
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
Cheers, Henry
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
On Fri, 16 Dec 2011, Mariano Martinez Peck wrote:
Wow......
Henrik: thank you so much for teaching me :) Indeed, I didn't notice that in that case I use using a LargePositiveInteger, and indeed I had removed the basicSize since I also noticed it wouldn't make much sense. Second, thanks a LOT for finding Levente's LargeIdentitySet in Fuel repo with our small adaptation (#addIfNotPresent: anObject ifPresentDo: aBlock). Thanks for fixing it and commiting a new version.
All I can say is that I am impressed by the numbers it is really much faster. I still don't understand why I send this email with a subject say IdentitySet because what I really need is a fast/large IdentityDictionary :( Anyway, there's a place where we can use this LargeIdentitySet in Fuel I think).
So Levente, you say this is not possible to adapt this for dictionary? can we contact Eliot to provide such a primitive?
As promised, I uploaded my LargeIdentityDictionary implementation to http://leves.web.elte.hu/squeak/LargeIdentityDictionary.st . The numbers will be a bit worse compared to LargeIdentitySet, because of the lack of the primitive, but it's still 2-3x faster than other solutions (IdentityDictionary, PluggableIdentityDictionary, subclassing, etc). I'm about to propose this primitive with other improvements on the vm-dev list. Levente
thanks
On Fri, Dec 16, 2011 at 3:28 PM, Levente Uzonyi <leves@elte.hu> wrote:
On Fri, 16 Dec 2011, Henrik Sperre Johansen wrote:
On 16.12.2011 03:26, Levente Uzonyi wrote:
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
Hehe yes, if writing a version fully exploiting the limited range, that's probably the approach I would go for as well. (IAssuming it's the version at http://leves.web.elte.hu/** squeak/LargeIdentitySet.st<http://leves.web.elte.hu/squeak/LargeIdentitySet.st> )
Mariano commented in the version at http://www.squeaksource.com/** FuelExperiments <http://www.squeaksource.com/FuelExperiments> that it's slow for them, which I guess is due to not adopting #identityHash calls to #basicIdentityHash calls for Pharo: ((0 to: 4095) collect: [:each | each << 22 \\ 4096 ]) asSet size -> 1 So it basically uses 1 bucket instead of 4096... Whoops. :)
Uploaded a new version to the MC repository which is adapted for Pharo, on the same machine my numbers were taken from, it does the same test as I used above in 871 ms. (181 with preallocation).
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
Cheers, Henry
-- Mariano http://marianopeck.wordpress.com
On Sat, Dec 17, 2011 at 12:52 AM, Levente Uzonyi <leves@elte.hu> wrote:
On Fri, 16 Dec 2011, Mariano Martinez Peck wrote:
Wow......
Henrik: thank you so much for teaching me :) Indeed, I didn't notice that in that case I use using a LargePositiveInteger, and indeed I had removed the basicSize since I also noticed it wouldn't make much sense. Second, thanks a LOT for finding Levente's LargeIdentitySet in Fuel repo with our small adaptation (#addIfNotPresent: anObject ifPresentDo: aBlock). Thanks for fixing it and commiting a new version.
All I can say is that I am impressed by the numbers it is really much faster. I still don't understand why I send this email with a subject say IdentitySet because what I really need is a fast/large IdentityDictionary :( Anyway, there's a place where we can use this LargeIdentitySet in Fuel I think).
So Levente, you say this is not possible to adapt this for dictionary? can we contact Eliot to provide such a primitive?
As promised, I uploaded my LargeIdentityDictionary implementation to http://leves.web.elte.hu/**squeak/**LargeIdentityDictionary.st<http://leves.web.elte.hu/squeak/LargeIdentityDictionary.st>. The numbers will be a bit worse compared to LargeIdentitySet, because of the lack of the primitive, but it's still 2-3x faster than other solutions (IdentityDictionary, PluggableIdentityDictionary, subclassing, etc). I'm about to propose this primitive with other improvements on the vm-dev list.
Thanks Levente. Is there something else I should change apart from #identityHash to #basicIdentityHash for Pharo? Because I tried to running Fuel tests using an instance of LargeIdentityDictionary in the place were we usually use a IdentityDictionary and some tests are failing. It is difficult to reproduce them or to isolate from Fuel. I will try to figure it out, but in the meanwhile, maybe you already know something. I commited the first changes (#basicIdentityHash) in http://www.squeaksource.com/FuelExperiments and explained in the commit what should be changed in Fuel. I commented that because magically Herny fixed for us ;) Time to sleep now...thanks!
Levente
thanks
On Fri, Dec 16, 2011 at 3:28 PM, Levente Uzonyi <leves@elte.hu> wrote:
On Fri, 16 Dec 2011, Henrik Sperre Johansen wrote:
On 16.12.2011 03:26, Levente Uzonyi wrote:
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
Hehe yes, if writing a version fully exploiting the limited range, that's probably the approach I would go for as well. (IAssuming it's the version at http://leves.web.elte.hu/** squeak/LargeIdentitySet.st<htt**p://leves.web.elte.hu/squeak/** LargeIdentitySet.st<http://leves.web.elte.hu/squeak/LargeIdentitySet.st>
)
Mariano commented in the version at http://www.squeaksource.com/** FuelExperiments <http://www.squeaksource.com/**FuelExperiments<http://www.squeaksource.com/FuelExperiments>> that it's
slow for them, which I guess is due to not adopting #identityHash calls to #basicIdentityHash calls for Pharo: ((0 to: 4095) collect: [:each | each << 22 \\ 4096 ]) asSet size -> 1 So it basically uses 1 bucket instead of 4096... Whoops. :)
Uploaded a new version to the MC repository which is adapted for Pharo, on the same machine my numbers were taken from, it does the same test as I used above in 871 ms. (181 with preallocation).
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
Cheers,
Henry
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.com
BTW...I notice that I cannod do: LargeIdentityDictionary new: 5454 So...it doesn't help if I know before hand the exact number of objects I will put? thanks On Sat, Dec 17, 2011 at 1:25 AM, Mariano Martinez Peck < marianopeck@gmail.com> wrote:
On Sat, Dec 17, 2011 at 12:52 AM, Levente Uzonyi <leves@elte.hu> wrote:
On Fri, 16 Dec 2011, Mariano Martinez Peck wrote:
Wow......
Henrik: thank you so much for teaching me :) Indeed, I didn't notice that in that case I use using a LargePositiveInteger, and indeed I had removed the basicSize since I also noticed it wouldn't make much sense. Second, thanks a LOT for finding Levente's LargeIdentitySet in Fuel repo with our small adaptation (#addIfNotPresent: anObject ifPresentDo: aBlock). Thanks for fixing it and commiting a new version.
All I can say is that I am impressed by the numbers it is really much faster. I still don't understand why I send this email with a subject say IdentitySet because what I really need is a fast/large IdentityDictionary :( Anyway, there's a place where we can use this LargeIdentitySet in Fuel I think).
So Levente, you say this is not possible to adapt this for dictionary? can we contact Eliot to provide such a primitive?
As promised, I uploaded my LargeIdentityDictionary implementation to http://leves.web.elte.hu/**squeak/**LargeIdentityDictionary.st<http://leves.web.elte.hu/squeak/LargeIdentityDictionary.st>. The numbers will be a bit worse compared to LargeIdentitySet, because of the lack of the primitive, but it's still 2-3x faster than other solutions (IdentityDictionary, PluggableIdentityDictionary, subclassing, etc). I'm about to propose this primitive with other improvements on the vm-dev list.
Thanks Levente. Is there something else I should change apart from #identityHash to #basicIdentityHash for Pharo? Because I tried to running Fuel tests using an instance of LargeIdentityDictionary in the place were we usually use a IdentityDictionary and some tests are failing. It is difficult to reproduce them or to isolate from Fuel. I will try to figure it out, but in the meanwhile, maybe you already know something. I commited the first changes (#basicIdentityHash) in http://www.squeaksource.com/FuelExperiments and explained in the commit what should be changed in Fuel. I commented that because magically Herny fixed for us ;)
Time to sleep now...thanks!
Levente
thanks
On Fri, Dec 16, 2011 at 3:28 PM, Levente Uzonyi <leves@elte.hu> wrote:
On Fri, 16 Dec 2011, Henrik Sperre Johansen wrote:
On 16.12.2011 03:26, Levente Uzonyi wrote:
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
Hehe yes, if writing a version fully exploiting the limited range, that's probably the approach I would go for as well. (IAssuming it's the version at http://leves.web.elte.hu/** squeak/LargeIdentitySet.st<htt**p://leves.web.elte.hu/squeak/** LargeIdentitySet.st<http://leves.web.elte.hu/squeak/LargeIdentitySet.st>
)
Mariano commented in the version at http://www.squeaksource.com/** FuelExperiments <http://www.squeaksource.com/**FuelExperiments<http://www.squeaksource.com/FuelExperiments>> that it's
slow for them, which I guess is due to not adopting #identityHash calls to #basicIdentityHash calls for Pharo: ((0 to: 4095) collect: [:each | each << 22 \\ 4096 ]) asSet size -> 1 So it basically uses 1 bucket instead of 4096... Whoops. :)
Uploaded a new version to the MC repository which is adapted for Pharo, on the same machine my numbers were taken from, it does the same test as I used above in 871 ms. (181 with preallocation).
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
Cheers,
Henry
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
On Sat, Dec 17, 2011 at 1:25 AM, Mariano Martinez Peck < marianopeck@gmail.com> wrote:
On Sat, Dec 17, 2011 at 12:52 AM, Levente Uzonyi <leves@elte.hu> wrote:
On Fri, 16 Dec 2011, Mariano Martinez Peck wrote:
Wow......
Henrik: thank you so much for teaching me :) Indeed, I didn't notice that in that case I use using a LargePositiveInteger, and indeed I had removed the basicSize since I also noticed it wouldn't make much sense. Second, thanks a LOT for finding Levente's LargeIdentitySet in Fuel repo with our small adaptation (#addIfNotPresent: anObject ifPresentDo: aBlock). Thanks for fixing it and commiting a new version.
All I can say is that I am impressed by the numbers it is really much faster. I still don't understand why I send this email with a subject say IdentitySet because what I really need is a fast/large IdentityDictionary :( Anyway, there's a place where we can use this LargeIdentitySet in Fuel I think).
So Levente, you say this is not possible to adapt this for dictionary? can we contact Eliot to provide such a primitive?
As promised, I uploaded my LargeIdentityDictionary implementation to http://leves.web.elte.hu/**squeak/**LargeIdentityDictionary.st<http://leves.web.elte.hu/squeak/LargeIdentityDictionary.st>. The numbers will be a bit worse compared to LargeIdentitySet, because of the lack of the primitive, but it's still 2-3x faster than other solutions (IdentityDictionary, PluggableIdentityDictionary, subclassing, etc). I'm about to propose this primitive with other improvements on the vm-dev list.
Thanks Levente. Is there something else I should change apart from #identityHash to #basicIdentityHash for Pharo? Because I tried to running Fuel tests using an instance of LargeIdentityDictionary in the place were we usually use a IdentityDictionary and some tests are failing. It is difficult to reproduce them or to isolate from Fuel. I will try to figure it out, but in the meanwhile, maybe you already know something. I commited the first changes (#basicIdentityHash) in http://www.squeaksource.com/FuelExperiments and explained in the commit what should be changed in Fuel. I commented that because magically Herny fixed for us ;)
Just for fun I took a Pharo image and in IdentityDictionaryTest I changed the method classToBeTested ^ LargeIdentityDictionary and there are 7 failures and 48 errors while with IdentityDictionary they are all green. So I guess there are some differences. The red ones are easy because I guess it is just that LargeIdentityDictionary does not have the whole protocol but a subset. The problem are the failing one I think because the suggest the usage or API is different? Thanks in advance,
Time to sleep now...thanks!
Levente
thanks
On Fri, Dec 16, 2011 at 3:28 PM, Levente Uzonyi <leves@elte.hu> wrote:
On Fri, 16 Dec 2011, Henrik Sperre Johansen wrote:
On 16.12.2011 03:26, Levente Uzonyi wrote:
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
Hehe yes, if writing a version fully exploiting the limited range, that's probably the approach I would go for as well. (IAssuming it's the version at http://leves.web.elte.hu/** squeak/LargeIdentitySet.st<htt**p://leves.web.elte.hu/squeak/** LargeIdentitySet.st<http://leves.web.elte.hu/squeak/LargeIdentitySet.st>
)
Mariano commented in the version at http://www.squeaksource.com/** FuelExperiments <http://www.squeaksource.com/**FuelExperiments<http://www.squeaksource.com/FuelExperiments>> that it's
slow for them, which I guess is due to not adopting #identityHash calls to #basicIdentityHash calls for Pharo: ((0 to: 4095) collect: [:each | each << 22 \\ 4096 ]) asSet size -> 1 So it basically uses 1 bucket instead of 4096... Whoops. :)
Uploaded a new version to the MC repository which is adapted for Pharo, on the same machine my numbers were taken from, it does the same test as I used above in 871 ms. (181 with preallocation).
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
Cheers,
Henry
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
Hi Levente, Have you tried a different value for your array and tallies size instead of 4096 in the code you provided for LargeIdentitySet? Such as prime numbers, as it is usually the case for hash tables? I've tried 3079, and 4093 (prime numbers) and 3079 performs a little bit better . Other meaningful suggestions can be found here : http://planetmath.org/encyclopedia/GoodHashTablePrimes.html P.S. So far, 3079 is the best candidate saving between 26 and 35% on very large sets !! P.P.S. Nice work! ----------------- Benoit St-Jean Yahoo! Messenger: bstjean A standpoint is an intellectual horizon of radius zero. (Albert Einstein)
________________________________ From: Levente Uzonyi <leves@elte.hu> To: Pharo-project@lists.gforge.inria.fr Sent: Friday, December 16, 2011 6:52:29 PM Subject: Re: [Pharo-project] IdentitySet but using #hash rather than #identityHash ?
On Fri, 16 Dec 2011, Mariano Martinez Peck wrote:
Wow......
Henrik: thank you so much for teaching me :) Indeed, I didn't notice that in that case I use using a LargePositiveInteger, and indeed I had removed the basicSize since I also noticed it wouldn't make much sense. Second, thanks a LOT for finding Levente's LargeIdentitySet in Fuel repo with our small adaptation (#addIfNotPresent: anObject ifPresentDo: aBlock). Thanks for fixing it and commiting a new version.
All I can say is that I am impressed by the numbers it is really much faster. I still don't understand why I send this email with a subject say IdentitySet because what I really need is a fast/large IdentityDictionary :(Â Anyway, there's a place where we can use this LargeIdentitySet in Fuel I think).
So Levente, you say this is not possible to adapt this for dictionary? can we contact Eliot to provide such a primitive?
As promised, I uploaded my LargeIdentityDictionary implementation to http://leves.web.elte.hu/squeak/LargeIdentityDictionary.st . The numbers will be a bit worse compared to LargeIdentitySet, because of the lack of the primitive, but it's still 2-3x faster than other solutions (IdentityDictionary, PluggableIdentityDictionary, subclassing, etc). I'm about to propose this primitive with other improvements on the vm-dev list.
Levente
thanks
On Fri, Dec 16, 2011 at 3:28 PM, Levente Uzonyi <leves@elte.hu> wrote:
On Fri, 16 Dec 2011, Henrik Sperre Johansen wrote:
 On 16.12.2011 03:26, Levente Uzonyi wrote:
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
Hehe yes, if writing a version fully exploiting the limited range, that's probably the approach I would go for as well. (IAssuming it's the version at http://leves.web.elte.hu/** squeak/LargeIdentitySet.st<http://leves.web.elte.hu/squeak/LargeIdentitySet.st> )
Mariano commented in the version at http://www.squeaksource.com/** FuelExperiments <http://www.squeaksource.com/FuelExperiments> that it's slow for them, which I guess is due to not adopting #identityHash calls to #basicIdentityHash calls for Pharo: ((0 to: 4095) collect: [:each | each << 22 \\ 4096 ]) asSet size -> 1 So it basically uses 1 bucket instead of 4096... Whoops. :)
Uploaded a new version to the MC repository which is adapted for Pharo, on the same machine my numbers were taken from, it does the same test as I used above in 871 ms. (181 with preallocation).
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
Cheers, Henry
-- Mariano http://marianopeck.wordpress.com
On Fri, 16 Dec 2011, Benoit St-Jean wrote:
Hi Levente,
Have you tried a different value for your array and tallies size instead of 4096 in the code you provided for LargeIdentitySet? Such as prime numbers, as it is usually the case for hash tables? I've tried 3079, and 4093 (prime numbers) and 3079 performs a little bit better . Other meaningful suggestions can be found here : http://planetmath.org/encyclopedia/GoodHashTablePrimes.html P.S. So far, 3079 is the best candidate saving between 26 and 35% on very large sets !! P.P.S. Nice work! Using primes is suboptimal in this case, because there are exactly 4096 possible identityHash values (for non-SmallInteger objects), so the mapping from hash value to slot is as simple (and fast) as possible. Also note that not all hash tables use prime sizes, using a power of two for size and multiplying in the hash function with a special prime is also very common. Levente ----------------- Benoit St-Jean Yahoo! Messenger: bstjean A standpoint is an intellectual horizon of radius zero. (Albert Einstein)
________________________________ From: Levente Uzonyi <leves@elte.hu> To: Pharo-project@lists.gforge.inria.fr Sent: Friday, December 16, 2011 6:52:29 PM Subject: Re: [Pharo-project] IdentitySet but using #hash rather than #identityHash ?
On Fri, 16 Dec 2011, Mariano Martinez Peck wrote:
Wow......
Henrik: thank you so much for teaching me :) Indeed, I didn't notice that in that case I use using a LargePositiveInteger, and indeed I had removed the basicSize since I also noticed it wouldn't make much sense. Second, thanks a LOT for finding Levente's LargeIdentitySet in Fuel repo with our small adaptation (#addIfNotPresent: anObject ifPresentDo: aBlock). Thanks for fixing it and commiting a new version.
All I can say is that I am impressed by the numbers it is really much faster. I still don't understand why I send this email with a subject say IdentitySet because what I really need is a fast/large IdentityDictionary :(Â Anyway, there's a place where we can use this LargeIdentitySet in Fuel I think).
So Levente, you say this is not possible to adapt this for dictionary? can we contact Eliot to provide such a primitive?
As promised, I uploaded my LargeIdentityDictionary implementation to http://leves.web.elte.hu/squeak/LargeIdentityDictionary.st . The numbers will be a bit worse compared to LargeIdentitySet, because of the lack of the primitive, but it's still 2-3x faster than other solutions (IdentityDictionary, PluggableIdentityDictionary, subclassing, etc). I'm about to propose this primitive with other improvements on the vm-dev list.
Levente
thanks
On Fri, Dec 16, 2011 at 3:28 PM, Levente Uzonyi <leves@elte.hu> wrote:
On Fri, 16 Dec 2011, Henrik Sperre Johansen wrote:
 On 16.12.2011 03:26, Levente Uzonyi wrote:
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
Hehe yes, if writing a version fully exploiting the limited range, that's probably the approach I would go for as well. (IAssuming it's the version at http://leves.web.elte.hu/** squeak/LargeIdentitySet.st<http://leves.web.elte.hu/squeak/LargeIdentitySet.st> )
Mariano commented in the version at http://www.squeaksource.com/** FuelExperiments <http://www.squeaksource.com/FuelExperiments> that it's slow for them, which I guess is due to not adopting #identityHash calls to #basicIdentityHash calls for Pharo: ((0 to: 4095) collect: [:each | each << 22 \\ 4096 ]) asSet size -> 1 So it basically uses 1 bucket instead of 4096... Whoops. :)
Uploaded a new version to the MC repository which is adapted for Pharo, on the same machine my numbers were taken from, it does the same test as I used above in 871 ms. (181 with preallocation).
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
Cheers, Henry
-- Mariano http://marianopeck.wordpress.com
On Fri, Dec 16, 2011 at 3:28 PM, Levente Uzonyi <leves@elte.hu> wrote:
On Fri, 16 Dec 2011, Henrik Sperre Johansen wrote:
On 16.12.2011 03:26, Levente Uzonyi wrote:
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
Hehe yes, if writing a version fully exploiting the limited range, that's probably the approach I would go for as well. (IAssuming it's the version at http://leves.web.elte.hu/** squeak/LargeIdentitySet.st<http://leves.web.elte.hu/squeak/LargeIdentitySet.st> )
Mariano commented in the version at http://www.squeaksource.com/** FuelExperiments <http://www.squeaksource.com/FuelExperiments> that it's slow for them, which I guess is due to not adopting #identityHash calls to #basicIdentityHash calls for Pharo: ((0 to: 4095) collect: [:each | each << 22 \\ 4096 ]) asSet size -> 1 So it basically uses 1 bucket instead of 4096... Whoops. :)
Uploaded a new version to the MC repository which is adapted for Pharo, on the same machine my numbers were taken from, it does the same test as I used above in 871 ms. (181 with preallocation).
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added.
In Pharo we have: pointsTo: anObject "This method returns true if self contains a pointer to anObject, and returns false otherwise" <primitive: 132> So I guess it is correct to let it like this.
I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
I am lost. thought I read something saying you couldn't do that for Dictionaries because you needed a primitive? Sorry...long day, maybe I am just crazy ;) Anyway, I would appreaciate and take a look to LargeIdentityDictionary if you do it. BTW, I guess both are MIT ? Thanks Levente
Levente
Cheers, Henry
-- Mariano http://marianopeck.wordpress.com
On Fri, 16 Dec 2011, Mariano Martinez Peck wrote:
On Fri, Dec 16, 2011 at 3:28 PM, Levente Uzonyi <leves@elte.hu> wrote:
On Fri, 16 Dec 2011, Henrik Sperre Johansen wrote:
On 16.12.2011 03:26, Levente Uzonyi wrote:
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
Hehe yes, if writing a version fully exploiting the limited range, that's probably the approach I would go for as well. (IAssuming it's the version at http://leves.web.elte.hu/** squeak/LargeIdentitySet.st<http://leves.web.elte.hu/squeak/LargeIdentitySet.st> )
Mariano commented in the version at http://www.squeaksource.com/** FuelExperiments <http://www.squeaksource.com/FuelExperiments> that it's slow for them, which I guess is due to not adopting #identityHash calls to #basicIdentityHash calls for Pharo: ((0 to: 4095) collect: [:each | each << 22 \\ 4096 ]) asSet size -> 1 So it basically uses 1 bucket instead of 4096... Whoops. :)
Uploaded a new version to the MC repository which is adapted for Pharo, on the same machine my numbers were taken from, it does the same test as I used above in 871 ms. (181 with preallocation).
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added.
In Pharo we have:
pointsTo: anObject "This method returns true if self contains a pointer to anObject, and returns false otherwise" <primitive: 132>
So I guess it is correct to let it like this.
Right, until you apply the patch. :)
I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
I am lost. thought I read something saying you couldn't do that for Dictionaries because you needed a primitive? Sorry...long day, maybe I am just crazy ;) Anyway, I would appreaciate and take a look to LargeIdentityDictionary if you do it. BTW, I guess both are MIT ?
Yes, there's a license.txt file at the download page. Levente
Thanks Levente
Levente
Cheers, Henry
-- Mariano http://marianopeck.wordpress.com
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected." I do not get the following. Indeed pointTo: looks like instVarsInclude: now I do not understand the rest of your paragraph.
Stef
Hi Levente. I take a deeper look to see why LargeIdentityDictionary is not working as expected for us. The way we are putting objects in the Dict is always this way: registerIndexesOn: aDictionary self objects do: [ :instance | aDictionary at: instance put: aDictionary size + 1 ]. Soâ¦keys are the objects of the graphs and the values are the internal position in the serialization. However, when I run a serialization it looks like if the follow happens that when we are doing:
encodeReferenceTo: anObject
indexCluster serialize: (objectsIndexes at: anObject) on: stream (objectsIndexes at: anObject) == anObject -> true so (objectsIndexes at: anObject) is answering "self" rather than the number (which was the dict size + 1 at the serialization moment). Something interesting is that most tests seem to pass and the problem is with benchmarks (where graphs are much bigger), so maybe it could be something related to that. For example, the following benchmark for bitmaps is failing: numbers := OrderedCollection new. bitmaps := OrderedCollection new. numbers addAll: ( 1 << 30 to:( ( 1 << 30) + 10000) ) asArray. numbers do: [:each | bitmaps add: (Bitmap with: each with: each + 1) ]. ^ bitmaps it happens the mentioned problem when trying to serialize the collection 'bitmaps'. I tried to reproduce it outside Fuel and I think I succeeded (not sure). The following does work with IdentityDictionary but not with LargeIdentityDictionary. Basically I am simulating the way we use this dict in Fuel: testLargeIdentityDictionary | numbers bitmaps dict | "Create some bitmaps" numbers := OrderedCollection new. bitmaps := OrderedCollection new. numbers addAll: ( 1 << 30 to:( ( 1 << 30) + 10000) ) asArray. numbers do: [:each | bitmaps add: (Bitmap with: each with: each + 1) ]. "Put them in a dictionary using dict as as key" dict := LargeIdentityDictionary new. bitmaps do: [:each | dict at: each put: dict size + 1. ]. "Check they are correct" bitmaps doWithIndex: [:each :index | self assert: index == (dict at: each)] Of course that test works with IdentityDictionary. Thanks for any idea. On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr
wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected." I do not get the following. Indeed pointTo: looks like instVarsInclude: now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.com
2011/12/17 Mariano Martinez Peck <marianopeck@gmail.com>:
Hi Levente. I take a deeper look to see why LargeIdentityDictionary is not working as expected for us.
The way we are putting objects in the Dict is always this way:
registerIndexesOn: aDictionary
   self objects do: [ :instance | aDictionary at: instance put: aDictionary size + 1 ].
Soâ¦keys are the objects of the graphs and the values are the internal position in the serialization. However, when I run a serialization it looks like if the follow happens that when we are doing:
encodeReferenceTo: anObject
   indexCluster       serialize: (objectsIndexes at: anObject)       on: stream
(objectsIndexes at: anObject) == anObject  -> true
so (objectsIndexes at: anObject) is answering "self" rather than the number (which was the dict size + 1 at the serialization moment).
Something interesting is that most tests seem to pass and the problem is with benchmarks (where graphs are much bigger), so maybe it could be something related to that. For example, the following benchmark for bitmaps is failing:
        numbers := OrderedCollection new.    bitmaps := OrderedCollection new.    numbers addAll: ( 1 << 30 to:( ( 1 << 30) + 10000) ) asArray.    numbers do: [:each | bitmaps add: (Bitmap with: each with: each + 1) ].    ^ bitmaps
it happens the mentioned problem when trying to serialize the collection 'bitmaps'.
I tried to reproduce it outside Fuel and I think I succeeded (not sure). The following does work with IdentityDictionary but not with LargeIdentityDictionary. Basically I am simulating the way we use this dict in Fuel:
testLargeIdentityDictionary
   | numbers bitmaps dict |
"Create some bitmaps"
   numbers := OrderedCollection new.    bitmaps := OrderedCollection new.    numbers addAll: ( 1 << 30 to:( ( 1 << 30) + 10000) ) asArray.    numbers do: [:each | bitmaps add: (Bitmap with: each with: each + 1) ].
"Put them in a dictionary using dict as as key" Â Â Â dict := LargeIdentityDictionary new. Â Â Â bitmaps do: [:each | Â Â Â Â Â Â Â dict at: each put: dict size + 1. Â Â Â Â Â Â ].
"Check they are correct" Â Â Â bitmaps doWithIndex: [:each :index | self assert: index == (dict at: each)]
Of course that test works with IdentityDictionary.
Can't you debug it ?
Thanks for any idea.
On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected." I do not get the following. Indeed pointTo: looks like instVarsInclude: now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.com
2011/12/17 Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com>:
2011/12/17 Mariano Martinez Peck <marianopeck@gmail.com>:
Hi Levente. I take a deeper look to see why LargeIdentityDictionary is not working as expected for us.
The way we are putting objects in the Dict is always this way:
registerIndexesOn: aDictionary
   self objects do: [ :instance | aDictionary at: instance put: aDictionary size + 1 ].
Soâ¦keys are the objects of the graphs and the values are the internal position in the serialization. However, when I run a serialization it looks like if the follow happens that when we are doing:
encodeReferenceTo: anObject
   indexCluster       serialize: (objectsIndexes at: anObject)       on: stream
(objectsIndexes at: anObject) == anObject  -> true
so (objectsIndexes at: anObject) is answering "self" rather than the number (which was the dict size + 1 at the serialization moment).
Something interesting is that most tests seem to pass and the problem is with benchmarks (where graphs are much bigger), so maybe it could be something related to that. For example, the following benchmark for bitmaps is failing:
        numbers := OrderedCollection new.    bitmaps := OrderedCollection new.    numbers addAll: ( 1 << 30 to:( ( 1 << 30) + 10000) ) asArray.    numbers do: [:each | bitmaps add: (Bitmap with: each with: each + 1) ].    ^ bitmaps
it happens the mentioned problem when trying to serialize the collection 'bitmaps'.
I tried to reproduce it outside Fuel and I think I succeeded (not sure). The following does work with IdentityDictionary but not with LargeIdentityDictionary. Basically I am simulating the way we use this dict in Fuel:
testLargeIdentityDictionary
   | numbers bitmaps dict |
"Create some bitmaps"
   numbers := OrderedCollection new.    bitmaps := OrderedCollection new.    numbers addAll: ( 1 << 30 to:( ( 1 << 30) + 10000) ) asArray.    numbers do: [:each | bitmaps add: (Bitmap with: each with: each + 1) ].
"Put them in a dictionary using dict as as key" Â Â Â dict := LargeIdentityDictionary new. Â Â Â bitmaps do: [:each | Â Â Â Â Â Â Â dict at: each put: dict size + 1. Â Â Â Â Â Â ].
"Check they are correct" Â Â Â bitmaps doWithIndex: [:each :index | self assert: index == (dict at: each)]
Of course that test works with IdentityDictionary.
Can't you debug it ?
It took 2 minutes to find this sentence at line 19 of LargeDictionary>>at:put: (values at: hash) at: newIndex put: key Can you replace key with value and retry the tests ? Nicolas
Thanks for any idea.
On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected." I do not get the following. Indeed pointTo: looks like instVarsInclude: now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.com
Can't you debug it ?
Of course I could do it when I have some time. It already took me 1 hour to isolate the bug from Fuel and make a reproducible test. I hope that at least you find that useful. I found the bug and I thought I could send my progress and see if someone could continue it. Otherwise, I was going to debug it as soon as I have some free time (which I don't have much this year).
It took 2 minutes to find this sentence at line 19 of LargeDictionary>>at:put:
But you are so smart and a Collection hacker. Me, I am newbie, and just the method at:put: scares me, but I understand if it has to be that way in order to be fast. And so far it seems to be fast, so I am happy with it.
(values at: hash) at: newIndex put: key
Can you replace key with value and retry the tests ?
Yes, that works. Thanks! Now I noticed that SmallIntegers storing is really slow numbers := OrderedCollection new. numbers add: 1. numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ). dict := LargeIdentityDictionary new. [numbers do: [:each | dict at: each put: dict size + 1. ]. ] timeToRun -> 12657 whereas with IdentityDictionary it is 37. I guess it could be related to #identityHash or #basicIdentityHash. I tried in Squeak 4.3 and it is also also there. I will try to take a look into it during the next week. Thanks in advance
Nicolas
Thanks for any idea.
On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132
directly
was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected." I do not get the following. Indeed pointTo: looks like instVarsInclude: now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
On Sat, 17 Dec 2011, Mariano Martinez Peck wrote:
Can't you debug it ?
Of course I could do it when I have some time. It already took me 1 hour to isolate the bug from Fuel and make a reproducible test. I hope that at least you find that useful. I found the bug and I thought I could send my progress and see if someone could continue it. Otherwise, I was going to debug it as soon as I have some free time (which I don't have much this year).
It took 2 minutes to find this sentence at line 19 of LargeDictionary>>at:put:
But you are so smart and a Collection hacker. Me, I am newbie, and just the method at:put: scares me, but I understand if it has to be that way in order to be fast. And so far it seems to be fast, so I am happy with it.
(values at: hash) at: newIndex put: key
Can you replace key with value and retry the tests ?
Yes, that works. Thanks!
Now I noticed that SmallIntegers storing is really slow
This is not entirely true. Every hash table can be made slow if you know how it's hash function works. Since in your example all numbers are congruent to 1 modulo 4096 and the size of the array is also 4096, therefore they will be mapped to the same slot (1). Try using random (or at least more realistic) numbers in your test. If this is a real problem, then it may be necessary to implement a new hash method, which uses the primitive for general objects and does something else with SmallIntegers and that method shoul be used from these large collections. Levente
numbers := OrderedCollection new. numbers add: 1. numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
dict := LargeIdentityDictionary new. [numbers do: [:each | dict at: each put: dict size + 1. ]. ] timeToRun -> 12657
whereas with IdentityDictionary it is 37. I guess it could be related to #identityHash or #basicIdentityHash. I tried in Squeak 4.3 and it is also also there. I will try to take a look into it during the next week.
Thanks in advance
Nicolas
Thanks for any idea.
On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132
directly
was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected." I do not get the following. Indeed pointTo: looks like instVarsInclude: now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
On Sun, 18 Dec 2011, Levente Uzonyi wrote:
On Sat, 17 Dec 2011, Mariano Martinez Peck wrote:
Can't you debug it ?
Of course I could do it when I have some time. It already took me 1 hour to isolate the bug from Fuel and make a reproducible test. I hope that at least you find that useful. I found the bug and I thought I could send my progress and see if someone could continue it. Otherwise, I was going to debug it as soon as I have some free time (which I don't have much this year).
It took 2 minutes to find this sentence at line 19 of LargeDictionary>>at:put:
But you are so smart and a Collection hacker. Me, I am newbie, and just the method at:put: scares me, but I understand if it has to be that way in order to be fast. And so far it seems to be fast, so I am happy with it.
(values at: hash) at: newIndex put: key
Can you replace key with value and retry the tests ?
Yes, that works. Thanks!
Now I noticed that SmallIntegers storing is really slow
This is not entirely true. Every hash table can be made slow if you know how it's hash function works. Since in your example all numbers are congruent to 1 modulo 4096 and the size of the array is also 4096, therefore they will be mapped to the same slot (1). Try using random (or at least more realistic) numbers in your test. If this is a real problem, then it may be necessary to implement a new hash method, which uses the primitive for general objects and does something else with SmallIntegers and that method shoul be used from these large collections.
I uploaded a new mcz to the FuelExperiments repository, which is unaffected by the identity hash differences between Pharo and Squeak and works better with SmallIntegers. It includes both the dictionary and the set and (in theory) has slightly better performance for non-SmallInteger objects. Levente
Levente
numbers := OrderedCollection new. numbers add: 1. numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
dict := LargeIdentityDictionary new. [numbers do: [:each | dict at: each put: dict size + 1. ]. ] timeToRun -> 12657
whereas with IdentityDictionary it is 37. I guess it could be related to #identityHash or #basicIdentityHash. I tried in Squeak 4.3 and it is also also there. I will try to take a look into it during the next week.
Thanks in advance
Nicolas
Thanks for any idea.
On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132
directly
was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected." I do not get the following. Indeed pointTo: looks like instVarsInclude: now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
Now I noticed that SmallIntegers storing is really slow
This is not entirely true. Every hash table can be made slow if you know how it's hash function works. Since in your example all numbers are congruent to 1 modulo 4096 and the size of the array is also 4096, therefore they will be mapped to the same slot (1). Try using random (or at least more realistic) numbers in your test. If this is a real problem, then it may be necessary to implement a new hash method, which uses the primitive for general objects and does something else with SmallIntegers and that method shoul be used from these large collections.
I uploaded a new mcz to the FuelExperiments repository, which is unaffected by the identity hash differences between Pharo and Squeak and works better with SmallIntegers. It includes both the dictionary and the set and (in theory) has slightly better performance for non-SmallInteger objects.
Hi Levente. First let me say I really appreaciate your effort in make it work. It makes definitvly Fuel faster and it would make sense to integrate them also in Squeak and Pharo. Now, I found another bug. To reproduce it: | dict | dict := LargeIdentityDictionary new. dict at: 16941057 put: 1035. Now, it seems 16941057 largeIdentityHash answers 4096 and the comment of #largeIdentityHash says ""Return an integer between 0 and 4095 based on all of my bits. Make sure that for nearby receivers the result will not be nearby with high probability."" The thing is that LargeIdentityHashedCollection permuteHash: hash + 1 answers 4096, and hence, when in #at:put: you do: at: key put: value | hash | (keys at: (hash := key largeIdentityHash + 1)) then you get the out of bounds. Modyfing initialize | rng | rng := Random seed: 664399324. PermutationMap := (1 to: 4096) asArray shuffleBy: rng to 4095 make some tests to pass, but there are some other failing. I will try to continue to see if I find the error. Thanks!
Levente
Levente
numbers := OrderedCollection new. numbers add: 1. numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
dict := LargeIdentityDictionary new. [numbers do: [:each | dict at: each put: dict size + 1. ]. ] timeToRun -> 12657
whereas with IdentityDictionary it is 37. I guess it could be related to #identityHash or #basicIdentityHash. I tried in Squeak 4.3 and it is also also there. I will try to take a look into it during the next week.
Thanks in advance
Nicolas
Thanks for any idea.
On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132
directly
was renamed to #instVarsInclude:, so now #pointsTo: works as
expected. If
this was also added to Pharo, then the #pointsTo: sends should be
changed to
#instVarsInclude:, otherwise Array can be reported as included even
if it
wasn't added.
I'll upload my LargeIdentityDictionary implementation to the same
place
this evening, since it's still 2-3 factor faster than other
solutionts and
there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to
#instVarsInclude:, so now #pointsTo: works as expected."
I do not get the following. Indeed pointTo: looks like instVarsInclude: now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.com
Actually, the long test is "Create some bitmaps" numbers := OrderedCollection new. numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ). "Put them in a dictionary using dict as as key" dict := LargeIdentityDictionary new. numbers do: [:each | dict at: each put: dict size + 1. ]. "Check they are correct" numbers doWithIndex: [:each :index | self assert: index == (dict at: each)] On Sun, Dec 18, 2011 at 7:17 PM, Mariano Martinez Peck < marianopeck@gmail.com> wrote:
Now I noticed that SmallIntegers storing is really slow
This is not entirely true. Every hash table can be made slow if you know how it's hash function works. Since in your example all numbers are congruent to 1 modulo 4096 and the size of the array is also 4096, therefore they will be mapped to the same slot (1). Try using random (or at least more realistic) numbers in your test. If this is a real problem, then it may be necessary to implement a new hash method, which uses the primitive for general objects and does something else with SmallIntegers and that method shoul be used from these large collections.
I uploaded a new mcz to the FuelExperiments repository, which is unaffected by the identity hash differences between Pharo and Squeak and works better with SmallIntegers. It includes both the dictionary and the set and (in theory) has slightly better performance for non-SmallInteger objects.
Hi Levente. First let me say I really appreaciate your effort in make it work. It makes definitvly Fuel faster and it would make sense to integrate them also in Squeak and Pharo. Now, I found another bug. To reproduce it:
| dict | dict := LargeIdentityDictionary new. dict at: 16941057 put: 1035.
Now, it seems 16941057 largeIdentityHash answers 4096 and the comment of #largeIdentityHash says ""Return an integer between 0 and 4095 based on all of my bits. Make sure that for nearby receivers the result will not be nearby with high probability.""
The thing is that LargeIdentityHashedCollection permuteHash: hash + 1 answers 4096, and hence, when in #at:put: you do:
at: key put: value
| hash | (keys at: (hash := key largeIdentityHash + 1))
then you get the out of bounds.
Modyfing
initialize
| rng | rng := Random seed: 664399324. PermutationMap := (1 to: 4096) asArray shuffleBy: rng
to 4095 make some tests to pass, but there are some other failing.
I will try to continue to see if I find the error.
Thanks!
Levente
Levente
numbers := OrderedCollection new. numbers add: 1. numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
dict := LargeIdentityDictionary new. [numbers do: [:each | dict at: each put: dict size + 1. ]. ] timeToRun -> 12657
whereas with IdentityDictionary it is 37. I guess it could be related to #identityHash or #basicIdentityHash. I tried in Squeak 4.3 and it is also also there. I will try to take a look into it during the next week.
Thanks in advance
Nicolas
Thanks for any idea.
On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132
directly
was renamed to #instVarsInclude:, so now #pointsTo: works as
expected. If
this was also added to Pharo, then the #pointsTo: sends should be
changed to
#instVarsInclude:, otherwise Array can be reported as included even
if it
wasn't added.
I'll upload my LargeIdentityDictionary implementation to the same
place
this evening, since it's still 2-3 factor faster than other
solutionts and
there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to
#instVarsInclude:, so now #pointsTo: works as expected."
I do not get the following. Indeed pointTo: looks like instVarsInclude: now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.**com<http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
On Sun, 18 Dec 2011, Mariano Martinez Peck wrote:
Actually, the long test is "Create some bitmaps"
numbers := OrderedCollection new. numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
"Put them in a dictionary using dict as as key" dict := LargeIdentityDictionary new. numbers do: [:each | dict at: each put: dict size + 1. ].
"Check they are correct" numbers doWithIndex: [:each :index | self assert: index == (dict at: each)]
Fixed. Levente
On Sun, Dec 18, 2011 at 7:17 PM, Mariano Martinez Peck < marianopeck@gmail.com> wrote:
Now I noticed that SmallIntegers storing is really slow
This is not entirely true. Every hash table can be made slow if you know how it's hash function works. Since in your example all numbers are congruent to 1 modulo 4096 and the size of the array is also 4096, therefore they will be mapped to the same slot (1). Try using random (or at least more realistic) numbers in your test. If this is a real problem, then it may be necessary to implement a new hash method, which uses the primitive for general objects and does something else with SmallIntegers and that method shoul be used from these large collections.
I uploaded a new mcz to the FuelExperiments repository, which is unaffected by the identity hash differences between Pharo and Squeak and works better with SmallIntegers. It includes both the dictionary and the set and (in theory) has slightly better performance for non-SmallInteger objects.
Hi Levente. First let me say I really appreaciate your effort in make it work. It makes definitvly Fuel faster and it would make sense to integrate them also in Squeak and Pharo. Now, I found another bug. To reproduce it:
| dict | dict := LargeIdentityDictionary new. dict at: 16941057 put: 1035.
Now, it seems 16941057 largeIdentityHash answers 4096 and the comment of #largeIdentityHash says ""Return an integer between 0 and 4095 based on all of my bits. Make sure that for nearby receivers the result will not be nearby with high probability.""
The thing is that LargeIdentityHashedCollection permuteHash: hash + 1 answers 4096, and hence, when in #at:put: you do:
at: key put: value
| hash | (keys at: (hash := key largeIdentityHash + 1))
then you get the out of bounds.
Modyfing
initialize
| rng | rng := Random seed: 664399324. PermutationMap := (1 to: 4096) asArray shuffleBy: rng
to 4095 make some tests to pass, but there are some other failing.
I will try to continue to see if I find the error.
Thanks!
Levente
Levente
numbers := OrderedCollection new. numbers add: 1. numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
dict := LargeIdentityDictionary new. [numbers do: [:each | dict at: each put: dict size + 1. ]. ] timeToRun -> 12657
whereas with IdentityDictionary it is 37. I guess it could be related to #identityHash or #basicIdentityHash. I tried in Squeak 4.3 and it is also also there. I will try to take a look into it during the next week.
Thanks in advance
Nicolas
Thanks for any idea.
On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132
directly
was renamed to #instVarsInclude:, so now #pointsTo: works as
expected. If
this was also added to Pharo, then the #pointsTo: sends should be
changed to
#instVarsInclude:, otherwise Array can be reported as included even
if it
wasn't added.
I'll upload my LargeIdentityDictionary implementation to the same
place
this evening, since it's still 2-3 factor faster than other
solutionts and
there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to
#instVarsInclude:, so now #pointsTo: works as expected."
I do not get the following. Indeed pointTo: looks like instVarsInclude: now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.**com<http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
2011/12/18 Levente Uzonyi <leves@elte.hu>
On Sun, 18 Dec 2011, Mariano Martinez Peck wrote:
Actually, the long test is
"Create some bitmaps"
numbers := OrderedCollection new. numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
"Put them in a dictionary using dict as as key" dict := LargeIdentityDictionary new. numbers do: [:each | dict at: each put: dict size + 1. ].
"Check they are correct" numbers doWithIndex: [:each :index | self assert: index == (dict at: each)]
Fixed.
That was FAST :) Thanks Levente. Where can I find the fix? Cheers
Levente
On Sun, Dec 18, 2011 at 7:17 PM, Mariano Martinez Peck < marianopeck@gmail.com> wrote:
Now I noticed that SmallIntegers storing is really slow
This is not entirely true. Every hash table can be made slow if you know how it's hash function works. Since in your example all numbers are congruent to 1 modulo 4096 and the size of the array is also 4096, therefore they will be mapped to the same slot (1). Try using random (or at least more realistic) numbers in your test. If this is a real problem, then it may be necessary to implement a new hash method, which uses the primitive for general objects and does something else with SmallIntegers and that method shoul be used from these large collections.
I uploaded a new mcz to the FuelExperiments repository, which is unaffected by the identity hash differences between Pharo and Squeak and works better with SmallIntegers. It includes both the dictionary and the set and (in theory) has slightly better performance for non-SmallInteger objects.
Hi Levente. First let me say I really appreaciate your effort in make it work. It makes definitvly Fuel faster and it would make sense to integrate them also in Squeak and Pharo. Now, I found another bug. To reproduce it:
| dict | dict := LargeIdentityDictionary new. dict at: 16941057 put: 1035.
Now, it seems 16941057 largeIdentityHash answers 4096 and the comment of #largeIdentityHash says ""Return an integer between 0 and 4095 based on all of my bits. Make sure that for nearby receivers the result will not be nearby with high probability.""
The thing is that LargeIdentityHashedCollection permuteHash: hash + 1 answers 4096, and hence, when in #at:put: you do:
at: key put: value
| hash | (keys at: (hash := key largeIdentityHash + 1))
then you get the out of bounds.
Modyfing
initialize
| rng | rng := Random seed: 664399324. PermutationMap := (1 to: 4096) asArray shuffleBy: rng
to 4095 make some tests to pass, but there are some other failing.
I will try to continue to see if I find the error.
Thanks!
Levente
Levente
numbers := OrderedCollection new.
numbers add: 1. numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
dict := LargeIdentityDictionary new. [numbers do: [:each | dict at: each put: dict size + 1. ]. ] timeToRun -> 12657
whereas with IdentityDictionary it is 37. I guess it could be related to #identityHash or #basicIdentityHash. I tried in Squeak 4.3 and it is also also there. I will try to take a look into it during the next week.
Thanks in advance
Nicolas
Thanks for any idea.
On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132
directly
was renamed to #instVarsInclude:, so now #pointsTo: works as
expected. If
this was also added to Pharo, then the #pointsTo: sends should be
changed to
#instVarsInclude:, otherwise Array can be reported as included even
if it
wasn't added.
I'll upload my LargeIdentityDictionary implementation to the same
place
this evening, since it's still 2-3 factor faster than other
solutionts and
there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to
#instVarsInclude:, so now #pointsTo: works as expected."
I do not get the following. Indeed pointTo: looks like instVarsInclude: now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.****com<http://marianopeck.** wordpress.com <http://marianopeck.wordpress.com>>
-- Mariano http://marianopeck.wordpress.****com <http://marianopeck.wordpress.** com <http://marianopeck.wordpress.com>>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.com
On Sun, 18 Dec 2011, Mariano Martinez Peck wrote:
2011/12/18 Levente Uzonyi <leves@elte.hu>
On Sun, 18 Dec 2011, Mariano Martinez Peck wrote:
Actually, the long test is
"Create some bitmaps"
numbers := OrderedCollection new. numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
"Put them in a dictionary using dict as as key" dict := LargeIdentityDictionary new. numbers do: [:each | dict at: each put: dict size + 1. ].
"Check they are correct" numbers doWithIndex: [:each :index | self assert: index == (dict at: each)]
Fixed.
That was FAST :) Thanks Levente. Where can I find the fix?
It should be in the FuelExperiments repository, though I had to upload it one more time for some reason. Levente
Cheers
Levente
On Sun, Dec 18, 2011 at 7:17 PM, Mariano Martinez Peck < marianopeck@gmail.com> wrote:
Now I noticed that SmallIntegers storing is really slow
This is not entirely true. Every hash table can be made slow if you know how it's hash function works. Since in your example all numbers are congruent to 1 modulo 4096 and the size of the array is also 4096, therefore they will be mapped to the same slot (1). Try using random (or at least more realistic) numbers in your test. If this is a real problem, then it may be necessary to implement a new hash method, which uses the primitive for general objects and does something else with SmallIntegers and that method shoul be used from these large collections.
I uploaded a new mcz to the FuelExperiments repository, which is unaffected by the identity hash differences between Pharo and Squeak and works better with SmallIntegers. It includes both the dictionary and the set and (in theory) has slightly better performance for non-SmallInteger objects.
Hi Levente. First let me say I really appreaciate your effort in make it work. It makes definitvly Fuel faster and it would make sense to integrate them also in Squeak and Pharo. Now, I found another bug. To reproduce it:
| dict | dict := LargeIdentityDictionary new. dict at: 16941057 put: 1035.
Now, it seems 16941057 largeIdentityHash answers 4096 and the comment of #largeIdentityHash says ""Return an integer between 0 and 4095 based on all of my bits. Make sure that for nearby receivers the result will not be nearby with high probability.""
The thing is that LargeIdentityHashedCollection permuteHash: hash + 1 answers 4096, and hence, when in #at:put: you do:
at: key put: value
| hash | (keys at: (hash := key largeIdentityHash + 1))
then you get the out of bounds.
Modyfing
initialize
| rng | rng := Random seed: 664399324. PermutationMap := (1 to: 4096) asArray shuffleBy: rng
to 4095 make some tests to pass, but there are some other failing.
I will try to continue to see if I find the error.
Thanks!
Levente
Levente
numbers := OrderedCollection new.
numbers add: 1. numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
dict := LargeIdentityDictionary new. [numbers do: [:each | dict at: each put: dict size + 1. ]. ] timeToRun -> 12657
whereas with IdentityDictionary it is 37. I guess it could be related to #identityHash or #basicIdentityHash. I tried in Squeak 4.3 and it is also also there. I will try to take a look into it during the next week.
Thanks in advance
Nicolas
Thanks for any idea.
On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132
directly
was renamed to #instVarsInclude:, so now #pointsTo: works as
expected. If
this was also added to Pharo, then the #pointsTo: sends should be
changed to
#instVarsInclude:, otherwise Array can be reported as included even
if it
wasn't added.
I'll upload my LargeIdentityDictionary implementation to the same
place
this evening, since it's still 2-3 factor faster than other
solutionts and
there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to
#instVarsInclude:, so now #pointsTo: works as expected."
I do not get the following. Indeed pointTo: looks like instVarsInclude: now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.****com<http://marianopeck.** wordpress.com <http://marianopeck.wordpress.com>>
-- Mariano http://marianopeck.wordpress.****com <http://marianopeck.wordpress.** com <http://marianopeck.wordpress.com>>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.com
2011/12/18 Levente Uzonyi <leves@elte.hu>
On Sun, 18 Dec 2011, Mariano Martinez Peck wrote:
2011/12/18 Levente Uzonyi <leves@elte.hu>
On Sun, 18 Dec 2011, Mariano Martinez Peck wrote:
Actually, the long test is
"Create some bitmaps"
numbers := OrderedCollection new. numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
"Put them in a dictionary using dict as as key" dict := LargeIdentityDictionary new. numbers do: [:each | dict at: each put: dict size + 1. ].
"Check they are correct" numbers doWithIndex: [:each :index | self assert: index == (dict at: each)]
Fixed.
That was FAST :)
Thanks Levente. Where can I find the fix?
It should be in the FuelExperiments repository, though I had to upload it one more time for some reason.
Thanks Levente. Well, now all our tests and benchmarks pass like a charm :) We will soon include it in the "trunk" of Fuel. Will them be available in a repository for squeak? because if so, I can adapt ConfiguratioOfFuel so that in Squeak it loads another collections. So...from the benchmarks I can say that in large graphs the improve in performance was 30% in serialization, and only use in one place the set and in another one the dictionary. Thanks!!!
Levente
Cheers
Levente
On Sun, Dec 18, 2011 at 7:17 PM, Mariano Martinez Peck <
marianopeck@gmail.com> wrote:
Now I noticed that SmallIntegers storing is really slow
This is not entirely true. Every hash table can be made slow if you
know how it's hash function works. Since in your example all numbers are congruent to 1 modulo 4096 and the size of the array is also 4096, therefore they will be mapped to the same slot (1). Try using random (or at least more realistic) numbers in your test. If this is a real problem, then it may be necessary to implement a new hash method, which uses the primitive for general objects and does something else with SmallIntegers and that method shoul be used from these large collections.
I uploaded a new mcz to the FuelExperiments repository, which is unaffected by the identity hash differences between Pharo and Squeak and works better with SmallIntegers. It includes both the dictionary and the set and (in theory) has slightly better performance for non-SmallInteger objects.
Hi Levente. First let me say I really appreaciate your effort in make
it work. It makes definitvly Fuel faster and it would make sense to integrate them also in Squeak and Pharo. Now, I found another bug. To reproduce it:
| dict | dict := LargeIdentityDictionary new. dict at: 16941057 put: 1035.
Now, it seems 16941057 largeIdentityHash answers 4096 and the comment of #largeIdentityHash says ""Return an integer between 0 and 4095 based on all of my bits. Make sure that for nearby receivers the result will not be nearby with high probability.""
The thing is that LargeIdentityHashedCollection permuteHash: hash + 1 answers 4096, and hence, when in #at:put: you do:
at: key put: value
| hash | (keys at: (hash := key largeIdentityHash + 1))
then you get the out of bounds.
Modyfing
initialize
| rng | rng := Random seed: 664399324. PermutationMap := (1 to: 4096) asArray shuffleBy: rng
to 4095 make some tests to pass, but there are some other failing.
I will try to continue to see if I find the error.
Thanks!
Levente
Levente
numbers := OrderedCollection new.
numbers add: 1. numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
dict := LargeIdentityDictionary new. [numbers do: [:each | dict at: each put: dict size + 1. ]. ] timeToRun -> 12657
whereas with IdentityDictionary it is 37. I guess it could be related to #identityHash or #basicIdentityHash. I tried in Squeak 4.3 and it is also also there. I will try to take a look into it during the next week.
Thanks in advance
Nicolas
Thanks for any idea.
On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132
directly
was renamed to #instVarsInclude:, so now #pointsTo: works as
expected. If
this was also added to Pharo, then the #pointsTo: sends should
be
changed to
#instVarsInclude:, otherwise Array can be reported as included
even
if it
wasn't added.
I'll upload my LargeIdentityDictionary implementation to the same
place
this evening, since it's still 2-3 factor faster than other
solutionts and
there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to
#instVarsInclude:, so now #pointsTo: works as expected."
I do not get the following. Indeed pointTo: looks like
instVarsInclude: now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.******com<http://marianopeck.** wordpress.com <http://marianopeck.wordpress.**com<http://marianopeck.wordpress.com>
--
Mariano http://marianopeck.wordpress.******com < http://marianopeck.wordpress.**** com <http://marianopeck.wordpress.**com<http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.****com <http://marianopeck.wordpress.** com <http://marianopeck.wordpress.com>>
-- Mariano http://marianopeck.wordpress.****com <http://marianopeck.wordpress.** com <http://marianopeck.wordpress.com>>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.com
On Sun, 18 Dec 2011, Mariano Martinez Peck wrote:
2011/12/18 Levente Uzonyi <leves@elte.hu>
On Sun, 18 Dec 2011, Mariano Martinez Peck wrote:
2011/12/18 Levente Uzonyi <leves@elte.hu>
On Sun, 18 Dec 2011, Mariano Martinez Peck wrote:
Actually, the long test is
"Create some bitmaps"
numbers := OrderedCollection new. numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
"Put them in a dictionary using dict as as key" dict := LargeIdentityDictionary new. numbers do: [:each | dict at: each put: dict size + 1. ].
"Check they are correct" numbers doWithIndex: [:each :index | self assert: index == (dict at: each)]
Fixed.
That was FAST :)
Thanks Levente. Where can I find the fix?
It should be in the FuelExperiments repository, though I had to upload it one more time for some reason.
Thanks Levente. Well, now all our tests and benchmarks pass like a charm :) We will soon include it in the "trunk" of Fuel. Will them be available in a repository for squeak? because if so, I can adapt ConfiguratioOfFuel so that in Squeak it loads another collections.
The best would be to add the patch to Pharo, which fixes #pointsTo: and adds #instVarsIncludes:. Then change the code to use #instVarsInclude: in these collections. If that's all done, then this code should work in both Pharo and Squeak.
So...from the benchmarks I can say that in large graphs the improve in performance was 30% in serialization, and only use in one place the set and in another one the dictionary.
Great, hopefully the new primitive will increase this even more. :) Levente
Thanks!!!
Levente
Cheers
Levente
On Sun, Dec 18, 2011 at 7:17 PM, Mariano Martinez Peck <
marianopeck@gmail.com> wrote:
Now I noticed that SmallIntegers storing is really slow
This is not entirely true. Every hash table can be made slow if you
know how it's hash function works. Since in your example all numbers are congruent to 1 modulo 4096 and the size of the array is also 4096, therefore they will be mapped to the same slot (1). Try using random (or at least more realistic) numbers in your test. If this is a real problem, then it may be necessary to implement a new hash method, which uses the primitive for general objects and does something else with SmallIntegers and that method shoul be used from these large collections.
I uploaded a new mcz to the FuelExperiments repository, which is unaffected by the identity hash differences between Pharo and Squeak and works better with SmallIntegers. It includes both the dictionary and the set and (in theory) has slightly better performance for non-SmallInteger objects.
Hi Levente. First let me say I really appreaciate your effort in make
it work. It makes definitvly Fuel faster and it would make sense to integrate them also in Squeak and Pharo. Now, I found another bug. To reproduce it:
| dict | dict := LargeIdentityDictionary new. dict at: 16941057 put: 1035.
Now, it seems 16941057 largeIdentityHash answers 4096 and the comment of #largeIdentityHash says ""Return an integer between 0 and 4095 based on all of my bits. Make sure that for nearby receivers the result will not be nearby with high probability.""
The thing is that LargeIdentityHashedCollection permuteHash: hash + 1 answers 4096, and hence, when in #at:put: you do:
at: key put: value
| hash | (keys at: (hash := key largeIdentityHash + 1))
then you get the out of bounds.
Modyfing
initialize
| rng | rng := Random seed: 664399324. PermutationMap := (1 to: 4096) asArray shuffleBy: rng
to 4095 make some tests to pass, but there are some other failing.
I will try to continue to see if I find the error.
Thanks!
Levente
Levente
numbers := OrderedCollection new.
numbers add: 1. numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
dict := LargeIdentityDictionary new. [numbers do: [:each | dict at: each put: dict size + 1. ]. ] timeToRun -> 12657
whereas with IdentityDictionary it is 37. I guess it could be related to #identityHash or #basicIdentityHash. I tried in Squeak 4.3 and it is also also there. I will try to take a look into it during the next week.
Thanks in advance
Nicolas
Thanks for any idea.
On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132
directly
was renamed to #instVarsInclude:, so now #pointsTo: works as
expected. If
this was also added to Pharo, then the #pointsTo: sends should
be
changed to
#instVarsInclude:, otherwise Array can be reported as included
even
if it
wasn't added.
I'll upload my LargeIdentityDictionary implementation to the same
place
this evening, since it's still 2-3 factor faster than other
solutionts and
there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to
#instVarsInclude:, so now #pointsTo: works as expected."
I do not get the following. Indeed pointTo: looks like
instVarsInclude: now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.******com<http://marianopeck.** wordpress.com <http://marianopeck.wordpress.**com<http://marianopeck.wordpress.com>
--
Mariano http://marianopeck.wordpress.******com < http://marianopeck.wordpress.**** com <http://marianopeck.wordpress.**com<http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.****com <http://marianopeck.wordpress.** com <http://marianopeck.wordpress.com>>
-- Mariano http://marianopeck.wordpress.****com <http://marianopeck.wordpress.** com <http://marianopeck.wordpress.com>>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.com
Hi levente We will certainly do that. Right now I'm resting from the crazy weeks before christmas and too many articles writing at the last minute (this is part of the job but working even the saturday and sunday can simply lead to energy burnout. Anyway I'm happy we did it). @Mariano I opened a bug entry for it. If you have the time (have a look). I will try tomorrow but I would like to relax and I booked a real holiday day: (gym, game with kids and probably hacking with igor :)). Stef
The best would be to add the patch to Pharo, which fixes #pointsTo: and adds #instVarsIncludes:. Then change the code to use #instVarsInclude: in these collections. If that's all done, then this code should work in both Pharo and Squeak.
Thanks Levente. Well, now all our tests and benchmarks pass like a charm :) We will soon include it in the "trunk" of Fuel. Will them be available in a repository for squeak? because if so, I can adapt ConfiguratioOfFuel so that in Squeak it loads another collections.
The best would be to add the patch to Pharo, which fixes #pointsTo: and adds #instVarsIncludes:. Then change the code to use #instVarsInclude: in these collections. If that's all done, then this code should work in both Pharo and Squeak.
Yes, I agree. But anyway, Fuel will load in previous versions of Pharo, where such fix won't be integrated. So we will need to handle this.
So...from the benchmarks I can say that in large graphs the improve in performance was 30% in serialization, and only use in one place the set and in another one the dictionary.
Great, hopefully the new primitive will increase this even more. :)
Hopefully. Did you answer Eliot? he was asking what you needed... Ahh BTW, I found another small bug.. LargeIdentityDictionary sends #keyNotFound but it is not implemented. Just adding: errorKeyNotFound: aKey KeyNotFound signalFor: aKey is enough. Cheers
Levente
Thanks!!!
Levente
Cheers
Levente
On Sun, Dec 18, 2011 at 7:17 PM, Mariano Martinez Peck <
marianopeck@gmail.com> wrote:
Now I noticed that SmallIntegers storing is really slow
This is not entirely true. Every hash table can be made slow if you
know how it's hash function works. Since in your example all numbers are congruent to 1 modulo 4096 and the size of the array is also 4096, therefore they will be mapped to the same slot (1). Try using random (or at least more realistic) numbers in your test. If this is a real problem, then it may be necessary to implement a new hash method, which uses the primitive for general objects and does something else with SmallIntegers and that method shoul be used from these large collections.
I uploaded a new mcz to the FuelExperiments repository, which is
unaffected by the identity hash differences between Pharo and Squeak and works better with SmallIntegers. It includes both the dictionary and the set and (in theory) has slightly better performance for non-SmallInteger objects.
Hi Levente. First let me say I really appreaciate your effort in make
it
work. It makes definitvly Fuel faster and it would make sense to integrate them also in Squeak and Pharo. Now, I found another bug. To reproduce it:
| dict | dict := LargeIdentityDictionary new. dict at: 16941057 put: 1035.
Now, it seems 16941057 largeIdentityHash answers 4096 and the comment of #largeIdentityHash says ""Return an integer between 0 and 4095 based on all of my bits. Make sure that for nearby receivers the result will not be nearby with high probability.""
The thing is that LargeIdentityHashedCollection permuteHash: hash + 1 answers 4096, and hence, when in #at:put: you do:
at: key put: value
| hash | (keys at: (hash := key largeIdentityHash + 1))
then you get the out of bounds.
Modyfing
initialize
| rng | rng := Random seed: 664399324. PermutationMap := (1 to: 4096) asArray shuffleBy: rng
to 4095 make some tests to pass, but there are some other failing.
I will try to continue to see if I find the error.
Thanks!
Levente
Levente
numbers := OrderedCollection new.
numbers add: 1.
numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
dict := LargeIdentityDictionary new. [numbers do: [:each | dict at: each put: dict size + 1. ]. ] timeToRun -> 12657
whereas with IdentityDictionary it is 37. I guess it could be related to #identityHash or #basicIdentityHash. I tried in Squeak 4.3 and it is also also there. I will try to take a look into it during the next week.
Thanks in advance
Nicolas
Thanks for any idea.
On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132
directly
was renamed to #instVarsInclude:, so now #pointsTo: works as
expected. If
this was also added to Pharo, then the #pointsTo: sends
should
be
changed to
#instVarsInclude:, otherwise Array can be reported as
included
even
if it
wasn't added.
I'll upload my LargeIdentityDictionary implementation to the same
place
this evening, since it's still 2-3 factor faster than other
solutionts and
there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to
#instVarsInclude:, so now #pointsTo: works as expected."
I do not get the following. Indeed pointTo: looks like
instVarsInclude:
now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.********com<http://marianopeck.** wordpress.com <http://marianopeck.wordpress.****com<; http://marianopeck.**wordpress.com<http://marianopeck.wordpress.com>
--
Mariano http://marianopeck.wordpress.********com < http://marianopeck.wordpress.****** com <http://marianopeck.wordpress.****com<http://marianopeck.** wordpress.com <http://marianopeck.wordpress.com>>
--
Mariano http://marianopeck.wordpress.******com < http://marianopeck.wordpress.**** com <http://marianopeck.wordpress.**com<http://marianopeck.wordpress.com>
--
Mariano http://marianopeck.wordpress.******com <http://marianopeck.wordpress. **** com <http://marianopeck.wordpress.**com<http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.****com <http://marianopeck.wordpress.** com <http://marianopeck.wordpress.com>>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.com
On Tue, 20 Dec 2011, Mariano Martinez Peck wrote:
Thanks Levente. Well, now all our tests and benchmarks pass like a charm :) We will soon include it in the "trunk" of Fuel. Will them be available in a repository for squeak? because if so, I can adapt ConfiguratioOfFuel so that in Squeak it loads another collections.
The best would be to add the patch to Pharo, which fixes #pointsTo: and adds #instVarsIncludes:. Then change the code to use #instVarsInclude: in these collections. If that's all done, then this code should work in both Pharo and Squeak.
Yes, I agree. But anyway, Fuel will load in previous versions of Pharo, where such fix won't be integrated. So we will need to handle this.
This can easily solved with a separate Metacello configuration.
So...from the benchmarks I can say that in large graphs the improve in performance was 30% in serialization, and only use in one place the set and in another one the dictionary.
Great, hopefully the new primitive will increase this even more. :)
Hopefully. Did you answer Eliot? he was asking what you needed...
I did answer his private email about the primitive.
Ahh BTW, I found another small bug.. LargeIdentityDictionary sends #keyNotFound but it is not implemented. Just adding:
errorKeyNotFound: aKey
KeyNotFound signalFor: aKey
is enough.
Go ahead. :) Levente
Cheers
Levente
Thanks!!!
Levente
Cheers
Levente
On Sun, Dec 18, 2011 at 7:17 PM, Mariano Martinez Peck <
marianopeck@gmail.com> wrote:
Now I noticed that SmallIntegers storing is really slow
This is not entirely true. Every hash table can be made slow if you
know how it's hash function works. Since in your example all numbers are congruent to 1 modulo 4096 and the size of the array is also 4096, therefore they will be mapped to the same slot (1). Try using random (or at least more realistic) numbers in your test. If this is a real problem, then it may be necessary to implement a new hash method, which uses the primitive for general objects and does something else with SmallIntegers and that method shoul be used from these large collections.
I uploaded a new mcz to the FuelExperiments repository, which is
unaffected by the identity hash differences between Pharo and Squeak and works better with SmallIntegers. It includes both the dictionary and the set and (in theory) has slightly better performance for non-SmallInteger objects.
Hi Levente. First let me say I really appreaciate your effort in make
it
work. It makes definitvly Fuel faster and it would make sense to integrate them also in Squeak and Pharo. Now, I found another bug. To reproduce it:
| dict | dict := LargeIdentityDictionary new. dict at: 16941057 put: 1035.
Now, it seems 16941057 largeIdentityHash answers 4096 and the comment of #largeIdentityHash says ""Return an integer between 0 and 4095 based on all of my bits. Make sure that for nearby receivers the result will not be nearby with high probability.""
The thing is that LargeIdentityHashedCollection permuteHash: hash + 1 answers 4096, and hence, when in #at:put: you do:
at: key put: value
| hash | (keys at: (hash := key largeIdentityHash + 1))
then you get the out of bounds.
Modyfing
initialize
| rng | rng := Random seed: 664399324. PermutationMap := (1 to: 4096) asArray shuffleBy: rng
to 4095 make some tests to pass, but there are some other failing.
I will try to continue to see if I find the error.
Thanks!
Levente
Levente
numbers := OrderedCollection new.
numbers add: 1.
numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
dict := LargeIdentityDictionary new. [numbers do: [:each | dict at: each put: dict size + 1. ]. ] timeToRun -> 12657
whereas with IdentityDictionary it is 37. I guess it could be related to #identityHash or #basicIdentityHash. I tried in Squeak 4.3 and it is also also there. I will try to take a look into it during the next week.
Thanks in advance
Nicolas
Thanks for any idea.
On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132
directly
was renamed to #instVarsInclude:, so now #pointsTo: works as
expected. If
this was also added to Pharo, then the #pointsTo: sends
should
be
changed to
#instVarsInclude:, otherwise Array can be reported as
included
even
if it
wasn't added.
I'll upload my LargeIdentityDictionary implementation to the same
place
this evening, since it's still 2-3 factor faster than other
solutionts and
there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to
#instVarsInclude:, so now #pointsTo: works as expected."
I do not get the following. Indeed pointTo: looks like
instVarsInclude:
now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.********com<http://marianopeck.** wordpress.com <http://marianopeck.wordpress.****com<; http://marianopeck.**wordpress.com<http://marianopeck.wordpress.com>
--
Mariano http://marianopeck.wordpress.********com < http://marianopeck.wordpress.****** com <http://marianopeck.wordpress.****com<http://marianopeck.** wordpress.com <http://marianopeck.wordpress.com>>
--
Mariano http://marianopeck.wordpress.******com < http://marianopeck.wordpress.**** com <http://marianopeck.wordpress.**com<http://marianopeck.wordpress.com>
--
Mariano http://marianopeck.wordpress.******com <http://marianopeck.wordpress. **** com <http://marianopeck.wordpress.**com<http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.****com <http://marianopeck.wordpress.** com <http://marianopeck.wordpress.com>>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.com
2011/12/20 Levente Uzonyi <leves@elte.hu>
On Tue, 20 Dec 2011, Mariano Martinez Peck wrote:
Thanks Levente. Well, now all our tests and benchmarks pass like a
charm
:) We will soon include it in the "trunk" of Fuel. Will them be available in a repository for squeak? because if so, I can adapt ConfiguratioOfFuel so that in Squeak it loads another collections.
The best would be to add the patch to Pharo, which fixes #pointsTo: and adds #instVarsIncludes:. Then change the code to use #instVarsInclude: in these collections. If that's all done, then this code should work in both Pharo and Squeak.
Yes, I agree. But anyway, Fuel will load in previous versions of Pharo, where such fix won't be integrated. So we will need to handle this.
This can easily solved with a separate Metacello configuration.
Yes, I will do that.
So...from the benchmarks I can say that in large graphs the improve in
performance was 30% in serialization, and only use in one place the set and in another one the dictionary.
Great, hopefully the new primitive will increase this even more. :)
Hopefully. Did you answer Eliot? he was asking what you needed...
I did answer his private email about the primitive.
Ahh ok, excellent :)
Ahh BTW, I found another small bug.. LargeIdentityDictionary sends #keyNotFound but it is not implemented. Just adding:
errorKeyNotFound: aKey
KeyNotFound signalFor: aKey
is enough.
Go ahead. :)
Done
Levente
Cheers
Levente
Thanks!!!
Levente
Cheers
Levente
On Sun, Dec 18, 2011 at 7:17 PM, Mariano Martinez Peck <
marianopeck@gmail.com> wrote:
Now I noticed that SmallIntegers storing is really slow
This is not entirely true. Every hash table can be made slow if
you
know how it's hash function works. Since in your example all numbers are congruent to 1 modulo 4096 and the size of the array is also 4096, therefore they will be mapped to the same slot (1). Try using random (or at least more realistic) numbers in your test. If this is a real problem, then it may be necessary to implement a new hash method, which uses the primitive for general objects and does something else with SmallIntegers and that method shoul be used from these large collections.
I uploaded a new mcz to the FuelExperiments repository, which is
unaffected by the identity hash differences between Pharo and Squeak and works better with SmallIntegers. It includes both the dictionary and the set and (in theory) has slightly better performance for non-SmallInteger objects.
Hi Levente. First let me say I really appreaciate your effort in make
it
work. It makes definitvly Fuel faster and it would make sense to integrate them also in Squeak and Pharo. Now, I found another bug. To reproduce it:
| dict | dict := LargeIdentityDictionary new. dict at: 16941057 put: 1035.
Now, it seems 16941057 largeIdentityHash answers 4096 and the comment of #largeIdentityHash says ""Return an integer between 0 and 4095 based on all of my bits. Make sure that for nearby receivers the result will not be nearby with high probability.""
The thing is that LargeIdentityHashedCollection permuteHash: hash + 1 answers 4096, and hence, when in #at:put: you do:
at: key put: value
| hash | (keys at: (hash := key largeIdentityHash + 1))
then you get the out of bounds.
Modyfing
initialize
| rng | rng := Random seed: 664399324. PermutationMap := (1 to: 4096) asArray shuffleBy: rng
to 4095 make some tests to pass, but there are some other failing.
I will try to continue to see if I find the error.
Thanks!
Levente
Levente
numbers := OrderedCollection new.
numbers add: 1.
numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
dict := LargeIdentityDictionary new. [numbers do: [:each | dict at: each put: dict size + 1. ]. ] timeToRun -> 12657
whereas with IdentityDictionary it is 37. I guess it could be related to #identityHash or #basicIdentityHash. I tried in Squeak 4.3 and it is also also there. I will try to take a look into it during the next week.
Thanks in advance
Nicolas
Thanks for any idea.
On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132
directly
was renamed to #instVarsInclude:, so now #pointsTo: works as
expected. If
this was also added to Pharo, then the #pointsTo: sends
should
be
changed to
#instVarsInclude:, otherwise Array can be reported as
included
even
if it
wasn't added.
I'll upload my LargeIdentityDictionary implementation to the
same
place
this evening, since it's still 2-3 factor faster than other
solutionts and
there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to
#instVarsInclude:, so now #pointsTo: works as expected."
I do not get the following. Indeed pointTo: looks like
instVarsInclude:
now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.**********com<; http://marianopeck.**** wordpress.com <http://marianopeck.wordpress.******com<; http://marianopeck.**wordpress**.com <http://wordpress.com><; http://marianopeck.**wordpress.com<http://marianopeck.wordpress.com>
--
Mariano
http://marianopeck.wordpress.**********com < http://marianopeck.wordpress.******** com <http://marianopeck.wordpress.******com<http://marianopeck. ** wordpress.com <http://marianopeck.wordpress.**com<http://marianopeck.wordpress.com>
--
Mariano
http://marianopeck.wordpress.********com < http://marianopeck.wordpress.****** com <http://marianopeck.wordpress.****com<http://marianopeck.** wordpress.com <http://marianopeck.wordpress.com>>
--
Mariano http://marianopeck.wordpress.********com < http://marianopeck.wordpress.
**** com <http://marianopeck.wordpress.****com<http://marianopeck.** wordpress.com <http://marianopeck.wordpress.com>>
--
Mariano http://marianopeck.wordpress.******com <http://marianopeck.wordpress. **** com <http://marianopeck.wordpress.**com<http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.****com <http://marianopeck.wordpress.** com <http://marianopeck.wordpress.com>>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.com
So...the fix for #pointsTo: and #instVarsInclude: is in inbox: http://code.google.com/p/pharo/issues/detail?id=5118 If anyone wants to take a look... Cheers On Tue, Dec 20, 2011 at 11:01 PM, Mariano Martinez Peck < marianopeck@gmail.com> wrote:
2011/12/20 Levente Uzonyi <leves@elte.hu>
On Tue, 20 Dec 2011, Mariano Martinez Peck wrote:
Thanks Levente. Well, now all our tests and benchmarks pass like a
charm
:) We will soon include it in the "trunk" of Fuel. Will them be available in a repository for squeak? because if so, I can adapt ConfiguratioOfFuel so that in Squeak it loads another collections.
The best would be to add the patch to Pharo, which fixes #pointsTo: and adds #instVarsIncludes:. Then change the code to use #instVarsInclude: in these collections. If that's all done, then this code should work in both Pharo and Squeak.
Yes, I agree. But anyway, Fuel will load in previous versions of Pharo, where such fix won't be integrated. So we will need to handle this.
This can easily solved with a separate Metacello configuration.
Yes, I will do that.
So...from the benchmarks I can say that in large graphs the improve in
performance was 30% in serialization, and only use in one place the set and in another one the dictionary.
Great, hopefully the new primitive will increase this even more. :)
Hopefully. Did you answer Eliot? he was asking what you needed...
I did answer his private email about the primitive.
Ahh ok, excellent :)
Ahh BTW, I found another small bug.. LargeIdentityDictionary sends #keyNotFound but it is not implemented. Just adding:
errorKeyNotFound: aKey
KeyNotFound signalFor: aKey
is enough.
Go ahead. :)
Done
Levente
Cheers
Levente
Thanks!!!
Levente
Cheers
Levente
On Sun, Dec 18, 2011 at 7:17 PM, Mariano Martinez Peck <
marianopeck@gmail.com> wrote:
Now I noticed that SmallIntegers storing is really slow
This is not entirely true. Every hash table can be made slow if
you
know how it's hash function works. Since in your example all numbers are congruent to 1 modulo 4096 and the size of the array is also 4096, therefore they will be mapped to the same slot (1). Try using random (or at least more realistic) numbers in your test. If this is a real problem, then it may be necessary to implement a new hash method, which uses the primitive for general objects and does something else with SmallIntegers and that method shoul be used from these large collections.
I uploaded a new mcz to the FuelExperiments repository, which is
unaffected by the identity hash differences between Pharo and Squeak and works better with SmallIntegers. It includes both the dictionary and the set and (in theory) has slightly better performance for non-SmallInteger objects.
Hi Levente. First let me say I really appreaciate your effort in make
it
work. It makes definitvly Fuel faster and it would make sense to integrate them also in Squeak and Pharo. Now, I found another bug. To reproduce it:
| dict | dict := LargeIdentityDictionary new. dict at: 16941057 put: 1035.
Now, it seems 16941057 largeIdentityHash answers 4096 and the comment of #largeIdentityHash says ""Return an integer between 0 and 4095 based on all of my bits. Make sure that for nearby receivers the result will not be nearby with high probability.""
The thing is that LargeIdentityHashedCollection permuteHash: hash + 1 answers 4096, and hence, when in #at:put: you do:
at: key put: value
| hash | (keys at: (hash := key largeIdentityHash + 1))
then you get the out of bounds.
Modyfing
initialize
| rng | rng := Random seed: 664399324. PermutationMap := (1 to: 4096) asArray shuffleBy: rng
to 4095 make some tests to pass, but there are some other failing.
I will try to continue to see if I find the error.
Thanks!
Levente
Levente
numbers := OrderedCollection new.
numbers add: 1.
numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
dict := LargeIdentityDictionary new. [numbers do: [:each | dict at: each put: dict size + 1. ]. ] timeToRun -> 12657
whereas with IdentityDictionary it is 37. I guess it could be related to #identityHash or #basicIdentityHash. I tried in Squeak 4.3 and it is also also there. I will try to take a look into it during the next week.
Thanks in advance
Nicolas
Thanks for any idea.
On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132
directly
was renamed to #instVarsInclude:, so now #pointsTo: works as
expected. If
this was also added to Pharo, then the #pointsTo: sends
should
be
changed to
#instVarsInclude:, otherwise Array can be reported as
included
even
if it
wasn't added.
I'll upload my LargeIdentityDictionary implementation to the
same
place
this evening, since it's still 2-3 factor faster than other
solutionts and
there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to
#instVarsInclude:, so now #pointsTo: works as expected."
I do not get the following. Indeed pointTo: looks like
instVarsInclude:
now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.**********com<; http://marianopeck.**** wordpress.com <http://marianopeck.wordpress.******com<; http://marianopeck.**wordpress**.com <http://wordpress.com> <http://marianopeck.**wordpress.com<http://marianopeck.wordpress.com>
--
Mariano
http://marianopeck.wordpress.**********com < http://marianopeck.wordpress.******** com <http://marianopeck.wordpress.******com<; http://marianopeck.** wordpress.com <http://marianopeck.wordpress.**com<http://marianopeck.wordpress.com>
--
Mariano
http://marianopeck.wordpress.********com < http://marianopeck.wordpress.****** com <http://marianopeck.wordpress.****com<http://marianopeck.** wordpress.com <http://marianopeck.wordpress.com>>
--
Mariano http://marianopeck.wordpress.********com < http://marianopeck.wordpress.
**** com <http://marianopeck.wordpress.****com<http://marianopeck.** wordpress.com <http://marianopeck.wordpress.com>>
--
Mariano http://marianopeck.wordpress.******com < http://marianopeck.wordpress.**** com <http://marianopeck.wordpress.**com<http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.****com <http://marianopeck.wordpress.** com <http://marianopeck.wordpress.com>>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
I will :) Thanks mariano On Dec 22, 2011, at 9:11 PM, Mariano Martinez Peck wrote:
So...the fix for #pointsTo: and #instVarsInclude: is in inbox:
http://code.google.com/p/pharo/issues/detail?id=5118
If anyone wants to take a look...
Cheers
On Tue, Dec 20, 2011 at 11:01 PM, Mariano Martinez Peck <marianopeck@gmail.com> wrote:
2011/12/20 Levente Uzonyi <leves@elte.hu> On Tue, 20 Dec 2011, Mariano Martinez Peck wrote:
Thanks Levente. Well, now all our tests and benchmarks pass like a charm :) We will soon include it in the "trunk" of Fuel. Will them be available in a repository for squeak? because if so, I can adapt ConfiguratioOfFuel so that in Squeak it loads another collections.
The best would be to add the patch to Pharo, which fixes #pointsTo: and adds #instVarsIncludes:. Then change the code to use #instVarsInclude: in these collections. If that's all done, then this code should work in both Pharo and Squeak.
Yes, I agree. But anyway, Fuel will load in previous versions of Pharo, where such fix won't be integrated. So we will need to handle this.
This can easily solved with a separate Metacello configuration.
Yes, I will do that.
So...from the benchmarks I can say that in large graphs the improve in performance was 30% in serialization, and only use in one place the set and in another one the dictionary.
Great, hopefully the new primitive will increase this even more. :)
Hopefully. Did you answer Eliot? he was asking what you needed...
I did answer his private email about the primitive.
Ahh ok, excellent :)
Ahh BTW, I found another small bug.. LargeIdentityDictionary sends #keyNotFound but it is not implemented. Just adding:
errorKeyNotFound: aKey
KeyNotFound signalFor: aKey
is enough.
Go ahead. :)
Done
Levente
Cheers
Levente
Thanks!!!
Levente
Cheers
Levente
On Sun, Dec 18, 2011 at 7:17 PM, Mariano Martinez Peck <
marianopeck@gmail.com> wrote:
Now I noticed that SmallIntegers storing is really slow
This is not entirely true. Every hash table can be made slow if you
know how it's hash function works. Since in your example all numbers are congruent to 1 modulo 4096 and the size of the array is also 4096, therefore they will be mapped to the same slot (1). Try using random (or at least more realistic) numbers in your test. If this is a real problem, then it may be necessary to implement a new hash method, which uses the primitive for general objects and does something else with SmallIntegers and that method shoul be used from these large collections.
I uploaded a new mcz to the FuelExperiments repository, which is
unaffected by the identity hash differences between Pharo and Squeak and works better with SmallIntegers. It includes both the dictionary and the set and (in theory) has slightly better performance for non-SmallInteger objects.
Hi Levente. First let me say I really appreaciate your effort in make
it work. It makes definitvly Fuel faster and it would make sense to integrate them also in Squeak and Pharo. Now, I found another bug. To reproduce it:
| dict | dict := LargeIdentityDictionary new. dict at: 16941057 put: 1035.
Now, it seems 16941057 largeIdentityHash answers 4096 and the comment of #largeIdentityHash says ""Return an integer between 0 and 4095 based on all of my bits. Make sure that for nearby receivers the result will not be nearby with high probability.""
The thing is that LargeIdentityHashedCollection permuteHash: hash + 1 answers 4096, and hence, when in #at:put: you do:
at: key put: value
| hash | (keys at: (hash := key largeIdentityHash + 1))
then you get the out of bounds.
Modyfing
initialize
| rng | rng := Random seed: 664399324. PermutationMap := (1 to: 4096) asArray shuffleBy: rng
to 4095 make some tests to pass, but there are some other failing.
I will try to continue to see if I find the error.
Thanks!
Levente
Levente
numbers := OrderedCollection new.
numbers add: 1. numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray. numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
dict := LargeIdentityDictionary new. [numbers do: [:each | dict at: each put: dict size + 1. ]. ] timeToRun -> 12657
whereas with IdentityDictionary it is 37. I guess it could be related to #identityHash or #basicIdentityHash. I tried in Squeak 4.3 and it is also also there. I will try to take a look into it during the next week.
Thanks in advance
Nicolas
Thanks for any idea.
On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132
directly
was renamed to #instVarsInclude:, so now #pointsTo: works as
expected. If
this was also added to Pharo, then the #pointsTo: sends should
be
changed to
#instVarsInclude:, otherwise Array can be reported as included
even
if it
wasn't added.
I'll upload my LargeIdentityDictionary implementation to the same
place
this evening, since it's still 2-3 factor faster than other
solutionts and
there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to
#instVarsInclude:, so now #pointsTo: works as expected."
I do not get the following. Indeed pointTo: looks like
instVarsInclude: now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.********com<http://marianopeck.** wordpress.com <http://marianopeck.wordpress.****com<; http://marianopeck.**wordpress.com<http://marianopeck.wordpress.com>
--
Mariano http://marianopeck.wordpress.********com < http://marianopeck.wordpress.****** com <http://marianopeck.wordpress.****com<http://marianopeck.** wordpress.com <http://marianopeck.wordpress.com>>
-- Mariano http://marianopeck.wordpress.******com < http://marianopeck.wordpress.**** com <http://marianopeck.wordpress.**com<http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.******com <http://marianopeck.wordpress.
**** com <http://marianopeck.wordpress.**com<http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.****com <http://marianopeck.wordpress.** com <http://marianopeck.wordpress.com>>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
2011/12/17 Mariano Martinez Peck <marianopeck@gmail.com>:
Can't you debug it ?
Of course I could do it when I have some time. It already took me 1 hour to isolate the bug from Fuel and make a reproducible test. I hope that at least you find that useful. I found the bug and I thought I could send my progress and see if someone could continue it. Otherwise, I was going to debug it as soon as I have some free time (which I don't have much this year).
Yes, great job, thank you. But that's what amazed me, you stopped just before the easiest part ;)
It took 2 minutes to find this sentence at line 19 of  LargeDictionary>>at:put:
But you are so smart and a Collection hacker. Me, I am newbie, and just the method at:put: scares me, but I understand if it has to be that way in order to be fast. And so far it seems to be fast, so I am happy with it.
I'm not born a "Collection hacker", nor have any Collection diploma. I'm just driven by curiosity, and in this case, no need to understand the code, reviewing it with the symptom you discovered in mind is enough. It seems to me that you put unnecessary mental barriers ;) Oh but maybe you're not so smart, you're just a casual VM hacker, and succeeded to carry Fuel project just by luck ;) I just don't believe you Nicolas
(values at: hash) at: newIndex put: key
Can you replace key with value and retry the tests ?
Yes, that works. Thanks!
Now I noticed that SmallIntegers storing is really slow
   numbers := OrderedCollection new.    numbers add: 1.    numbers addAll: (1 to: 1 << 29 by: 1 << 14) asArray.    numbers addAll: ((1 to: 1 << 29 by: 1 << 14) asArray collect: [:each | each negated] ).
   dict := LargeIdentityDictionary new.    [numbers do: [:each |
       dict at: each put: dict size + 1.       ].    ] timeToRun     -> 12657
whereas with IdentityDictionary it is 37. I guess it could be related to #identityHash or #basicIdentityHash. I tried in Squeak 4.3 and it is also also there. I will try to take a look into it during the next week.
Thanks in advance
Nicolas
Thanks for any idea.
On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected." I do not get the following. Indeed pointTo: looks like instVarsInclude: now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
On Sat, 17 Dec 2011, Nicolas Cellier wrote:
2011/12/17 Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com>:
2011/12/17 Mariano Martinez Peck <marianopeck@gmail.com>:
Hi Levente. I take a deeper look to see why LargeIdentityDictionary is not working as expected for us.
The way we are putting objects in the Dict is always this way:
registerIndexesOn: aDictionary
   self objects do: [ :instance | aDictionary at: instance put: aDictionary size + 1 ].
So?keys are the objects of the graphs and the values are the internal position in the serialization. However, when I run a serialization it looks like if the follow happens that when we are doing:
encodeReferenceTo: anObject
   indexCluster       serialize: (objectsIndexes at: anObject)       on: stream
(objectsIndexes at: anObject) == anObject  -> true
so (objectsIndexes at: anObject) is answering "self" rather than the number (which was the dict size + 1 at the serialization moment).
Something interesting is that most tests seem to pass and the problem is with benchmarks (where graphs are much bigger), so maybe it could be something related to that. For example, the following benchmark for bitmaps is failing:
        numbers := OrderedCollection new.    bitmaps := OrderedCollection new.    numbers addAll: ( 1 << 30 to:( ( 1 << 30) + 10000) ) asArray.    numbers do: [:each | bitmaps add: (Bitmap with: each with: each + 1) ].    ^ bitmaps
it happens the mentioned problem when trying to serialize the collection 'bitmaps'.
I tried to reproduce it outside Fuel and I think I succeeded (not sure). The following does work with IdentityDictionary but not with LargeIdentityDictionary. Basically I am simulating the way we use this dict in Fuel:
testLargeIdentityDictionary
   | numbers bitmaps dict |
"Create some bitmaps"
   numbers := OrderedCollection new.    bitmaps := OrderedCollection new.    numbers addAll: ( 1 << 30 to:( ( 1 << 30) + 10000) ) asArray.    numbers do: [:each | bitmaps add: (Bitmap with: each with: each + 1) ].
"Put them in a dictionary using dict as as key" Â Â Â dict := LargeIdentityDictionary new. Â Â Â bitmaps do: [:each | Â Â Â Â Â Â Â dict at: each put: dict size + 1. Â Â Â Â Â Â ].
"Check they are correct" Â Â Â bitmaps doWithIndex: [:each :index | self assert: index == (dict at: each)]
Of course that test works with IdentityDictionary.
Can't you debug it ?
It took 2 minutes to find this sentence at line 19 of LargeDictionary>>at:put:
(values at: hash) at: newIndex put: key
Can you replace key with value and retry the tests ?
Nice find, thanks. :) Levente
Nicolas
Thanks for any idea.
On Sat, Dec 17, 2011 at 1:50 PM, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected." I do not get the following. Indeed pointTo: looks like instVarsInclude: now I do not understand the rest of your paragraph.
Stef
-- Mariano http://marianopeck.wordpress.com
On Sat, 17 Dec 2011, Stéphane Ducasse wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected." I do not get the following. Indeed pointTo: looks like instVarsInclude: now I do not understand the rest of your paragraph.
#pointsTo: should answer true if the receiver has a pointer to the argument. Every object (except for SmallIntegers and instances of compact classes) holds a pointer to its class in the header. Since the primitive only checks the slots, it will not always return true if the argument is the object's class. This breaks pointer finding/tracing tools, that's why it was changed in Squeak. See how #instVarsInclude: and #pointsTo: is implemented there. Levente
Stef
Thanks I will have a look On Dec 18, 2011, at 12:43 AM, Levente Uzonyi wrote:
On Sat, 17 Dec 2011, Stéphane Ducasse wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added. I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected." I do not get the following. Indeed pointTo: looks like instVarsInclude: now I do not understand the rest of your paragraph.
#pointsTo: should answer true if the receiver has a pointer to the argument. Every object (except for SmallIntegers and instances of compact classes) holds a pointer to its class in the header. Since the primitive only checks the slots, it will not always return true if the argument is the object's class. This breaks pointer finding/tracing tools, that's why it was changed in Squeak. See how #instVarsInclude: and #pointsTo: is implemented there.
Levente
Stef
2011/12/18 Levente Uzonyi <leves@elte.hu>:
On Sat, 17 Dec 2011, Stéphane Ducasse wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added.
Ah yes, but in this case LargeIdentitySet/Dictionary should use #instVarInclude: rather than #pointsTo; otherwise here is a bug (LargeIdentitySet with: Array identityHash \\ 4096) includes: Array Nicolas
I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected."
I do not get the following. Indeed pointTo: looks like instVarsInclude: now I do not understand the rest of your paragraph.
#pointsTo: should answer true if the receiver has a pointer to the argument. Every object (except for SmallIntegers and instances of compact classes) holds a pointer to its class in the header. Since the primitive only checks the slots, it will not always return true if the argument is the object's class. This breaks pointer finding/tracing tools, that's why it was changed in Squeak. See how #instVarsInclude: and #pointsTo: is implemented there.
Levente
Stef
2011/12/18 Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com>:
2011/12/18 Levente Uzonyi <leves@elte.hu>:
On Sat, 17 Dec 2011, Stéphane Ducasse wrote:
On Dec 16, 2011, at 3:28 PM, Levente Uzonyi wrote:
Cool. One more thing: in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If this was also added to Pharo, then the #pointsTo: sends should be changed to #instVarsInclude:, otherwise Array can be reported as included even if it wasn't added.
Ah yes, but in this case LargeIdentitySet/Dictionary should use #instVarInclude: rather than #pointsTo; otherwise here is a bug
(LargeIdentitySet with: Array identityHash \\ 4096) includes: Array
Nicolas
Oops, that's just what you were telling, apologize...
I'll upload my LargeIdentityDictionary implementation to the same place this evening, since it's still 2-3 factor faster than other solutionts and there seem to be demand for it.
Levente
"in Squeak the method using primitive 132 directly was renamed to #instVarsInclude:, so now #pointsTo: works as expected."
I do not get the following. Indeed pointTo: looks like instVarsInclude: now I do not understand the rest of your paragraph.
#pointsTo: should answer true if the receiver has a pointer to the argument. Every object (except for SmallIntegers and instances of compact classes) holds a pointer to its class in the header. Since the primitive only checks the slots, it will not always return true if the argument is the object's class. This breaks pointer finding/tracing tools, that's why it was changed in Squeak. See how #instVarsInclude: and #pointsTo: is implemented there.
Levente
Stef
I would love to have that! Stef
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
participants (6)
-
Benoit St-Jean -
Henrik Sperre Johansen -
Levente Uzonyi -
Mariano Martinez Peck -
Nicolas Cellier -
Stéphane Ducasse