Forgive me, but that just sounds like arguing:

But, if you use a car, you can't haul around large objects like you can with a truck.

But, to me, it seems reasonable that if you want to haul around large objects, you use a truck.  You can't have dangling pointers with arrays anyway without a GC or knowing in advance, can you?  Maybe I'm mistaken, but that is specifically one of the disadvantages of reference counting, is it not?

Thus, it seems like if you wanted to modify D to not use garbage collecting - or even to use reference counting - you would have to avoid using slices, and instead use functions (e.g. array.slice(0, 5)) like you already have to in C with reference counting!

IMHO, D only makes it easier.  I don't see how it makes it harder to use reference counting; you just have to live without some of the nicities D gives you that you never had with C/C++ anyway.

-[Unknown]


> But how do you do this without garbage collection?  Almost any operation on a
> dynamic array might require a memory allocation, and the old memory has to go
> somewhere.  If it's cleaned immediately then you could be stuck with dangling
> pointers (please note that I'm trying to look at this from a compiler/library
> writer's perspective).  I suppose it may be possible to implement a conforming D
> compiler that does reference counting instead of garbage collection, but I'm not
> sure it would be a worthwhile endeavor.

In article <d9a158$qmq$1@digitaldaemon.com>, clayasaurus says...
>
>Brad Beveridge wrote:
>> pragma wrote:
>> 
>>> In article <d99kcq$hd0$1@digitaldaemon.com>, Brad Beveridge says...
>> 
>> 
>>>
>>> OT: Living here in the USA, I had no clue what a "Lada" was. So here we go. This is the low-end model on their website:
>>>
>>> http://www.lada.de/html_e/content_e/models/lada_2110_pricelist.html
>>>
>>> (at today's rate, thats $9634.39 USD.)
>>>
>>> And the sales pitch:
>>>
>>> This saloon not only looks good on the outside! Inside it offers spacious
>>> accommodation for 5, easily accessed by 4 doors. The generous interior
>>> of the
>>> LADA 2110 offers even more comfort-from the four electric windows via
>>> the remote
>>> bootlock to the electronic immobilizer and the automatic heating system.
>>> All fitted as standard in the LADA 2110 with 56kW (77hp) or 67kW
>>> (91hp) and
>>> unbeatable value for money!
>>>
>>> - EricAnderton at yahoo
>> 
>> 
>> I've recently moved to the USA, but couldn't think of a brand of car that has a poor reputation for comfort, etc :)  I'm originally from New Zealand, and Lada's (although they may be better now) don't have a good reputation there :)
>> 
>> Brad
>
>I think the USA equivilent is the Geo!
>
>Brand new... http://www.canadiandriver.com/articles/jc/images/98metro_cpe.jpg
>
>What happens when you drive them too much... http://www.crh.noaa.gov/ict/wxstory/2001070813_mvc-016s.jpg http://www.awsomecar.com/pix/wreckmetro.jpg
>
>I know someone who has a geo, it looks like crap.


I had a geo :P.

The only card I've ever wrecked lol.

Charlie

On Thu, 23 Jun 2005 11:45:29 -0400, Jarrett Billingsley <kb3ctd2@yahoo.com> wrote:
> "Regan Heath" <regan@netwin.co.nz> wrote in message
> news:opsstqq2vz23k2f5@nrage.netwin.co.nz...
>> Cycles? example pls.
>
> You know, objects that point to each other.  Even if nothing else is
> pointing to them, and they are for all purposes "dead," they won't be
> automatically collected because they still point to each other and thus
> still have one reference each.  You'd have to establish some kind of manual
> cleanup for these objects, such as a "parent-child" relationship, where
> deleting the parent would cause the child to .Release() the reference to the
> parent.

Coo, I suspected that's what was meant :)

Like a doubly linked list perhaps? One where you have nulled your pointer to it's root item? This wouldn't happen to me, as I'd be 'free' ing the root, causing a free of the next item, etc.

Or perhaps a circular list (I've never had cause to used one). Even there you'd have a pointer to some starting point, or current point or something. When freeing such a list I'd imagine you need it to be double linked so as you can null the previous items 'next' pointer (in other words turning it into a normal list) before recursively freeing the items.

How does a GC handle 'cycles'? Does it analyse and figure out it's a cycle or does it just not free them? I suspect it depends on how clever the GC is, right?

Regan

Regan Heath wrote:

> How does a GC handle 'cycles'? Does it analyse and figure out it's a cycle  or does it just not free them? I suspect it depends on how clever the GC  is, right?
> 
> Regan

As I understand it, it works like:  Starting from the CPU registers the GC looks for pointers, it also looks for pointers in the stack and global static data.  From those pointers it marks areas of the heap as "don't touch" and further checks those areas.  So the GC ends up knowing where all valid (ie, reachable) objects are in memory.
All other parts of memory - the lost circular list will be in here - are fair game for the GC to use in future allocations.

Brad

"Regan Heath" <regan@netwin.co.nz> wrote in message news:opssujy2j723k2f5@nrage.netwin.co.nz...
> On Thu, 23 Jun 2005 11:45:29 -0400, Jarrett Billingsley <kb3ctd2@yahoo.com> wrote:
>> "Regan Heath" <regan@netwin.co.nz> wrote in message news:opsstqq2vz23k2f5@nrage.netwin.co.nz...
>>> Cycles? example pls.
>>
>> You know, objects that point to each other.  Even if nothing else is
>> pointing to them, and they are for all purposes "dead," they won't be
>> automatically collected because they still point to each other and thus
>> still have one reference each.  You'd have to establish some kind of
>> manual
>> cleanup for these objects, such as a "parent-child" relationship, where
>> deleting the parent would cause the child to .Release() the reference to
>> the
>> parent.
>
> Coo, I suspected that's what was meant :)
>
> Like a doubly linked list perhaps? One where you have nulled your pointer to it's root item? This wouldn't happen to me, as I'd be 'free' ing the root, causing a free of the next item, etc.
>
> Or perhaps a circular list (I've never had cause to used one). Even there you'd have a pointer to some starting point, or current point or something. When freeing such a list I'd imagine you need it to be double linked so as you can null the previous items 'next' pointer (in other words turning it into a normal list) before recursively freeing the items.
>
> How does a GC handle 'cycles'? Does it analyse and figure out it's a cycle or does it just not free them? I suspect it depends on how clever the GC is, right?
>

Cyclic references is what COM+  (reference counting) these days is dying of.
Imagine Recordset class and Field class.
class Recordset { Field[] fields; ... }
class Field { Recordest rs; .... }
As auto deletion of object happens when it reference count becomes zero
than such system will never be freed by itself.

What does mark-n-sweep GC (it is used in D):

1) It freezes execution of the process.
2) Mark phase: Scans root and perimeter: stack and statics -
    looks in each memory location and tries to guess is it pointer
    on the heap or not. If it looks like a pointer for some memory chunk
    it scans that memory. Doing such scanning, it sets 'marked' flag to
    accessible blocks.
3) Sweep phase: scans list of all allocated memory chunks and
    if 'marked' flag is not set for it - frees it (deletes from heap).
4) Resumes execution of your process.

As you may see it solves problem of cyclic references.

But! As you may also see it stops your process for some amount of time. Obviously as much stuff you have allocated (which was not explicetely deleted) as longer GC pause - your app is non-responsive.

Resume: if you you know that something can be deleted you'd better delete it *now* :)

All this talks: opAssign, ctors/dtors, 'const' are about this and not about beautification of syntax (this is also matters as Lada example shows but you'd better install first best engine available - it is better that this engine use hybrid technologies, right?).

This is why I am personally not buying advices to use .dup when I can simply solve this by using 'const' in 95% of cases.

Andrew.

On Thu, 23 Jun 2005 14:29:31 +0000 (UTC), Sean Kelly <sean@f4.ca> wrote:
> In article <opsstiikkp23k2f5@nrage.netwin.co.nz>, Regan Heath says...
>>
>> On Thu, 23 Jun 2005 08:07:06 +0000 (UTC), Mike Capp <mike.capp@gmail.com>
>> wrote:
>>> In article <opsssligap23k2f5@nrage.netwin.co.nz>, Regan Heath says...
>>>>
>>>>> + Much tighter control over memory usage than GC. (Smaller working set,
>>>>> much
>>>>> less risk of unacceptable pauses.) A bit tedious when you don't need
>>>>> it,
>>>>> but
>>>>> irreplaceable when you do, and manageable given RAII. This point alone
>>>>> creates a
>>>>> sizeable niche in which D will _never_ supplant C/C++.
>>>>
>>>> D can do this too, just diasble the GC and memory manage to your hearts
>>>> content.
>>>
>>> Except that, to return to an earlier gripe, the rules for 'auto' don't
>>> allow
>>> automatic refcounted smart pointers along the lines of boost::shared_ptr.
>>
>> I'll take your word for it. I've never used them.
>
> The basic problem is that D doesn't support copy semantics for user-defined
> types.  So it's impossible to implement anything that does refcounting.

After reading this thread and also this one Andrew dug up:
  http://www.digitalmars.com/d/archives/7988.html

It appears you need a type that:

1 - is stack based.
2 - has deterministic destruction.
3 - has opAssign.

It seems (from recent posts) that Walter plans to put auto classes on the stack, so they'd then fulfil requirements 1 and 2.

But what about 3? To me, opAssign isn't generally a good idea for classes (assigning a value to a reference seems illogical) but would be a good for structs (they're value types, assignment assigns a value).

Can you do reference counting without opAssign?

The idea for D (or so I've read) is that opAssign isn't required, instead you use a copy constructor. Now, I've little experience with ref counting, or with writing an implementation of one, but, does this work?

import std.c.windows.windows;
import std.random;
import std.thread;
import std.stdio;

class RefPtr
{
	RefPtr parent;
	Object resource = null;
	int refs = 0;

	this(Object res)
	{
		resource = res;
		writefln("ThreadID=(",Thread.getThis().id,") Initial RefPtr for resource=(",resource,")");
		increment();		
	}

	this(RefPtr rhs)
	{
		parent = rhs;
		parent.increment();
		writefln("ThreadID=(",Thread.getThis().id,") Ref=(",parent.refs,") for resource=(",parent.resource,")");
	}
	
	~this()
	{
		int r;
		
		if ((r = decrement()) == 0)
		{
			writefln("ThreadID=(",Thread.getThis().id,") release last ref Ref=(",r,")");
			if (parent) parent = null;
			else if (resource)
			{
				writefln("ThreadID=(",Thread.getThis().id,") delete resource=(",resource,")");
				delete resource;
				resource = null;
			}
		}
		writefln("ThreadID=(",Thread.getThis().id,") release Ref=(",r,")");
	}
protected:
	int increment()
	{
		int ret;
		
		if (parent) ret = parent.increment();
		else {
			synchronized(this)
			{
				ret = ++refs;
				writefln("ThreadID=(",Thread.getThis().id,") increment to Ref=(",refs,")");
			}
		}
		
		return ret;
	}
	int decrement()
	{
		int ret;
		
		if (parent) ret = parent.decrement();
		else {
			synchronized(this)
			{
				ret = --refs;
				writefln("ThreadID=(",Thread.getThis().id,") decrement to Ref=(",refs,")");
			}
		}
		
		return ret;
	}
}

class Resource
{
	char[] name = "11 was a racehorse";
	char[] toString() { return name; }
}

RefPtr pbob;

static this()
{
	pbob = new RefPtr(new Resource());
}

static ~this()
{
	delete pbob;
}

void main()
{
	Thread t;
	int i;
	
	writefln("ThreadID=(",Thread.getThis().id,") is the main thread");
	
	for(i = 0; i < 10; i++)
	{
		t = new Thread(&thread_function,null);
		t.start();
	}
	
	/* How do I wait for all threads? This code cause access violation.
	while(true)
	{
		i = 0;
		foreach(Thread t; Thread.getAll())
		{
			if (t.getState() == Thread.TS.TERMINATED) i++;
		}
		if (i == 10) break;
		Sleep(100);
	}*/
	
	Sleep(5000);
	
	writefln("Main exiting");
}

int thread_function(void* isnull)
{
	auto RefPtr p = new RefPtr(pbob);
	Sleep(1000+rand()%1000);	
	return 0;
}

Regan

On Thu, 23 Jun 2005 17:06:11 -0700, Brad Beveridge <brad@somewhere.net> wrote:
> Regan Heath wrote:
>
>> How does a GC handle 'cycles'? Does it analyse and figure out it's a cycle  or does it just not free them? I suspect it depends on how clever the GC  is, right?
>>  Regan
>
> As I understand it, it works like:  Starting from the CPU registers the GC looks for pointers, it also looks for pointers in the stack and global static data.  From those pointers it marks areas of the heap as "don't touch" and further checks those areas.  So the GC ends up knowing where all valid (ie, reachable) objects are in memory.
> All other parts of memory - the lost circular list will be in here - are fair game for the GC to use in future allocations.

Ahh.. thanks, good description.

Regan

On Thu, 23 Jun 2005 17:17:50 -0700, Andrew Fedoniouk <news@terrainformatica.com> wrote:
> "Regan Heath" <regan@netwin.co.nz> wrote in message
> news:opssujy2j723k2f5@nrage.netwin.co.nz...
>> On Thu, 23 Jun 2005 11:45:29 -0400, Jarrett Billingsley
>> <kb3ctd2@yahoo.com> wrote:
>>> "Regan Heath" <regan@netwin.co.nz> wrote in message
>>> news:opsstqq2vz23k2f5@nrage.netwin.co.nz...
>>>> Cycles? example pls.
>>>
>>> You know, objects that point to each other.  Even if nothing else is
>>> pointing to them, and they are for all purposes "dead," they won't be
>>> automatically collected because they still point to each other and thus
>>> still have one reference each.  You'd have to establish some kind of
>>> manual
>>> cleanup for these objects, such as a "parent-child" relationship, where
>>> deleting the parent would cause the child to .Release() the reference to
>>> the
>>> parent.
>>
>> Coo, I suspected that's what was meant :)
>>
>> Like a doubly linked list perhaps? One where you have nulled your pointer
>> to it's root item? This wouldn't happen to me, as I'd be 'free' ing the
>> root, causing a free of the next item, etc.
>>
>> Or perhaps a circular list (I've never had cause to used one). Even there
>> you'd have a pointer to some starting point, or current point or
>> something. When freeing such a list I'd imagine you need it to be double
>> linked so as you can null the previous items 'next' pointer (in other
>> words turning it into a normal list) before recursively freeing the items.
>>
>> How does a GC handle 'cycles'? Does it analyse and figure out it's a cycle
>> or does it just not free them? I suspect it depends on how clever the GC
>> is, right?
>>
>
> Cyclic references is what COM+  (reference counting) these days is dying of.
> Imagine Recordset class and Field class.
> class Recordset { Field[] fields; ... }
> class Field { Recordest rs; .... }
> As auto deletion of object happens when it reference count becomes zero
> than such system will never be freed by itself.

Yep, I see.

> What does mark-n-sweep GC (it is used in D):
>
> 1) It freezes execution of the process.
> 2) Mark phase: Scans root and perimeter: stack and statics -
>     looks in each memory location and tries to guess is it pointer
>     on the heap or not. If it looks like a pointer for some memory chunk
>     it scans that memory. Doing such scanning, it sets 'marked' flag to
>     accessible blocks.
> 3) Sweep phase: scans list of all allocated memory chunks and
>     if 'marked' flag is not set for it - frees it (deletes from heap).
> 4) Resumes execution of your process.
>
> As you may see it solves problem of cyclic references.

Yep.

> But! As you may also see it stops your process for some amount of
> time. Obviously as much stuff you have allocated (which was not
> explicetely deleted) as longer GC pause - your app is non-responsive.

Sure. But for 'how long', and is that length of time 'too long' or not. I can see how in a 'realtime' application this might be a *big* problem, but in a typical application as long as the pause is very brief it should be fine, right?

In applications with a realtime portion i.e. a game rendering to the screen there are techniques for avoiding pauses when it really matters, they generally involve pre-allocating and not allocating due the rendering phase. I believe a game written *without* a GC would use the same techniques in order to keep the frame rate as fast as possible. I'm no expert though.

A friend of mine, much older than I, who once used a GC for some anchient language (I cannot remember the name of) mentioned to me, a few weeks back, about how an application he wrote was 'going away' for a few minutes. That sort of pause is unacceptable in just about every application type. That said, GC implmentation (and the hardware they operate on) has improved vastly.

> Resume: if you you know that something can be deleted you'd better
> delete it *now* :)

This is sensible advice in any case.

> All this talks: opAssign, ctors/dtors, 'const' are about this and
> not about beautification of syntax

I never once thought it was :)

> (this is also matters as Lada
> example shows but you'd better install first best engine available -
> it is better that this engine use hybrid technologies, right?).
>
> This is why I am personally not buying advices to use .dup
> when I can simply solve this by using 'const' in 95% of cases.

I don't buy them either. To me it smacks of inefficiency and doing something "just in case". While I agree/think Copy-On-Write is a good method (it is efficient) I also think we do need some method to enforce readonly.

The best soln I've seen IMO is the compile/runtime flags for verifying readonly data is not modified.

In short, I agree there is a problem. I have a favourite solution and it's not 'exactly' what you're saying we should do ;)

Regan

AFAIK, some of the threads in getAll() could be null.  You might want something like:

    while(true)
    {
        i = 0;
        foreach(Thread t; Thread.getAll())
        {
            if (t !is null && t.getState() == Thread.TS.TERMINATED) i++;
        }
        if (i == 10) break;
        Sleep(100);
    }

Which may or may not fix the access violation.  Anyway, I'd do this:

    Thread[] t;
    int i;

    writefln("ThreadID=(",Thread.getThis().id,") is the main thread");

    t.length = 10;
    for (i = 0; i < t.length; i++)
    {
        t[i] = new Thread(&thread_function,null);
        t[i].start();
    }

    bool keep_going = true;
    while (keep_going)
    {
        keep_going = false;

        foreach (Thread th; t)
        {
            if (th.getState() != Thread.TS.TERMINATED)
                keep_going = true;
        }

        Sleep(100);
    }

Or something instead.  There's probably a lot better way than that, though.

-[Unknown]


>     /* How do I wait for all threads? This code cause access violation.
>     while(true)
>     {
>         i = 0;
>         foreach(Thread t; Thread.getAll())
>         {
>             if (t.getState() == Thread.TS.TERMINATED) i++;
>         }
>         if (i == 10) break;
>         Sleep(100);
>     }*/

On Thu, 23 Jun 2005 19:38:43 -0700, Unknown W. Brackets <unknown@simplemachines.org> wrote:
> AFAIK, some of the threads in getAll() could be null.

Yeah, that was it.

> Which may or may not fix the access violation.  Anyway, I'd do this:
>
>      Thread[] t;
>      int i;
>
>      writefln("ThreadID=(",Thread.getThis().id,") is the main thread");
>
>      t.length = 10;
>      for (i = 0; i < t.length; i++)
>      {
>          t[i] = new Thread(&thread_function,null);
>          t[i].start();
>      }
>
>      bool keep_going = true;
>      while (keep_going)
>      {
>          keep_going = false;
>
>          foreach (Thread th; t)
>          {
>              if (th.getState() != Thread.TS.TERMINATED)
>                  keep_going = true;
>          }
>
>          Sleep(100);
>      }
>
> Or something instead.  There's probably a lot better way than that, though.

I considered storing them all, decided I didn't want to (on a whim really).

Regan