From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id TAA19364 for caml-redistribution; Tue, 18 Mar 1997 19:20:11 +0100 (MET) Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id QAA17210 for ; Tue, 18 Mar 1997 16:53:56 +0100 (MET) Received: from cherub.heidelbg.ibm.com (firewall.hd.ibm.de [192.101.197.10]) by concorde.inria.fr (8.7.6/8.7.3) with SMTP id QAA21499 for ; Tue, 18 Mar 1997 16:53:47 +0100 (MET) Received: from kaa.heidelbg.ibm.com by cherub.heidelbg.ibm.com (AIX 4.1/UCB 5.64/4.03/chkV1.0) id AA13830; Tue, 18 Mar 1997 16:53:55 +0100 Received: from idse.heidelbg.ibm.com by kaa.heidelbg.ibm.com (AIX 3.2/UCB 5.64/4.03) id AA10092; Tue, 18 Mar 1997 16:54:27 +0100 Received: by idse.heidelbg.ibm.com (AIX 3.2/UCB 5.64/4.03) id AA46238; Tue, 18 Mar 1997 16:54:19 +0100 Message-Id: <9703181554.AA46238@idse.heidelbg.ibm.com> X-Mailer: exmh version 1.6.4p2 10/10/95 (wish4.1) To: Kohler Markus Cc: caml-list@pauillac.inria.fr Subject: Re: Weak pointers In-Reply-To: (Your message of Tue, 18 Mar 97 10:09:38 GMT.) <199703181009.LAA23108@betze.bbn.hp.com> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable Date: Tue, 18 Mar 97 16:54:19 +0100 From: Wolfgang Lux Sender: weis > [...] > > You can use them to implement hash-consing. Assume you have some tree > > data structure. If you want to share the nodes wherever possible, you > > can put every created node into a hash table. Then when you are about > > to create a new node, you first look in the hash table to see if the > > same node has already been created. If this is the case, you return > > the old one from the hash table instead of creating a new one. > > > > But the above prevents the GC from collecting the nodes when they > > become unused, because they will always be reachable from the hash > > table. If you use weak pointers in your hash table, the GC will be > > able to deallocate the dead nodes, but you still can have access to > > the live ones through the weak pointers. > > > > I'm not sure if it makes sense to implement such a tree with weak pointers. > To be honest, I think it's not a good idea to do so. > > The problem is that if you delete an element in the tree it may be that the > hash table still points to the node, because there was no garbage collection > yet. It could be possible that you would still find the entry trough the hash > table. Surely this is possible, but I do not see why this should be a problem. It will just prevent you from creating an identical copy of an element which had been present in the hash table. > > IMHO the real solution is to implement a delete method for the tree whcih > takes care of all that internal pointers. > No. The delete method for the tree is the wrong place. You would link your tree implementation hardly with the use of the hash table and disallow the use of the data structure without a hash table or with another hash table implementation. This does not seem good software engineering practice to me. BTW, in implementing such a method you would have to implement some kind of weak pointer yourself. A data structure might be an element in more than one tree so would have to keep reference counts as well to be sure that you can remove a data structure from the hash table. I would admit that weak pointers are some dirty kind of feature in the language and I'm not quite happy that they. It is very easy to write programs in the presence of weak pointers, whose outcome is completly random. But in some cases like the one of Damien's example it may be the least dirty one. > By the way, I know what I'm speaking about because we have here an application > using the same idea to implement some kind of cache. I does not work properly > because nobody knows at which point of time the garbage collector throws way > the objects. Sure. But this only demonstrates the fact, that you have to use weak pointer with care. If you work with objects where a data structure which is recreated differs from a data structure that is refetched from the cache,weak pointers are really not applicable. (And maintaining cache consistency is not trival at all in this case!) Regards Wolfgang ---- Wolfgang Lux WZH Heidelberg, IBM Germany Phone: +49-6221-59-4546 Fax: +49-6221-59-3500 Internet: lux@heidelbg.ibm.com Office: mazvm01(lux)