| Newsgroups |
gmane.comp.lang.ocaml.beginners |
| Message-ID |
<[email protected]> |
Replied inline.
On Monday, June 29, 2015 8:55 AM, "Gerd Stolpmann [email protected] [ocaml_beginners]" <[email protected]> wrote:
Am Montag, den 29.06.2015, 04:11 +0000 schrieb Kenneth Miller
[email protected] [ocaml_beginners]:
> Garbage collection "leaks" can be one of several, right? I'm sure you
> know, but I'll just describe a few here to make it clear what I'm
> saying. A program that uses a GC could leak in that it doesn't
> maintain it's data structures, so collection is untimely or
> impossible.
Right, you waste memory when your objects or values are reachable for
longer than strictly necessary. For example, when you put them into a
global data structure and forget to remove them after use. The GC cannot
help here, because it does not know what is intentional or not.I understand this part. Is there a way for me to help the GC distinguish in your example below with x1? That would be the general jest of the email as per title.
> But the GC itself could also be authored incorrectly-that's not good.
> Programs don't come generated from Coq very often, so I don't really
> trust them, but that's not what I'm saying here-I know the OCaml GC is
> very good.
There was a scientific review of the OCaml GC, and I guess we can assume
that the groundwork is correct. There could be implementation errors,
however, in particular in ocamlopt-generated code this is imaginable.
ocamlopt code needs to follow certain rules, and it is possible that
this goes wrong. Look at this:
let f arg =
let x1 = g arg in
let x2 = h x1 in
... (* x1 does not occur here *)
Assume x1 is a large value. The question is when exactly x1 is
considered as collectible. After computing x1 a pointer to this value
will be put onto the stack. ocamlopt informs the GC about that with
special descriptor table that there is a live value on the stack. The
danger is that x1 is considered as live for longer than needed, and this
can be tricky. Imagine the function goes on like:
let f arg =
let x1 = g arg in
let x2 = h x1 in
while not finished do
...
done;
exit 0
i.e. this function is actually the main program. If x1 is considered as
live for the duration of the while loop it cannot be collected, and for
the user this looks as if there was a memory leak. ocamlopt tries to get
this right and marks values like x1 as dead in the descriptor after the
last access, but there is a chance that this goes wrong (marking values
as live or dead collides to some degree with optimizations that change
the order of computations).
====="assume the groundwork is correct" -> Yes, I'm not questioning OCaml GC, just distinguishing what I'm saying to be clear."chance that this goes wrong" -> Agreed as well, subtle changes occur when we introduce optimization because preserving semantics very precisely is hard to begin with and almost no one machine checks anything.
> Well, if I'm wrong about this, then so is a good number of other very
> smart people. How does the GC know to collect a circularly linked
> list?
On the low level there are two ways of traversing the memory blocks.
Number 1: You just start with a pointer to the first block, add the
length of the block and get the next pointer, and so on. This way you
can iterate over _all_ memory blocks, and you visit both the logically
reachable blocks and the unreachable blocks.
Number 2: The GC maintains a list of pointers that it considers as live
without question (the so-called GC roots, e.g. global pointers, but also
pointers on the stack and in CPU registers currently needed). The
traversal now starts with the root blocks, and from there the GC follows
the pointers in the blocks, and recurses over this. There are special
bits in the memory blocks reserved for the GC where it can mark already
visited blocks (so when there is a cycle it follows the cycle only
once). Essentially, you get here a graph traversal of only the reachable
blocks.
A "mark and sweep" collector now first performs the graph traversal to
mark the reachable blocks (the mark phase), and after that it does a
full traversal over all blocks, and can now deallocate the unreachable
blocks (the sweep phase).
There are many difficulties in the implementation. The biggest one is
that the GC needs to be able to distinguish between pointers and other
data (in the graph traversal it only follows pointers and ignores any
other data). Note that this is the main reason why a precise GC is not
possible for old languages such as C.
> What tricks does Java use in order to implement such a data structure
> where the GC will find it?
> https://groups.google.com/forum/#!topic/comp.theory/4S0Jt721i6w
This is a quite funny discussion. The whole point is that languages need
to be designed to permit precise GCs, and this usually implies formal
restrictions of the allowed constructions. If these are missing (like
e.g. in C), you in deed run into the halting problem, because then you
cannot statically distinguish between pointers and other data. E.g. look
at this type declaration in C:
union foo {
char *p;
long d;
}
This is a union of a pointer p and data d. Depending on dynamic
conditions the programmer either assumes the former or latter. A GC
supporting this would run into complex problems (either you need extra
space for an invisible tag, or you need to predetermine future uses of
the union). The solution is not to support such untagged unions. (In C
it is even worse than this because you can intentionally treat pointers
as data, via casts, making it the programmer's choice.)
=====Ah! So you are distinguishing the specifics of the problem to allow it to become decidable. Ok ok, I am convinced. (This happens often btw, a category of problem is undecidable or too difficult to calculate but a very similar niche case is solvable and pragmatic.)
> In either case, my program is currently eating up so much memory that
> it crashes due to memory exhaustion. Let me explain my consumption
> scenario.
> I have a file, it's kind of big, just 300 MB. I read that file and
> translate that into a data structure that shouldn't really be all that
> big; +- a some bytes.
> I then iterate over the data structures that the file contains, and
> translate them; the final result wanted, couldn't be but at maximum 4
> to 8 times bigger. So, between 1.2 to 2.4 gigs additional. *Not* 20
> gigs. I don't know what I did wrong though because I wrote all of my
> code in a straight forward fashion; there's no undue complexity issue
> that I know of, the task is inherently linear in time and space, as is
> my code in my knowledge. So I really do care which specific definition
> of leak you apply; I presume that I'm doing something wrong with
> regards to how the GC would collect information and that there's
> something that I *can* improve. Because what you seem to be saying
> that the GC is perfect, it can always collect memory, therefore
> there's nothing I can do. Well if there's nothing I can do, I will be
> sad.
It is hard to say what goes wrong without knowing the code. It could be
that you unintentionally keep pointers alive that should be dead. It
could be that the chosen data structures are actually bigger than you
expect.
Regarding the latter, one option is to use the objsize library to
measure the bytes consumed by data.=====Thanks for the tip about objsize, I was looking for a way to learn how many actual bytes were taken up by my variables.
> Yeah, I was just thinking that List.map was heavy for me, because as I
> transform from list 1 to list 2, I do not need each element of one.
> One and two are each big, so I'd like to be able to free more
> frequently, to reduce the load overall.
List.map is nothing more than
let rec map f = function
[] -> []
| a::l -> let r = f a in r :: map f l
and it is easy to have your own specially crafted version of it that
omits elements not needed anymore.
Gerd
Thank you so so much! I thought initially that you possibly were being diminutive, but I can appreciate that you are indeed very helpful and kind :)
> Thanks so much Gerd! :)
>
> Gerd
>
> > I had an assignment once where we used a tree-set data structure to
> > manage indexes to another reference array for fast lookup. We had to
> > do exactly this.
> >
> >
> >
> >
> > On Sunday, June 28, 2015 9:17 AM, "Gerd Stolpmann
> > [email protected] [ocaml_beginners]"
> > <[email protected]> wrote:
> >
> >
> >
> >
> >
> > Am Samstag, den 27.06.2015, 17:06 +0000 schrieb Kenneth Miller
> > [email protected] [ocaml_beginners]:
> > >
> > > For operations like List.map, I would imagine that the what is
> > > actually occurring, is a new list of equal size is being
> constructed
> > > where an operation on the old map is happening for every element.
> I
> > > would like to know what the real implications are for the garbage
> > > collector, and how I can minimize the performance and memory
> impact.
> >
> > You cannot do anything, and you need not.
> >
> > > Things like List.append calculate a new list by constructing a
> copy.
> > > That's incredibly inefficient to me, both in the sense that each
> > > element afterward (time) needs to be copied, and in that more
> memory
> > > (space) is needed.
> > >
> > >
> > > In addition, is there a set of advice points that can be given to
> > make
> > > sure that the garbage collector will appropriately see what it
> needs
> > > to in order to free items? In java, everything is reference
> counted,
> >
> > No, this is not true. Java, like OCaml, uses at least a
> mark-and-sweep
> > collector (of course, this depends on the JVM used, and there is
> > normally even a generational collector). Reference-counting is a bad
> > choice for any higher-level language because it cannot detect cyclic
> > pointer chains, and these remain uncollected.
> >
> > > so if you want an object to be freed and you're maintaining it in
> a
> > > tree the lack of use of that object is better treated by going to
> > the
> > > tree and updating the node that references it to mark it null. In
> > this
> > > way, the garbage collector can collect the item that you were
> > pointing
> > > to.
> >
> > There is no need to do this (breaking cycles) in Java, and no need
> to
> > do
> > this in OCaml.
> >
> > > OCaml is a different animal though, and it doesn't use reference
> > > counting. There doesn't seem to me to be any simple go-to practice
> > in
> > > order to ensure that the GC will in fact collect an item that I
> know
> > > at the moment because it's operation is so different.
> >
> > The OCaml collector is fully automatic like the one in Java. Cycles
> > are
> > collected when the whole cycle becomes unreachable.
> >
> > Gerd
> >
> > [Non-text portions of this message have been removed]
> >
> >
> >
> >
> >
> >
> >
>
>
>
>
>
>
>
>
#yiv1826186394 #yiv1826186394 -- #yiv1826186394ygrp-mkp {border:1px solid #d8d8d8;font-family:Arial;margin:10px 0;padding:0 10px;}#yiv1826186394 #yiv1826186394ygrp-mkp hr {border:1px solid #d8d8d8;}#yiv1826186394 #yiv1826186394ygrp-mkp #yiv1826186394hd {color:#628c2a;font-size:85%;font-weight:700;line-height:122%;margin:10px 0;}#yiv1826186394 #yiv1826186394ygrp-mkp #yiv1826186394ads {margin-bottom:10px;}#yiv1826186394 #yiv1826186394ygrp-mkp .yiv1826186394ad {padding:0 0;}#yiv1826186394 #yiv1826186394ygrp-mkp .yiv1826186394ad p {margin:0;}#yiv1826186394 #yiv1826186394ygrp-mkp .yiv1826186394ad a {color:#0000ff;text-decoration:none;}#yiv1826186394 #yiv1826186394ygrp-sponsor #yiv1826186394ygrp-lc {font-family:Arial;}#yiv1826186394 #yiv1826186394ygrp-sponsor #yiv1826186394ygrp-lc #yiv1826186394hd {margin:10px 0px;font-weight:700;font-size:78%;line-height:122%;}#yiv1826186394 #yiv1826186394ygrp-sponsor #yiv1826186394ygrp-lc .yiv1826186394ad {margin-bottom:10px;padding:0 0;}#yiv1826186394 #yiv1826186394actions {font-family:Verdana;font-size:11px;padding:10px 0;}#yiv1826186394 #yiv1826186394activity {background-color:#e0ecee;float:left;font-family:Verdana;font-size:10px;padding:10px;}#yiv1826186394 #yiv1826186394activity span {font-weight:700;}#yiv1826186394 #yiv1826186394activity span:first-child {text-transform:uppercase;}#yiv1826186394 #yiv1826186394activity span a {color:#5085b6;text-decoration:none;}#yiv1826186394 #yiv1826186394activity span span {color:#ff7900;}#yiv1826186394 #yiv1826186394activity span .yiv1826186394underline {text-decoration:underline;}#yiv1826186394 .yiv1826186394attach {clear:both;display:table;font-family:Arial;font-size:12px;padding:10px 0;width:400px;}#yiv1826186394 .yiv1826186394attach div a {text-decoration:none;}#yiv1826186394 .yiv1826186394attach img {border:none;padding-right:5px;}#yiv1826186394 .yiv1826186394attach label {display:block;margin-bottom:5px;}#yiv1826186394 .yiv1826186394attach label a {text-decoration:none;}#yiv1826186394 blockquote {margin:0 0 0 4px;}#yiv1826186394 .yiv1826186394bold {font-family:Arial;font-size:13px;font-weight:700;}#yiv1826186394 .yiv1826186394bold a {text-decoration:none;}#yiv1826186394 dd.yiv1826186394last p a {font-family:Verdana;font-weight:700;}#yiv1826186394 dd.yiv1826186394last p span {margin-right:10px;font-family:Verdana;font-weight:700;}#yiv1826186394 dd.yiv1826186394last p span.yiv1826186394yshortcuts {margin-right:0;}#yiv1826186394 div.yiv1826186394attach-table div div a {text-decoration:none;}#yiv1826186394 div.yiv1826186394attach-table {width:400px;}#yiv1826186394 div.yiv1826186394file-title a, #yiv1826186394 div.yiv1826186394file-title a:active, #yiv1826186394 div.yiv1826186394file-title a:hover, #yiv1826186394 div.yiv1826186394file-title a:visited {text-decoration:none;}#yiv1826186394 div.yiv1826186394photo-title a, #yiv1826186394 div.yiv1826186394photo-title a:active, #yiv1826186394 div.yiv1826186394photo-title a:hover, #yiv1826186394 div.yiv1826186394photo-title a:visited {text-decoration:none;}#yiv1826186394 div#yiv1826186394ygrp-mlmsg #yiv1826186394ygrp-msg p a span.yiv1826186394yshortcuts {font-family:Verdana;font-size:10px;font-weight:normal;}#yiv1826186394 .yiv1826186394green {color:#628c2a;}#yiv1826186394 .yiv1826186394MsoNormal {margin:0 0 0 0;}#yiv1826186394 o {font-size:0;}#yiv1826186394 #yiv1826186394photos div {float:left;width:72px;}#yiv1826186394 #yiv1826186394photos div div {border:1px solid #666666;height:62px;overflow:hidden;width:62px;}#yiv1826186394 #yiv1826186394photos div label {color:#666666;font-size:10px;overflow:hidden;text-align:center;white-space:nowrap;width:64px;}#yiv1826186394 #yiv1826186394reco-category {font-size:77%;}#yiv1826186394 #yiv1826186394reco-desc {font-size:77%;}#yiv1826186394 .yiv1826186394replbq {margin:4px;}#yiv1826186394 #yiv1826186394ygrp-actbar div a:first-child {margin-right:2px;padding-right:5px;}#yiv1826186394 #yiv1826186394ygrp-mlmsg {font-size:13px;font-family:Arial, helvetica, clean, sans-serif;}#yiv1826186394 #yiv1826186394ygrp-mlmsg table {font-size:inherit;font:100%;}#yiv1826186394 #yiv1826186394ygrp-mlmsg select, #yiv1826186394 input, #yiv1826186394 textarea {font:99% Arial, Helvetica, clean, sans-serif;}#yiv1826186394 #yiv1826186394ygrp-mlmsg pre, #yiv1826186394 code {font:115% monospace;}#yiv1826186394 #yiv1826186394ygrp-mlmsg * {line-height:1.22em;}#yiv1826186394 #yiv1826186394ygrp-mlmsg #yiv1826186394logo {padding-bottom:10px;}#yiv1826186394 #yiv1826186394ygrp-msg p a {font-family:Verdana;}#yiv1826186394 #yiv1826186394ygrp-msg p#yiv1826186394attach-count span {color:#1E66AE;font-weight:700;}#yiv1826186394 #yiv1826186394ygrp-reco #yiv1826186394reco-head {color:#ff7900;font-weight:700;}#yiv1826186394 #yiv1826186394ygrp-reco {margin-bottom:20px;padding:0px;}#yiv1826186394 #yiv1826186394ygrp-sponsor #yiv1826186394ov li a {font-size:130%;text-decoration:none;}#yiv1826186394 #yiv1826186394ygrp-sponsor #yiv1826186394ov li {font-size:77%;list-style-type:square;padding:6px 0;}#yiv1826186394 #yiv1826186394ygrp-sponsor #yiv1826186394ov ul {margin:0;padding:0 0 0 8px;}#yiv1826186394 #yiv1826186394ygrp-text {font-family:Georgia;}#yiv1826186394 #yiv1826186394ygrp-text p {margin:0 0 1em 0;}#yiv1826186394 #yiv1826186394ygrp-text tt {font-size:120%;}#yiv1826186394 #yiv1826186394ygrp-vital ul li:last-child {border-right:none !important;}#yiv1826186394