| Newsgroups |
gmane.comp.lang.ocaml.beginners |
| Message-ID |
<[email protected]> |
Replied inline.
On Sunday, June 28, 2015 8:26 PM, "Gerd Stolpmann [email protected] [ocaml_beginners]" <[email protected]> wrote:
Am Sonntag, den 28.06.2015, 17:56 +0000 schrieb Kenneth Miller
[email protected] [ocaml_beginners]:
>
> Everything that you've said sounds very counter-intuitive to what I've
> read and learned so far. If there's nothing I can do about my ocaml
> program running until there is no more memory or swap before dying
> that would be abysmally sad.
I don't know from where you have your knowledge, but it is definitely
wrong. Java has always had a fully automatic garbage collector: An
object is collected when it cannot be reached by any pointer. The same
holds for OCaml, only substitute the word "value" for "object".
And this is not "sad". You have the guarantee that all unused memory is
really reclaimed. Why do you want to improve something that is already
perfect?
| Cannot be reached by any pointer...Two things - it's clear now that we're talking about the same thing. The GC is correct in it's implementation, but that doesn't mean that users won't do something like leave objects around that are referenced by one or more data structures, hence my example. The second thing is I wasn't very clear about what I learned and what was new-I didn't know what algorithm Java used, only what was pertinent in order to make my Java programs effective.Also, I'm usually pretty bad at speak precisely, and sometimes it just takes several rounds in order to elicit the knowledge that I have and what I'm lacking. So when I say leak, I know that there's a clear difference in leak between a collected program and a C program, and someone might also distinguish several different scenarios of "leak" in a collected program. In a C/++ program, a leak is any one of a myriad of ways in which resources aren't effectively released-that doesn't just mean lack of there being a free; logical bugs, concurrency issues, all manner of wild stuff can go wrong in unsafe languages. I've been writing exploit payloads for years, so I'm not even going down that long pipe.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. 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.
> From what I understand about garbage collection in the general
> problem, it's undecidable;
I guess you also don't know what the word "undecidable" means. (A
problem is called undecidable when there is no algorithm that can answer
the problem positively or negatively in a finite number of steps - note
that there is also a strict formal definition).I have a degree, and I'm not an idiot-I know what it means. But thanks, your explanation was clear and without undue negative connotation.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? 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
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.
> garbage collectors aim just for optimal performance and good behavior
> in most cases.
No. There is a class known as precise collectors, and these find all
unused memory and reclaim it. It is true that there also imprecise
collectors (e.g. using reference counting or conservative collection),
but these are not state of the art anymore.
I would agree specifically to the idea that "unused" is a gotcha here; if you maintain your references as you should, the GC will find that and free the memory appropriately. That sounds to be decidable.
> So then if there are even memory profilers for ocaml there must be
> some corrective action that can be taken, that's what I need to know.
The memory profilers do not exist for finding leaks. There are no leaks
in the usual sense that memory is completely forgotten about.
Nevertheless, you sometimes want to know how much bytes you need for
your data structures, and if you want to measure this after running a
complex program for a while a memory profiler can be handy.My program leaks, so I don't really have an interest in discussing profilers true purpose, only what I will use them for.
> The pervasives library just logged a leak-they will do something
> about that. There has to be some kind of general practice that will
> allow me to keep moving forward.
I don't know to which bug you refer. The pervasives library has also a
part implemented in C.Just saying I saw something recently (can't find it now), so there will be a patch out.
> Some of the other stuff about the JVM's GC you say is not what I've
> heard so far (JVM GC use mark and sweep?), so wouldn't dispute what
> algorithm it uses until I've read about it in depth. Java not using
> reference counting is precisely the opposite of what I've learned.
Just google for it. E.g. I found
http://www.cubrid.org/blog/dev-platform/understanding-java-garbage-collection/
> Suppose I have an array which stores null or a reference to an
> object. If I finish working with an object, do I not mark any
> reference null in order to ensure that it gets garbage collected?
Well, the reason for this is not to ensure _that_ it is garbage
collected, but to get more control _when_ it is collected. If you leave
the unused objects in the array, they will first get unreachable when
the pointers are overwritten in the array or when the array is
completely dropped. I'd bother with this only in special situations, in
particular when the array is long-living and you'd spend a lot of memory
for too long.Right, agreed.
As your initial question was about OCaml lists, and List.map. As this
function always creates a new list, the old list gets out of use
immediately, and will be collected soon. This is very different from a
long-living array.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.
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]
>
>
>
>
>
>
>
#yiv7537605681 #yiv7537605681 -- #yiv7537605681ygrp-mkp {border:1px solid #d8d8d8;font-family:Arial;margin:10px 0;padding:0 10px;}#yiv7537605681 #yiv7537605681ygrp-mkp hr {border:1px solid #d8d8d8;}#yiv7537605681 #yiv7537605681ygrp-mkp #yiv7537605681hd {color:#628c2a;font-size:85%;font-weight:700;line-height:122%;margin:10px 0;}#yiv7537605681 #yiv7537605681ygrp-mkp #yiv7537605681ads {margin-bottom:10px;}#yiv7537605681 #yiv7537605681ygrp-mkp .yiv7537605681ad {padding:0 0;}#yiv7537605681 #yiv7537605681ygrp-mkp .yiv7537605681ad p {margin:0;}#yiv7537605681 #yiv7537605681ygrp-mkp .yiv7537605681ad a {color:#0000ff;text-decoration:none;}#yiv7537605681 #yiv7537605681ygrp-sponsor #yiv7537605681ygrp-lc {font-family:Arial;}#yiv7537605681 #yiv7537605681ygrp-sponsor #yiv7537605681ygrp-lc #yiv7537605681hd {margin:10px 0px;font-weight:700;font-size:78%;line-height:122%;}#yiv7537605681 #yiv7537605681ygrp-sponsor #yiv7537605681ygrp-lc .yiv7537605681ad {margin-bottom:10px;padding:0 0;}#yiv7537605681 #yiv7537605681actions {font-family:Verdana;font-size:11px;padding:10px 0;}#yiv7537605681 #yiv7537605681activity {background-color:#e0ecee;float:left;font-family:Verdana;font-size:10px;padding:10px;}#yiv7537605681 #yiv7537605681activity span {font-weight:700;}#yiv7537605681 #yiv7537605681activity span:first-child {text-transform:uppercase;}#yiv7537605681 #yiv7537605681activity span a {color:#5085b6;text-decoration:none;}#yiv7537605681 #yiv7537605681activity span span {color:#ff7900;}#yiv7537605681 #yiv7537605681activity span .yiv7537605681underline {text-decoration:underline;}#yiv7537605681 .yiv7537605681attach {clear:both;display:table;font-family:Arial;font-size:12px;padding:10px 0;width:400px;}#yiv7537605681 .yiv7537605681attach div a {text-decoration:none;}#yiv7537605681 .yiv7537605681attach img {border:none;padding-right:5px;}#yiv7537605681 .yiv7537605681attach label {display:block;margin-bottom:5px;}#yiv7537605681 .yiv7537605681attach label a {text-decoration:none;}#yiv7537605681 blockquote {margin:0 0 0 4px;}#yiv7537605681 .yiv7537605681bold {font-family:Arial;font-size:13px;font-weight:700;}#yiv7537605681 .yiv7537605681bold a {text-decoration:none;}#yiv7537605681 dd.yiv7537605681last p a {font-family:Verdana;font-weight:700;}#yiv7537605681 dd.yiv7537605681last p span {margin-right:10px;font-family:Verdana;font-weight:700;}#yiv7537605681 dd.yiv7537605681last p span.yiv7537605681yshortcuts {margin-right:0;}#yiv7537605681 div.yiv7537605681attach-table div div a {text-decoration:none;}#yiv7537605681 div.yiv7537605681attach-table {width:400px;}#yiv7537605681 div.yiv7537605681file-title a, #yiv7537605681 div.yiv7537605681file-title a:active, #yiv7537605681 div.yiv7537605681file-title a:hover, #yiv7537605681 div.yiv7537605681file-title a:visited {text-decoration:none;}#yiv7537605681 div.yiv7537605681photo-title a, #yiv7537605681 div.yiv7537605681photo-title a:active, #yiv7537605681 div.yiv7537605681photo-title a:hover, #yiv7537605681 div.yiv7537605681photo-title a:visited {text-decoration:none;}#yiv7537605681 div#yiv7537605681ygrp-mlmsg #yiv7537605681ygrp-msg p a span.yiv7537605681yshortcuts {font-family:Verdana;font-size:10px;font-weight:normal;}#yiv7537605681 .yiv7537605681green {color:#628c2a;}#yiv7537605681 .yiv7537605681MsoNormal {margin:0 0 0 0;}#yiv7537605681 o {font-size:0;}#yiv7537605681 #yiv7537605681photos div {float:left;width:72px;}#yiv7537605681 #yiv7537605681photos div div {border:1px solid #666666;height:62px;overflow:hidden;width:62px;}#yiv7537605681 #yiv7537605681photos div label {color:#666666;font-size:10px;overflow:hidden;text-align:center;white-space:nowrap;width:64px;}#yiv7537605681 #yiv7537605681reco-category {font-size:77%;}#yiv7537605681 #yiv7537605681reco-desc {font-size:77%;}#yiv7537605681 .yiv7537605681replbq {margin:4px;}#yiv7537605681 #yiv7537605681ygrp-actbar div a:first-child {margin-right:2px;padding-right:5px;}#yiv7537605681 #yiv7537605681ygrp-mlmsg {font-size:13px;font-family:Arial, helvetica, clean, sans-serif;}#yiv7537605681 #yiv7537605681ygrp-mlmsg table {font-size:inherit;font:100%;}#yiv7537605681 #yiv7537605681ygrp-mlmsg select, #yiv7537605681 input, #yiv7537605681 textarea {font:99% Arial, Helvetica, clean, sans-serif;}#yiv7537605681 #yiv7537605681ygrp-mlmsg pre, #yiv7537605681 code {font:115% monospace;}#yiv7537605681 #yiv7537605681ygrp-mlmsg * {line-height:1.22em;}#yiv7537605681 #yiv7537605681ygrp-mlmsg #yiv7537605681logo {padding-bottom:10px;}#yiv7537605681 #yiv7537605681ygrp-msg p a {font-family:Verdana;}#yiv7537605681 #yiv7537605681ygrp-msg p#yiv7537605681attach-count span {color:#1E66AE;font-weight:700;}#yiv7537605681 #yiv7537605681ygrp-reco #yiv7537605681reco-head {color:#ff7900;font-weight:700;}#yiv7537605681 #yiv7537605681ygrp-reco {margin-bottom:20px;padding:0px;}#yiv7537605681 #yiv7537605681ygrp-sponsor #yiv7537605681ov li a {font-size:130%;text-decoration:none;}#yiv7537605681 #yiv7537605681ygrp-sponsor #yiv7537605681ov li {font-size:77%;list-style-type:square;padding:6px 0;}#yiv7537605681 #yiv7537605681ygrp-sponsor #yiv7537605681ov ul {margin:0;padding:0 0 0 8px;}#yiv7537605681 #yiv7537605681ygrp-text {font-family:Georgia;}#yiv7537605681 #yiv7537605681ygrp-text p {margin:0 0 1em 0;}#yiv7537605681 #yiv7537605681ygrp-text tt {font-size:120%;}#yiv7537605681 #yiv7537605681ygrp-vital ul li:last-child {border-right:none !important;}#yiv7537605681