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] Re: Generalized Algebraic Datatypes
On 30/10/2010 1:14 AM, Jacques Garrigue wrote: On 2010/10/30, at 8:01, Jacques Le Normand wrote: Note that, as in Jacques's examples, the constructor function was not curryfied. (type t = A of bool * int) would generate a function (A : bool * int - t). Actually, curryfied constructors are not allowed, so this is not accepted. (Existential types are allowed, which may have confused the other Jacques) I was not confused at all. Jacques Carette PS: ;-) ___ 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] Re: Generalized Algebraic Datatypes
Hi, While this does make sense in Haskell, in Ocaml it feels a bit out of place, because you cannot, for example, partially apply a type constructor. The types above don't allow partial applications either. They use the OCaml/SML style of constructors were partial application is not possible because the various arguments are not provided in a curried way. That was precisely my point (I think you may have misunderstood what I said). In Ocaml, whenever you see a curried type declaration you can safely assume that the constructors may be partially applied. The GADT syntax under discussion breaks this assumption; hence my reticence. Cheers, Dario Teixeira ___ 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] Re: Generalized Algebraic Datatypes
Hi,
If the risk of confusion with constructors-as-functions is deemed
problematic, a syntax like
App of ('a - 'b) t * 'a t : 'b t
seems OK too.
Actually this would have the advantage of allowing the scope of
existential variables to be explicit. I.e. one could write
App of 'a. ('a - 'b) t * 'a t : 'b t
I find this new syntax preferable too. As I just mentioned in my reply to
Stefan Monnier, my main criticism to the currently implemented GADT syntax
is that type constructors are declared in a curried way, despite the fact
that they cannot actually be partially applied. This breaks an assumption
that is otherwise consistent throughout the language, and I think we can
all agree that adding caveats and exceptions to a language specification
is something that should be avoided as much as possible (and is often the
symptom of a bad specification).
Best regards,
Dario Teixeira
___
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
