The biggest problem I see is that creating an std::vector<Value> is inefficient for a number of reasons. Many new objects being creared, but also the Value objects add and remove themselves from the linked list every time.

What you probably want is to write a visit() function which takes a refptr argument and a Tag as input. While the GC is doing its thing, we don't need to actively track Value objects, because the program isn't running.

Ideally, we would also use tag bits in the object headers to store which objects were visited (mark bits), but you can use an unordered_set<refptr> for a first version if you want.

Some other remarks:

• what is the tags file?

• tests should probably all go under tests/gc

• vm.setHead(this); => make head a static member of the Value class, and make the VM class a friend of the Value class.

• We should rename the VM class to GC.

I was going to implement the visitor soon. The array was just an easy way in order to first understand what to do.

I'm not sure what the tags file is, I'll get rid of it in the next commit.

Oh yes, the static method is very good suggestion! Thanks :)

Comments:

void markValues(Value* root) => you should probably use a Value&.

void mark() { => the humanity! semicolons on their own line.

void Value::unsetMark() => I would rename this to clearMark. Totally a nitpick.

You're missing something here:
https://github.com/zetavm/zetavm/pull/80/files#diff-14e33e1ac98adcf7ec27bee50b2b5dbbR101

Even if this->prev is NULL, you still need to set this->next->prev = NULL.

Also, I would rename the VM class to GC, since that is memory allocation is really all it is handling.

The most obvious flaw I see is that the Value class is missing a copy constructor and assignment operator:
http://www.fredosaurus.com/notes-cpp/oop-condestructors/copyconstructors.html

Linking you again to the implementation I made for Higgs, which implements all the list management in the assignment operator:
https://github.com/higgsjs/Higgs/blob/master/source/runtime/gc.d#L60

The assignment operator and copy constructor are needed, because otherwise the prev and next pointers will be copied when an assignment happens, which is not what we want.

Progressing very well :)

@Maaarcocr @krypt-n Made this fix following our discussion. This might fix the bug you were running into (hopefully): a7e9430

That should fix the first of the issues that valgrind showed, pushVal still uses operator= on potentially uninitialized memory though.

@krypt-n Ok noted, will take a look at that too 👍

Rebasing my latest changes onto master make all the tests pass! 😄 Thanks @krypt-n and @maximecb for the help. I still need to do some more work to better tests that everything is actually fine and also I still need to make the GC understand that when it sweeps something it has to decrease allocated variable.

@Maaarcocr it passes? Awesome.

Regarding testing, I put a bunch of GC torture tests I had written for Higgs in:
https://github.com/zetavm/zetavm/tree/master/tests/gc

They're written in JavaScript, so we would need to change some things. They also rely on some higgs-specific primitives to force garbage collections to happen more often. We could add similar things to Zeta, or add command-line arguments to make the heap size artificially small. We need to do a really thorough job with testing, because GC bugs can easily remain hidden for a long time.

Oh, one thing we might want to do is, when compiled with assertions, write non-zero bytes over memory before calling free. That will basically force things to crash/fail if an object that has been freed is still in use.

@Maaarcocr do you need help porting the GC tests to Plush? If you want, I can start working on that.

@maximecb that would be lovely 😄 in the meanwhile I'll make sure that the variable holding the amount of memory allocated get reduced on sweep.

@Maaarcocr I added a vm.get_gc_count() function for you to implement. This is useful for GC tests: 7dac602

Ok. Ported a second test, and added another function: vm.gc_collect(), this will serve to manually trigger a collection for testing.

@maximecb we are not actually passing the tests. I did run the tests with free commented out. I'm so so sorry for this.

I will implement the functions that you are adding 👍

@Maaarcocr don't panic. I believe in you :D