<br><br><div class="gmail_quote">On Sat, May 5, 2012 at 1:58 AM, Levente Uzonyi <span dir="ltr"><<a href="mailto:leves@elte.hu" target="_blank">leves@elte.hu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>On Fri, 4 May 2012, Igor Stasenko wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Sorry, its hard to devise what are primitive we're talking about?<br>
<br>
if i understood correctly you need a primitive which answers an index<br>
of element in<br>
array, if found, and nil or 0 otherwise?<br>
</blockquote>
<br>
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":<br>
- return the index of the first slot (including indexable and non indexable ones) which points to the argument<br>
- otherwise return -1 if the class of the receiver is the argument<br>
- otherwise return 0<br>
It is trivial to rewrite the current #pointsTo: primitive in the interpreter this way, not sure about Cog.<br></blockquote><div><br></div><div>Trivial since Cog can and does use Interpreter primitives (except that they live in a separate hierarchy, InterpreterPrimitives, STackInterpreterPrimitives, CoInterpreterPrimitives).</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Btw I'm not sure if it's worth using the same primitive for both purposes. I'd probably separate the two if possible.<br>
<br>
Also, to make the linear search primitive more general, I'd add two more optional arguments: one for startIndex and one for endIndex.<br>
<br>
<br>
Levente<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
On 4 May 2012 21:07, Eliot Miranda <<a href="mailto:eliot.miranda@gmail.com" target="_blank">eliot.miranda@gmail.com</a>> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
<br>
<br>
On Thu, Apr 26, 2012 at 8:19 AM, Mariano Martinez Peck <<a href="mailto:marianopeck@gmail.com" target="_blank">marianopeck@gmail.com</a>> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
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?<br>
</blockquote>
<br>
<br>
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.<br>
I'll rewrite both LargeIdentitySet and LargeIdentityDictionary when the primitive is ready.<br>
</blockquote>
<br>
<br>
Thanks Levente. So we should wait Eliot.<br>
I will ping again in a couple of weeks/months ;)<br>
<br>
</blockquote>
<br>
Ping. So I did it :)<br>
Eliot if you tell us what it is needed maybe I can push Esteban or Igor (or me?) to do it ;)<br>
</blockquote>
<br>
<br>
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.<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
<br>
Thanks!<br>
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
<br>
<br>
Levente<br>
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Thanks!<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
Levente<br>
<br>
<br>
thanks<br>
<br>
On Fri, Dec 16, 2011 at 3:28 PM, Levente Uzonyi <<a href="mailto:leves@elte.hu" target="_blank">leves@elte.hu</a>> wrote:<br>
<br>
On Fri, 16 Dec 2011, Henrik Sperre Johansen wrote:<br>
<br>
On 16.12.2011 03:26, Levente Uzonyi wrote:<br>
<br>
<br>
How about my numbers? :)<br>
<br>
"Preallocate objects, so we won't count gc time."<br>
n := 1000000.<br>
objects := Array new: n streamContents: [ :stream |<br>
n timesRepeat: [ stream nextPut: Object new ] ].<br>
<br>
set := IdentitySet new: n.<br>
Smalltalk garbageCollect.<br>
[1 to: n do: [ :i | set add: (objects at: i) ] ] timeToRun. "4949"<br>
<br>
set := LargeIdentitySet new.<br>
Smalltalk garbageCollect.<br>
[1 to: n do: [ :i | set add: (objects at: i) ] ] timeToRun. "331"<br>
<br>
set := (PluggableSet new: n)<br>
hashBlock: [ :object | object identityHash * 4096 + object class<br>
identityHash * 64 ]; "Change this to #basicIdentityHash in Pharo"<br>
equalBlock: [ :a :b | a == b ];<br>
yourself.<br>
Smalltalk garbageCollect.<br>
[1 to: n do: [ :i | set add: (objects at: i) ] ] timeToRun. "5511"<br>
<br>
<br>
I also have a LargeIdentityDictionary, which is relatively fast, but not<br>
as fast as LargeIdentitySet, because (for some unknown reason) we don't<br>
have a primitive that could support it. If we had a primitive like<br>
primitive 132 which would return the index of the element if found or 0 if<br>
not, then we could have a really fast LargeIdentityDictionary.<br>
<br>
<br>
Levente<br>
<br>
Hehe yes, if writing a version fully exploiting the limited range, that's<br>
probably the approach I would go for as well.<br>
(IAssuming it's the version at <a href="http://leves.web.elte.hu/**" target="_blank">http://leves.web.elte.hu/**</a><br>
squeak/LargeIdentitySet.st<<a href="http://leves.web.elte.hu/squeak/LargeIdentitySet.st" target="_blank">htt<u></u>p://leves.web.elte.hu/squeak/<u></u>LargeIdentitySet.st</a>><br>
)<br>
<br>
Mariano commented in the version at <a href="http://www.squeaksource.com/**" target="_blank">http://www.squeaksource.com/**</a><br>
FuelExperiments <<a href="http://www.squeaksource.com/FuelExperiments" target="_blank">http://www.squeaksource.com/<u></u>FuelExperiments</a>> that it's<br>
slow for them, which I guess is due to not adopting #identityHash calls to<br>
#basicIdentityHash calls for Pharo:<br>
((0 to: 4095) collect: [:each | each << 22 \\ 4096 ]) asSet size -> 1<br>
So it basically uses 1 bucket instead of 4096... Whoops. :)<br>
<br>
Uploaded a new version to the MC repository which is adapted for Pharo,<br>
on the same machine my numbers were taken from, it does the same test as I<br>
used above in 871 ms. (181 with preallocation).<br>
<br>
<br>
Cool. One more thing: in Squeak the method using primitive 132 directly<br>
was renamed to #instVarsInclude:, so now #pointsTo: works as expected. If<br>
this was also added to Pharo, then the #pointsTo: sends should be changed<br>
to #instVarsInclude:, otherwise Array can be reported as included even if<br>
it wasn't added.<br>
I'll upload my LargeIdentityDictionary implementation to the same place<br>
this evening, since it's still 2-3 factor faster than other solutionts and<br>
there seem to be demand for it.<br>
<br>
<br>
Levente<br>
<br>
<br>
Cheers,<br>
Henry<br>
<br>
<br>
<br>
<br>
<br>
<br>
--<br>
Mariano<br>
<a href="http://marianopeck.wordpress.com" target="_blank">http://marianopeck.wordpress.<u></u>com</a><br>
<br>
<br>
<br>
<br>
<br>
--<br>
Mariano<br>
<a href="http://marianopeck.wordpress.com" target="_blank">http://marianopeck.wordpress.<u></u>com</a><br>
<br>
<br>
</blockquote></blockquote>
<br>
<br>
<br>
--<br>
Mariano<br>
<a href="http://marianopeck.wordpress.com" target="_blank">http://marianopeck.wordpress.<u></u>com</a><br>
<br>
</blockquote>
<br>
<br>
<br>
--<br>
Mariano<br>
<a href="http://marianopeck.wordpress.com" target="_blank">http://marianopeck.wordpress.<u></u>com</a><br>
<br>
<br>
</blockquote>
<br>
<br>
<br>
--<br>
best,<br>
Eliot<br>
<br>
<br>
</blockquote>
<br>
<br>
<br>
-- <br>
Best regards,<br>
Igor Stasenko.<br>
</blockquote>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br>best,<div>Eliot</div><br>