Smalltalk › Cincom › VisualWorks

[vwnc] [7.5 bug] WeakKeyDictionary growth loop

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

4 messages Options

Paul Baumann

[vwnc] [7.5 bug] WeakKeyDictionary growth loop

Storing Float instances in a WeakKeyDictionary is looping/crashing like this:

Name: AsyncPerformer>>processBlock Priority: 60
WeakKeyDictionary>>growBound
WeakKeyDictionary>>grow
WeakKeyDictionary>>findKeyOrNil:
WeakKeyDictionary>>findKeyOrNil:
WeakKeyDictionary>>findKeyOrNil:
WeakKeyDictionary>>findKeyOrNil:
WeakKeyDictionary>>findKeyOrNil:
*
*
*
WeakKeyDictionary>>findKeyOrNil:
WeakKeyDictionary>>findKeyOrNil:
WeakKeyDictionary>>findKeyOrNil:
WeakKeyDictionary>>findKeyOrNil:
WeakKeyDictionary>>findKeyOrNil:
optimized [] in WeakKeyDictionary>>at:ifAbsent:
BlockClosure>>ensure:
optimized [] in RecursionLock>>critical:
BlockClosure>>ensure:
Semaphore>>critical:
RecursionLock>>critical:
WeakKeyDictionary>>at:ifAbsent:
WeakKeyDictionary>>at:ifAbsentPut:

...

The keys are instances of Float. The code had worked for months without problem, but now with greater use it occasionally gets into a growth loop where it can never obtain a slot for the float key. It looks to me like the #privateGrow send is conditional within #grow and that #reclaimElements alone is not enough to release other strongly-referenced floats that collide for the slot. I assume it is looping as it does unproductive reclaims.

Anyone seen this or worked around it? I know Andres has worked on hashing since VW 7.5 so I'll show the code that has this problem...

Here is the VW 7.5 code for WeakKeyDictionary:

WeakKeyDictionary>>findKeyOrNil: key
"Look for the key in the receiver. If it is found, answer
the index of the association containing the key, otherwise
answer the index of the first unused slot."

| location length probe pass |
length := keys size.
pass := 1.
location := self initialIndexFor: key hash boundedBy: length.

[probe := keys at: location.
probe = 0 ifTrue: [values at: location put: 0].
probe == nil or: [probe == key]]
  whileFalse: [(location := location + 1) > length
    ifTrue:
     [location := 1.
     pass := pass + 1.
     pass > 2 ifTrue: [^self grow findKeyOrNil: key]]].
^location

WeakKeyDictionary>>grow
"The receiver becomes roomier."
"Reclaim elements to get an accurate 'tally' before the grow."

self reclaimElements.
self tally / self capacity > self growBound
ifTrue: [ self privateGrow ]

Here are the VW 7.5 implementations of #= and #hash.

Float>>= aNumber
"Answer whether the receiver is equal to the argument.
The primitive fails if it cannot coerce the argument to a Float"

<primitive: 47>
^aNumber respondsToArithmetic and: [aNumber equalFromFloat: self]

Float>>hash
"Try to have a hash function that matches integers.
The assumption is that for hashing, other rationals
will convert themselves to Floats or Doubles to hash,
so we'll have good hash functions for them."

| tr |
tr := self truncated.
^self = tr
  ifTrue: [tr hash]
  ifFalse:
   [| b1 b2 b3 b4 |
   b1 := self basicAt: 1.
   b2 := self basicAt: 2.
   b3 := self basicAt: 3.
   b4 := self basicAt: 4.
   (((b1 bitShift: 20) bitXor: (b4 bitShift: 14))
    bitXor: (b3 bitShift: 7)) bitXor: b2]

Sorry, I don't yet have information about the collection and floats that cause the problem.

Paul Baumann

This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

_______________________________________________
vwnc mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/vwnc

Martin McClure

Re: [vwnc] [7.5 bug] WeakKeyDictionary growth loop

Paul Baumann wrote:

> Storing Float instances in a WeakKeyDictionary is looping/crashing like
> this:
>
> Name: AsyncPerformer>>processBlock Priority: 60
> WeakKeyDictionary>>growBound
> WeakKeyDictionary>>grow
> WeakKeyDictionary>>findKeyOrNil:
> WeakKeyDictionary>>findKeyOrNil:
> WeakKeyDictionary>>findKeyOrNil:
> WeakKeyDictionary>>findKeyOrNil:
> WeakKeyDictionary>>findKeyOrNil:
> *
> *
> *
> WeakKeyDictionary>>findKeyOrNil:
> WeakKeyDictionary>>findKeyOrNil:
> WeakKeyDictionary>>findKeyOrNil:
> WeakKeyDictionary>>findKeyOrNil:
> WeakKeyDictionary>>findKeyOrNil:
> optimized [] in WeakKeyDictionary>>at:ifAbsent:
> BlockClosure>>ensure:
> optimized [] in RecursionLock>>critical:
> BlockClosure>>ensure:
> Semaphore>>critical:
> RecursionLock>>critical:
> WeakKeyDictionary>>at:ifAbsent:
> WeakKeyDictionary>>at:ifAbsentPut:
> ...
>
>
> The keys are instances of Float. The code had worked for months without
> problem, but now with greater use it occasionally gets into a growth
> loop where it can never obtain a slot for the float key. It looks to me
> like the #privateGrow send is conditional within #grow and that
> #reclaimElements alone is not enough to release other
> strongly-referenced floats that collide for the slot. I assume it
> is looping as it does unproductive reclaims.

Paul Baumann

Re: [vwnc] [7.5 bug] WeakKeyDictionary growth loop

The semaphore hit by the WeakKeyDictionary>>printOn: makes debugging a minefield; it prevented getting all the data until this morning. The collection was saturated and looped when doing #at:ifAbsent: to find a key. The problem is that the tally is wrong and that is used to determine whether growth should happen. The tally was observed to be 5 when there were really 41 pairs.

values := #(597.11d 603.61d 265.48d 641.63d 608.17d 175.89d 179.85d 428.06d 458.86d 442.02d 564.07d 617.42d 646.29d 451.2d 440.18d 431.99d 450.34d 635.73d 421.6d 432.25d 167.63d 171.5d 174.4d 173.59d 177.55d 373.21d 423.37d 370.2d 176.73d 168.4d 449.15d 376.11d 589.13d 584.51d 262.31d 260.14d 569.32d 424.06d 559.17d 302.65d 114.045d).
keys := (WeakArray withAll: #(597.11 603.61 265.48 641.63 608.17 175.89 179.85 428.06 458.86 442.02 564.07 617.42 646.29 451.2 440.18 431.99 450.34 635.73 421.6 432.25 167.63 171.5 174.4 173.59 177.55 373.21 423.37 370.2 176.73 168.4 449.15 376.11 589.13 584.51 262.31 260.14 569.32 424.06 559.17 302.65 114.045) inspect) addDependent: self; yourself.
tally := 5.

self at: 300.44 ifAbsent: []

The conditions can reproduce the loop, but the cause of the tally being understated is a little deeper...

The bug is that WeakKeyDictionary>>reclaimElements is not niling the value slot for the cleared key slot (like WeakValueDictionary>>reclaimElements does). WeakKeyDictionary>>privateAt:put: and #at:put: do conditional tally increments because #findKeyOrNil: can place a 0 value to indicate pre-reclaim slot recycling. This would fix the problem:

WeakKeyDictinary>>reclaimElements
| deathMarker size |
size := keys size.
deathMarker := 1.
[deathMarker ~= 0] whileTrue:
[(deathMarker := keys
indexOf: 0
replaceWith: nil
startingAt: deathMarker
stoppingAt: size) = 0
ifFalse:
[values at: deathMarker put: nil.
tally := tally - 1]]

Paul Baumann

-----Original Message-----
From: Martin McClure [mailto:[hidden email]]
Sent: Thursday, April 23, 2009 5:56 PM
To: Paul Baumann
Cc: vwnc NC
Subject: Re: [vwnc] [7.5 bug] WeakKeyDictionary growth loop
Importance: High

Paul Baumann wrote:

> Storing Float instances in a WeakKeyDictionary is looping/crashing
> like
> this:
>
> Name: AsyncPerformer>>processBlock Priority: 60
> WeakKeyDictionary>>growBound
> WeakKeyDictionary>>grow
> WeakKeyDictionary>>findKeyOrNil:
> WeakKeyDictionary>>findKeyOrNil:
> WeakKeyDictionary>>findKeyOrNil:
> WeakKeyDictionary>>findKeyOrNil:
> WeakKeyDictionary>>findKeyOrNil:
> *
> *
> *
> WeakKeyDictionary>>findKeyOrNil:
> WeakKeyDictionary>>findKeyOrNil:
> WeakKeyDictionary>>findKeyOrNil:
> WeakKeyDictionary>>findKeyOrNil:
> WeakKeyDictionary>>findKeyOrNil:
> optimized [] in WeakKeyDictionary>>at:ifAbsent:
> BlockClosure>>ensure:
> optimized [] in RecursionLock>>critical:
> BlockClosure>>ensure:
> Semaphore>>critical:
> RecursionLock>>critical:
> WeakKeyDictionary>>at:ifAbsent:
> WeakKeyDictionary>>at:ifAbsentPut:
> ...
>
>
> The keys are instances of Float. The code had worked for months
> without problem, but now with greater use it occasionally gets into a
> growth loop where it can never obtain a slot for the float key. It
> looks to me like the #privateGrow send is conditional within #grow and
> that #reclaimElements alone is not enough to release other
> strongly-referenced floats that collide for the slot. I assume it is
> looping as it does unproductive reclaims.

Interesting.

In a quick look at the code, the only obvious way to get into this kind of recursion is if growBound is too large, and I assume you've checked that. If you can catch one in this state, check to see whether the keys array contains any nils or zeroes (either should prevent this condition) and whether the tally is = keys basicSize (if there are no nils or zeroes I believe they should be equal).

Regards,

-Martin

This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

_______________________________________________
vwnc mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/vwnc

Andres Valloud-6

Re: [vwnc] [7.5 bug] WeakKeyDictionary growth loop

AR 58426...

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On
Behalf Of Paul Baumann
Sent: Friday, April 24, 2009 7:46 AM
To: vwnc NC
Subject: Re: [vwnc] [7.5 bug] WeakKeyDictionary growth loop

The semaphore hit by the WeakKeyDictionary>>printOn: makes debugging a
minefield; it prevented getting all the data until this morning. The
collection was saturated and looped when doing #at:ifAbsent: to find a
key. The problem is that the tally is wrong and that is used to
determine whether growth should happen. The tally was observed to be 5
when there were really 41 pairs.

values := #(597.11d 603.61d 265.48d 641.63d 608.17d 175.89d 179.85d
428.06d 458.86d 442.02d 564.07d 617.42d 646.29d 451.2d 440.18d 431.99d
450.34d 635.73d 421.6d 432.25d 167.63d 171.5d 174.4d 173.59d 177.55d
373.21d 423.37d 370.2d 176.73d 168.4d 449.15d 376.11d 589.13d 584.51d
262.31d 260.14d 569.32d 424.06d 559.17d 302.65d 114.045d).
keys := (WeakArray withAll: #(597.11 603.61 265.48 641.63 608.17 175.89
179.85 428.06 458.86 442.02 564.07 617.42 646.29 451.2 440.18 431.99
450.34 635.73 421.6 432.25 167.63 171.5 174.4 173.59 177.55 373.21
423.37 370.2 176.73 168.4 449.15 376.11 589.13 584.51 262.31 260.14
569.32 424.06 559.17 302.65 114.045) inspect) addDependent: self;
yourself.
tally := 5.

self at: 300.44 ifAbsent: []

The conditions can reproduce the loop, but the cause of the tally being
understated is a little deeper...

The bug is that WeakKeyDictionary>>reclaimElements is not niling the
value slot for the cleared key slot (like
WeakValueDictionary>>reclaimElements does).
WeakKeyDictionary>>privateAt:put: and #at:put: do conditional tally
increments because #findKeyOrNil: can place a 0 value to indicate
pre-reclaim slot recycling. This would fix the problem:

WeakKeyDictinary>>reclaimElements
| deathMarker size |
size := keys size.
deathMarker := 1.
[deathMarker ~= 0] whileTrue:
[(deathMarker := keys
indexOf: 0
replaceWith: nil
startingAt: deathMarker
stoppingAt: size) = 0
ifFalse:
[values at: deathMarker put:
nil.
tally := tally - 1]]

Paul Baumann

-----Original Message-----
From: Martin McClure [mailto:[hidden email]]
Sent: Thursday, April 23, 2009 5:56 PM
To: Paul Baumann
Cc: vwnc NC
Subject: Re: [vwnc] [7.5 bug] WeakKeyDictionary growth loop
Importance: High

Paul Baumann wrote:

> that #reclaimElements alone is not enough to release other
> strongly-referenced floats that collide for the slot. I assume it is
> looping as it does unproductive reclaims.

Interesting.

In a quick look at the code, the only obvious way to get into this kind
of recursion is if growBound is too large, and I assume you've checked
that. If you can catch one in this state, check to see whether the keys
array contains any nils or zeroes (either should prevent this condition)
and whether the tally is = keys basicSize (if there are no nils or
zeroes I believe they should be equal).

Regards,

-Martin

This message may contain confidential information and is intended for
specific recipients unless explicitly noted otherwise. If you have
reason to believe you are not an intended recipient of this message,
please delete it and notify the sender. This message may not represent
the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or
affiliates, and does not constitute a contract or guarantee. Unencrypted
electronic mail is not secure and the recipient of this message is
expected to provide safeguards from viruses and pursue alternate means
of communication where privacy or a binding message is desired.

_______________________________________________
vwnc mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/vwnc

_______________________________________________
vwnc mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/vwnc