Re: [Caml-list] How does OCaml update references when values are moved by the GC?
On Sat, Oct 30, 2010 at 09:40:32PM +0100, Jon Harrop wrote: Thanks for the info. I stumbled upon Richard's excellent web page describing the internals of OCaml and the write barrier but it does not describe how the pointers actually get rewritten. I found out the details by reading the C code of the garbage collector and sometimes the generated assembler from ocamlopt -S. It's pretty straightforward to follow. Rich. -- Richard Jones Red Hat ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] How does OCaml update references when values are moved by the GC?
Jon Harrop wrote: I was hoping for a little more detail, of course. :-) How is the mapping from old to new pointers stored? With forwaring pointers. Just take 10 minutes to familiarize yourself with the standard stopcopy algorithm and everything will be clear: http://en.wikipedia.org/wiki/Cheney's_algorithm - Xavier Leroy ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] How does OCaml update references when values are moved by the GC?
2010/10/29 Damien Doligez damien.doli...@inria.fr: On 2010-10-28, at 23:48, Jon Harrop wrote: How does OCaml update references in the stacks and heap when values are moved by the GC? They are updated by the GC, of course. can't the GC just put a new reference for it in a data structure? it has to physically move it? (i think you are referring to moving data to the older generation; it could be a tree or a linked list, marking what exactly is old) -- Elias Gabriel Amaral da Silva tolkiend...@gmail.com ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
RE: [Caml-list] How does OCaml update references when values are moved by the GC?
I was hoping for a little more detail, of course. :-) How is the mapping from old to new pointers stored? Does the GC rewrite all of the thread-local stacks in series before allowing any of them to continue? Does the write barrier record pointers written into the major heap so only those specific locations are rewritten at minor heap collections but the entire major heap is rewritten upon compaction? Can the GC distinguish between an array of ints and an array of pointers at run-time in order to avoid traversing all of the ints when trying to rewrite pointers? Also, any idea what the maximum proportion of the running time of a program is spent doing this rewriting? For example, if you fill a float-float hash table with values does updating the pointers in the major heap account for a significant proportion of the total running time of the program? Cheers, Jon. -Original Message- From: caml-list-boun...@yquem.inria.fr [mailto:caml-list- boun...@yquem.inria.fr] On Behalf Of Damien Doligez Sent: 29 October 2010 08:48 To: caml users Subject: Re: [Caml-list] How does OCaml update references when values are moved by the GC? On 2010-10-28, at 23:48, Jon Harrop wrote: How does OCaml update references in the stacks and heap when values are moved by the GC? They are updated by the GC, of course. -- Damien ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] How does OCaml update references when values are moved by the GC?
On 10/30/2010 12:15 PM, Jon Harrop wrote: I was hoping for a little more detail, of course. :-) How is the mapping from old to new pointers stored? Does the GC rewrite all of the thread-local stacks in series before allowing any of them to continue? I imagine so. Does the write barrier record pointers written into the major heap so only those specific locations are rewritten at minor heap collections but the entire major heap is rewritten upon compaction? Yes. The runtime maintains a 'remembered set', a list of pointers from the major heap back to the minor heap. Maintaining this set is why mutable data can be expensive in OCaml - any time you store a pointer into a mutable field, the runtime must check whether the new link is from the major to the minor heap and update the refs list accordingly. Richard WM Jones has details here: http://rwmj.wordpress.com/2009/08/08/ocaml-internals-part-5-garbage-collection/ Can the GC distinguish between an array of ints and an array of pointers at run-time in order to avoid traversing all of the ints when trying to rewrite pointers? Not that I know of. The tag block does not have a documented reserved value to indicate that - there are values to indicate an unboxed float array, a string, and an array of opaque values, but not an integer array (unless the opaque value flag is set for integer arrays). Also, any idea what the maximum proportion of the running time of a program is spent doing this rewriting? For example, if you fill a float-float hash table with values does updating the pointers in the major heap account for a significant proportion of the total running time of the program? In my data analysis jobs (which wind up allocating quite large heaps), the compactor almost never (detectably) runs. Minor cycles and major slices are a much larger concern in my experience. I work around that by increasing the minor heap size to decrease minor heap thrashing (my general rule of thumb is that I want each work unit, whatever that may be, to fit in the minor heap). It could well be that other applications will have different characteristics that trigger more compactions. I cannot speak for those applications. Further, when I have huge floating-point data structures, I'm usually using bigarrays (not because I choose them over arrays, typically, but because such code in my work frequently has to interact with BLAS or SPARSKIT at some point). - Michael ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
RE: [Caml-list] How does OCaml update references when values are moved by the GC?
I just found some interesting statements made by others on this post about optimizing OCaml's write barrier: http://eigenclass.org/R2/writings/optimizing-caml_modify In the comments, Mauricio said that caml_modify (the write barrier) accounted for over 30% of the total running time of the whole application. -Original Message- From: Jon Harrop [mailto:j...@ffconsultancy.com] Sent: 30 October 2010 18:16 To: 'Damien Doligez'; 'caml-l...@inria.fr' Subject: RE: [Caml-list] How does OCaml update references when values are moved by the GC? I was hoping for a little more detail, of course. :-) How is the mapping from old to new pointers stored? Does the GC rewrite all of the thread-local stacks in series before allowing any of them to continue? Does the write barrier record pointers written into the major heap so only those specific locations are rewritten at minor heap collections but the entire major heap is rewritten upon compaction? Can the GC distinguish between an array of ints and an array of pointers at run-time in order to avoid traversing all of the ints when trying to rewrite pointers? Also, any idea what the maximum proportion of the running time of a program is spent doing this rewriting? For example, if you fill a float-float hash table with values does updating the pointers in the major heap account for a significant proportion of the total running time of the program? Cheers, Jon. -Original Message- From: caml-list-boun...@yquem.inria.fr [mailto:caml-list- boun...@yquem.inria.fr] On Behalf Of Damien Doligez Sent: 29 October 2010 08:48 To: caml users Subject: Re: [Caml-list] How does OCaml update references when values are moved by the GC? On 2010-10-28, at 23:48, Jon Harrop wrote: How does OCaml update references in the stacks and heap when values are moved by the GC? They are updated by the GC, of course. -- Damien ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
RE: [Caml-list] How does OCaml update references when values are moved by the GC?
Hi Michael, Thanks for the info. I stumbled upon Richard's excellent web page describing the internals of OCaml and the write barrier but it does not describe how the pointers actually get rewritten. Cheers, Jon. -Original Message- From: caml-list-boun...@yquem.inria.fr [mailto:caml-list- boun...@yquem.inria.fr] On Behalf Of Michael Ekstrand Sent: 30 October 2010 18:38 To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] How does OCaml update references when values are moved by the GC? On 10/30/2010 12:15 PM, Jon Harrop wrote: I was hoping for a little more detail, of course. :-) How is the mapping from old to new pointers stored? Does the GC rewrite all of the thread-local stacks in series before allowing any of them to continue? I imagine so. Does the write barrier record pointers written into the major heap so only those specific locations are rewritten at minor heap collections but the entire major heap is rewritten upon compaction? Yes. The runtime maintains a 'remembered set', a list of pointers from the major heap back to the minor heap. Maintaining this set is why mutable data can be expensive in OCaml - any time you store a pointer into a mutable field, the runtime must check whether the new link is from the major to the minor heap and update the refs list accordingly. Richard WM Jones has details here: http://rwmj.wordpress.com/2009/08/08/ocaml-internals-part-5-garbage- collection/ Can the GC distinguish between an array of ints and an array of pointers at run-time in order to avoid traversing all of the ints when trying to rewrite pointers? Not that I know of. The tag block does not have a documented reserved value to indicate that - there are values to indicate an unboxed float array, a string, and an array of opaque values, but not an integer array (unless the opaque value flag is set for integer arrays). Also, any idea what the maximum proportion of the running time of a program is spent doing this rewriting? For example, if you fill a float- float hash table with values does updating the pointers in the major heap account for a significant proportion of the total running time of the program? In my data analysis jobs (which wind up allocating quite large heaps), the compactor almost never (detectably) runs. Minor cycles and major slices are a much larger concern in my experience. I work around that by increasing the minor heap size to decrease minor heap thrashing (my general rule of thumb is that I want each work unit, whatever that may be, to fit in the minor heap). It could well be that other applications will have different characteristics that trigger more compactions. I cannot speak for those applications. Further, when I have huge floating-point data structures, I'm usually using bigarrays (not because I choose them over arrays, typically, but because such code in my work frequently has to interact with BLAS or SPARSKIT at some point). - Michael ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] How does OCaml update references when values are moved by the GC?
On 2010-10-28, at 23:48, Jon Harrop wrote: How does OCaml update references in the stacks and heap when values are moved by the GC? They are updated by the GC, of course. -- Damien ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
[Caml-list] How does OCaml update references when values are moved by the GC?
How does OCaml update references in the stacks and heap when values are moved by the GC? -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
