<div dir="ltr"><br><br><div class="gmail_quote">On Fri, Aug 8, 2008 at 6:09 PM, Igor Stasenko <span dir="ltr"><<a href="mailto:siguctua@gmail.com">siguctua@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div><div></div><div class="Wj3C7c">2008/8/9 Eliot Miranda <<a href="mailto:eliot.miranda@gmail.com">eliot.miranda@gmail.com</a>>:<br>
><br>
><br>
> On Fri, Aug 8, 2008 at 5:46 PM, Igor Stasenko <<a href="mailto:siguctua@gmail.com">siguctua@gmail.com</a>> wrote:<br>
>><br>
>> 2008/8/9 Eliot Miranda <<a href="mailto:eliot.miranda@gmail.com">eliot.miranda@gmail.com</a>>:<br>
>> ><br>
>> ><br>
>> > On Fri, Aug 8, 2008 at 3:53 PM, Igor Stasenko <<a href="mailto:siguctua@gmail.com">siguctua@gmail.com</a>><br>
>> > wrote:<br>
>> >><br>
>> >> Sets which not allowing contain nil as element is a point of<br>
>> >> inconvenience.<br>
>> >><br>
>> >> There are two ways how get around that:<br>
>> >> - initialize an array which contains set elements with unique object ~~<br>
>> >> nil.<br>
>> >> and fix methods which testing for an empty slots to compare against<br>
>> >> this object, not nil.<br>
>> >> This can cause a slowdown during rehashing, because VM initially<br>
>> >> creating arrays filled with nils, while we need to fill them with<br>
>> >> another object.<br>
>> >> There is also a problem with preserving it 'uniqueness' by not giving<br>
>> >> this object outside a set.<br>
>> >><br>
>> >> - add an instVar 'containsNil'<br>
>> >> then when set receiving 'add: nil' , it simply sets this flag to true.<br>
>> >> modify #collect: , #do: , #remove: to be aware of flag value.<br>
>> >><br>
>> >> I find the second way is more appropriate. While it costs additional<br>
>> >> memory per Set/IdentitySet instance, it costs almost nothing in speed.<br>
>> >><br>
>> >> What do you think about supporting Sets to contain nils in general,<br>
>> >> and about methods how to achieve that?<br>
>> ><br>
>> > Here's a third approach (a variation on your 2nd approach). Have an<br>
>> > instVar<br>
>> > 'includesSelf' and fill the array with the Set itself. So add a new<br>
>> > primitive new:fillWith: (primitiveNewWithArgAndFillValue?) and use this<br>
>> > to<br>
>> > create the empty array filled with the Set itself. Check for adding the<br>
>> > set<br>
>> > itself, and itself being the null entry. The advantage over the flag<br>
>> > for<br>
>> > nil approach is that you kill two birds with one stone.<br>
>> > 1. You need a unique value anyway, and the Set can nicely be its own<br>
>> > unique<br>
>> > value<br>
>> > 2. recursive collections are a problem to print and with the explicit<br>
>> > flag<br>
>> > this becomes much easier to deal with.<br>
>><br>
>> In math domain, any set includes itself , not as element of course,<br>
>> but as subset :)<br>
>> And i don't see how this is better comparing to having 'containsNil' ivar?<br>
>> You still have to test this flag in each method which deals with<br>
>> elements , so be it containsFoo or containsBar - no real difference.<br>
><br>
> One difference is the use of self for the unique object instead of another.<br>
> Another difference is that recursive sets no longer fail to print, inspect,<br>
> etc.<br>
> I think those are real differences.<br>
><br>
<br>
</div></div>Valid point.<br>
<br>
As a bytecode proofy, can you tell how much different a bytecode will be for:</blockquote><div><br></div><div>what's a proofy? ;)</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
obj == nil<br>
versus<br>
obj == self<br>
versus<br>
obj isNil<br></blockquote><div><br></div><div>Depends. In an Interpreter obj == self likely to be slightly faster than obj == nil since nil must be fetched either form the specialObjectsArray (if bytecode set has pushNl, as it does) or from the method's literal frame. In a JIT they're liely the same because self is a read through the frame pointer and nil is a constant embedded in the instruction stream. These are likely to be of similar cost.</div>
<div><br></div><div>obj isNil will either be the same cost as == nil or slower depending on whether the bytecode compiler inlines it.</div><div>But the difference between obj == self & obj == nil/obj isNil will be in the noise.</div>
<div><br></div><div>You should make the decision on convenience.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">what is faster/slower?</blockquote>
<div><br></div><div>anArray asSet size is faster than any of the alternatives because it is easier to thunk about ;) Faster thought is much more valuable than faster processing, c.f. Smalltalk programs vs C++ programs ;)</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><br>
<font color="#888888"><br>
<br>
--<br>
</font><div><div></div><div class="Wj3C7c">Best regards,<br>
Igor Stasenko AKA sig.<br>
<br>
</div></div></blockquote></div><br></div>