Smalltalk › Squeak › Squeak - Dev

Ideas about sets and dictionaries round #2

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

8 messages Options

Levente Uzonyi-2

Ideas about sets and dictionaries round #2

Hi,

Round #1 was mostly about sets containing nil, and the winner seems to be
the object-oriented solution implemented by Igor:
http://bugs.squeak.org/file_download.php?file_id=3829&type=bug

What about the other ideas?

- create a common superclass (HashedCollection) for Set and Dictionary

- implement #valuesDo: only in Dictionary as a single self send of #do:
and remove other implementations from it's subclasses

- add Andres' changes (or something similar)
http://lists.gforge.inria.fr/pipermail/pharo-project/2009-November/015464.html
which help with weak hash values (#identityHash).

- add #keySet to dictionaries which returns a set with the keys, since
#keys now returns an Array

If you have anything against these ideas, please let us know.

Cheers,
Levente

Tobias Pape

Re: Ideas about sets and dictionaries round #2

Hello
Am 2009-11-17 um 02:11 schrieb Levente Uzonyi:

>
> What about the other ideas?
>
> - create a common superclass (HashedCollection) for Set and Dictionary

… Which would allow "boxing dangerous elements" for both Classes

just my 2ct

so long,
-Tobias

Nicolas Cellier

Re: Ideas about sets and dictionaries round #2

In reply to this post by Levente Uzonyi-2

2009/11/17 Levente Uzonyi <[hidden email]>:

> Hi,
>
> Round #1 was mostly about sets containing nil, and the winner seems to be
> the object-oriented solution implemented by Igor:
> http://bugs.squeak.org/file_download.php?file_id=3829&type=bug
>
> What about the other ideas?
>
> - create a common superclass (HashedCollection) for Set and Dictionary
>

+1 http://lists.squeakfoundation.org/pipermail/squeak-dev/2007-June/117894.html
(biased opinion)

> - implement #valuesDo: only in Dictionary as a single self send of #do: and
> remove other implementations from it's subclasses
>

+1

> - add Andres' changes (or something similar)
> http://lists.gforge.inria.fr/pipermail/pharo-project/2009-November/015464.html
> which help with weak hash values (#identityHash).
>

+1

> - add #keySet to dictionaries which returns a set with the keys, since #keys
> now returns an Array
>

If it add something to keys asSet, why not.
For large collections a clever trick could be to not rehash the keys
(Use a Set of same capacity...).

cheers
Nicolas

>
> If you have anything against these ideas, please let us know.
>
> Cheers,
> Levente
>
>

Igor Stasenko

Re: Ideas about sets and dictionaries round #2

+1 for dissecting Set & Dictionary.
and of course +1 for improving the hashing.

2009/11/17 Nicolas Cellier <[hidden email]>:

> 2009/11/17 Levente Uzonyi <[hidden email]>:
>> Hi,
>>
>> Round #1 was mostly about sets containing nil, and the winner seems to be
>> the object-oriented solution implemented by Igor:
>> http://bugs.squeak.org/file_download.php?file_id=3829&type=bug
>>
>> What about the other ideas?
>>
>> - create a common superclass (HashedCollection) for Set and Dictionary
>>
>
> +1 http://lists.squeakfoundation.org/pipermail/squeak-dev/2007-June/117894.html
> (biased opinion)
>
>> - implement #valuesDo: only in Dictionary as a single self send of #do: and
>> remove other implementations from it's subclasses
>>
>
> +1
>
>> - add Andres' changes (or something similar)
>> http://lists.gforge.inria.fr/pipermail/pharo-project/2009-November/015464.html
>> which help with weak hash values (#identityHash).
>>
>
> +1
>
>> - add #keySet to dictionaries which returns a set with the keys, since #keys
>> now returns an Array
>>
>
> If it add something to keys asSet, why not.
> For large collections a clever trick could be to not rehash the keys
> (Use a Set of same capacity...).
>
> cheers
> Nicolas
>
>>
>> If you have anything against these ideas, please let us know.
>>
>> Cheers,
>> Levente
>>
>>
>
>

--
Best regards,
Igor Stasenko AKA sig.

Ralph Johnson

Re: Ideas about sets and dictionaries round #2

In reply to this post by Levente Uzonyi-2

On Mon, Nov 16, 2009 at 7:11 PM, Levente Uzonyi <[hidden email]> wrote:
> Hi,
>
> Round #1 was mostly about sets containing nil, and the winner seems to be
> the object-oriented solution implemented by Igor:
> http://bugs.squeak.org/file_download.php?file_id=3829&type=bug
>
> What about the other ideas?
>
> - create a common superclass (HashedCollection) for Set and Dictionary

I think a better solution is to give Set and Dictionary a common
component, a HashTable. I've seen this done several times and it
always resulted in a clean design. The major drawback is that
MethodDictionary doesn't fit that design, and the VM needs to know the
format of MethodDictionary.

-Ralph

Levente Uzonyi-2

Re: Ideas about sets and dictionaries round #2

In reply to this post by Nicolas Cellier

On Tue, 17 Nov 2009, Nicolas Cellier wrote:

> 2009/11/17 Levente Uzonyi <[hidden email]>:
>> - add #keySet to dictionaries which returns a set with the keys, since #keys
>> now returns an Array
>>
>
> If it add something to keys asSet, why not.
> For large collections a clever trick could be to not rehash the keys
> (Use a Set of same capacity...).
>

The idea is to (ab)use the fact that every dictionary has a set which is
hashed the same way as the dictionary's keys. So a dictionary can create a
set stub without an array, collect it's keys into an array and inject it
into the set. This way creating a set with the keys is basically just a
#collect: of the dictionary's array.

Levente

> cheers
> Nicolas
>

Bryce Kampjes

Re: Ideas about sets and dictionaries round #2

In reply to this post by Ralph Johnson

On Tue, 2009-11-17 at 07:48 -0600, Ralph Johnson wrote:

> On Mon, Nov 16, 2009 at 7:11 PM, Levente Uzonyi <[hidden email]> wrote:
> > Hi,
> >
> > Round #1 was mostly about sets containing nil, and the winner seems to be
> > the object-oriented solution implemented by Igor:
> > http://bugs.squeak.org/file_download.php?file_id=3829&type=bug
> >
> > What about the other ideas?
> >
> > - create a common superclass (HashedCollection) for Set and Dictionary
>
> I think a better solution is to give Set and Dictionary a common
> component, a HashTable. I've seen this done several times and it
> always resulted in a clean design. The major drawback is that
> MethodDictionary doesn't fit that design, and the VM needs to know the
> format of MethodDictionary.

MethodDictionary already uses a different implementation, it uses two
arrays one being part of the MethodDictionary and accessed via basicAt:.
Dictionary uses one Array and Associations.

Bryce

Levente Uzonyi-2

Re: Ideas about sets and dictionaries round #2

In reply to this post by Ralph Johnson

On Tue, 17 Nov 2009, Ralph Johnson wrote:

> On Mon, Nov 16, 2009 at 7:11 PM, Levente Uzonyi <[hidden email]> wrote:
>> Hi,
>>
>> Round #1 was mostly about sets containing nil, and the winner seems to be
>> the object-oriented solution implemented by Igor:
>> http://bugs.squeak.org/file_download.php?file_id=3829&type=bug
>>
>> What about the other ideas?
>>
>> - create a common superclass (HashedCollection) for Set and Dictionary
>
> I think a better solution is to give Set and Dictionary a common
> component, a HashTable. I've seen this done several times and it
> always resulted in a clean design. The major drawback is that
> MethodDictionary doesn't fit that design, and the VM needs to know the
> format of MethodDictionary.

I've been thinking about this a lot before I uploaded the latest changes,
but I came to a decision that if were using encapsulation instead of
inheritance, we would have to duplicate the common interface methods. Also
performance would be worse (extra message sends) mainly because HashTable
would have to behave differently in Set and Dictionary. So I decided to
sacrifice a bit of clarity for simplicity and performance.

Levente

>
> -Ralph
>
>