Do we have the new primitive?? [WAS] Re: [Pharo-project] IdentitySet but using #hash rather than #identityHash ?
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.sthttp://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.
Hi Eliot/Levente. What is the status of this? Do we have already the new primitive? If true, how can we adapt LargeIdentitySet to use such new primitive?
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.sthttp://leves.web.elte.hu/squeak/LargeIdentitySet.st
)
Mariano commented in the version at http://www.squeaksource.com/** FuelExperiments <http://www.squeaksource.com/**FuelExperimentshttp://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
On Sat, 25 Feb 2012, Mariano Martinez Peck wrote:
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.
My proposals are still on the way. :)
Hi Eliot/Levente. What is the status of this? Do we have already the new primitive? If true, how can we adapt LargeIdentitySet to use such new primitive?
AFAIK the new primitive is not implemented yet. Adding the primitive to the interpreter VM is very easy, but it seems to be a lot more complicated (to me) to add it to Cog, because the receiver can be a MethodContext which needs special handling. I'll rewrite both LargeIdentitySet and LargeIdentityDictionary when the primitive is ready.
Levente
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.sthttp://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 Mon, Feb 27, 2012 at 3:16 PM, Levente Uzonyi leves@elte.hu wrote:
On Sat, 25 Feb 2012, Mariano Martinez Peck wrote:
All I can say is that I am impressed by the numbers it isreally 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 fordictionary? can we contact Eliot to provide such a primitive?
As promised, I uploaded my LargeIdentityDictionary implementation to http://leves.web.elte.hu/**squeak/**LargeIdentityDictionary.sthttp://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.
My proposals are still on the way. :)
Hi Eliot/Levente. What is the status of this? Do we have already the new primitive? If true, how can we adapt LargeIdentitySet to use such new primitive?
AFAIK the new primitive is not implemented yet. Adding the primitive to the interpreter VM is very easy, but it seems to be a lot more complicated (to me) to add it to Cog, because the receiver can be a MethodContext which needs special handling. I'll rewrite both LargeIdentitySet and LargeIdentityDictionary when the primitive is ready.
Thanks Levente. So we should wait Eliot. I will ping again in a couple of weeks/months ;)
Levente
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 + objectclass 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 relativelyfast, 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/**FuelExperimentshttp://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 http://marianopeck.wordpress.com
Hi Eliot/Levente. What is the status of this? Do we have already the new primitive? If true, how can we adapt LargeIdentitySet to use such new primitive?
AFAIK the new primitive is not implemented yet. Adding the primitive to the interpreter VM is very easy, but it seems to be a lot more complicated (to me) to add it to Cog, because the receiver can be a MethodContext which needs special handling. I'll rewrite both LargeIdentitySet and LargeIdentityDictionary when the primitive is ready.
Thanks Levente. So we should wait Eliot. I will ping again in a couple of weeks/months ;)
Ping. So I did it :) Eliot if you tell us what it is needed maybe I can push Esteban or Igor (or me?) to do it ;)
Thanks!
Levente
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 + objectclass 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 relativelyfast, 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.sthttp://leves.web.elte.hu/squeak/LargeIdentitySet.st
)
Mariano commented in the version at http://www.squeaksource.com/** FuelExperiments <http://www.squeaksource.com/**FuelExperimentshttp://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 http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
On Thu, Apr 26, 2012 at 8:19 AM, Mariano Martinez Peck < marianopeck@gmail.com> wrote:
Hi Eliot/Levente. What is the status of this? Do we have already the new primitive? If true, how can we adapt LargeIdentitySet to use such new primitive?
AFAIK the new primitive is not implemented yet. Adding the primitive to the interpreter VM is very easy, but it seems to be a lot more complicated (to me) to add it to Cog, because the receiver can be a MethodContext which needs special handling. I'll rewrite both LargeIdentitySet and LargeIdentityDictionary when the primitive is ready.
Thanks Levente. So we should wait Eliot. I will ping again in a couple of weeks/months ;)
Ping. So I did it :) Eliot if you tell us what it is needed maybe I can push Esteban or Igor (or me?) to do it ;)
Some form of accurate spec. e.g. a simulation in Smalltalk, along with a specification of the types. I'm not happy about the receiver being a MethodContext because that means the primitive has to check argument types. A primitive can assume the type of the receiver because the primitive can be put on a specific class in the hierarchy. Hence aBehavior adoptInstance: anObject is much better than anObject changeClassTo: aClass, because the former can know that the receiver is a valid behavior, and simply check that the argument is a suitable instance of the receiver, whereas the latter has to check both that aClass is a valid behavior (walking its hierarchy? checking it has a valid methodDictionary, etc, etc) /and/ that the receiver is a suitable instance of the argument. So if possible specify it as one or two primitives on LargeIdentitySet & LargeIdentityDictionary.
Thanks!
Levente
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 + objectclass 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 relativelyfast, 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.sthttp://leves.web.elte.hu/squeak/LargeIdentitySet.st
)
Mariano commented in the version at http://www.squeaksource.com/** FuelExperiments <http://www.squeaksource.com/**FuelExperimentshttp://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 http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
Sorry, its hard to devise what are primitive we're talking about?
if i understood correctly you need a primitive which answers an index of element in array, if found, and nil or 0 otherwise?
On 4 May 2012 21:07, Eliot Miranda eliot.miranda@gmail.com wrote:
On Thu, Apr 26, 2012 at 8:19 AM, Mariano Martinez Peck marianopeck@gmail.com wrote:
Hi Eliot/Levente. What is the status of this? Do we have already the new primitive? If true, how can we adapt LargeIdentitySet to use such new primitive?
AFAIK the new primitive is not implemented yet. Adding the primitive to the interpreter VM is very easy, but it seems to be a lot more complicated (to me) to add it to Cog, because the receiver can be a MethodContext which needs special handling. I'll rewrite both LargeIdentitySet and LargeIdentityDictionary when the primitive is ready.
Thanks Levente. So we should wait Eliot. I will ping again in a couple of weeks/months ;)
Ping. So I did it :) Eliot if you tell us what it is needed maybe I can push Esteban or Igor (or me?) to do it ;)
Some form of accurate spec. e.g. a simulation in Smalltalk, along with a specification of the types. I'm not happy about the receiver being a MethodContext because that means the primitive has to check argument types. A primitive can assume the type of the receiver because the primitive can be put on a specific class in the hierarchy. Hence aBehavior adoptInstance: anObject is much better than anObject changeClassTo: aClass, because the former can know that the receiver is a valid behavior, and simply check that the argument is a suitable instance of the receiver, whereas the latter has to check both that aClass is a valid behavior (walking its hierarchy? checking it has a valid methodDictionary, etc, etc) /and/ that the receiver is a suitable instance of the argument. So if possible specify it as one or two primitives on LargeIdentitySet & LargeIdentityDictionary.
Thanks!
Levente
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.sthttp://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
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
-- best, Eliot
On Fri, 4 May 2012, Igor Stasenko wrote:
Sorry, its hard to devise what are primitive we're talking about?
if i understood correctly you need a primitive which answers an index of element in array, if found, and nil or 0 otherwise?
This is what a primitive (basically a linear search) should do if the only goal is to support LargeIdentityDictionary (and LargeIdentitySet). But there were ideas to use the same primitive for pointer tracing, which adds the following "extensions": - return the index of the first slot (including indexable and non indexable ones) which points to the argument - otherwise return -1 if the class of the receiver is the argument - otherwise return 0 It is trivial to rewrite the current #pointsTo: primitive in the interpreter this way, not sure about Cog.
Btw I'm not sure if it's worth using the same primitive for both purposes. I'd probably separate the two if possible.
Also, to make the linear search primitive more general, I'd add two more optional arguments: one for startIndex and one for endIndex.
Levente
On 4 May 2012 21:07, Eliot Miranda eliot.miranda@gmail.com wrote:
On Thu, Apr 26, 2012 at 8:19 AM, Mariano Martinez Peck marianopeck@gmail.com wrote:
Hi Eliot/Levente. What is the status of this? Do we have already the new primitive? If true, how can we adapt LargeIdentitySet to use such new primitive?
AFAIK the new primitive is not implemented yet. Adding the primitive to the interpreter VM is very easy, but it seems to be a lot more complicated (to me) to add it to Cog, because the receiver can be a MethodContext which needs special handling. I'll rewrite both LargeIdentitySet and LargeIdentityDictionary when the primitive is ready.
Thanks Levente. So we should wait Eliot. I will ping again in a couple of weeks/months ;)
Ping. So I did it :) Eliot if you tell us what it is needed maybe I can push Esteban or Igor (or me?) to do it ;)
Some form of accurate spec. e.g. a simulation in Smalltalk, along with a specification of the types. I'm not happy about the receiver being a MethodContext because that means the primitive has to check argument types. A primitive can assume the type of the receiver because the primitive can be put on a specific class in the hierarchy. Hence aBehavior adoptInstance: anObject is much better than anObject changeClassTo: aClass, because the former can know that the receiver is a valid behavior, and simply check that the argument is a suitable instance of the receiver, whereas the latter has to check both that aClass is a valid behavior (walking its hierarchy? checking it has a valid methodDictionary, etc, etc) /and/ that the receiver is a suitable instance of the argument. So if possible specify it as one or two primitives on LargeIdentitySet & LargeIdentityDictionary.
Thanks!
Levente
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.sthttp://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
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
-- best, Eliot
-- Best regards, Igor Stasenko.
On Sat, May 5, 2012 at 1:58 AM, Levente Uzonyi leves@elte.hu wrote:
On Fri, 4 May 2012, Igor Stasenko wrote:
Sorry, its hard to devise what are primitive we're talking about?
if i understood correctly you need a primitive which answers an index of element in array, if found, and nil or 0 otherwise?
This is what a primitive (basically a linear search) should do if the only goal is to support LargeIdentityDictionary (and LargeIdentitySet). But there were ideas to use the same primitive for pointer tracing, which adds the following "extensions":
- return the index of the first slot (including indexable and non
indexable ones) which points to the argument
- otherwise return -1 if the class of the receiver is the argument
- otherwise return 0
It is trivial to rewrite the current #pointsTo: primitive in the interpreter this way, not sure about Cog.
Trivial since Cog can and does use Interpreter primitives (except that they live in a separate hierarchy, InterpreterPrimitives, STackInterpreterPrimitives, CoInterpreterPrimitives).
Btw I'm not sure if it's worth using the same primitive for both purposes. I'd probably separate the two if possible.
Also, to make the linear search primitive more general, I'd add two more optional arguments: one for startIndex and one for endIndex.
Levente
On 4 May 2012 21:07, Eliot Miranda eliot.miranda@gmail.com wrote:
On Thu, Apr 26, 2012 at 8:19 AM, Mariano Martinez Peck < marianopeck@gmail.com> wrote:
> Hi Eliot/Levente. What is the status of this? Do we have already the > new primitive? If true, how can we adapt LargeIdentitySet to use such new > primitive? >
AFAIK the new primitive is not implemented yet. Adding the primitive to the interpreter VM is very easy, but it seems to be a lot more complicated (to me) to add it to Cog, because the receiver can be a MethodContext which needs special handling. I'll rewrite both LargeIdentitySet and LargeIdentityDictionary when the primitive is ready.
Thanks Levente. So we should wait Eliot. I will ping again in a couple of weeks/months ;)
Ping. So I did it :) Eliot if you tell us what it is needed maybe I can push Esteban or Igor (or me?) to do it ;)
Some form of accurate spec. e.g. a simulation in Smalltalk, along with a specification of the types. I'm not happy about the receiver being a MethodContext because that means the primitive has to check argument types. A primitive can assume the type of the receiver because the primitive can be put on a specific class in the hierarchy. Hence aBehavior adoptInstance: anObject is much better than anObject changeClassTo: aClass, because the former can know that the receiver is a valid behavior, and simply check that the argument is a suitable instance of the receiver, whereas the latter has to check both that aClass is a valid behavior (walking its hierarchy? checking it has a valid methodDictionary, etc, etc) /and/ that the receiver is a suitable instance of the argument. So if possible specify it as one or two primitives on LargeIdentitySet & LargeIdentityDictionary.
Thanks!
Levente
> 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.sthttp://leves.web.elte.hu/squeak/LargeIdentitySet.st > > > ) > > Mariano commented in the version at http://www.squeaksource.com/** > FuelExperiments <http://www.squeaksource.com/**FuelExperimentshttp://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.**comhttp://marianopeck.wordpress.com > > > > > > -- > Mariano > http://marianopeck.wordpress.**comhttp://marianopeck.wordpress.com > > >
-- Mariano http://marianopeck.wordpress.**com http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.**com http://marianopeck.wordpress.com
-- best, Eliot
-- Best regards, Igor Stasenko.
On Sat, May 5, 2012 at 1:58 AM, Levente Uzonyi leves@elte.hu wrote:
On Fri, 4 May 2012, Igor Stasenko wrote:
Sorry, its hard to devise what are primitive we're talking about?
if i understood correctly you need a primitive which answers an index of element in array, if found, and nil or 0 otherwise?
This is what a primitive (basically a linear search) should do if the only goal is to support LargeIdentityDictionary (and LargeIdentitySet). But there were ideas to use the same primitive for pointer tracing, which adds the following "extensions":
- return the index of the first slot (including indexable and non
indexable ones) which points to the argument
- otherwise return -1 if the class of the receiver is the argument
- otherwise return 0
It is trivial to rewrite the current #pointsTo: primitive in the interpreter this way, not sure about Cog.
Btw I'm not sure if it's worth using the same primitive for both purposes. I'd probably separate the two if possible.
Also, to make the linear search primitive more general, I'd add two more optional arguments: one for startIndex and one for endIndex.
The startIndex is useful. Is the endIndex?
I've attached an Interpreter primitive that doesn't yet support the index arguments. Turns out Cog is much more complex because of context-to-stack mapping; searching through a stack frame is difficult because of mapping back to the correct index in the context object. But that can wait.
primitiveObjectIndexOf "Search for a reference to the argument in the receiver. - answer the index of the first slot (including indexable and non indexable ones) which points to the argument - otherwise return -1 if the class of the receiver is the argument - otherwise return 0 This primitive is assumed to be fast (see e.g. MethodDictionary>>includesKey:) so make it so." | rcvr thang lastField | thang := self stackTop. rcvr := self stackValue: 1. (self isIntegerObject: rcvr) ifTrue: [^self pop: 2 thenPushInteger: (thang = (self splObj: ClassInteger) ifTrue: [-1] ifFalse: [0])].
lastField := self lastPointerOf: rcvr. BaseHeaderSize to: lastField by: BytesPerWord do: [:i | (self longAt: rcvr + i) = thang ifTrue: [^self pop: 2 thenPushInteger: i / BytesPerWord]]. self pop: 2 thenPushInteger: ((self fetchClassOfNonInt: rcvr) = thang ifTrue: [-1] ifFalse: [0])
Levente
On 4 May 2012 21:07, Eliot Miranda eliot.miranda@gmail.com wrote:
On Thu, Apr 26, 2012 at 8:19 AM, Mariano Martinez Peck < marianopeck@gmail.com> wrote:
> Hi Eliot/Levente. What is the status of this? Do we have already the > new primitive? If true, how can we adapt LargeIdentitySet to use such new > primitive? >
AFAIK the new primitive is not implemented yet. Adding the primitive to the interpreter VM is very easy, but it seems to be a lot more complicated (to me) to add it to Cog, because the receiver can be a MethodContext which needs special handling. I'll rewrite both LargeIdentitySet and LargeIdentityDictionary when the primitive is ready.
Thanks Levente. So we should wait Eliot. I will ping again in a couple of weeks/months ;)
Ping. So I did it :) Eliot if you tell us what it is needed maybe I can push Esteban or Igor (or me?) to do it ;)
Some form of accurate spec. e.g. a simulation in Smalltalk, along with a specification of the types. I'm not happy about the receiver being a MethodContext because that means the primitive has to check argument types. A primitive can assume the type of the receiver because the primitive can be put on a specific class in the hierarchy. Hence aBehavior adoptInstance: anObject is much better than anObject changeClassTo: aClass, because the former can know that the receiver is a valid behavior, and simply check that the argument is a suitable instance of the receiver, whereas the latter has to check both that aClass is a valid behavior (walking its hierarchy? checking it has a valid methodDictionary, etc, etc) /and/ that the receiver is a suitable instance of the argument. So if possible specify it as one or two primitives on LargeIdentitySet & LargeIdentityDictionary.
Thanks!
Levente
> 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.sthttp://leves.web.elte.hu/squeak/LargeIdentitySet.st > > > ) > > Mariano commented in the version at http://www.squeaksource.com/** > FuelExperiments <http://www.squeaksource.com/**FuelExperimentshttp://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.**comhttp://marianopeck.wordpress.com > > > > > > -- > Mariano > http://marianopeck.wordpress.**comhttp://marianopeck.wordpress.com > > >
-- Mariano http://marianopeck.wordpress.**com http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.**com http://marianopeck.wordpress.com
-- best, Eliot
-- Best regards, Igor Stasenko.
(neither alpine, nor imp/horde can quote your mail due to the empty first attachment added by gmail, sorry)
Thanks Eliot for looking into this issue.
Yes, endIndex is very useful. For example LargeIdentityDictionary uses dynamic arrays to store the keys and values. The first element is stored at the first slot and we know the index of the last slot where an element is stored. The slots after that index conatain nil. The endIndex parameter makes it possible to avoid searching those nils if the element is not in the dictionary and simplifies the code, because searching for nil doesn't need special handling.
I'm not sure if it's okay to use #longAt: in the loop, because the receiver can be an object which stores bytes (e.g.: ByteString/ByteArray) and I'd expect that the primivite also works correctly in that case. This would also make it possible to replace the existing linear search primitive for strings with this primitive.
Levente
On Sat, May 5, 2012 at 1:46 PM, Levente Uzonyi leves@elte.hu wrote:
(neither alpine, nor imp/horde can quote your mail due to the empty first attachment added by gmail, sorry)
Thanks Eliot for looking into this issue.
Yes, endIndex is very useful. For example LargeIdentityDictionary uses dynamic arrays to store the keys and values. The first element is stored at the first slot and we know the index of the last slot where an element is stored. The slots after that index conatain nil. The endIndex parameter makes it possible to avoid searching those nils if the element is not in the dictionary and simplifies the code, because searching for nil doesn't need special handling.
I'm not sure if it's okay to use #longAt: in the loop, because the receiver can be an object which stores bytes (e.g.: ByteString/ByteArray) and I'd expect that the primivite also works correctly in that case. This would also make it possible to replace the existing linear search primitive for strings with this primitive.
Is it OK if the primitive fails for CompiledMethod and/or MethodContext or are you looking for good performance for these too, e.g. with the PointerFinder?
Levente
On Sat, 5 May 2012, Eliot Miranda wrote:
Is it OK if the primitive fails for CompiledMethod and/or MethodContext
or are you looking for good performance for these too, e.g. with the PointerFinder?
I think it's ok if it fails for those classes for now, we can implement that part in the image. Later when someone has time and will can extend the primitive to support these receivers.
Levente
On Tue, Feb 28, 2012 at 7:52 PM, Mariano Martinez Peck < marianopeck@gmail.com> wrote:
On Mon, Feb 27, 2012 at 3:16 PM, Levente Uzonyi leves@elte.hu wrote:
On Sat, 25 Feb 2012, Mariano Martinez Peck wrote:
All I can say is that I am impressed by the numbers it isreally 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 fordictionary? 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.
My proposals are still on the way. :)
Hi Eliot/Levente. What is the status of this? Do we have already the new primitive? If true, how can we adapt LargeIdentitySet to use such new primitive?
AFAIK the new primitive is not implemented yet. Adding the primitive to the interpreter VM is very easy, but it seems to be a lot more complicated (to me) to add it to Cog, because the receiver can be a MethodContext which needs special handling. I'll rewrite both LargeIdentitySet and LargeIdentityDictionary when the primitive is ready.
Thanks Levente. So we should wait Eliot. I will ping again in a couple of weeks/months ;)
I am reviving a very old thread. Levente, as you know, we are using a variation of your LargeIdentitySet and LargeIdentityDictionary for Fuel. Considering Spur's new #identityHash, had you have the chance to try/think if these large collection classes is still worth? What it seems clear is that with Spur we could simply replace:
ProtoObject >> largeIdentityHash
<primitive: 75>
With:
ProtoObject >> largeIdentityHash
^ self basicIdentityHash
Right?
But I still wonder about the collection classes itself.
Thoughts?
Levente
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 + objectclass 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 relativelyfast, 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.sthttp://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
-- Mariano http://marianopeck.wordpress.com
vm-dev@lists.squeakfoundation.org
-
Eliot Miranda -
Igor Stasenko -
Levente Uzonyi -
Mariano Martinez Peck