Ideas about sets and dictionaries

Igor Stasenko wrote:
> The main purpose to be able to handle nils in sets as an elements is to make Set
> be able to hold _any_ potentially existing objects in image.

Absolutely not. The main purpose of having nil be included in sets is to
remove a particular restriction (namely that Sets cannot contain nil),
not to "be able to hold _any_ potentially existing objects in an image".
What is being proposed is trading one restriction (Sets cannot contain
nil) against another one (Sets cannot contain their internal private
marker) which is deemed advantageous as it allows us to convert many
collections that contain nil into sets without blowing up. *That* is the
main purpose.

The goal of "be able to hold _any_ potentially existing objects in an
image" is neither achievable nor worthwhile. Try this for starters:

   (s := Set new) add: s; add: s.

Without having to do anything like reflection and picking arbitrary
objects I can create an (undetected) problem that no proposal addresses.
If you actually mean what you say above I think there are more
problematic issues to solve (problems similar to the above have actually
caused random lockups in the wild).

The point here is that Sets *do* have limitations and what we're trying
to do is to be more helpful in the set of limitations that we require.
Not being able to say "Set with: nil" is silly; not being able to say
"(s := Set new) add: (s instVarAt: 3)" is a much more reasonable
restriction.

BTW, even having said all of the above I'm still not fully convinced
that Randal's proposal is the best way to go. It might be simpler to
just have a flag that says "this set contains nil" like you were
proposing. Whether that needs to be done by using a negative tally or
whether it is better to just add an ivar "hasNil" is yet another question.

It would be rather more interesting to me to discuss the practical
tradeoffs of the choosing one way (marker instead of nil) over the other
(flag indicating nil containment) in terms of implementation and
performance costs.

Cheers,
   - Andreas

Igor Stasenko wrote:
> A simple illustration:
>
>  set := Set new.
>  Object allInstancesDo: [:obj | set add: obj ]   "using 'Object new'
> as filler, right?"
>
> we could argue very long why one would want to do that, but the fact
> is clear: your proposal have nothing
> to offer to developer how to get around that.

Don't use Object then. Use instances of EmptySetMarkers. That way you
know that when adding instances of EmptySetMarkers to sets that have
been previously created will cause problems. And if you want to
enumerate those in a Set use a different marker explicitly, i.e.,

set := Set withMarker: MyPrivateSetMarkerThatIsUsedNowWhereElse.
EmptySetMarker allInstancesDo:[:obj | set add: obj].

(seriously, Igor, this is not a good line of argumentation, the problems
you are describing simply do not exist in practice)

Cheers,
   - Andreas

2009/11/12 Andreas Raab <[hidden email]>:
Why its not worthwhile? I think instead it worthwhile to have a
collections safe from
such recursive problems, so developers won't need to look for
workarounds in order to prevent recursion.

Because:

s := Set new.
badThing := Array with: s.
s add: badThing; add: badThing.

shows that problem is not with Sets per se, but with #hash
implementation for all collections.
Now imagine that developer could not always in direct control where
such badThing's come from, and hence he's always under the risk of
blowing up the image because of running away recursion.
I think this issue alone is worthwhile and needed to be fixed aside
the current discussion topic.

> Without having to do anything like reflection and picking arbitrary objects
> I can create an (undetected) problem that no proposal addresses. If you
> actually mean what you say above I think there are more problematic issues
> to solve (problems similar to the above have actually caused random lockups
> in the wild).
>

but why sit and wait for these problems lurking in the dark to strike
us suddenly?
Its more philosophical problem i think, an approaches we not sharing.
I could declare any piece of code 'its good enough for use by me'. But
does that means that its good enough for use by others?
Does that means that we should stop thinking how to remove the
obstacles and limitation and make better, future-proof
implementation, once its 'good enough' especially when we are talking
about collections - one of the most widely used objects in system?


Sure thing. When tires meet the road.
Lets run benchmarks (know any good bench suite for sets?) and see the
difference.

> Cheers,
>  - Andreas
>
>
>



--
Best regards,
Igor Stasenko AKA sig.

2009/11/12 Andreas Raab <[hidden email]>:
it doesn't exists in practice in same way as you can't find any set in
current image which would respond true
on #includes: nil, nor any code which will make an attempt to include
nil in set, except tests maybe.
But once we remove such obstacle, i am sure they will appear.

In same way one could write a method and say: guys here the method
which adds two numbers. But be careful, adding 0 to any other number
will lead to error.
And guess what? You will see no uses in practice, where people adding
0 to number, instead they will write everywhere:

a = 0 or: [b =0 ] ifFalse: [ ^ a + b ].
a = 0 ifTrue: [ ^ b].
^ a

or something similar...


> Cheers,
>  - Andreas
>
>
>



--
Best regards,
Igor Stasenko AKA sig.

Hello —,
Am 2009-11-12 um 06:35 schrieb Andreas Raab:

> Igor Stasenko wrote:
>> The main purpose to be able to handle nils in sets as an elements is to make Set
>> be able to hold _any_ potentially existing objects in image.
>
> Absolutely not. The main purpose of having nil be included in sets is to remove a particular restriction (namely that Sets cannot contain nil), not to "be able to hold _any_ potentially existing objects in an image". What is being proposed is trading one restriction (Sets cannot contain nil) against another one (Sets cannot contain their internal private marker) which is deemed advantageous as it allows us to convert many collections that contain nil into sets without blowing up. *That* is the main purpose.
>
> The goal of "be able to hold _any_ potentially existing objects in an image" is neither achievable nor worthwhile. Try this for starters:
>
>  (s := Set new) add: s; add: s.

As far as I know, another approach is to have
Distinct Entry Object inside the set. cf. the GemStone
approach.  A set, there, contains an ordered collection of
nils an Entry elements. Thus, the actual element is stored _inside_
the entry element, not in the underlying (storage) collection
of the array itself.  As far as I know, this is similar to its Dictionary
approach.
   Probably, this will introduce a slightly broader spectrum of
optimization possibilities.

So long,
        -Tobias

Igor Stasenko wrote:
> 2009/11/12 Andreas Raab <[hidden email]>:
>> The goal of "be able to hold _any_ potentially existing objects in an image"
>> is neither achievable nor worthwhile. Try this for starters:
>>
>>  (s := Set new) add: s; add: s.
>
> Why its not worthwhile?

Because it's an intractable problem. If I understand you correctly then
you are saying that one should be able to add arbitrary objects to sets
without any constraints whatsoever. That's not worthwhile because at the
  very least you will require that objects you're adding to Sets must
contain finite implementations of #hash as well as implementations of #=
  that allow comparing instances of arbitrary classes (and probably
more). That is already an intractable constraint (most images I am aware
about contain objects that cannot be compared using #=).

At this point you've given up on your initial position of no constraints
whatsoever and now we're just haggling about which constraints are
better or worse. Which is of course fair but it's no longer "any
constraints vs. no constraints" but rather "these constraints vs. those
constraints".

To repeat, my point here is: All sets have constraints. We're just
discussing whether the constraint of not allowing nil as an element is
useful (I happen to think it's not) and whether not allowing an internal
marker of a set being a member of that set is useful (I happen to think
that's okay). You may disagree with this but please don't claim that the
goal is to add objects free of any constraints to sets because none of
the proposals address this.

> I think instead it worthwhile to have a collections safe from
> such recursive problems, so developers won't need to look for
> workarounds in order to prevent recursion.

It most certainly is. But it's a different problem from allowing nil in
sets and neither one removes all constraints from objects being added to
sets. Yes we *should* address this but let's leave this for a different
discussion on another day. Today we're trying to deal with nil in sets.

> but why sit and wait for these problems lurking in the dark to strike
> us suddenly?
> Its more philosophical problem i think, an approaches we not sharing.
> I could declare any piece of code 'its good enough for use by me'. But
> does that means that its good enough for use by others?
> Does that means that we should stop thinking how to remove the
> obstacles and limitation and make better, future-proof
> implementation, once its 'good enough' especially when we are talking
> about collections - one of the most widely used objects in system?

Please remember that I started this part of the discussion by saying
"let's lean back and think about how we would address the problem if we
weren't constrained". I want the discussion about what the best
long-term solution is, in fact I started it.

However, instead of making any constructive comments towards that end
you have been viciously attacking the only proposal that was made in
this context with (from my perspective) completely bogus arguments. That
doesn't strike me as trying to find the best solution - it strikes me as
the behavior of someone who is deeply in love with his (admittedly very
clever) hack ;-)

To be explicit: Do you think that your proposal of using a negative
tally is truly the *best*, the long-term, the future-proof solution to
the problem? That it is the solution that you would choose if you would
implement Set from first principles? Then please say so. But if you can
think of a better solution, please propose that instead. That's what
this phase is all about - not about trying to prove someone else wrong
but to propose -free of constraints- what you think is the best way
forward. Comparisons are fair in this context, shooting down other
proposals is not.

>> It would be rather more interesting to me to discuss the practical tradeoffs
>> of the choosing one way (marker instead of nil) over the other (flag
>> indicating nil containment) in terms of implementation and performance
>> costs.
>
> Sure thing. When tires meet the road.
> Lets run benchmarks (know any good bench suite for sets?) and see the
> difference.

I think what we should do is:

a) Run benchmarks (tiny and macroBenchmarks). I expect no difference but
I only believe that after having run the benchmarks.

b) Count the number of Set subinstances in an image and compute the
additional space overhead that adding a slot would bring. In my current
trunk image that's

        Set allSubInstances size

12906 * 4 => 51624 bytes, i.e., neglectable given that

        Set allSubInstances detectSum:[:s| s capacity].

541602 * 4 => 2166408, so the increase in space is roughly 2.4% per set.

(Interesting. That's less than I expected. If these numbers hold up we
should definitely consider adding an ivar to Set regardless of what we
end up using it for)

c) Consider how each proposal affects implementations. Is the
modification clear and understandable? How many methods did you have to
change? Are further changes required? What about subclasses (i.e., do
they need to be aware that they might now contain nil)? Does the change
affect extension methods loaded from Monticello?

BTW, someone with interest in Randal's proposal will have to step
forward to provide an implementation for it or else Igor's proposal will
likely win by default. I'm not in favor of delaying the discussion by
having proposals that aren't being implemented since we need the
comparison and I'm not going to do that myself since I'm trying to
preserve a bit of neutrality here and I tend to be less objective when
comparing my own code to that of others ;-)

Cheers,
   - Andreas

Tobias Pape wrote:
> As far as I know, another approach is to have
> Distinct Entry Object inside the set. cf. the GemStone
> approach.  A set, there, contains an ordered collection of
> nils an Entry elements. Thus, the actual element is stored _inside_
> the entry element, not in the underlying (storage) collection
> of the array itself.  As far as I know, this is similar to its Dictionary
> approach.

Oh, that's good! One way this could be harnessed is to only wrap up
objects that otherwise couldn't be stored directly in the set. So when
you're storing nil you'd wrap it in a SetEntry and of course if you were
storing a SetEntry you would wrap that in another SetEntry. In the end,
Sets could contain every other object; most of them natively, some of
them wrapped.

Done as polymorphic implementation it could even help dealing with those
infinite collection-inside-collection hash implementations (i.e.,
CollectionSetEntry>>hash would only use a basic hash of the underlying
collection so that adding a set to itself would even work).

A very interesting idea, thanks! This actually sounds like a fun little
project - anyone up for implementing such a Set to see what that would take?

Cheers,
   - Andreas

Hi,

My plan is to split Set and Dictionary first, then let sets contain nil,
because dictionaries don't have this issue.

My original idea was to create a class variable in Set called EmptyFlag
which would take the role of nil as the global marker of empty slots.
I expect it to cause minimal changes in the implementation and have
similar performance as the current implementation, though it may have
caveats I didn't think about. Also, WeakSets could be simplified.

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?

Cheers,
Levente

Levente Uzonyi wrote:
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.

Cheers,
   - Andreas

> All tests in CollectionTests are green except one unrelated
> (ArrayTest>>testPrinting)

But that is boring and obvious.

What I want to know is that you don't break any tests on any published
Squeak -based system.  I don't just mean all the tests in the standard
Squeak images, I mean all the applications, too.

I imagine that a change of this magnitude WILL break things.  Then we
can discuss how badly it breaks things and how hard it is to fix.  If
it only breaks a few applications, and they are easy to fix, then it
is no big deal.  But the main problem with your proposal is that
changing fundamental behavior of base classes is likely to break
applications, and you won't address that questions with tests of
collection classes.

-Ralph

2009/11/12 Andreas Raab <[hidden email]>:
I am agree with all of the above. Except that i didn't claimed that my
proposal having no constraints, but it leaving less constraints
comparing to existing one and comparing Randal's, IMO.

Now your point is clear to me. I didn't understood initially, what you
meant by 'first principles'.
And of course, i am for viewing at problem from different angles and
choose best one.
Concerning why i am heating up the discussion, because i want these
changes to be adopted
and it is more matter to me to see any move (even not one, which i
proposed), instead of none.
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'

seems like, even if there is an overhead it is within the bounds of
noise level/timer accuracy.

Concerning macro benchmarks - where i could download them?

but what i have proposed doesn't requires adding new slot to sets.
And about the cost of having non-nil filler object -> #rehash and #new
will be slower,
unless VM will support new primitive which would allow to pre-fill the
newly created object(s)
slots with other than nils.

> c) Consider how each proposal affects implementations. Is the modification
> clear and understandable? How many methods did you have to change? Are
> further changes required? What about subclasses (i.e., do they need to be
> aware that they might now contain nil)? Does the change affect extension
> methods loaded from Monticello?

that's could take quite a bit of time to document & describe all of the above.
I think that making sure that all tests green is 'good enough' (c),
and if there are breakage,
discovered later, it will show us that our tests need more attention :)

There are quite few methods which suspectible to new functionality
(sets with nils) - actually i think just one  - #like:
which works ok for all non-nil arguments, but may lie to you if you
pass nil as argument,
since it using nil as return value to indicate that nothing similar found.
It should be replaced by #like:ifNone: and all users of #like shoud
use it instead.
Given that there are only 3 senders of #like: in my image there is not
much work to do.

>
> BTW, someone with interest in Randal's proposal will have to step forward to
> provide an implementation for it or else Igor's proposal will likely win by
> default. I'm not in favor of delaying the discussion by having proposals
> that aren't being implemented since we need the comparison and I'm not going
> to do that myself since I'm trying to preserve a bit of neutrality here and
> I tend to be less objective when comparing my own code to that of others ;-)
>
No, i think winner will be approach described by Tobias :)

> Cheers,
>  - Andreas
>
>



--
Best regards,
Igor Stasenko AKA sig.

2009/11/12 Ralph Johnson <[hidden email]>:
>> All tests in CollectionTests are green except one unrelated
>> (ArrayTest>>testPrinting)
>
> But that is boring and obvious.
>
not for those who cares, and changed the printing behavior. But it was not me.

Ralph, by putting such high demands you can kill any potential
initiative to see any changes in
existing core classes, not only mine.
Tests and only tests should cover all the cases, needed to be tested
against correct behavior.
If some application breaking up, it would mean only that either
current set of tests not sufficient, and therefore we
need better test coverage, or application plays against the rules and
breaking an encapsulation.
Testing against virtually every existing application is unreasonable
demand and nobody having time to do that.

> -Ralph
>
>



--
Best regards,
Igor Stasenko AKA sig.

On 11/12/09 7:44 AM, "Igor Stasenko" <[hidden email]> wrote:

> Testing against virtually every existing application is unreasonable
> demand and nobody having time to do that.

But was done in 3.10.
In fact I do all each time and for Mac, Windows Xp and SymplyMepis 6.5.
And found not all perform same on different OS.

Edgar

2009/11/12 Andreas Raab <[hidden email]>:
Of course, I agree to split Set and Dictionary.

I like 2a) trick, and see no problem if it is well documented and
properly isolated
2b) seems a bit too vicious to me, beside, i don't like Float ;)
Otherwise, I would go for 1)

Nicolas

2009/11/12 Andreas Raab <[hidden email]>:
My preferences:

[4] - 2a - 2b, 1

2a-2b, might be a hacks, but could be look as 1 with space-sufficient
optimization.

About 4. IMO would be best way, since it can be implemented right in
the spirit of smalltalk
- dispatch a message, instead of putting extra checks, sometimes
non-obvious ones (like in 2a-2b).

Anyone interesting in discussing this more deeper in another topic?

> Cheers,
>  - Andreas


--
Best regards,
Igor Stasenko AKA sig.

On 12.11.2009, at 09:42, Andreas Raab wrote:

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 -

...
 >
 > I'd prefer (3d): make a class called UnoccupiedSlot ...
 >

3c or 3d. All solutions that add inst vars or even container objects
mean a bad tradeoff in my opinion - wasting tons of space in exchange
for a special case that obviously wasn't absolutely necessary for all
the years.

The question is not only how much a standard image would be inflated,
because there are applications (thinkable) with many small sets and
Squeak should be as universally usable as possible.

If nil can be excluded from sets system-wide, the same thing should be
possible with a class variable or a specific class that has a much more
specific meaning and usage than nil.

Unless the above turns out to be wrong, using a specific marker object
is the most straightforward thing to do. Using nil for that marker
object is sort of a hack itself and treating nil specially makes (1) and
(2) not better.

Regards,
Martin

2009/11/12 Edgar J. De Cleene <[hidden email]>:
really? have you tested it against all and every code in squeakmap and
squeaksource, runned their tests, if any?
If you testing against image - it is ok. I agree with that.. but with
all existing applications?? (while many of them might even fail to
load...).

> Edgar
>


--
Best regards,
Igor Stasenko AKA sig.

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.

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

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?

- Bert -