Re: Comment on ContainerCache?

[prev] [thread] [next] [Date index for 2004/07/16]

--OXfL5xGRrasGEqWY
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Fri, Jul 16, 2004 at 08:27:58 +0200, Heiko Klein wrote:
> When retrieving a object/row, it would first look in the CacheContainer=
=20
> and only when it doesn't exists there, it would connect to the database=
=20
> and put it into the ContainerCache.
>=20
> The difference to LiveObjects is the lifetime of objects in the=20
> ContainerCache, which would be much longer than in LiveObjects, i.e.
> a) as long as the low-watermark hasn't been reached, objects will live=20
> forever
> b) above the high-watermark, all objects with refcount < 1 (not=20
> currently referenced in the rest of the program) will be removed until=20
> the low-watermark is reached
>=20
>=20

> The main disadvantage I currently see:
> The cycling through the ContainerCache and testing for refcount < 1=20
> might take some time.

It's very simple to implement an LRU cache with O(1) (actually
O(high_water - low_water) cleanup time, using a dually linked list and a
hash.

	store all the objects, and the cache keys used to retrieve them  in
	linked list nodes
=09
	store references to the linked list nodes in a hash keyed by the
	cache key if an object exists in the cache:

		hash->ll node->cached object is the way to retrieve it, but with
		a twist - move the linked list node to the head of the linked
		list

	when you hit the high water mark, start popping objects off the tail
	of the linked list, and delete the keys in the hash.

using LRU means that "good" objects, that is, ones which are used often,
are less likely to be purged. You can iterate the linked list and skip
objects which have a refcount that is >=3D 1.

It is reasonable to assume that low refcounted objects will bubble to
the end of the list, since this cache will encourage reconstructing
objects instead of keeping them.

If not, you can have DESTROY save objects in the "dead objects" cache,
thus lifting the refcount (yes, it is allowed. You get a warning in
global destruction though). Then you can purge from it unconditionally,
and still maintain an LRU policy, which can help make smarter lookups.

If you use it as a mixin per class, then doing

sub DESTROY {
	__PACKAGE__->cache->store($_[0]);
}

sub _really_destroy { # called when purging from cache
	$_[0]->SUPER::DESTROY();
}

will even be reasonably safe.


LRU benefits from very large caches, and since this is perl, we're used
to being generous.


Finally, the Cache:: namespace on the CPAN probably has an LRU
implementation like this, but I've never used it, so I don't know. It's
been a while since i've used caching. More complex caching policies (or
actually cache removal policies) probably exist, and AFAIK the API to
Cache:: will let the user select which policy they would like quite
easily.

I think my real point is: use Cache:: - it's already been done.

--=20
 ()  Yuval Kogman <nothingmuch@xxxxxxxx.xxx> 0xEBD27418  perl hacker &
 /\  kung foo master: /me beats up some cheese: neeyah!!!!!!!!!!!!!!!!!


--OXfL5xGRrasGEqWY
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (Darwin)

iD8DBQFA9+HfVCwRwOvSdBgRAn8VAJ9U6YBqYfTc4qjMpqvuOi7DxJO/pACghJVT
wivr7/7jYrCnm8K274NbHrk=
=j6WR
-----END PGP SIGNATURE-----

--OXfL5xGRrasGEqWY--