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 reply 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
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 bearophile <bearophileHUG lycos.com> writes:
Denis Koroskin:

 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.


That's why such problems make my head hurt, when I find them. This may be the
20th new problem I find.



 I think you should put the whole test program into bugzilla for Walter  
 play with.


I'm shy.



 Even though it *looks like* problem is gone in 1.029+ it might  
 just be hidden and may arise under different circumstances.


Probably the problem isn't gone, I have found this problem with DMD 1.035 (the
last one).
I think this problem (if it's not just a bug in my code) may be related to this
thing that everyone has ignored:

http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=75846

Bye, and thank you very much for helping me,
bearophile
Sep 06 2008
prev 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;
 


 What are you doing here?


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;


 So that code looks correct to me.


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


 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
Sep 07 2008
next sibling parent reply "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
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 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 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 reply "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
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 reply 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
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 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 reply "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
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
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 parent reply "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
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
parent reply "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
next sibling parent reply "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
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 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 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

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


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


 ~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 reply "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
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