Ideas about sets and dictionaries

>
> On 12.11.2009, at 09:42, Andreas Raab wrote:
>
>> Levente Uzonyi wrote:
>>> But we now have a lot more proposals, let me summarize them all:
>>> - (1)add a new instance variable: containsNil
>>> - (2)use tally to indicate if nil is in the set
>>> - (a)negative values mean nil is contained by the set
>>> - (b)floats - (3)use a marker object
>>> - (a)self
>>> - (b)a unique object in each set
>>> - (c)a class variable
>>> - (4)use container objects in occupied slots, like associations in dictionaries
>>> I prefer 3c, 2a, 3a, 1, 4 in the given order.
>>> What about you?
>>
>> Nice summary. My current preferences would be (1) (clear and obvious) (3b) (ditto) and (3a)/(3c) (both with some hesitation). I'm not sure about (4) (I've only just heard of it; it sounds cool but I haven't seen no code yet). I would veto both (2a) and (2b) as obscure hacks compared to (1) unless the size overhead is significant.
>
> I'd prefer (3d): make a class called UnoccupiedSlot, use it as marker (either the class itself [I'd like that] or its singleton instance [for the purists]). This would make it blatantly obvious what's happening when inspecting the innards of a Set.
>
> I'd reluctantly accept (1) but fear it would complicate the logic - containsNil checks will have to be scattered all over the place.
>
> - Bert -

>
> On 12.11.2009, at 12:49, radoslav hodnicak wrote:
>
>>
>> In all my time I've been programming in Smalltalk (since about 2000), the idea that Sets simply do not contain nil was a core assumption of using collection classes for me, not just an implementation detail. I routinely do "something asSet" to get rid of nils, and this change would break all my code.
>
> (Array new: 5) asSet
>
> raises an error in Squeak ...
>
>> Now, I obvioulsy do not see the value of allowing Sets to contain nil, but other people do. How about creating a new class to handle this? NilSet or whatever
>>
>> rado
>
> Not a bad suggestion. SetWithNil?
>

>
> On 12.11.2009, at 09:42, Andreas Raab wrote:
>
>> Levente Uzonyi wrote:
>>> But we now have a lot more proposals, let me summarize them all:
>>> - (1)add a new instance variable: containsNil
>>> - (2)use tally to indicate if nil is in the set
>>> - (a)negative values mean nil is contained by the set
>>> - (b)floats - (3)use a marker object
>>> - (a)self
>>> - (b)a unique object in each set
>>> - (c)a class variable
>>> - (4)use container objects in occupied slots, like associations in dictionaries
>>> I prefer 3c, 2a, 3a, 1, 4 in the given order.
>>> What about you?
>>
>> Nice summary. My current preferences would be (1) (clear and obvious) (3b) (ditto) and (3a)/(3c) (both with some hesitation). I'm not sure about (4) (I've only just heard of it; it sounds cool but I haven't seen no code yet). I would veto both (2a) and (2b) as obscure hacks compared to (1) unless the size overhead is significant.
>
> I'd prefer (3d): make a class called UnoccupiedSlot, use it as marker (either the class itself [I'd like that] or its singleton instance [for the purists]). This would make it blatantly obvious what's happening when inspecting the innards of a Set.
>

> Hi!
>
> On Thu, 12 Nov 2009, Bert Freudenberg wrote:
>
>>
>> On 12.11.2009, at 09:42, Andreas Raab wrote:
>>
>>> Levente Uzonyi wrote:
>>>> But we now have a lot more proposals, let me summarize them all:
>>>> - (1)add a new instance variable: containsNil
>>>> - (2)use tally to indicate if nil is in the set
>>>> - (a)negative values mean nil is contained by the set
>>>> - (b)floats - (3)use a marker object
>>>> - (a)self
>>>> - (b)a unique object in each set
>>>> - (c)a class variable
>>>> - (4)use container objects in occupied slots, like associations in dictionaries
>>>> I prefer 3c, 2a, 3a, 1, 4 in the given order.
>>>> What about you?
>>>
>>> Nice summary. My current preferences would be (1) (clear and obvious) (3b) (ditto) and (3a)/(3c) (both with some hesitation). I'm not sure about (4) (I've only just heard of it; it sounds cool but I haven't seen no code yet). I would veto both (2a) and (2b) as obscure hacks compared to (1) unless the size overhead is significant.
>>
>> I'd prefer (3d): make a class called UnoccupiedSlot, use it as marker (either the class itself [I'd like that] or its singleton instance [for the purists]). This would make it blatantly obvious what's happening when inspecting the innards of a Set.
>>
>
> What about this?
> (3e): make a class called UnoccupiedSlot with a single instance. Add EmptyFlag to Set, and make sure that EmptyFlag is the instance of UnoccupiedSlot.
> This way the inspector would print "an UnoccupiedSlot" for empty slots and we could save a message send in the implementation.

>> a) Run benchmarks (tiny and macroBenchmarks). I expect no difference but I
>> only believe that after having run the benchmarks.
>>
> before:
> 1 tinyBenchmarks
> '436115843 bytecodes/sec; 12718765 sends/sec'
> '473635522 bytecodes/sec; 12718765 sends/sec'
> '473635522 bytecodes/sec; 12727537 sends/sec'
>
> after:
> 1 tinyBenchmarks
> '472324723 bytecodes/sec; 12657701 sends/sec'
> '472324723 bytecodes/sec; 12683800 sends/sec'
> '472760849 bytecodes/sec; 12969029 sends/sec'

>
> On 12.11.2009, at 13:05, Levente Uzonyi wrote:
>
>> Hi!
>>
>> On Thu, 12 Nov 2009, Bert Freudenberg wrote:
>>
>>>
>>> On 12.11.2009, at 09:42, Andreas Raab wrote:
>>>
>>>> Levente Uzonyi wrote:
>>>>> But we now have a lot more proposals, let me summarize them all:
>>>>> - (1)add a new instance variable: containsNil
>>>>> - (2)use tally to indicate if nil is in the set
>>>>> - (a)negative values mean nil is contained by the set
>>>>> - (b)floats - (3)use a marker object
>>>>> - (a)self
>>>>> - (b)a unique object in each set
>>>>> - (c)a class variable
>>>>> - (4)use container objects in occupied slots, like associations in dictionaries
>>>>> I prefer 3c, 2a, 3a, 1, 4 in the given order.
>>>>> What about you?
>>>>
>>>> Nice summary. My current preferences would be (1) (clear and obvious) (3b) (ditto) and (3a)/(3c) (both with some hesitation). I'm not sure about (4) (I've only just heard of it; it sounds cool but I haven't seen no code yet). I would veto both (2a) and (2b) as obscure hacks compared to (1) unless the size overhead is significant.
>>>
>>> I'd prefer (3d): make a class called UnoccupiedSlot, use it as marker (either the class itself [I'd like that] or its singleton instance [for the purists]). This would make it blatantly obvious what's happening when inspecting the innards of a Set.
>>>
>>
>> What about this?
>> (3e): make a class called UnoccupiedSlot with a single instance. Add EmptyFlag to Set, and make sure that EmptyFlag is the instance of UnoccupiedSlot.
>> This way the inspector would print "an UnoccupiedSlot" for empty slots and we could save a message send in the implementation.
>
> Which message send would you save in
>
> ... == UnoccupiedSlot
>

> On Thu, 12 Nov 2009, Igor Stasenko wrote:
>
>>> a) Run benchmarks (tiny and macroBenchmarks). I expect no difference but
>>> I
>>> only believe that after having run the benchmarks.
>>>
>> before:
>> 1 tinyBenchmarks
>> '436115843 bytecodes/sec; 12718765 sends/sec'
>> '473635522 bytecodes/sec; 12718765 sends/sec'
>> '473635522 bytecodes/sec; 12727537 sends/sec'
>>
>> after:
>> 1 tinyBenchmarks
>> '472324723 bytecodes/sec; 12657701 sends/sec'
>> '472324723 bytecodes/sec; 12683800 sends/sec'
>> '472760849 bytecodes/sec; 12969029 sends/sec'
>
> Well, I doubt Andreas ment to use Integer >> #tinyBenchmarks, because it
> doesn't use sets. I think he ment microbenchmarks like this one:
> http://leves.web.elte.hu/collections/Set%20class-microBenchmark.st
>
> I just ran them with the current implementation, 2a and 3c, the results are
> here: http://leves.web.elte.hu/collections/SetBenchmarkResults.txt
> The values are microseconds/element in the table (smaller valuesa are
> better).
>
> I summed up the rows and created a table (smaller numbers are better):
>        trunk   2a      3c
> add: (included) 2,594   2,599   2,443
> add: (not included)     9,370   9,957   9,441
> includes: (included)    2,869   2,961   2,822
> includes: (not included)        3,685   3,717   3,671
> like: (included)        2,446   2,486   2,508
> like: (not included)    3,268   3,258   3,310
> rehash  2,924   2,841   2,238
> remove:ifAbsent: (included)     7,190   7,228   7,240
> remove:ifAbsent: (not included) 3,966   3,980   3,856
>
> I don't see any real differences. Some values are pretty strange (like
> rehash at 3c, I expected it to be slower than trunk). It may be because of
> noise, even though I tried to avoid noise as much as possible.
>

> On Thu, Nov 12, 2009 at 3:44 AM, Igor Stasenko <[hidden email]> wrote:
>
>> Testing against virtually every existing application is unreasonable
>> demand and nobody having time to do that.
>
> But did you run it against the standard set of tests in Squeak?
>
> The question is whether changing the behavior of Set will break the
> image.   And if it does, how hard will it be to fix? i can't remember
> ever reading or writing code that would break if Sets could include
> nil, but that doesn't mean there isn't any.  The whole reason for
> having these tests is so we can see if changes break something.  But
> if we don't run the tests then they don't do us any good.
>
> Since there are no unit tests that ensure that Sets never contain nil,
> it should not be hard to make a version of Set that can contain nil.
> That is why I said it was boring and obvious to say that your version
> of Set plassed the unit tests for Collections.
>

> Hi!
>
> On Thu, 12 Nov 2009, radoslav hodnicak wrote:
>
>>
>> In all my time I've been programming in Smalltalk (since about 2000), the
>> idea that Sets simply do not contain nil was a core assumption of using
>> collection classes for me, not just an implementation detail. I routinely
>> do "something asSet" to get rid of nils, and this change would break all my
>> code.
>>
> I doubt that. I get an Error when I'm evaluating this: #(1 nil 2) asSet
> You should use #(1 nil 2) reject: [ :each | each isNil ] instead.
>
> Cheers,
> Levente
>

> Levente Uzonyi wrote:
>>> Which message send would you save in
>>>
>>> ... == UnoccupiedSlot
>>>
>>
>> UnoccupiedSlot instance.
>> I wouldn't use a class, because I think we should be able create a set
>> with any classes in it.
>
> Indeed - I am sure there are several places in the image that deal with
> sets of all classes or all globals.

> Levente Uzonyi wrote:
>>> Which message send would you save in
>>>
>>> ... == UnoccupiedSlot
>>>
>>
>> UnoccupiedSlot instance.
>> I wouldn't use a class, because I think we should be able create a set
>> with any classes in it.
>
> Indeed - I am sure there are several places in the image that deal with
> sets of all classes or all globals.
>
> One example of a Smalltalk with a non nil object to mark empty slots in
> sets is Self, so it has been done before. On the other hand, Self
> doesn't use associations but instead implements dictionaries with two
> parallel arrays.

>
> On 12.11.2009, at 14:30, Jecel Assumpcao Jr wrote:
>
>> Levente Uzonyi wrote:
>>>> Which message send would you save in
>>>>
>>>> ... == UnoccupiedSlot
>>>>
>>>
>>> UnoccupiedSlot instance.
>>> I wouldn't use a class, because I think we should be able create a set
>>> with any classes in it.
>>
>> Indeed - I am sure there are several places in the image that deal with
>> sets of all classes or all globals.
>
> Good point.
>
>> One example of a Smalltalk with a non nil object to mark empty slots in
>> sets is Self, so it has been done before. On the other hand, Self
>> doesn't use associations but instead implements dictionaries with two
>> parallel arrays.
>
> It has even been done in Squeak - see class WeakSet.

>
> On 12.11.2009, at 11:35, Bert Freudenberg wrote:
>
>>
>> On 12.11.2009, at 09:42, Andreas Raab wrote:
>>
>>> Levente Uzonyi wrote:
>>>> But we now have a lot more proposals, let me summarize them all:
>>>> - (1)add a new instance variable: containsNil
>>>> - (2)use tally to indicate if nil is in the set
>>>> - (a)negative values mean nil is contained by the set
>>>> - (b)floats - (3)use a marker object
>>>> - (a)self
>>>> - (b)a unique object in each set
>>>> - (c)a class variable
>>>> - (4)use container objects in occupied slots, like associations in dictionaries
>>>> I prefer 3c, 2a, 3a, 1, 4 in the given order.
>>>> What about you?
>>>
>>> Nice summary. My current preferences would be (1) (clear and obvious) (3b) (ditto) and (3a)/(3c) (both with some hesitation). I'm not sure about (4) (I've only just heard of it; it sounds cool but I haven't seen no code yet). I would veto both (2a) and (2b) as obscure hacks compared to (1) unless the size overhead is significant.
>>
>> I'd prefer (3d): make a class called UnoccupiedSlot, use it as marker (either the class itself [I'd like that] or its singleton instance [for the purists]). This would make it blatantly obvious what's happening when inspecting the innards of a Set.
>>
>> I'd reluctantly accept (1) but fear it would complicate the logic - containsNil checks will have to be scattered all over the place.
>>
>> - Bert -
>
> Thinking about migrating (possibly) old data - how do the options fare with respect to reloading serialized Sets? I guess we could count nils and detect a mismatch with tally?
>
> - Bert -
>
>

>>>>>> "Bert" == Bert Freudenberg <[hidden email]> writes:
>
> Bert> I'd prefer (3d): make a class called UnoccupiedSlot, use it as marker
> Bert> (either the class itself [I'd like that] or its singleton instance [for
> Bert> the purists]). This would make it blatantly obvious what's happening
> Bert> when inspecting the innards of a Set.
>
> The problem with that is that you're simply moving the problem.
>
> Now I can't have a Set of all classes. :(
>
> That's the beauty of my "each set contains its own unique nil marker"
> solution.  Any set can contain anything except its own insides, which is a
> limitation that would only occur if you're doing something very very nasty.  A
> set of all classes is far more likely to occur.

> 2428 run, 2406 passes, 0 expected failures, 15 failures, 7 errors, 0
> unexpected passes
>
>
> After applying changes to sets using nil wrappers [1]:
>
> 2428 run, 2406 passes, 0 expected failures, 15 failures, 7 errors, 0
> unexpected passes
>
>
> After adding changes to sets using negative tally[2]:
>
> 2428 run, 2406 passes, 0 expected failures, 15 failures, 7 errors, 0
> unexpected passes