<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div apple-content-edited="true"><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><div style="word-wrap: break-word; -khtml-nbsp-mode: space; -khtml-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><div>On 17 Nov 2008, at 03:35, Jay wrote:</div></span></span></span></span></span></span></span></span></div></span></div><div><br class="Apple-interchange-newline"><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div class="hmmessage" style="font-size: 10pt; font-family: Verdana; ">1meg pages weren't large enough to avoid running out of memory.</div></span></blockquote><div><br></div><div>Is this still the sidespan array problem?</div><br><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div class="hmmessage" style="font-size: 10pt; font-family: Verdana; ">Any thoughts on using the boehm-gc?</div></span></blockquote><div><br></div><div>Hell no.</div><br><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div class="hmmessage" style="font-size: 10pt; font-family: Verdana; ">I don't know if it is compacting.</div></span></blockquote><div><br></div><div>Indeed, Boehm's collector does not do compaction. Also, Boehm's is fully conservative ("ambiguous-roots + ambiguous heap"), though it is possible to configure it to use precise heap information (which CM3 does provide).</div><br><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div class="hmmessage" style="font-size: 10pt; font-family: Verdana; ">Or even generational.</div></span></blockquote><div><br></div><div>It is generational, and has a parallel collection mode, but it is not concurrent like ours (we have a better chance of scaling on SMPs). Our collector will soon also be "on-the-fly", which means we won't need to have a stop-the-world phase where all the threads are stopped at the same time to initiate GC. Instead, we will simply signal threads one at a time to prepare for GC.</div><br><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div class="hmmessage" style="font-size: 10pt; font-family: Verdana; ">Or anything about it really, just that it is much ported and presumably well maintained, since it is part of "gcc", part of the gcc Java support.</div></span></blockquote><div><br></div><div>Our collector is much ported and well-maintained too! ;-) Seriously, I am quite sure we have no collector bugs currently (it has been running reliably for many years now). The problems you are encountering are porting issues and not bugs in the collector. Also, the current collector is written in Modula-3, and nicely integrated with the Modula-3 object model and run-time. There is a *huge* amount to be said for eating your own dog-food by writing the collector in Modula-3. There is *no* good reason to step outside Modula-3 to C as would be needed for Boehm GC.</div><br><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div class="hmmessage" style="font-size: 10pt; font-family: Verdana; ">Hm... I assume the right data structure here is a multi level array, that you index by picking off progressively less significant bits of an address (or page number) just like the hardware page tables for virtual memory (but without the perf benefits of a cache and using physical addresses after the first level).<br>When an entire level is at the same state, due to skipping a large span, you just have one shared entry for all of them, major savings.</div></span></blockquote><div><br></div><div>Right. I have this partially implemented already.</div><br><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div class="hmmessage" style="font-size: 10pt; font-family: Verdana; ">Either that, or a binary searched array where you only store entries for state changes.<br>You'd use like the STL's upper_bound/lower_bound/equal_range functions, that is, really the same thing as bsearch, but when an entry isn't found, you return where it would be inserted, which is like the last place you looked before giving up.</div></span></blockquote><div><br></div><div>I'm concerned about the lookup costs for this.</div><br><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div class="hmmessage" style="font-size: 10pt; font-family: Verdana; ">It might be worth confirming "that I'm not crazy" -- that mmap behaves this way for other people, or that skimming its code suggests it is not surprising. Could be related to how malloc works also.</div></span></blockquote><div><br></div><div>Are there hints that can be passed to mmap on that platform to cause less scattered mappings? It is odd that sbrk is less scattered, since it must also bottom out at mmap, but perhaps it is trying to maintain a reasonably compact allocation below the "brk".</div><br><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div class="hmmessage" style="font-size: 10pt; font-family: Verdana; "><br> <br> - Jay<br><br><hr id="stopSpelling"><br>From:<span class="Apple-converted-space"> </span><a href="mailto:hosking@cs.purdue.edu">hosking@cs.purdue.edu</a><br>To:<span class="Apple-converted-space"> </span><a href="mailto:jay.krell@cornell.edu">jay.krell@cornell.edu</a><br>Date: Sun, 16 Nov 2008 20:14:55 -0600<br>CC:<span class="Apple-converted-space"> </span><a href="mailto:m3devel@elegosoft.com">m3devel@elegosoft.com</a><br>Subject: Re: [M3devel] duplicated code?<br><br><br><div><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div style="word-wrap: break-word; "><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div>On 16 Nov 2008, at 10:18, Jay wrote:</div></span></span></span></span></span></span></span></span></div></span></div><div><br class="EC_Apple-interchange-newline"><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">Er, the large allocation does come from the gc itself.</div></span></blockquote><div><br></div><div>What's being allocated? The side array should not be too huge.</div><br><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">Tony, is there is an assumption that the heap is contiguous?<br>That calls to RTOS.GetMemory return adjacent addresses?</div></span></blockquote><div><br></div><div>No assumption.</div><br><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">This code allocates a large array:<br> <br> IF desc = NIL OR newSideSpan # NUMBER(desc^) THEN<br> WITH newDesc = NEW(UNTRACED REF ARRAY OF Desc, newSideSpan) DO<br><br>I'll know more shortly.<br> <br>I guess..it looks like the heap can be discontiguous, but<br>we do record keeping for what it all spans.</div></span></blockquote><div><br></div><div>Correct.</div><br><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">The comments say:<br>(* The array desc and the global variables p0, and p1 describe the pages<br> that are part of the traced heap. Either p0 and p1 are equal to Nil and<br> no pages are allocated; or both are valid pages and page p is allocated<br> iff<br>| p0 <= p < p1<br>| AND desc[p - p0] != Unallocated<br><br> <br>Hm..<br> <br>Grow (0x44000) => 0x2b1e45256000 total: 1.5M<br>GetUntracedOpenArray(0x1a80)<br> span: 6.6M density: 24%<br>stubgen: Processing RemoteView.T<br>GetUntracedOpenArray(0x3f0)<br>t1:0xc<br>t2:0xa<br>t3:0x1<br>Grow (0x52000) => 0x2aaaaaaab000 total: 1.8M<br>GetUntracedOpenArray(0x1ce69fc8)<br> <br>I have GetUntracedOpenArray<strong><span class="EC_Apple-converted-space"> </span></strong>printing how many bytes it is asked for.<br>t1,t2,t3 are just the lengths of the strings being concatented.<br>Grow(x)=>y means Grow allocated x bytes at address y.<br> <br>So now, these two addresses 0x2aaaaaaab000 and 0x2b1e45256000 are very far apart, like 400gig.<br>And it seems the heap allocator wants to allocate an array to describe the pages.</div></span></blockquote><div><br></div><div>Ah, yes, that is most unfortunate.</div><div><br></div><br><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">Hm. Page size is no longer tied to the underlying system -- no longer vm-tied gc.<br>Perhaps perhaps blowing it up, to say, 1meg, will address this?</div></span></blockquote><div><br></div><div>I am working on minimizing the need for the global array, but we do need something that can be easily indexed like this. Perhaps we need to pass a hint to RTOS.GetMemory that will try to allocate its regions close together.</div><br><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">But really, an array to describe pages spanning the results of separate memory allocations, seems wrong.<br>A sparser data structure would be good, that could describe arbitrary sized runs of pages as being in the same state.</div></span></blockquote><div><br></div><div>Indeed. As mentioned above, I am working to eliminate the need for this. Code that starts us on this path will be checked in within a day or so.</div><br><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; "> - Jay<br><br><br><hr id="EC_stopSpelling"><br>From:<span class="EC_Apple-converted-space"> </span><a href="mailto:jay.krell@cornell.edu">jay.krell@cornell.edu</a><br>To:<span class="EC_Apple-converted-space"> </span><a href="mailto:m3devel@elegosoft.com">m3devel@elegosoft.com</a><br>Date: Sun, 16 Nov 2008 15:31:25 +0000<br>Subject: [M3devel] duplicated code?<br><br>Anyone want to clean up this duplicity?<br> <br> <br>D:\dev2\cm3.2>dir /s/b asttotype.m3 StubCode.m3<br>D:\dev2\cm3.2\m3-comm\sharedobjgen\src\AstToType.m3<br>D:\dev2\cm3.2\m3-comm\stubgen\src\AstToType.m3<br>D:\dev2\cm3.2\m3-db\stablegen\src\AstToType.m3<br>D:\dev2\cm3.2\m3-comm\sharedobjgen\src\StubCode.m3<br>D:\dev2\cm3.2\m3-comm\stubgen\src\StubCode.m3<br><br> <br>somewhere in there, AMD64_LINUX tries to allocate a lot of memory, and fails<br>either there or soon thereafter.<br>The garbage collector is working.<br> <br> - Jay<br><br><br><br><br><br><br></div></span></blockquote></div><br></div></span><br class="Apple-interchange-newline"></blockquote></div><br></body></html>