www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - A bug in my code

reply bearophile <bearophileHUGS lycos.com> writes:
This code isn't short, but can someone help me spot the bug/problem (D1, DMD)?
I have tried to write clean & short code, to help spotting problems.

It produces an (no error line given):
Error: overlapping array copy

It's just a stack data structure (here for simplicity just for items of type
int), made with a single linked list of blocks that become geometrically bigger.


import std.gc: malloc, hasNoPointers;

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;
        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;

        // Here: Error: overlapping array copy
        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);
            
            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;

    auto aux = st.toarray;
    aux = st.toarray;
}



---------------------

Note: in that code I haven't used variable-length structs, like the following
idiom sometimes used in C, because it gives array bounds errors:


struct Block {
    int len;
    Block* next;
    int[1] data;
}
...
auto new_block = cast(Block*)mem_alloc(Block.sizeof + (nints - 1) * int.sizeof);


I presume that can't be done in D (I don't want to write code that works only
in release mode).

Bye and thank you,
bearophile
Sep 05 2008
next sibling parent BCS <ao pathlink.com> writes:
I don't known what the error comes from in your code but I do know that it 
is a result of trying to copy from one slice to another that overlap. Someone 
has a copy function that works in this cases (look at cashew)
Sep 06 2008
prev sibling next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Sat, 06 Sep 2008 21:17:31 +0400, BCS <ao pathlink.com> wrote:

 I don't known what the error comes from in your code but I do know that  
 it is a result of trying to copy from one slice to another that overlap.  
 Someone has a copy function that works in this cases (look at cashew)

Not necessarily. I once wrote a code that was passing and returning some arrays, but never copying them. In some cases I was getting some weird array overlapping exception that disappeared after small refactoring. I am 100% sure it was a DMD bug.
Sep 06 2008
prev sibling next sibling parent reply "Denis Koroskin" <2korden gmail.com> writes:
On Sat, 06 Sep 2008 05:12:56 +0400, bearophile <bearophileHUGS lycos.com>  
wrote:

 This code isn't short, but can someone help me spot the bug/problem (D1,  
 DMD)?
 I have tried to write clean & short code, to help spotting problems.

 It produces an (no error line given):
 Error: overlapping array copy

 It's just a stack data structure (here for simplicity just for items of  
 type int), made with a single linked list of blocks that become  
 geometrically bigger.


 import std.gc: malloc, hasNoPointers;

 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;
         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;

         // Here: Error: overlapping array copy
         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);
            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;

     auto aux = st.toarray;
     aux = st.toarray;
 }



 ---------------------

 Note: in that code I haven't used variable-length structs, like the  
 following idiom sometimes used in C, because it gives array bounds  
 errors:


 struct Block {
     int len;
     Block* next;
     int[1] data;
 }
 ...
 auto new_block = cast(Block*)mem_alloc(Block.sizeof + (nints - 1) *  
 int.sizeof);


 I presume that can't be done in D (I don't want to write code that works  
 only in release mode).

 Bye and thank you,
 bearophile

Just started digging your case. This behaviour is 100% repeatable with DMD1.028 but never takes place with DMD1.029+ (Windows).
Sep 06 2008
parent "Denis Koroskin" <2korden gmail.com> writes:
On Sat, 06 Sep 2008 23:09:56 +0400, Denis Koroskin <2korden gmail.com>  
wrote:

 On Sat, 06 Sep 2008 05:12:56 +0400, bearophile  
 <bearophileHUGS lycos.com> wrote:

 This code isn't short, but can someone help me spot the bug/problem  
 (D1, DMD)?
 I have tried to write clean & short code, to help spotting problems.

 It produces an (no error line given):
 Error: overlapping array copy

 It's just a stack data structure (here for simplicity just for items of  
 type int), made with a single linked list of blocks that become  
 geometrically bigger.


 import std.gc: malloc, hasNoPointers;

 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;
         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;

         // Here: Error: overlapping array copy
         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);
            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;

     auto aux = st.toarray;
     aux = st.toarray;
 }



 ---------------------

 Note: in that code I haven't used variable-length structs, like the  
 following idiom sometimes used in C, because it gives array bounds  
 errors:


 struct Block {
     int len;
     Block* next;
     int[1] data;
 }
 ...
 auto new_block = cast(Block*)mem_alloc(Block.sizeof + (nints - 1) *  
 int.sizeof);


 I presume that can't be done in D (I don't want to write code that  
 works only in release mode).

 Bye and thank you,
 bearophile

Just started digging your case. This behaviour is 100% repeatable with DMD1.028 but never takes place with DMD1.029+ (Windows).

WTF? Changing nearly *anything* (like, decreasing loop counf from 70_000 to 65_000, putting logging of any kind or commenting out almost any line) makes problem disappear. I think you should put the whole test program into bugzilla for Walter play with. Even though it *looks like* problem is gone in 1.029+ it might just be hidden and may arise under different circumstances.
Sep 06 2008
prev sibling next sibling parent reply "Manfred_Nowak" <svv1999 hotmail.com> writes:
bearophile wrote:

             this.list_tail.next = new_block;
             this.list_tail = new_block;
 

What are you doing here? -manfred -- If life is going to exist in this Universe, then the one thing it cannot afford to have is a sense of proportion. (Douglas Adams)
Sep 06 2008
parent reply bearophile <bearophileHUGS lycos.com> writes:
Manfred_Nowak Wrote:
             this.list_tail.next = new_block;
             this.list_tail = new_block;
 


Let's see. This is a singly linked list, the list header that is the pointer to the oldest allocated block is (this doesn't change often): this.list_head The last block of the linked list is pointed by: this.list_tail Each block has a "next" pointer. When the user wants to add an item to the data structure and the last block is full, I have to allocate a new block, that is pointed by: new_block So I allocate: new_block = GC_malloc ... Then I set the 'next' pointer of the last block of the list (that was null) to point the new block: this.list_tail.next = new_block; Then I move the tail pointer to point to the newly allocate block: this.list_tail = new_block; So now the tail pointer correctly points to the last block. Now I can reset to zero the number of the items in the last block: this.used_last_block = 0; Then I can copy the new item in the correct position, that is 0 if the block is newly allocated: this.list_tail.data[this.used_last_block] = x; Then I increment the number of items used in the last block, so next time I'll insert in the second space: this.used_last_block++; Then I increment the total length of the data structure, to remember how much long it is: this.total_len++; So that code looks correct to me. Bye, bearophile
Sep 06 2008
parent reply "Manfred_Nowak" <svv1999 hotmail.com> writes:
bearophile wrote:
 this.list_tail.next = new_block;


Sorrily it might be correct only at the surface. In the deeper grounds your coding might be lead by some wrong assumptions on the semantics of the interface to the GC. You are setting the attribute of `hasNoPointers' for each and every memory block you `malloc'. But this is not true, because with the assignment above you are introducing a pointer into that area, without calling `hasPointers'. This means that on the nextrun of `FullCollect' close to no elements of the list are referenced anymore: they all get collected, except `head' and `tail' ofcourse. You can see this by introducing a simple printout: | int ncopy = min(aux_ptr.len, this.total_len - pos); | writefln( ncopy); which will printout the lines | 4 | 69996 | 0 | ..... for the second run of `st.toarray'. -manfred -- If life is going to exist in this Universe, then the one thing it cannot afford to have is a sense of proportion. (Douglas Adams)
Sep 06 2008
parent reply bearophile <bearophileHUGS lycos.com> writes:
Manfred_Nowak:
 Sorrily it might be correct only at the surface. In the deeper grounds 
 your coding might be lead by some wrong assumptions on the semantics of 
 the interface to the GC.
 You are setting the attribute of `hasNoPointers' for each and every 
 memory block you `malloc'. But this is not true, because with the 
 assignment above you are introducing a pointer into that area, without 
 calling `hasPointers'.
 This means that on the nextrun of `FullCollect' close to no elements of 
 the list are referenced anymore: they all get collected, except `head' 
 and `tail' ofcourse.

You are right, that's the bug, thank you very much. I am used with languages where you have no GC, and you do everything by yourself, and high-level languages with GC where the GC works by itself. In the D code like that you have to interact with the GC a bit more closely :-) If not already present somewhere, I think D newbies will enjoy a small tutorial on such GC usage. This is the line of code that creates a new Block, it calls hasNoPointers() internally: auto new_block = cast(Block*)mem_alloc(Block.sizeof); The best way to solve the bug is to allocate that struct normally: auto new_block = new Block; So the GC knows where the GC pointers are. (Later I have realized that for this problem an even better solution is to not use a linked list at all, and append the block structs into a growing dynamic array, where the structs now have just two fields: a len and a pointer to the block data). But I'm trying to learn to use the GC, not just to debug this little experimental program. This is an alternative solution, that works, but I don't trust/like this much because I *think* the GC may scan all the struct fields for possible pointers, even the 'len' (an integer) one (if that idea of mine is wrong then please tell me): auto new_block = cast(Block*)mem_alloc(Block.sizeof); hasPointers(new_block); So I have tried this, I have written this assuming that addRoot() adds a single pointer to the GC collected pool, but this last solution doesn't work, I don't know why: 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); Bye and thank you, bearophile
Sep 07 2008
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
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);


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
Sep 07 2008
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Jarrett Billingsley:
 You are obsessed with performance.  Please stop it, it's not everything.

I use D only when/because I need more performance, when performance isn't strictly essential, I always use Python (or other languages). The <vector> of the C++ STL that I can use with MinGW is 30-40% faster than the faster code I have written for the stack in D. I think the designers of that vector are more obsessed than me. If most D programmers don't care for efficient data structures, and they are happy with the current bad ones (I am not talking about Tango now), then maybe I can just stop bothering with D and stick with the much uglier/crancky/bug-prone C++. bearophile
Sep 07 2008
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Bill Baxter:
 At some point you used to be able to create variables using an "=void"
 initializer to prevent the automatic initialization.  Is that no
 longer the case?

I think the = void can be used with static arrays/variables, but not with dynamic arrays. Note: I'll write a better answer to the gentle Jarrett Billingsley, sorry for my nervous answer of before :-) Bye, bearophile
Sep 07 2008
parent reply bearophile <bearophileHUGS lycos.com> writes:
Jarrett Billingsley:
 There's no way to do it with any heap-allocated value, which does seem
 a bit like a hole to me.

I think there's both a syntax problem (what syntax to use?), and the fact that when possible D wants to avoid programming mistakes, so it wants to initialize memory to a clean state (this is even more important for the GC). A first possible syntax? auto a = new int[10] = void; That syntax is also usable to replace this: auto a = new int[10]; a[] = 5; With: auto a = new int[10] = 5; But maybe this isn't important enough. Bye, bearophile
Sep 07 2008
next sibling parent "Manfred_Nowak" <svv1999 hotmail.com> writes:
Bill Baxter wrote:

   auto a = new int(void)[10];

Does this imply the decision, that on upsizing no change of the init value is allowed? Otherwise how to change the init value? -manfred -- If life is going to exist in this Universe, then the one thing it cannot afford to have is a sense of proportion. (Douglas Adams)
Sep 07 2008
prev sibling parent reply Sergey Gromov <snake.scaly gmail.com> writes:
Bill Baxter <wbaxter gmail.com> wrote:
 On Mon, Sep 8, 2008 at 8:33 AM, bearophile <bearophileHUGS lycos.com> wrote:
 Jarrett Billingsley:
 There's no way to do it with any heap-allocated value, which does seem
 a bit like a hole to me.

I think there's both a syntax problem (what syntax to use?), and the fact that when possible D wants to avoid programming mistakes, so it wants to initialize memory to a clean state (this is even more important for the GC).

 But maybe this isn't important enough.

Yeh, maybe not this one thing. But enough grains of sand like this and you have a sizable obstacle. And D has a fair number of such grains.

A non-initialized array must never be scanned for pointers, even if the underlying type contains them. This is a very dangerous feature which must not be available in SafeD. You can always use T[] allocArrayNoInit(T)(size_t count) { void[] mem = std.gc.malloc(count * T.sizeof); std.gc.hasNoPointers(mem.ptr); return cast(T[])mem; }
Sep 08 2008
parent reply "Manfred_Nowak" <svv1999 hotmail.com> writes:
Sergey Gromov wrote:

 You can always use
   return cast(T[])mem;

I doubt this, because that `cast' might not be valid for all types `T'. -manfred -- If life is going to exist in this Universe, then the one thing it cannot afford to have is a sense of proportion. (Douglas Adams)
Sep 08 2008
parent Sergey Gromov <snake.scaly gmail.com> writes:
Manfred_Nowak <svv1999 hotmail.com> wrote:
 Sergey Gromov wrote:
 
 You can always use
   return cast(T[])mem;

I doubt this, because that `cast' might not be valid for all types `T'.

Could you explain your point in a bit more detail? std.gc.malloc() is guaranteed to return a memory block with alignment requirements sufficient for any type.
Sep 08 2008
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Jarrett Billingsley:

I think what you should be using instead is addRange.  addRoot more or less
tells the GC "never collect memory referenced by this pointer", but it doesn't
actually scan the memory _pointed to_ by the roots for pointers.  addRange
tells the GC "scan this range of memory for pointers", which is what you want
to tell the GC to do for Blocks. But then you run into another problem --
addRange and removeRange are terribly inefficient.<

Uhm... saddening.
Uh, you don't have to do anything special.  You just use "new" to allocate a
block of memory, and if it could contain pointers, and that block of memory is
transitively accessible from the stack/registers/globals, then any pointers it
contains will be scanned, and any memory pointed to by it will not be freed.<

That may be not enough to design a bit more complex data strutures, I don't know, we'll see.
I think you're making things way more complicated than they need to be.<

For this toy program yes, but to create more complex data structures I'll need to learn more things about the GC. Bye, bearophile
Sep 07 2008
parent bearophile <bearophileHUGS lycos.com> writes:
Jarrett Billingsley Wrote:
 How complex are you trying to get?

Well, I may want to try to implement finger trees, ecc.
How horribly are you planning on subverting the GC and for what purpose?<

I'm planning in making the GC become evil. The purpose is total world domination, of course. Be scared, bearophile
Sep 08 2008
prev sibling parent Sergey Gromov <snake.scaly gmail.com> writes:
Jarrett Billingsley <jarrett.billingsley gmail.com> wrote:
 On Sun, Sep 7, 2008 at 12:59 PM, bearophile <bearophileHUGS lycos.com> wrote:
 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."

I think what you should be using instead is addRange. addRoot more or less tells the GC "never collect memory referenced by this pointer", but it doesn't actually scan the memory _pointed to_ by the roots for pointers.

This just cannot be. A root is a place where a tree of live memory objects is grafted. That's why it is called a "root". A memory block pointed to by a root is kept alive and, obviously, scanned for pointers to other memory blocks if it hasPointers(). There's a problem with addRoot() that, if the memory block is re- allocated, the old root stops serving its purpose. In that case you need to remove an old root and add the new one, pointing into the re- allocated block.
Sep 08 2008
prev sibling parent reply Sergey Gromov <snake.scaly gmail.com> writes:
bearophile <bearophileHUGS lycos.com> wrote:
 So I have tried this, I have written this assuming that addRoot() adds
 a single pointer to the GC collected pool, but this last solution
 doesn't work, I don't know why:
 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);

What you do here is add two roots to GC: null and a pointer to your ints. While the latter is relatively valid, the former is obviously wrong: you tell GC to never collect a memory block which includes an address of 0. What happens next is a) whatever you assign to block.next is not kept alive by block since the .next field itself is not checked for pointers; and b) if you ever change .data the old block will live forever while the new one will not be referenced for the same reason as a). Here are the possible solutions. Note that they are independent, you need to implement only one of them to make your code work. 1. Replace Block.next with private Block* _next; Block* next() {return _next;} Block* next(Block* other) { removeRoot(_next); _next = other; addRoot(_next); return _next; } 2. Replace addRoot(new_block.next); addRoot(new_block.data); with addRange(&new_block.next, &new_block.data+1); which will make GC scan Block.next and Block.data for pointers on every collection cycle, therefore automatically picking any changes to these pointers. Both changes make your code work. Both require Block.~this() to remove any unneeded roots or ranges, since they are permanent by their nature and will keep any pointed memory allocated until the process terminates.
Sep 08 2008
parent reply bearophile <bearophileHUGS lycos.com> writes:
Sergey Gromov, thank you for your explanations, you are quite clear, I have
understood everything you have explained :-) And your code works.

I think this discussion may deserve to become a little tutorial useful for
people that have never done such things (probably most people coming from all
scripting languages, Pascal, Java and maybe C/C# don't know such things if the
haven't seen in the University, so they are lot of people), it may be written
here:
http://www.prowiki.org/wiki4d/wiki.cgi?DocComments/Phobos/StdGc


 addRange(&new_block.next, &new_block.data+1);

The trick of adding a range of pointers to pointers is cute :-) I presume that +1 is necessary because it's an interval open on the right, even if the Phobos docs don't tell it: void addRange(void* pbot, void* ptop);
Both require Block.~this() to remove any unneeded roots or ranges<

Okay, I understand now. Jarrett Billingsley has told me that those ranges are inefficient, so I hope the roots are more efficient. Using your second solution: addRange(&new_block.next, &new_block.data+1); I have added this destructor: ~this() { while (this.list_head != null) { Block* next_ptr = this.list_head.next; std.gc.removeRange(&this.list_head.next); std.gc.realloc(this.list_head.data, 0); std.gc.realloc(this.list_head, 0); this.list_head = next_ptr; } } Now I think I understand the Phobos GC API a bit better. But I'll have to be really careful, because doing mistakes with such things looks very easy still for me. Bye and thank you, bearophile
Sep 08 2008
next sibling parent reply Sergey Gromov <snake.scaly gmail.com> writes:
bearophile <bearophileHUGS lycos.com> wrote:
 Sergey Gromov, thank you for your explanations, you are quite clear, I 
 have understood everything you have explained :-) And your code works.

You're welcome. :)
 addRange(&new_block.next, &new_block.data+1);

The trick of adding a range of pointers to pointers is cute :-) I presume that +1 is necessary because it's an interval open on the right, even if the Phobos docs don't tell it: void addRange(void* pbot, void* ptop);

Well, I assumed that. Void doesn't have size after all, so I thought pbot and ptop were specifying byte boundaries, not bytes or words themselves.
Both require Block.~this() to remove any unneeded roots or ranges<

Okay, I understand now. Jarrett Billingsley has told me that those ranges are inefficient, so I hope the roots are more efficient. Using your second solution: addRange(&new_block.next, &new_block.data+1); I have added this destructor: ~this() { while (this.list_head != null) { Block* next_ptr = this.list_head.next; std.gc.removeRange(&this.list_head.next); std.gc.realloc(this.list_head.data, 0); std.gc.realloc(this.list_head, 0); this.list_head = next_ptr; } }

I think that
         std.gc.realloc(this.list_head.data, 0);
         std.gc.realloc(this.list_head, 0);

elements in data other than in Blocks, reallocing data would silently invalidate those references eventually causing GPF (segfault). The correct code is
 ~this() {
     while (this.list_head != null) {
         Block* next_ptr = this.list_head.next;
         std.gc.removeRange(&this.list_head.next);
         this.list_head = next_ptr;
     }
 }

What it does is: 1. next_ptr makes a reference to list_head.next on the stack so that it isn't GC'd immediately. 2. removeRange() prevents GC from scanning list_head.next and list_head.data for pointers. The next is still referenced from stack so it lives yet. The data is not referenced from list_head anymore, and if there are no other references to it, it is GC'd eventually. If there are references though, it lives while those references are alive, which is expected and correct. 3. list_head = next_ptr removes the last reference to the former list_head so it gets GC'd automatically later.
 Now I think I understand the Phobos GC API a bit better. But I'll have 
 to be really careful, because doing mistakes with such things looks very 
 easy still for me.

Sep 08 2008
parent reply bearophile <bearophileHUGS lycos.com> writes:
Sergey Gromov:

I think that [...] is dangerous, not to mention redundant.  If there are
references to elements in data other than in Blocks, reallocing data would
silently invalidate those references eventually causing GPF (segfault).  The
correct code is<

- It's a depressing, in such kind of code it seems I'm unable to write 5 lines of code without putting in dangerous bugs :-] - That particular stack implementation is designed for ints only, so they don't contain references, so that code works (It seems). - But you are right, if the data block contains references then the realloc(... ,0) are very bad. - So generally in such programs the right thing to do seems to not dealloc memory, but remove the known references to it, and then let the GC deallocate such memory when it can't find references pointing to that memory. - Yet, I have seen that for some data structures (probably ones with long chains of references) letting the GC do all the work of looking for unconnected components to deallocate them leads to long destruction times (2-10 seconds of time in one case). In such situations I think it may be better to give the GC a hand, actually deallocating the data structure inside the destructor using an efficient algorithm (if the programmer is sure it doesn't contain references to other allocate data) (this needs just few hundreds of seconds in the same case of before). Bye, bearophile
Sep 08 2008
parent Sergey Gromov <snake.scaly gmail.com> writes:
bearophile <bearophileHUGS lycos.com> wrote:
 - That particular stack implementation is designed for ints only, so 
 they don't contain references, so that code works (It seems).
 - But you are right, if the data block contains references then the 
 realloc(... ,0) are very bad.

Your code will work with arrays of pointers either. The potential problem is not in array elements pointing somewhere else, but in some external references pointing into your array. Well, since your code guarantees that such external references are impossible, it always works as expected.
 - So generally in such programs the right thing to do seems to not 
 dealloc memory, but remove the known references to it, and then let the 
 GC deallocate such memory when it can't find references pointing to that 
 memory.

It's the safe thing to do.
 - Yet, I have seen that for some data structures (probably ones with 
 long chains of references) letting the GC do all the work of looking for 
 unconnected components to deallocate them leads to long destruction 
 times (2-10 seconds of time in one case). In such situations I think it 
 may be better to give the GC a hand, actually deallocating the data 
 structure inside the destructor using an efficient algorithm (if the 
 programmer is sure it doesn't contain references to other allocate data) 
 (this needs just few hundreds of seconds in the same case of before).

My apologies. Your last code was correct. It was just dangerous, as any other explicit memory management code is. The danger was in that it was easy to make breaking changes to your code and not notice. My variant was simply safer but also probably slower under some circumstances. Hugs.
Sep 08 2008
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
Jarrett Billingsley:

 They're both pretty inefficient.  Adding a root or range is pretty
 fast, it might have to resize its internal array.  But removing a root
 or range requires the linear traversal of the internal list of roots
 or ranges as well as copying every root/range after it down a slot,
 which is all very slow, as downs has found out

I have just read some of the relevant code: for (size_t i = nranges; i--;) { if (ranges[i].pbot == pbot) { nranges--; cstring.memmove(ranges+i, ranges+i+1, (nranges-i) * ranges[0].sizeof); return; } } it's written in D, but it looks like C because I presume that you can't rely on the GC (to use a more efficient associative array (of or better a set) of Range structs) inside the code that implements the GC itself :-) Even with that, if ranges are few, the slowdown is little. The addRange() function doesn't seem to control if a given Range is already present, so it appends it again and again, I think. This may be okay, because if two sources define a Range as source for roots, then they both independently will take care of removing them, but the GC itself may slow down, because it looks from the same starting points twice. So an associative Range->counter seems a better data structure, where the removeRange actually removes a range only of its counter goes to zero. In that code I have also understood why Sergey Gromov has added 1 to the second pointer given to addRange(): /// Search a range of memory values and mark any pointers into the GC pool. void mark(void *pbot, void *ptop) { void **p1 = cast(void **)pbot; void **p2 = cast(void **)ptop; uint changes = 0; for (; p1 < p2; p1++) { ... It's an interval open to the right, indeed.
(and patched, though it's not in the official GC yet).

Months ago a very gentle person has created a patch for the GC just for me, to reduce a lot a performance problem I have found, but I think that patch too is waiting still. Where can I find the patch by downs (mostly to take a look)? I presume the Tango GC doesn't suffer such performance problem. Bye, bearophile
Sep 08 2008
prev sibling next sibling parent "Jarrett Billingsley" <jarrett.billingsley gmail.com> writes:
On Sun, Sep 7, 2008 at 7:48 AM, bearophile <bearophileHUGS lycos.com> wrote:
 Manfred_Nowak:
 Sorrily it might be correct only at the surface. In the deeper grounds
 your coding might be lead by some wrong assumptions on the semantics of
 the interface to the GC.
 You are setting the attribute of `hasNoPointers' for each and every
 memory block you `malloc'. But this is not true, because with the
 assignment above you are introducing a pointer into that area, without
 calling `hasPointers'.
 This means that on the nextrun of `FullCollect' close to no elements of
 the list are referenced anymore: they all get collected, except `head'
 and `tail' ofcourse.

You are right, that's the bug, thank you very much. I am used with languages where you have no GC, and you do everything by yourself, and high-level languages with GC where the GC works by itself. In the D code like that you have to interact with the GC a bit more closely :-) If not already present somewhere, I think D newbies will enjoy a small tutorial on such GC usage. This is the line of code that creates a new Block, it calls hasNoPointers() internally: auto new_block = cast(Block*)mem_alloc(Block.sizeof); The best way to solve the bug is to allocate that struct normally: auto new_block = new Block; So the GC knows where the GC pointers are. (Later I have realized that for this problem an even better solution is to not use a linked list at all, and append the block structs into a growing dynamic array, where the structs now have just two fields: a len and a pointer to the block data).

..Or just, you know, arrays. Since that's exactly what they are.
 But I'm trying to learn to use the GC, not just to debug this little
experimental program. This is an alternative solution, that works, but I don't
trust/like this much because I *think* the GC may scan all the struct fields
for possible pointers, even the 'len' (an integer) one (if that idea of mine is
wrong then please tell me):
 auto new_block = cast(Block*)mem_alloc(Block.sizeof);
 hasPointers(new_block);

You're right, the GC will scan all the members of each block, len included, since it's imprecise and stupid. However there's no way around this. You _have_ pointers in your Blocks. If you tell the GC otherwise, you're lying to it, and it will misbehave. What you _can_ do, however, is allocate your Blocks with new, and then allocate the data they point to with malloc. Then just set the data blocks to hasNoPointers, and leave the Blocks as they are.
 So I have tried this, I have written this assuming that addRoot() adds a
single pointer to the GC collected pool, but this last solution doesn't work, I
don't know why:
 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);

Adding roots is certainly possible but it's not very elegant. 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. The simplest implementation, though, is to use arrays, like you thought earlier. 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. class IntStack { int[][] data; int[] last_data; size_t total_len; size_t used_last_block; this() { last_data = block_alloc(4); } int[] block_alloc(int nints) { auto d = new int[nints]; hasNoPointers(d.ptr); data ~= d; return d; } final void opCatAssign(int x) { if(used_last_block == last_data.length) { used_last_block = 0; last_data = block_alloc(last_data.length * 2); } last_data[used_last_block] = x; used_last_block++; total_len++; } int[] toarray() { if(!total_len) return null; auto result = new int[total_len]; size_t pos = 0; foreach(blk; data[0 .. $ - 1]) { result[pos .. pos + blk.length] = blk[]; pos += blk.length; } result[pos .. pos + used_last_block] = last_data[0 .. used_last_block]; return result; } }
Sep 07 2008
prev sibling next sibling parent "Jarrett Billingsley" <jarrett.billingsley gmail.com> writes:
On Sun, Sep 7, 2008 at 12:59 PM, bearophile <bearophileHUGS lycos.com> wrote:
 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)).

The array is only initialized when you allocate it. So, just allocate a raw block of uninitialized memory and slice it to get an array. I'm not so much trying to say that using a struct is the wrong way to do it, but rather that it's pointless to use a struct { int* data, size_t length } when that's _precisely_ what an array is, and arrays give you nicer syntax.
 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."

I think what you should be using instead is addRange. addRoot more or less tells the GC "never collect memory referenced by this pointer", but it doesn't actually scan the memory _pointed to_ by the roots for pointers. addRange tells the GC "scan this range of memory for pointers", which is what you want to tell the GC to do for Blocks. But then you run into another problem -- addRange and removeRange are terribly inefficient. So.. stop making things hard on yourself ;)
 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).

Uh, you don't have to do anything special. You just use "new" to allocate a block of memory, and if it could contain pointers, and that block of memory is transitively accessible from the stack/registers/globals, then any pointers it contains will be scanned, and any memory pointed to by it will not be freed.
 I'm trying to learn how to use the GC because I'd like to create quite more
complex data structures.

I think you're making things way more complicated than they need to be.
 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 are obsessed with performance. Please stop it, it's not everything.
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? :-)

Ah. Well, you can leave it in if you replace "new int[nints]" with "cast(int[])std.gc.malloc(nints * int.sizeof)". That'll get you an uninitialized array, but I think you still need to explicitly set the "has no pointers" flag.
Sep 07 2008
prev sibling next sibling parent Moritz Warning <moritzwarning web.de> writes:
On Sun, 07 Sep 2008 14:11:09 -0400, Jarrett Billingsley wrote:

 You are obsessed with performance.  Please stop it, it's not everything.

Being obsessed with performance is a good thing if it's a piece of code that is used often and can be wrapped in a library. Such piece of library does often yet exist, but sometimes it does not.
Sep 07 2008
prev sibling next sibling parent "Bill Baxter" <wbaxter gmail.com> writes:
On Mon, Sep 8, 2008 at 1:59 AM, bearophile <bearophileHUGS lycos.com> wrote:
 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)).

At some point you used to be able to create variables using an "=void" initializer to prevent the automatic initialization. Is that no longer the case? --bb
Sep 07 2008
prev sibling next sibling parent "Bill Baxter" <wbaxter gmail.com> writes:
On Mon, Sep 8, 2008 at 6:52 AM, bearophile <bearophileHUGS lycos.com> wrote:
 Bill Baxter:
 At some point you used to be able to create variables using an "=void"
 initializer to prevent the automatic initialization.  Is that no
 longer the case?

I think the = void can be used with static arrays/variables, but not with dynamic arrays.

If there is no way to do the same thing with dynamic arrays, I think that's a hole in the language. --bb
Sep 07 2008
prev sibling next sibling parent "Jarrett Billingsley" <jarrett.billingsley gmail.com> writes:
On Sun, Sep 7, 2008 at 5:58 PM, Bill Baxter <wbaxter gmail.com> wrote:
 On Mon, Sep 8, 2008 at 6:52 AM, bearophile <bearophileHUGS lycos.com> wrote:
 Bill Baxter:
 At some point you used to be able to create variables using an "=void"
 initializer to prevent the automatic initialization.  Is that no
 longer the case?

I think the = void can be used with static arrays/variables, but not with dynamic arrays.

If there is no way to do the same thing with dynamic arrays, I think that's a hole in the language. --bb

There's no way to do it with any heap-allocated value, which does seem a bit like a hole to me.
Sep 07 2008
prev sibling next sibling parent "Bill Baxter" <wbaxter gmail.com> writes:
On Mon, Sep 8, 2008 at 8:33 AM, bearophile <bearophileHUGS lycos.com> wrote:
 Jarrett Billingsley:
 There's no way to do it with any heap-allocated value, which does seem
 a bit like a hole to me.

I think there's both a syntax problem (what syntax to use?), and the fact that when possible D wants to avoid programming mistakes, so it wants to initialize memory to a clean state (this is even more important for the GC). A first possible syntax? auto a = new int[10] = void; That syntax is also usable to replace this: auto a = new int[10]; a[] = 5; With: auto a = new int[10] = 5;

My first thought was something more like auto a = new int(5)[10]; to init to 5, or auto a = new int(void)[10]; to not init.
 But maybe this isn't important enough.

Yeh, maybe not this one thing. But enough grains of sand like this and you have a sizable obstacle. And D has a fair number of such grains. --bb
Sep 07 2008
prev sibling next sibling parent "Jarrett Billingsley" <jarrett.billingsley gmail.com> writes:
On Sun, Sep 7, 2008 at 9:23 PM, bearophile <bearophileHUGS lycos.com> wrote:

 That may be not enough to design a bit more complex data strutures, I don't
know, we'll see.

How complex are you trying to get? How horribly are you planning on subverting the GC and for what purpose?
Sep 07 2008
prev sibling next sibling parent "Bill Baxter" <wbaxter gmail.com> writes:
On Mon, Sep 8, 2008 at 2:12 PM, Manfred_Nowak <svv1999 hotmail.com> wrote:
 Bill Baxter wrote:

   auto a = new int(void)[10];

Does this imply the decision, that on upsizing no change of the init value is allowed? Otherwise how to change the init value?

Well, you really don't want to have to carry around an init value with every array (or slice of one). So I think it would have to be the case that the initializer only applied to the original creation. Maybe that means the OP would still want to roll his own non-intializing array. --bb
Sep 07 2008
prev sibling next sibling parent "Jarrett Billingsley" <jarrett.billingsley gmail.com> writes:
On Mon, Sep 8, 2008 at 6:09 AM, Sergey Gromov <snake.scaly gmail.com> wrote:
 Jarrett Billingsley <jarrett.billingsley gmail.com> wrote:
 On Sun, Sep 7, 2008 at 12:59 PM, bearophile <bearophileHUGS lycos.com> wrote:
 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."

I think what you should be using instead is addRange. addRoot more or less tells the GC "never collect memory referenced by this pointer", but it doesn't actually scan the memory _pointed to_ by the roots for pointers.

This just cannot be. A root is a place where a tree of live memory objects is grafted. That's why it is called a "root". A memory block pointed to by a root is kept alive and, obviously, scanned for pointers to other memory blocks if it hasPointers(). There's a problem with addRoot() that, if the memory block is re- allocated, the old root stops serving its purpose. In that case you need to remove an old root and add the new one, pointing into the re- allocated block.

Sep 08 2008
prev sibling next sibling parent "Jarrett Billingsley" <jarrett.billingsley gmail.com> writes:
On Mon, Sep 8, 2008 at 6:09 AM, Sergey Gromov <snake.scaly gmail.com> wrote:
 Jarrett Billingsley <jarrett.billingsley gmail.com> wrote:
 On Sun, Sep 7, 2008 at 12:59 PM, bearophile <bearophileHUGS lycos.com> wrote:
 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."

I think what you should be using instead is addRange. addRoot more or less tells the GC "never collect memory referenced by this pointer", but it doesn't actually scan the memory _pointed to_ by the roots for pointers.

This just cannot be. A root is a place where a tree of live memory objects is grafted. That's why it is called a "root". A memory block pointed to by a root is kept alive and, obviously, scanned for pointers to other memory blocks if it hasPointers(). There's a problem with addRoot() that, if the memory block is re- allocated, the old root stops serving its purpose. In that case you need to remove an old root and add the new one, pointing into the re- allocated block.

Let's put some words in this one! You're right, I'm sorry for spreading misinformation.
Sep 08 2008
prev sibling parent "Jarrett Billingsley" <jarrett.billingsley gmail.com> writes:
On Mon, Sep 8, 2008 at 11:01 AM, bearophile <bearophileHUGS lycos.com> wrote:

Both require Block.~this() to remove any unneeded roots or ranges<

Okay, I understand now. Jarrett Billingsley has told me that those ranges are inefficient, so I hope the roots are more efficient.

They're both pretty inefficient. Adding a root or range is pretty fast, it might have to resize its internal array. But removing a root or range requires the linear traversal of the internal list of roots or ranges as well as copying every root/range after it down a slot, which is all very slow, as downs has found out (and patched, though it's not in the official GC yet).
Sep 08 2008