Re: Weak pointers

Re: Weak pointers

[Damien Doligez]

>From: Frank Christoph <christo@nextsolution.co.jp>
>  Does this mean that even a full weak pointer can be erased?

Yes.  An empty pointer doesn't contain anything, so talking about
erasure is only meaningful for full pointers.

> What does "at any time" mean --- even if the pointer is still
>accessible from the root set, its contents can be erased?

Yes, but if that object is still reachable through some normal
(non-weak) pointer (i.e. any object except a weak array), then the GC
will not erase that weak pointer.  In other words, the GC will only
erase a weak pointer if this erasure makes the object unreachable,
thus deallocatable.

>  Is this intended to contrast with a usual reference, which must
>always be initialized?

I think initialisation is irrelevant.

>  Are weak pointers intended to model C pointers?

No.  Weak pointers are essentially a GC feature: pointers that are not
considered as making the pointed object reachable.

>  Could someone post an example of their use?

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 don't have the weak hash table code yet, but it will certainly
be in the library at some point in the future.

Hope this helps.  If it's not clear, please ask more questions.

-- Damien

Re: Weak pointers

[Kohler Markus]

[...]
 
> >  Could someone post an example of their use?
> 
> 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.

IMHO the real solution is to implement a delete method for the tree whcih 
takes care of all that internal pointers. 

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. 

Regards,
Markus
 

-- 
+----------------------------------------------------------------------------+
| Markus Kohler                          Hewlett-Packard GmbH                |
| Software Engineer                      Network & System Management Division| 
|                                        IT/E Success Team                   |
+----------------------------------------------------------------------------+

Re: Weak pointers

[Wolfgang Lux]

> [...]
> > 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)

Re: Weak pointers

[Kohler Markus]

> > [...]
> > > 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 troughthe 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.
>

Ok, in this case it's no problem.

> >
> > 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.
>

That's no problem. In some sense this Tree is not a Tree but some kind of
directed graph. This graph datastructure could use a hash table and a tree by
aggregation for example.

There's n reason why this datastructures has to use a specific hash table.

If one deletes a node in graph this means that ALL references to the node hav
to be deleted.

> BTW, in implementing such a method you would have to implement some
> kind of weak pointer yourself.

If I would like to implement reuse of already deleted objects, perhaps
something  similiar would be necessary.

> 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.


Same argument as above, combining several trees probably means creating a new
datastructure, which should use appropriate delete methods.
This also has to do with the finalization mechanism. If a finalize method is
called when the object is destroyed, the object could tell all it's depends "
"hey I'm going to be deleted".  This is not directly  related to weak pointers.

>
> 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 workproperly
> > 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!)

I agree with that point.


Markus

--
+----------------------------------------------------------------------------+
| Markus Kohler                          Hewlett-Packard GmbH                |
| Software Engineer                      Network & System Management Division|
|                                        IT/E Success Team                   |
+----------------------------------------------------------------------------+

Re: Weak pointers

[Wolfgang Lux]

[...]
> > >
> > > 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.
> >
>
> That's no problem. In some sense this Tree is not a Tree but some kind of
> directed graph. This graph datastructure could use a hash table and a tree by
> aggregation for example.

>
> There's n reason why this datastructures has to use a specific hash table.

You are right.

>
> If one deletes a node in graph this means that ALL references to the node hav
> to be deleted.
>

But this may no be the thing you want to do! Consider the case where an
element might occur more than once in a tree. If you remove one
reference in the tree you cannot simply call delete because the other
references in the tree might be perfectly valid. But if the last such
reference is removed from the tree you also want to be able to release
the memory of the data structure without regard to the fact that the
element is still referenced from the hash table. In your proposal
either the user would have to make sure that he knows whether (s)he is
removing the last reference from the tree or not and calling a
different function in both cases, or the function which removes an
element from the tree has to count the number of references in the tree
and call delete in that case.

[...]
> This also has to do with the finalization mechanism. If a finalize method is
> called when the object is destroyed, the object could tell all it's depends "
> "hey I'm going to be deleted".

OK. But as long as there is a reference to object (and there is one
through the hash table) the object won't be destroyed. The point here
is thatthe status of a reference through the tree is different from
the reference through the hash table pointer. IMHO your proposed data
structure cannot be a simple aggregation of a tree and a hash table
in that 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)

Weak pointers

[Daniel de Rauglaudre]

I would like to use weak pointers in my code, and I wrote a little test
to check its behavior... It does not work. Why? Maybe I did not
understand them...

$ cat >foo.ml
let print_weak w i =
  begin match Weak.get w i with
    Some _ -> Printf.printf "Some ..."
  | None -> Printf.printf "None"
  end;
  Printf.printf "\n";
  flush stdout
;;

let w = Weak.create 1;;
let r = ref "hello";;

Weak.set w 0 (Some !r);;
print_weak w 0;;

Gc.full_major ();;
print_weak w 0;;

r := "world";;
print_weak w 0;;

Gc.full_major ();;
print_weak w 0;;

$ ocamlc -v
The Objective Caml compiler, version 1.05-2
Standard library directory: ...

$ ocamlc foo.ml

$ ./a.out
Some ...
Some ...
Some ...
Some ...

  I do not understand why the very last print is "Some ..." and not "None".

--------------------------------------------------------------------------
 Daniel de RAUGLAUDRE

 Projet Cristal - INRIA Rocquencourt
 Tel: +33 (01) 39 63 53 51
 Email: daniel.de_rauglaudre@inria.fr
 Web: http://pauillac.inria.fr/~ddr/
--------------------------------------------------------------------------

Re: Weak pointers

[Pierre Weis]

> I would like to use weak pointers in my code, and I wrote a little test
> to check its behavior... It does not work. Why? Maybe I did not
> understand them...
[...] 
> let w = Weak.create 1;;
> let r = ref "hello";;
> 
> Weak.set w 0 (Some !r);;
> print_weak w 0;;
> 
> Gc.full_major ();;
> print_weak w 0;;
> 
> r := "world";;
> print_weak w 0;;
[...] 

> Some ...
> Some ...
> 
>   I do not understand why the very last print is "Some ..." and not "None".

The problem here is that you use constant string data: these citations
are global references that are never garbage collected, since there
really exists a pointer to them from the global symbol table.

Use strings allocated by make_string (== String.create) instead: you
should observe what you expected to observe.

However, weak pointers are far from being simple to use: you should be
aware of fine grain details about the compiler and the memory manager

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/

Re: Weak pointers

[Daniel de Rauglaudre]

> The problem here is that you use constant string data: these citations
> are global references that are never garbage collected, since there
> really exists a pointer to them from the global symbol table.
> 
> Use strings allocated by make_string (== String.create) instead: you
> should observe what you expected to observe.

I found another trick to make my example work: replace
   let r = ref "hello"
by:
   let r = ref ("hello" ^ "")

:-)


--------------------------------------------------------------------------
 Daniel de RAUGLAUDRE

 Projet Cristal - INRIA Rocquencourt
 Tel: +33 (01) 39 63 53 51
 Email: daniel.de_rauglaudre@inria.fr
 Web: http://pauillac.inria.fr/~ddr/
--------------------------------------------------------------------------

Re: Weak pointers

[Damien Doligez]

>I wonder when Weaks pointers are erased by the GC.

With the incremental garbage collector, it's hard to say.

At the soonest, at the end of the first marking phase that ends after
all (strong) pointers to the object have disappeared; at the latest at
the end of the next marking phase, unless you have created more strong
pointers in the meantime by using Weak.get on the weak pointer.

In any case, integers and constant constructors (which are represented
by integers) are never erased by the GC (there is no memory to be
gained by erasing them).  But there's of course no guarantee on this
point.


>As soon as it can be or when there is no more memory ?

The answer is: as soon as it can be, for some meaning of "can".
Caml is not SML/NJ.  You don't need to assume that it will use all
your memory, and then some.


>Is it a good idea to use weak pointers to implement more
>or less a cache ?

If the objects are only in your cache (and not also in some other data
structure used by your program), no because the GC will erase them as
soon as it can.

-- Damien

Weak pointers

[Emmanuel Engel]

I wonder when Weaks pointers are erased by the GC. As soon
as it can be or when there is no more memory ? In the second
case, does all the weaks pointers that can be erased are erased
or just enough to allocate new memory. In this case, which are 
erased, the older or the younger ?


Is it a good idea to use weak pointers to implement more
or less a cache ?

Something like 

type ('a,'b) cache =             (* In fact a binary tree *)
    Node of 'a * 'b * ('a,'b)cache Weak.t
   |Leaf

and to use the usual fonctions over binary tree.


-- 

- Emmanuel Engel

Re: Weak pointers

[Kohler Markus]

> I wonder when Weaks pointers are erased by the GC. As soon
> as it can be or when there is no more memory ? 

I can't speak for caml, but usally when there is no more memory, or the system 
is idle. 

> In the second
> case, does all the weaks pointers that can be erased are erased
> or just enough to allocate new memory. In this case, which are 
> erased, the older or the younger ?
> 
> 
> Is it a good idea to use weak pointers to implement more
> or less a cache ?

 
IMHO not so  a good idea. 
1. Your replacement strategy for the cache will depend on internals of the 
garbage collector. 

2. Also it almost always makes sense to have a cache with a limited size.
 Therefore you have to implement a replacement strategy anyway. 
On machines with virtual memory, the garbage collector ,may always "think" 
that there's more memory left and prefer to grow the process instead of 
reclaiming space.  
Garbage collection in virtual memory can be VERY slow. 

Markus




 

-- 
+----------------------------------------------------------------------------+
| Markus Kohler                          Hewlett-Packard GmbH                |
| Software Engineer                      Network & System Management Division| 
|                                        IT/E Success Team                   |
+----------------------------------------------------------------------------+

Re: Weak pointers

[Kohler Markus]

> >But how do you know then that value is not valid anymore ?
> 
> What do you mean by "valid" ?  It remains valid as long as the GC has
> not deallocated it.  And the weak pointer is erased before the value
> is deallocated.
>  
> >The same could be done with a "normal" pointer. 
> 
> A normal pointer will never let the GC deallocate the value.

OK, I think i got the point, as long as you only use the hash table internally 
for adding, it's not a problem. 

If you use the hashtable to directly access specific nodes, you are running 
into trouble. If you want this feature, weak pointers are not usefull. 

It depends on what you want to do with your datastructure. 

If you "only" use your datastructure as a tree you probably want that only one 
node A is deleted if you call delete(A) for example. In this case you just 
delete ONE specific pointer to node A. 

If you want support operations like "delete all nodes A in the tree", it 
really means you have implemented a graph operation.  

In this case you have to delete ALL pointers to A.  


Regards, 
Markus

-- 
+----------------------------------------------------------------------------+
| Markus Kohler                          Hewlett-Packard GmbH                |
| Software Engineer                      Network & System Management Division| 
|                                        IT/E Success Team                   |
+----------------------------------------------------------------------------+

Re: Weak pointers

[Kohler Markus]

> >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.
> 
> I don't see a problem here.  You find the entry and use it instead of
> allocating a new node.  This is a rather good thing.  It means you
> avoid allocating, and leave less garbage for the GC to collect.
> 

But how do you know then that value is not valid anymore ?
I you use a flag to indicate that then I don't see an advantage of using a 
weak pointer. 
The same could be done with a "normal" pointer. 

Markus
  



 

-- 
+----------------------------------------------------------------------------+
| Markus Kohler                          Hewlett-Packard GmbH                |
| Software Engineer                      Network & System Management Division| 
|                                        IT/E Success Team                   |
+----------------------------------------------------------------------------+

Re: Weak pointers

[Kohler Markus]

I didn't take a look at Java's weak pointers, but I assume it's same as in 
Smalltalk. 

In Smalltalk a weak pointer is not counted when the garbage checks if the 
object is still referenced. That means if you have only weak pointers to an 
object and the application needs memory it will be garbage collected. 

In Smalltalk theres is a correspinding concept called "finalization". 
If a weak object is garbage collected a finalize message is called. 
This is used in Smalltalk to free external resources like windows. 


Markus
-- 
+----------------------------------------------------------------------------+
| Markus Kohler                          Hewlett-Packard GmbH                |
| Software Engineer                      Network & System Management Division| 
|                                        IT/E Success Team                   |
+----------------------------------------------------------------------------+

Objective Caml 1.04 released

[Xavier Leroy]

Release 1.04 of Objective Caml is now available.

The main novelty in this release is the port of the Caml Light replay
debugger. Also, the native-code compiler now works on Silicon
Graphics, weak pointers are supported, and the foreign interface
was enriched to make calling Caml from C easier.

A detailed list of changes follows at the end of this message.

The sources and Windows binaries are available by anonymous FTP
at ftp://ftp.inria.fr/lang/caml-light. Diffs are not available due to
bootstrapping difficulties.

See http://pauillac.inria.fr/ocaml/ for documentation and general info
about Objective Caml.

- Xavier Leroy

Objective Caml 1.04:
--------------------

* Replay debugger ported from Caml Light; added debugger support in
  compiler (option -g) and runtime system. Debugger is alpha-quality
  and needs testing.

* Parsing:
  - Support for "# linenum" directives.
  - At toplevel, allow several phrases without intermediate ";;".

* Typing:
  - Allow constraints on datatype parameters, e.g. 
    type 'a foo = ... constraint 'a = 'b * 'c.
  - Fixed bug in signature matching in presence of free type variables '_a.
  - Extensive cleanup of internals of type inference.

* Native-code compilation:
  - Inlining of small functions at point of call (fairly conservative).
  - MIPS code generator ported to SGI IRIX 6.
  - Better code generated for large integer constants.
  - Check for urgent GC when allocating large objects in major heap.
  - PowerPC port: better scheduling, reduced TOC consumption.
  - HPPA port: handle long conditional branches gracefully,
    several span-dependent bugs fixed.

* Standard library:
  - More floating-point functions (all ANSI C float functions now available).
  - Hashtbl: added functorial interface (allow providing own equality
    and hash functions); rehash when resizing, avoid memory leak on
    Hashtbl.remove.
  - Added Char.uppercase, Char.lowercase, String.uppercase, String.lowercase,
    String.capitalize, String.uncapitalize.
  - New module Weak for manipulating weak pointers.
  - New module Callback for registering closures and exceptions to be
    used from C.

* Foreign interface:
  - Better support for callbacks (C calling Caml), exception raising
    from C, and main() in C. Added function to remove a global root.
  - Option -output-obj to package Caml code as a C library.

* Thread library: fixed bug in timed_read and timed_write operations;
  Lexing.from_function and Lexing.from_channel now reentrant.

* Unix interface: renamed EACCESS to EACCES (the POSIX name); added setsid;
  fixed bug in inet_addr_of_string for 64-bit platforms.

* Ocamlyacc: default error function no longer prevents error recovery.

* Ocamllex: fixed reentrancy problem w.r.t. exceptions during refill;
  fixed output problem (\r\r\n) under Win32.

* Macintosh port:
  - The makefiles are provided for compiling and installing O'Caml on
    a Macintosh with MPW 3.4.1.
  - An application with the toplevel in a window is forthcoming.

* Windows NT/95 port: updated toplevel GUI to that of Caml Light 0.73.

* Emacs editing mode and debugger interface included in distribution.

Objective Caml 1.04 released

[Frank Christoph]

>>>>> "Xavier" == Xavier Leroy <Xavier.Leroy@inria.fr> writes:

> Release 1.04 of Objective Caml is now available.  The main novelty in this
> release is the port of the Caml Light replay debugger. Also, the native-code
> compiler now works on Silicon Graphics, weak pointers are supported, and the
> foreign interface was enriched to make calling Caml from C easier.

  What is a "weak pointer"?  Is it described in the manual?

-- 
Frank Christoph                 Next Solution Co.      Tel: 0424-98-1811
christo@nextsolution.co.jp                             Fax: 0424-98-1500

Re: Weak pointers

[Frank Christoph]

(I wrote:)

>>>>> "Xavier" == Xavier Leroy <Xavier.Leroy@inria.fr> writes:
>> Release 1.04 of Objective Caml is now available.  The main novelty in this
>> release is the port of the Caml Light replay debugger. Also, the
>> native-code compiler now works on Silicon Graphics, weak pointers are
>> supported, and the foreign interface was enriched to make calling Caml from
>> C easier.

>   What is a "weak pointer"?  Is it described in the manual?

  My apologies.  I just discovered module Weak in the standard library.
However, I still don't understand the concept.  The manual says:

  "A weak pointer is an object that the garbage collector may erase at any
time.  A weak pointer is said to be full if it points to an object, empty if
the object was erased by the GC."

  Does this mean that even a full weak pointer can be erased?  What does "at
any time" mean --- even if the pointer is still accessible from the root set,
its contents can be erased?  Is this intended to contrast with a usual
reference, which must always be initialized?  Are weak pointers intended to
model C pointers?

  Could someone post an example of their use?

-- 
Frank Christoph                 Next Solution Co.      Tel: 0424-98-1811
christo@nextsolution.co.jp                             Fax: 0424-98-1500