Compacting GC?

A neat trick is that directed acyclic graphs, the run-time structures egel programs manipulate, do allow for an efficient in-place compacting garbage collector. Which is what I am tempted to write at the moment.

Looks like sectorlisp uses that idea.

For future reference

cmake -DCMAKE_BUILD_TYPE=PROFILE ..




egel -e "import \"prelude.eg\";; using System;; using List;; foldl (+) 0 (from_to 0 1000000)"

/opt/homebrew/Cellar/llvm@12/12.0.1_1/bin/llvm-profdata merge -sparse default.profraw -o default.profdata

/opt/homebrew/Cellar/llvm@12/12.0.1_1/bin/llvm-profdata show -all-functions default.profraw

Testing 1.. 2.. 3..

// memory test

#include <memory>

#include <new>

#include <type_traits>

#include <utility>

// model values = atom int | array value*

static constexpr size_t roundup(size_t x, size_t m)

{

    return x % m == 0 ? x : (x + m) / m * m;

};

class Value;

typedef std::shared_ptr<Value> ValuePtr;

class Value {

public:

    Value() = default;

    virtual ~Value() {

    }

};

class Atom: public Value {

public:

    Atom(const int v): _value(v) {

    }

    virtual ~Atom() {

    }

    static ValuePtr create(const int v) {

        return std::shared_ptr<Atom>(new Atom(v));

    }

private:

    int _value;

};

struct ValueField {

    ValuePtr _value;

};

class Array: public Value {

public:

    Array() = default;

    virtual ~Array() {

        while (_size-- > 0)

            std::addressof(operator[](_size))->~ValueField();

    }

    ValueField &operator[](size_t i) {

        char *r0 = reinterpret_cast<char *>(this) + roundup(sizeof(*this), alignof(ValueField));

        ValueField *t0 = reinterpret_cast<ValueField *>(r0);

        return t0[i];

    }

    ValueField &at(size_t i) {

        if (i >= _size)

            throw std::out_of_range("duuude!");

        return operator[](i);

    }

    static ValuePtr create(size_t _sizes) {

        return std::shared_ptr<Array>(new(_sizes) Array(_sizes));

    }

    void *operator new(size_t count, size_t _sizes) {

        auto z = roundup(count, alignof(ValueField)) + sizeof(ValueField) * _sizes;

        return ::operator new(z);

    }

    void operator delete(void *x) {

        ::operator delete(x);

    }

    // not implemented for brevity reasons.

    // Also, it would have to handle (if only to throw an exception)

    // if someone attempted to move an Array(30) into an Array(20)

    /*

    Array(Array &&) = delete;

    void operator=(Array &&) = delete;

    */

private:

    Array(size_t n) {

        for (_size = 0; _size < n; ++_size)

            new(std::addressof(operator[](_size))) ValueField;

    }

    size_t _size = 0;

};

int main()

{

    Array fixed;

    auto flex = Array::create(20);

    // (*flex)[1]._value = 42;

}

Serialization

 I am more pondering than writing code at the moment. In order to get to mobile code, I need to be able to serialize, in order to serialize I need some representation independent of the runtime. Because when the serialized graph isn't independent it might corrupt the runtime when it is being loaded among other things.

It looks like I have little choice but to copy almost the complete runtime hierarchy into a serialization format.  Which sounds worse than it is, only four primitive types, arrays, then combinators. And then the combinators are the problem. Data is easy, bytecode can be (dis-)assembled, internal objects are always loaded, then the problem is externally defined C++ combinators. Or I do everything on a per-module basis, that's unclear at the moment.

Then there's the question of what goes into the graph. Say I have a bytecode combinator, do I only write the symbol or also the bytecode? No idea yet but I am tempted to have that separate from the graph.

The good part, serialization makes me think hard about how the interpreter is organized. The bad part, now I want to refactor again and get rid of some warts (macros), introduce namespaces, and employ c++20 modules. It's annoying to code against old code.

Also, pretty sure I am going to write the mobile code on top of grpc, which brings other problems since that's a client/server architecture and I want bidirectionality and more general a cloud of nodes which can talk to each other. But ah well, not everything is perfect. Maybe I'll just use it anyway.

Slides

 I felt like writing so I made some technical slides.