[Seaside] Re: Why isn't this a weak dictionary of some ilk?

[Philippe Marschall]

2009/4/22 Igor Stasenko <siguctua at gmail.com>:
> 2009/4/22 Lukas Renggli <renggli at gmail.com>:
>>> Lukas, all these topics is about a weak array finalization process,
>>> which is just made for a convenience and on top of  the fact, that VM
>>> supports weak references.
>>
>> I understand that. And I remember that the suggestion was to implement
>> our own finalization code. The reasons why we didn't do so were the
>> following:
>>
>> - It was pretty easy to get rid of the requirement for weak data
>> structures. The wasted memory was not significant enough to make it
>> worth worrying about a special solution.
>>
>> - Introducing custom finalization code is highly non-portable across.
>> At the time of Seaside 2.7 and 2.8, there were no easy possibilities
>> to factor such code out.
>>
>> - Last but not least, I might be wrong on this, we had the impression
>> that this was a Squeak only problem. I've never heard of similar
>> problems with other Smalltalk. The finalization of session state just
>> works out of the box.
>>
>> Maybe the real root of the problem is not even the weak finalization,
>> but the way Squeak handles and rehashes large Dictionaries?
>>
> Yes, rehashing is sloow and in linear dependency from a number of elements.
>
> To avoid rehashing, one could use a binary tree. But it having own
> cost: access to specific element takes O(log n) time, while current
> hash-based implementations is O(1) for best case, and, technically,
> O(n) for the worst case.
> If you remember, i implemented a separate set of Dictionaries
> (inluding Weak ones) for Magma, which were optimized for handling a
> large data sets at the cost of additional memory per key/value pair.
> It is also, have a different worst case access time - O(k), where k is
> number of elements which having same hash value under given key.
>
> As for finalization - its obvious, that you need to keep the amount of
> weak objects, which require finalization, small. Because to determine
> which object dies, you have to iterate over every item in collection -
> which is strictly linear.
> That's why putting too much objects into WeakRegistry makes squeak
> very slow, because it has to iterate over this collection over and
> over at _each_ garbage collection cycle, to determine which objects
> became garbage.
> Thus, without efficient support from VM side, a finalization scheme is
> doomed to be slow.

That's why we don't use it. Seriously we are talking about images
being blocked for 10 min to 20 min because of weak array finalization.

See also:
http://bugs.squeak.org/view.php?id=2910

Cheers
Philippe