Smalltalk › Squeak › Squeak - Dev

Set/Dictionary>>fixCollisionsFrom: broken

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

6 messages Options

Andreas.Raab

Set/Dictionary>>fixCollisionsFrom: broken

Hi -

I just noticed a subtle bug in Set>>fixCollisionsFrom: namely here:

[ (element := self keyAt: (index := index \\ array size + 1)) == nil ]
whileFalse: [...].

The problem is that the usage of #keyAt: is incorrect here for Set
subclasses (i.e., Dictionary). We don't want to stop when the *key* is
nil (which can happen in Dictionaries) but rather when the *set entry*
is nil. To illustrate the problem, here is the test that I just put into
trunk:

testNilHashCollision
"Ensures that fixCollisionsFrom: does the right thing in the presence
of a nil key"
| dict key |
dict := Dictionary new.
key := nil hash. "any key with same hash as nil"
dict at: key put: 1.
dict at: nil put: 2.
self assert: (dict includesKey: nil).
dict removeKey: key.
self assert: (dict includesKey: nil).

I'm not sure if this is an old problem or got broken recently (there
were various changes for faster sets etc).

Cheers,
- Andreas

Igor Stasenko

Re: Set/Dictionary>>fixCollisionsFrom: broken

2009/11/13 Andreas Raab <[hidden email]>:

> Hi -
>
> I just noticed a subtle bug in Set>>fixCollisionsFrom: namely here:
>
> [ (element := self keyAt: (index := index \\ array size + 1)) == nil ]
> whileFalse: [...].
>
> The problem is that the usage of #keyAt: is incorrect here for Set
> subclasses (i.e., Dictionary). We don't want to stop when the *key* is nil
> (which can happen in Dictionaries) but rather when the *set entry* is nil.
> To illustrate the problem, here is the test that I just put into trunk:
>
> testNilHashCollision
> "Ensures that fixCollisionsFrom: does the right thing in the presence
> of a nil key"
> | dict key |
> dict := Dictionary new.
> key := nil hash. "any key with same hash as nil"
> dict at: key put: 1.
> dict at: nil put: 2.
> self assert: (dict includesKey: nil).
> dict removeKey: key.
> self assert: (dict includesKey: nil).
>
> I'm not sure if this is an old problem or got broken recently (there were
> various changes for faster sets etc).
>

Aye, i finally got what it means :)
Here the fix (i suppose).

fixCollisionsFrom: start
"The element at start has been removed and replaced by nil.
This method moves forward from there, relocating any entries
that had been placed below due to collisions with this one."

| element index |
index := start.
[ (element := array at: (index := index \\ array size + 1)) == nil ]
whileFalse: [
| newIndex |
(newIndex := self scanFor: ( self keyOfElement: element ) = index ifFalse: [
self swap: index with: newIndex ] ]

where:

Set >> keyOfElement: elem
^ elem

and

Dictionary >> keyOfElement: elem
^ elem key

and we can get rid of #keyAt:

> Cheers,
> - Andreas
>
>

--
Best regards,
Igor Stasenko AKA sig.

Levente Uzonyi-2

Re: Set/Dictionary>>fixCollisionsFrom: broken

On Fri, 13 Nov 2009, Igor Stasenko wrote:

> 2009/11/13 Andreas Raab <[hidden email]>:
>> Hi -
>>
>> I just noticed a subtle bug in Set>>fixCollisionsFrom: namely here:
>>
>> [ (element := self keyAt: (index := index \\ array size + 1)) == nil ]
>> whileFalse: [...].

Nice find, and the fix looks nice too, except for:
- every implementor of #keyAt: should implement #keyOfElement:
- it won't work with MethodDictionary
- it's slow, compared to what it could be

I uploaded another approach to the inbox (Kernel-ul.295 and
Collections-ul.188). It implements #fixCollisionsFrom: where its required
and removes all implementors of #keyAt:. All kernel and collecions
tests are green and the remove performance should be a bit better than
before for all sets and dictionaries, while the number of methods didn't
change (though loc is a bit more than before).

Levente

> Here the fix (i suppose).
>
> fixCollisionsFrom: start
> "The element at start has been removed and replaced by nil.
> This method moves forward from there, relocating any entries
> that had been placed below due to collisions with this one."
>
> | element index |
> index := start.
> [ (element := array at: (index := index \\ array size + 1)) == nil ]
> whileFalse: [
> | newIndex |
> (newIndex := self scanFor: ( self keyOfElement: element ) = index ifFalse: [
> self swap: index with: newIndex ] ]
>
> where:
>
> Set >> keyOfElement: elem
> ^ elem
>
> and
>
> Dictionary >> keyOfElement: elem
> ^ elem key
>
> and we can get rid of #keyAt:
>
>
>> Cheers,
>> - Andreas
>>
>>
>
>
>
> --
> Best regards,
> Igor Stasenko AKA sig.
>
>

Levente Uzonyi-2

Re: Set/Dictionary>>fixCollisionsFrom: broken

Hi,

On Fri, 13 Nov 2009, Levente Uzonyi wrote:

> I uploaded another approach to the inbox (Kernel-ul.295 and
> Collections-ul.188). It implements #fixCollisionsFrom: where its required and
> removes all implementors of #keyAt:. All kernel and collecions tests are
> green and the remove performance should be a bit better than before for all
> sets and dictionaries, while the number of methods didn't change (though loc
> is a bit more than before).

Just found out that Set >> #swap:with: can be removed too, since
#fixCollisionsFrom: is implemented in MethodDictionary which was the only
class in the Set hierarchy that overrode that method. One method less,
same amount of code, slightly better remove performance. Load
Kernel-ul.297 first, then Collections-ul.190 from the inbox. Ignore the
previous versions (Kernel-ul.295 and Collections-ul.188).

Levente

Nicolas Cellier

Re: Set/Dictionary>>fixCollisionsFrom: broken

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

> Hi,
>
> On Fri, 13 Nov 2009, Levente Uzonyi wrote:
>
>> I uploaded another approach to the inbox (Kernel-ul.295 and
>> Collections-ul.188). It implements #fixCollisionsFrom: where its required
>> and removes all implementors of #keyAt:. All kernel and collecions tests are
>> green and the remove performance should be a bit better than before for all
>> sets and dictionaries, while the number of methods didn't change (though loc
>> is a bit more than before).
>
> Just found out that Set >> #swap:with: can be removed too, since
> #fixCollisionsFrom: is implemented in MethodDictionary which was the only
> class in the Set hierarchy that overrode that method. One method less, same
> amount of code, slightly better remove performance. Load Kernel-ul.297
> first, then Collections-ul.190 from the inbox. Ignore the previous versions
> (Kernel-ul.295 and Collections-ul.188).
>
> Levente
>
>

+1 even if swap:with: is private, it's even better to not expose such
a method at all

Igor Stasenko

Re: Set/Dictionary>>fixCollisionsFrom: broken

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

> 2009/11/13 Levente Uzonyi <[hidden email]>:
>> Hi,
>>
>> On Fri, 13 Nov 2009, Levente Uzonyi wrote:
>>
>>> I uploaded another approach to the inbox (Kernel-ul.295 and
>>> Collections-ul.188). It implements #fixCollisionsFrom: where its required
>>> and removes all implementors of #keyAt:. All kernel and collecions tests are
>>> green and the remove performance should be a bit better than before for all
>>> sets and dictionaries, while the number of methods didn't change (though loc
>>> is a bit more than before).
>>
>> Just found out that Set >> #swap:with: can be removed too, since
>> #fixCollisionsFrom: is implemented in MethodDictionary which was the only
>> class in the Set hierarchy that overrode that method. One method less, same
>> amount of code, slightly better remove performance. Load Kernel-ul.297
>> first, then Collections-ul.190 from the inbox. Ignore the previous versions
>> (Kernel-ul.295 and Collections-ul.188).
>>
>> Levente
>>
>>
>
> +1 even if swap:with: is private, it's even better to not expose such
> a method at all
>

+1 , especially in base class, which could provoke abuses.

>

--
Best regards,
Igor Stasenko AKA sig.