[squeak-dev] Re: Odd performance characteristics of symbol creation

Nicolas Cellier nicolas.cellier.aka.nice at gmail.com
Thu May 7 10:35:29 UTC 2009


2009/5/7 Adrian Lienhard <adi at netstyle.ch>:
> Thanks Nicolas!
>
> As expected, the performance graph is constant with your fix.
>
> Your tests cover a lot of cases. Anything in particular one should test
> before integrating the fix?
>
> Cheers,
> Adrian
>

Well, there is a possible infinite loop in #fixCollisionsFrom:
- 1) This infinite loop can happen if set is full
    but full set never happens in "normal" condition
   unless some uncarefull programmer break contracts and use private messages
- 2) This infinite loop was already there (but #fixCollisionsFrom: was
used less frequently)
- 3) This infinite loop is easy to avoid

But as Andres suggested, the biggest problem might be concurrency issues...
(several process changing/accessing a WeakSet concurrently).
These issues did already exist, but are now more likely to happen
statistically...
- before the change, this was limited to concurrent write of WeakSet.
- after the change, this can also happen for concurrent read
This is because instance variable 'array' can be modified during the
look-up phase (#scanFor:) if ever a hash-colliding entry was reclaimed
near the accessed zone...
Not the kind of issue easy to identify/debug/reproduce...

Nicolas


> On May 7, 2009, at 01:45 , Nicolas Cellier wrote:
>
>> Wait, there is a bug in scanFor: fixCollisionsFrom: does not recycle
>> the first nil and scanFor: then loops indefinitely :( see
>> http://bugs.squeak.org/view.php?id=7350 for update
>>
>> 2009/5/7 Andreas Raab <andreas.raab at gmx.de>:
>>>
>>> Nicolas Cellier wrote:
>>>>
>>>> Created http://bugs.squeak.org/view.php?id=7350
>>>
>>> Thanks, this is great. Is this approach applicable to weak dictionaries
>>> as
>>> well?
>>>
>>
>> Should inquire, but it's getting late...
>>
>>> Cheers,
>>> - Andreas
>>>
>>>> 2009/5/6 Nicolas Cellier <nicolas.cellier.aka.nice at gmail.com>:
>>>>>
>>>>> Ah, I forgot to accept one change!
>>>>> It's even better if we decrease the tally when recycling a nil slot in
>>>>> #fixCollisionsFrom:
>>>>>
>>>>> Nicolas
>>>>>
>>>>> 2009/5/6 Nicolas Cellier <nicolas.cellier.aka.nice at gmail.com>:
>>>>>>
>>>>>> Though I have tried to attack it with some tricky combinations, I did
>>>>>> not found a problem with current implementation.
>>>>>> It was funny to see how nil is handled as any other object in WeakSet
>>>>>> fixCollisionsFrom: (scanFor: nil works).
>>>>>>
>>>>>> However, it's a pity not to recycle all those nils until next grow!
>>>>>> Here comes a little trial for recycling reclaimed nil slots in Pharo
>>>>>> (seems compatible with 3.10.2).
>>>>>> No guarantee... Note there is no WeakSet tests in Pharo nor 3.10.2
>>>>>> currently :(
>>>>>>
>>>>>> Nicolas
>>>>>>
>>>>>> 2009/5/6 Andreas Raab <andreas.raab at gmx.de>:
>>>>>>>
>>>>>>> Nicolas Cellier wrote:
>>>>>>>>
>>>>>>>> Take this example:
>>>>>>>
>>>>>>> Ah, good point. (it works fine with o1 = 'g' and o2 = o3 = o4 = 'd').
>>>>>>> The
>>>>>>> thing is that the test in WeakSet>>add: was misleading - it tests for
>>>>>>> nil
>>>>>>> where scanFor: searches only for flag.
>>>>>>>
>>>>>>> Cheers,
>>>>>>> - Andreas
>>>>>>>
>>>>>>>> ws := WeakSet new.
>>>>>>>> array := WeakSet new instVarAt: (WeakSet allInstVarNames indexOf:
>>>>>>>> 'array').
>>>>>>>> o1 hash \\ array size + 1 -> 1.
>>>>>>>> o2 hash \\ array size + 1 -> 2.
>>>>>>>> o3 hash \\ array size + 1 -> 1.
>>>>>>>> ws add: o1; add: o2; add: o3.
>>>>>>>>
>>>>>>>> o1 := o2 := nil.
>>>>>>>> Smalltalk garbageCollect.
>>>>>>>> "o1 and o2 are reclaimed."
>>>>>>>> (array at: 1) -> nil.
>>>>>>>> (array at: 2) -> nil.
>>>>>>>>
>>>>>>>> o4 hash \\ array size + 1 -> 1.
>>>>>>>> ws add o4.
>>>>>>>> (array at: 1) -> o4.
>>>>>>>>
>>>>>>>> (ws includes: o3) -> false.
>>>>>>>>
>>>>>>>> I will try and build a test case. Should be easy with Fractions.
>>>>>>>>
>>>>>>>> 2009/5/6 Andreas Raab <andreas.raab at gmx.de>:
>>>>>>>>>
>>>>>>>>> Nicolas Cellier wrote:
>>>>>>>>>>
>>>>>>>>>> Isn't that dangerous if you don't fixCollisionsFrom: index ?
>>>>>>>>>
>>>>>>>>> Why would it? All this does is avoiding to update the tally ivar if
>>>>>>>>> we're
>>>>>>>>> replacing a previously reclaimed entry with a new value. And I
>>>>>>>>> don't
>>>>>>>>> think
>>>>>>>>> that #fixCollisionsFrom: even looks at tally.
>>>>>>>>>
>>>>>>>>> Cheers,
>>>>>>>>> - Andreas
>>>>>>>>>
>>>>>>>>>> Nicolas
>>>>>>>>>>
>>>>>>>>>> 2009/5/6 Andreas Raab <andreas.raab at gmx.de>:
>>>>>>>>>>>
>>>>>>>>>>> Adrian Lienhard wrote:
>>>>>>>>>>>>
>>>>>>>>>>>> I haven't had time to look into this very closely yet but maybe
>>>>>>>>>>>> somebody
>>>>>>>>>>>> else already knows what is going on. My guess is that the
>>>>>>>>>>>> NewSymbols
>>>>>>>>>>>> weak
>>>>>>>>>>>> set is repeatedly grown since tally is not decreased if the GC
>>>>>>>>>>>> removes
>>>>>>>>>>>> a
>>>>>>>>>>>> weak element.
>>>>>>>>>>>
>>>>>>>>>>> That's an excellent guess. Try changing WeakSet to e.g.,
>>>>>>>>>>>
>>>>>>>>>>> WeakSet>>atNewIndex: index put: aValue
>>>>>>>>>>> "Add newValue at the given index. Don't increment tally
>>>>>>>>>>> if current slot is nil since a previous value has been collected"
>>>>>>>>>>> (array at: index) ifNil:[^array at: index put: aValue].
>>>>>>>>>>> ^super atNewIndex: index put: aValue
>>>>>>>>>>>
>>>>>>>>>>> Cheers,
>>>>>>>>>>> - Andreas
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>
>>>>
>>>
>>>
>>>
>>
>
>
>



More information about the Squeak-dev mailing list