I haven't looked at the code, but I would be surprised if this turns out to be a GC issue. Three things seem to be going on. Let me explain what I'm thinking.

LIVENESS

All of the vectors that are getting allocated here are the same size. In both tests, there are *two* vectors alive in memory in the steady state. This is true because at the moment of allocation, the *previous* vector is still referenced by vvv. The newly allocated vector will eventually be assigned to vvv when the call to MAKE-VECTOR returns, but there is a window of time during the allocation where that has not yet occurred. So in particular, the *previous* vector allocated during the GC that is triggered by the *current* vector allocation.

Vectors are not allocated from a "large object space" in TinyScheme; they require contiguous space in the primary heap (this was at one time something I intended to fix). This means that a large block of contiguous free space is required in order for an array allocation to be possible. This means, in turn, that a single cons cell in the wrong place can make array allocation impossible.

NON-RELOCATION

The TinyScheme GC is a non-relocating GC. Most of the time this is fine, because almost every object allocated by TinyScheme is a cons cell. It becomes a problem when vectors are being allocated. If a single CONS cell sits in the middle of some big block of storage, the TinyScheme GC cannot move it out of the way in order to allocate a vector that would otherwise fit.

While there is no other obvious allocation going on in test2.scm, the implementation of TinyScheme constructs its stack out of cons cells that are allocated from the heap. This means that the calls to REMAINDER, BEGIN, WRITE, and NEWLINE are actually allocating operations. The effect of this is that the locations of two live vectors are probably not always the same. There is some variance, because depending on the actual heap size being used it is possible that GC is not being triggered on every array allocation.

When these three issues (two live arrays, CONS allocation, and non-relocation), it is *very* possible that the vectors and cons cells in the heap are getting allocated in oddly arranged locations in the heap, and that just a few of those CONS cells are dangling. Eventually, you have enough dangling CONS cells running around that no contiguous space exists in the heap to support allocation of the next vector.

IMPLEMENTATION OF DO

I do not recall how DO is implemented in TinyScheme. If it is a macro (as I suspect) that gets turned into a tail-recursive LAMBDA, or if the internal implementation operates in that sort of way, that would account for why CONS cells related to procedure calls are getting retained. Do we have a way to induce GC and get a dump of the number of heap words in use? If that number, computed immediately after the SET!, is rising, then the problem lies in either DO or WRITE.


The first place I would look in the code is the implementation of DO, just to check if a retained CONS cell may be happening there.

The second place I would look is the implementation of WRITE. There used to be an ungodly number of GC-related bugs in that part of the code, several of which would be triggered by int->string conversion.

I would try nulling out VVV - or at least setting it to #() - before calling make-vector. If both tests pass with that change, then GC is working correctly and the problem is that we have live islands in the heap. That will at least confirm where we need to be looking.

But more than anything, I would rerun this under a debugger with a breakpoint on the line that prints "No memory", and confirm that we're actually inside make-vector. I'm wondering if the internal implementation of WRITE may be leaking.


In the long term, the right solution to all of this is to implement relocating GC. That would be a fairly major change to the TinyScheme library API, because it would require a different API from the standpoint of C code.

Kevin: is TinyScheme being used actively enough at this point to make that sort of reimplementation worth considering?


Jonathan




On Wed, Jan 1, 2014 at 11:51 AM, Kevin Cozens <kevin@ve3syb.ca> wrote:
On 14-01-01 12:34 PM, Sanel Zukan wrote:> On 12/28/13, Andrea Rossetti wrote:
 >>    In the testcases I'm basically doing
 >> (set! vvv (make-vector ...)) several times,
 >> I expected that garbage collection would
 >> reclaim the previous vectors' memory.
 >
 > Looks like a bug in GC, because these vectors should be
 > collected. From my tests, even putting explicit collection with '(gc)'
 > as part of loop will not help.

I took a quick look at this but didn't see anything obvious. I'll take a
further look at this once I finish the documentation I'm working on for
another project.

--
Cheers!

Kevin.

http://www.ve3syb.ca/           |"Nerds make the shiny things that distract
Owner of Elecraft K2 #2172      | the mouth-breathers, and that's why we're
                                 | powerful!"
#include <disclaimer/favourite> |             --Chris Hardwick

------------------------------------------------------------------------------
Rapidly troubleshoot problems before they affect your business. Most IT
organizations don't have a clear picture of how application performance
affects their revenue. With AppDynamics, you get 100% visibility into your
Java,.NET, & PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro!
http://pubads.g.doubleclick.net/gampad/clk?id=84349831&iu=/4140/ostg.clktrk
_______________________________________________
Tinyscheme-issues mailing list
Tinyscheme-issues@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/tinyscheme-issues