A bug in my code

[bearophile]

Jarrett Billingsley:

> ..Or just, you know, arrays.  Since that's exactly what they are.

Right, but I don't want to use them because dynamic arrays always set their memory to .init. The point of that data structure is to have a fast allocation too (it's not necessary to clean it if you know how many items you are using and the items don't contain a GC-managed pointer (see at the bottom of this post)).


> > addRoot(new_block.next);
> > addRoot(new_block.data);
> Adding roots is certainly possible but it's not very elegant.

It's not just inelegant: it seems the program doesn't work yet:

import std.gc: malloc, hasNoPointers, addRoot, fullCollect, hasPointers;
import std.stdio: writefln;

int min(int a, int b) {
    return a <= b ? a : b;
}


class IntStack {
    struct Block {
        int len;
        Block* next;
        int* data;
    }

    Block* list_head, list_tail;
    int total_len;
    int used_last_block; // how many items are used in the last (tail) block


    this() {
        this.list_head = block_alloc(4);
        this.list_tail = list_head;
    }


    ubyte* mem_alloc(int nbytes) {
        auto p  = cast(ubyte*)malloc(nbytes);
        if (p is null)
            throw new Error("not enough mem");
        hasNoPointers(p);
        return p;
    }


    Block* block_alloc(int nints) {
        auto new_block = cast(Block*)mem_alloc(Block.sizeof);
        new_block.data = cast(int*)mem_alloc(nints * int.sizeof);
        new_block.len = nints;
        new_block.next = null;
        addRoot(new_block.next);
        addRoot(new_block.data);
        return new_block;
    }


    final void opCatAssign(int x) {
        if (this.used_last_block == this.list_tail.len) {
            // then last block is full and we must create a new one
            this.used_last_block = 0;
            auto new_block = block_alloc(this.list_tail.len * 2);

            // append to the linked list
            this.list_tail.next = new_block;
            this.list_tail = new_block;
        }

        this.list_tail.data[this.used_last_block] = x;
        this.used_last_block++;
        this.total_len++;
    }


    int[] toarray() {
        if (!this.total_len)
            return null;

        int* result_ptr = cast(int*)mem_alloc(this.total_len * int.sizeof);
        int[] result = result_ptr[0 .. this.total_len];

        Block* aux_ptr = this.list_head;
        int pos;

        while (aux_ptr != null) {
            // in the last block copy only up to the total_len
            int ncopy = min(aux_ptr.len, this.total_len - pos);
            writefln(ncopy, " ", aux_ptr.len); // ****

            result[pos .. pos + ncopy] = aux_ptr.data[0 .. ncopy];
            pos += ncopy;
            aux_ptr = aux_ptr.next;
        }

        return result;
    }
}


void main() {
    auto st = new IntStack();

    for (int i; i < 70_000; i++)
        st ~= i;

    fullCollect();
    auto aux = st.toarray;
}




> It means that that object will not be collected until you remove it as
> a root manually.  You can very easily end up with a memory leak that
> way.

Uhm... I don't understand fully: do you mean roots don't become deleted when they have nothing that points to them?
The docs say:
"Roots are references to memory allocated by the collector that are maintained in memory outside the collector pool."

If roots don't become deleted when they have nothing that points to them then I don't want to use roots in my code. What's the way to add a pointer to the pool of pointers scanned by the GC that become deleted when nothing points to it? :-)
(In this data structure I can remove roots manually during inside the ~this(), but I'd prefer to not have to).


>The simplest implementation, though, is to use arrays, like you thought earlier.  

I'm trying to learn how to use the GC because I'd like to create quite more complex data structures.
I have already solved this specific stack problem in a different way, that's the faster that I have found (it just keeps a single memory zone that I realloc() to make it grow geometrically. This solution is the faster among many different ones, I don't know why).

I have created a recursive template that tells if a data structure contains a reference. If they aren't present, I don't need to set memory to their .init. My template is not perfect, because it doesn't tell apart normal references from GC-references, so if you create a stack (ArrayBuilder) of not-GC pointers, they become set to null even if they don't need such thing, wasting a bit of time. On the other hand the only way to tell if a reference is GC-managed is to use (at runtime) TypeInfo.flags(), but someone has told that it's buggy (Phobos).


>You don't need to muck with the GC really at all in this case, other than to set the allocated arrays as having no pointers.<
> ...
> auto d = new int[nints];
> hasNoPointers(d.ptr);
> ...

That hasNoPointers is quite useless, because the GC knows that 'd' is a dynamic array of ints, so it knows its memory doesn't contain GC-managed pointers. Isn't muching with the GC nice? :-)

Thank you very much,
bearophile