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

[Igor Stasenko]

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.

> Lukas
>
> --
> Lukas Renggli
> http://www.lukas-renggli.ch
> _______________________________________________
> seaside mailing list
> seaside at lists.squeakfoundation.org
> http://lists.squeakfoundation.org/cgi-bin/mailman/listinfo/seaside
>



-- 
Best regards,
Igor Stasenko AKA sig.