Undeclared -> WeakIdentityDictionary -> wrong tally -> wrong #size

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Undeclared -> WeakIdentityDictionary -> wrong tally -> wrong #size

marcel.taeumel
Hi, there.

In Squeak 5.3 RC1, the size of Undeclared is wrong. It should be 1 (which is also wrong but I fixed that), but is actually 31.

WeakIdentityDictionary (HashedCollection) >> #size
   ^ tally

Well, there might be a bug lurking somewhere. Maybe an update script messed up the state of Undeclared in particular. I don't know.

What should I do? Just fix that value for tally in Undeclared?

Best,
Marcel

P.S.: The #capacity of Undeclared is 3, which is correct because the internal WeakArray array has that size.


Reply | Threaded
Open this post in threaded view
|

Re: Undeclared -> WeakIdentityDictionary -> wrong tally -> wrong #size

marcel.taeumel
Hmm... for all kinds of HashedCollection, there is #size and #slowSize. The
latter is more precise for weak collections, which answer only an upper
bound via #size. Because they cannot know better. While this might be
resolved with using ephemerons at some point, I still wonder whether
#isEmpty should really just use the tally or not:

HashedCollection >> #isEmpty
   ^tally = 0

We added this in 10/20/2016. Maybe we should override #isEmpty in all our
weak collections if they do not rely on #do as intended in Collection:

Collection >> #isEmpty
   self do: [:element | ^ false].
   ^ true

#do: works fine for those weak collections. I suppose it is as slow as
#slowSize. :-)

Best,
Marcel


marcel.taeumel wrote

> Hi, there.
>
> In Squeak 5.3 RC1, the size of Undeclared is wrong. It should be 1 (which
> is also wrong but I fixed that), but is actually 31.
>
> WeakIdentityDictionary (HashedCollection) >> #size
>    ^ tally
>
> Well, there might be a bug lurking somewhere. Maybe an update script
> messed up the state of Undeclared in particular. I don't know.
>
> What should I do? Just fix that value for tally in Undeclared?
>
> Best,
> Marcel
>
> P.S.: The #capacity of Undeclared is 3, which is correct because the
> internal WeakArray array has that size.





--
Sent from: http://forum.world.st/Squeak-Dev-f45488.html

Reply | Threaded
Open this post in threaded view
|

Re: Undeclared -> WeakIdentityDictionary -> wrong tally -> wrong #size

marcel.taeumel
Okay. I will add some #testIsEmpty for our weak collections to show the
issue. Then I will override all #isEmpty back to the original approach using
#do:. I will not remove the optimization in HashedCollection >> #isEmpty.

The tests will look like this:

testIsEmpty

        | ws o1 o2 |
        o1 := Object new.
        o2 := Object new.

        ws := WeakSet new.
        self assert: ws isEmpty.

        ws add: o1.
        ws add: o2.
        self deny: ws isEmpty.
       
        Smalltalk garbageCollect.
        self deny: ws isEmpty.

        o1 := nil.
        o2 := nil.
        Smalltalk garbageCollect.
        self assert: ws isEmpty.

Why am I doing this? See ReleaseTest >> #testUndeclared :-)

Best,
Marcel



marcel.taeumel wrote

> Hmm... for all kinds of HashedCollection, there is #size and #slowSize.
> The
> latter is more precise for weak collections, which answer only an upper
> bound via #size. Because they cannot know better. While this might be
> resolved with using ephemerons at some point, I still wonder whether
> #isEmpty should really just use the tally or not:
>
> HashedCollection >> #isEmpty
>    ^tally = 0
>
> We added this in 10/20/2016. Maybe we should override #isEmpty in all our
> weak collections if they do not rely on #do as intended in Collection:
>
> Collection >> #isEmpty
>    self do: [:element | ^ false].
>    ^ true
>
> #do: works fine for those weak collections. I suppose it is as slow as
> #slowSize. :-)
>
> Best,
> Marcel
>
>
> marcel.taeumel wrote
>> Hi, there.
>>
>> In Squeak 5.3 RC1, the size of Undeclared is wrong. It should be 1 (which
>> is also wrong but I fixed that), but is actually 31.
>>
>> WeakIdentityDictionary (HashedCollection) >> #size
>>    ^ tally
>>
>> Well, there might be a bug lurking somewhere. Maybe an update script
>> messed up the state of Undeclared in particular. I don't know.
>>
>> What should I do? Just fix that value for tally in Undeclared?
>>
>> Best,
>> Marcel
>>
>> P.S.: The #capacity of Undeclared is 3, which is correct because the
>> internal WeakArray array has that size.
>
>
>
>
>
> --
> Sent from: http://forum.world.st/Squeak-Dev-f45488.html





--
Sent from: http://forum.world.st/Squeak-Dev-f45488.html

Reply | Threaded
Open this post in threaded view
|

Re: Undeclared -> WeakIdentityDictionary -> wrong tally -> wrong #size

marcel.taeumel
Maybe weak collections should never claim to be empty anymore after any
element was added to them? I would understand that since repeated calls can
return different results.

Best,
Marcel



--
Sent from: http://forum.world.st/Squeak-Dev-f45488.html

Reply | Threaded
Open this post in threaded view
|

Re: Undeclared -> WeakIdentityDictionary -> wrong tally -> wrong #size

Levente Uzonyi
Hi Marcel,

The cause of the problem is that unlike other weak hashed collections,
WeakIdentityDictionary does not recalculate tally in
#noCheckNoGrowFillFrom:. And that's a bug, because it lets tally increase
indefinitely.

The bug appears now, because before Undeclared became a
WeakIdentityDictionary, #compact, which is part of what ReleaseBuilder
does, would recalculate the tally via #noCheckNoGrowFillFrom:.

So, even for weak hashed collections, tally should never be larger than
the actual capacity (not #capacity, which currently implemented as array
size is a misnomer) of the collection.


Levente

On Wed, 26 Feb 2020, marcel.taeumel wrote:

> Maybe weak collections should never claim to be empty anymore after any
> element was added to them? I would understand that since repeated calls can
> return different results.
>
> Best,
> Marcel
>
>
>
> --
> Sent from: http://forum.world.st/Squeak-Dev-f45488.html

Reply | Threaded
Open this post in threaded view
|

Re: Undeclared -> WeakIdentityDictionary -> wrong tally -> wrong #size

marcel.taeumel
Hi Levente,

hmm... but WeakSet does also not respond correctly to #isEmpty. Yes, there is a bug with tally calculation as you descrined. However, all weak collections can only support #maybeNotEmpty and never #isEmpty (because of the false case).

Best,
Marcel

Am 26.02.2020 14:54:46 schrieb Levente Uzonyi <[hidden email]>:

Hi Marcel,

The cause of the problem is that unlike other weak hashed collections,
WeakIdentityDictionary does not recalculate tally in
#noCheckNoGrowFillFrom:. And that's a bug, because it lets tally increase
indefinitely.

The bug appears now, because before Undeclared became a
WeakIdentityDictionary, #compact, which is part of what ReleaseBuilder
does, would recalculate the tally via #noCheckNoGrowFillFrom:.

So, even for weak hashed collections, tally should never be larger than
the actual capacity (not #capacity, which currently implemented as array
size is a misnomer) of the collection.


Levente

On Wed, 26 Feb 2020, marcel.taeumel wrote:

> Maybe weak collections should never claim to be empty anymore after any
> element was added to them? I would understand that since repeated calls can
> return different results.
>
> Best,
> Marcel
>
>
>
> --
> Sent from: http://forum.world.st/Squeak-Dev-f45488.html



Reply | Threaded
Open this post in threaded view
|

Re: Undeclared -> WeakIdentityDictionary -> wrong tally -> wrong #size

Levente Uzonyi
Hi Marcel,

On Wed, 26 Feb 2020, Marcel Taeumel wrote:

> Hi Levente,
> hmm... but WeakSet does also not respond correctly to #isEmpty. Yes, there is a bug with tally calculation as you descrined. However, all weak collections can only support #maybeNotEmpty and never #isEmpty (because of the false case).

Right, my response is more related to one of the previous emails of yours.
But, weak collections can and should respond to #isEmpty by using
Collection's implementation.
However, due to the way weak references are handled, the response is not
entirely reliable. IMO, it's the sender's responsibility to take care of
the possibility of the changed state (#isEmpty returns false, but the last
element is gone before the next message is processed by the VM).
Instead of overriding #isEmpty in all weak subclasses, we can handle
it in HashedCollection if we want to:

isEmpty
  "TODO: Add a nice comment here."

  ^array class isWeak
  ifFalse: [ tally = 0 ]
  ifTrue: [ super isEmpty ]


Levente

>
> Best,
> Marcel
>
>       Am 26.02.2020 14:54:46 schrieb Levente Uzonyi <[hidden email]>:
>
>       Hi Marcel,
>
>       The cause of the problem is that unlike other weak hashed collections,
>       WeakIdentityDictionary does not recalculate tally in
>       #noCheckNoGrowFillFrom:. And that's a bug, because it lets tally increase
>       indefinitely.
>
>       The bug appears now, because before Undeclared became a
>       WeakIdentityDictionary, #compact, which is part of what ReleaseBuilder
>       does, would recalculate the tally via #noCheckNoGrowFillFrom:.
>
>       So, even for weak hashed collections, tally should never be larger than
>       the actual capacity (not #capacity, which currently implemented as array
>       size is a misnomer) of the collection.
>
>
>       Levente
>
>       On Wed, 26 Feb 2020, marcel.taeumel wrote:
>
>       > Maybe weak collections should never claim to be empty anymore after any
>       > element was added to them? I would understand that since repeated calls can
>       > return different results.
>       >
>       > Best,
>       > Marcel
>       >
>       >
>       >
>       > --
>       > Sent from: http://forum.world.st/Squeak-Dev-f45488.html
>
>
>

Reply | Threaded
Open this post in threaded view
|

Re: Undeclared -> WeakIdentityDictionary -> wrong tally -> wrong #size

marcel.taeumel
Hi Levente.

Instead of overriding #isEmpty in all weak subclasses, we can handle 
it in HashedCollection if we want to:

I think I will do that in 5.3rc2 because I will also add #isEmpty tests for those weak collections, which would fail otherwise. I hope that's okay with everybody. That bug in #isEmpty is a regression since (about) Squeak 5.1.

Here is a benchmark of #isEmpty for Smalltalk's bindings dictionary:

BEFORE
'134,000,000 per second. 7.47 nanoseconds per run. 0 % GC time.'
AFTER
'51,700,000 per second. 19.3 nanoseconds per run. 0 % GC time.'

Best,
Marcel

Am 26.02.2020 15:44:57 schrieb Levente Uzonyi <[hidden email]>:

Hi Marcel,

On Wed, 26 Feb 2020, Marcel Taeumel wrote:

> Hi Levente,
> hmm... but WeakSet does also not respond correctly to #isEmpty. Yes, there is a bug with tally calculation as you descrined. However, all weak collections can only support #maybeNotEmpty and never #isEmpty (because of the false case).

Right, my response is more related to one of the previous emails of yours.
But, weak collections can and should respond to #isEmpty by using
Collection's implementation.
However, due to the way weak references are handled, the response is not
entirely reliable. IMO, it's the sender's responsibility to take care of
the possibility of the changed state (#isEmpty returns false, but the last
element is gone before the next message is processed by the VM).
Instead of overriding #isEmpty in all weak subclasses, we can handle
it in HashedCollection if we want to:

isEmpty
"TODO: Add a nice comment here."

^array class isWeak
ifFalse: [ tally = 0 ]
ifTrue: [ super isEmpty ]


Levente

>
> Best,
> Marcel
>
> Am 26.02.2020 14:54:46 schrieb Levente Uzonyi :
>
> Hi Marcel,
>
> The cause of the problem is that unlike other weak hashed collections,
> WeakIdentityDictionary does not recalculate tally in
> #noCheckNoGrowFillFrom:. And that's a bug, because it lets tally increase
> indefinitely.
>
> The bug appears now, because before Undeclared became a
> WeakIdentityDictionary, #compact, which is part of what ReleaseBuilder
> does, would recalculate the tally via #noCheckNoGrowFillFrom:.
>
> So, even for weak hashed collections, tally should never be larger than
> the actual capacity (not #capacity, which currently implemented as array
> size is a misnomer) of the collection.
>
>
> Levente
>
> On Wed, 26 Feb 2020, marcel.taeumel wrote:
>
> > Maybe weak collections should never claim to be empty anymore after any
> > element was added to them? I would understand that since repeated calls can
> > return different results.
> >
> > Best,
> > Marcel
> >
> >
> >
> > --
> > Sent from: http://forum.world.st/Squeak-Dev-f45488.html
>
>
>