Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #91708 > unrolled thread

A GC proposal

Back to article view | Back to comp.lang.c

Contents

  A GC proposal jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-05 10:34 +0200
    Re: A GC proposal Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-05 09:59 +0100
      Re: A GC proposal jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-05 11:29 +0200
        Re: A GC proposal Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-05 15:48 +0100
    Re: A GC proposal luser droog <luser.droog@gmail.com> - 2016-08-05 12:18 -0700
      Re: A GC proposal supercat@casperkitty.com - 2016-08-05 12:32 -0700
        Re: A GC proposal jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-05 22:07 +0200
          Re: A GC proposal Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-05 21:50 +0100
            Re: A GC proposal supercat@casperkitty.com - 2016-08-05 14:32 -0700
            Re: A GC proposal jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-06 00:05 +0200
              Re: A GC proposal Melzzzzz <mel@zzzzz.com> - 2016-08-06 00:28 +0200
              Re: A GC proposal Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-06 01:47 +0100

#91708 — A GC proposal

We have discussed here many times the GC feature. I think this could be 
solved by introducing a new kind of pointers that have restricted access:

The declarations would be in the "attributes" format. Since the 
committee is discussing this  as an enhancement to the language let's 
keep the (gcc) __attribute__ syntax or the microsoft __declspec syntax

#define GC __declspec(GC)

char * GC myPtr;

The "GC" marked pointers would support a subset of the operations 
possible with pointers:

1: Assignment/initializations: They can be only initialized or assigned 
from another pointer also marked as "GC".

2: Once initialized they can't be changed (they are all implicit "const").

3: They can't be stored in unions.

4: If not initialized at the start of the function, non-initialized gc 
pointers would be automatically initialized to NULL at the function entry.

The compiler can then provide an environment where the GC can be VERY 
accurate, not jkust conservative, as it is now. The compiler would emit 
a set of tables containing for each scope the addresses of all pointer 
marked as GC. The GC algorithm would be then like this:

1) From the current frame, mark as used all pointers in the current 
function.

2) Use the stack unwind info to retrieve the calling function, mark 
those until the global scope is reached and mark all that one too.

3) Do this for each thread.

4) Unmarked memory is free.

Note that the info can also be used by a debugger or the user itself if 
the language provides a run time interface. A stack trace of the program
becomes easy to do...

Note that this doesn't imply ANY change to the language besides the 
introduction of the GC-interface attribute names.

[toc] | [next] | [standalone]

#91710

jacobnavia <jacob@jacob.remcomp.fr> writes:

> We have discussed here many times the GC feature. I think this could
> be solved by introducing a new kind of pointers that have restricted
> access:

You don't say what the problem is that is being solved by the suggestion
that follows.  Since GC largely works with C as it is, you should say
what the specific problem is.  I think, from what you write below, it's
all about avoiding the "false positives" of current GC schemes.

> The declarations would be in the "attributes" format. Since the
> committee is discussing this  as an enhancement to the language let's
> keep the (gcc) __attribute__ syntax or the microsoft __declspec syntax
>
> #define GC __declspec(GC)
>
> char * GC myPtr;
>
> The "GC" marked pointers would support a subset of the operations
> possible with pointers:

I'd call these GC qualified pointers.  That's the term C uses in other
similar situations -- const qualified, restrict qualified and so on.
Since GC often uses a technique known as 'marking' to track collection,
avoiding the term here would help, I think.

> 1: Assignment/initializations: They can be only initialized or
> assigned from another pointer also marked as "GC".

Are casts permitted?  Given a void *vp, the expression (char *GC)vp is a
GC qualified pointer.  Could that be used?  I would imagine not, but
since the overall goal of this scheme is unclear, maybe I've got that
wrong.

> 2: Once initialized they can't be changed (they are all implicit
> "const").

Do you really mean initialised or do you mean "first assigned"?  If you
mean initialised (in the C sense), then there will be lots of important
cases where you can't use GC qualified pointers.  I'm thinking of
classic GC use cases such as dynamic lists and trees.

> 3: They can't be stored in unions.
>
> 4: If not initialized at the start of the function, non-initialized gc
> pointers would be automatically initialized to NULL at the function
> entry.
>
> The compiler can then provide an environment where the GC can be VERY
> accurate, not jkust conservative, as it is now. The compiler would
> emit a set of tables containing for each scope the addresses of all
> pointer marked as GC. The GC algorithm would be then like this:
>
> 1) From the current frame, mark as used all pointers in the current
> function.
>
> 2) Use the stack unwind info to retrieve the calling function, mark
> those until the global scope is reached and mark all that one too.
>
> 3) Do this for each thread.
>
> 4) Unmarked memory is free.

This seems to rule out having GC qualified pointers in allocated
storage.  That's going to seriously reduce its usefulness.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#91715

Le 05/08/2016 à 10:59, Ben Bacarisse a écrit :
> jacobnavia <jacob@jacob.remcomp.fr> writes:
>
>> We have discussed here many times the GC feature. I think this could
>> be solved by introducing a new kind of pointers that have restricted
>> access:
>
> You don't say what the problem is that is being solved by the suggestion
> that follows.  Since GC largely works with C as it is, you should say
> what the specific problem is.  I think, from what you write below, it's
> all about avoiding the "false positives" of current GC schemes.
>

Obviously. But I should have said that explicitely. It is a proposal to 
make GC not just "conservative" but 100% accurate.

>> The declarations would be in the "attributes" format. Since the
>> committee is discussing this  as an enhancement to the language let's
>> keep the (gcc) __attribute__ syntax or the microsoft __declspec syntax
>>
>> #define GC __declspec(GC)
>>
>> char * GC myPtr;
>>
>> The "GC" marked pointers would support a subset of the operations
>> possible with pointers:
>
> I'd call these GC qualified pointers.  That's the term C uses in other
> similar situations -- const qualified, restrict qualified and so on.
> Since GC often uses a technique known as 'marking' to track collection,
> avoiding the term here would help, I think.
>

Yes, we can say they are GC qualified.

>> 1: Assignment/initializations: They can be only initialized or
>> assigned from another pointer also marked as "GC".
>
> Are casts permitted?  Given a void *vp, the expression (char *GC)vp is a
> GC qualified pointer.  Could that be used?

Of course, we are in C. You can do today:

char *p = (char *)0xdeadbeef;

*p = '?';

and your propgram will crash. And it is your fault.

I would imagine not, but
> since the overall goal of this scheme is unclear, maybe I've got that
> wrong.

The main goal is to make an accurate description of memory to be used 
with the GC.

>
>> 2: Once initialized they can't be changed (they are all implicit
>> "const").
>
> Do you really mean initialised or do you mean "first assigned"?  If you
> mean initialised (in the C sense), then there will be lots of important
> cases where you can't use GC qualified pointers.  I'm thinking of
> classic GC use cases such as dynamic lists and trees.
>

1: If you allocate the nodes of the list using the GC it will work 
without any problems.

typedef struct tagNode { char * GC next; int data; } Node;

In this cases all nodes are allocated with the GC attribute. You can 
then have all Node pointers garbage collected.

Note that a normal pointer can receive the value of a GC allocated 
pointer to go through the list or to keep a pointer to the last node or 
whatever.


>> 3: They can't be stored in unions.
>>
>> 4: If not initialized at the start of the function, non-initialized gc
>> pointers would be automatically initialized to NULL at the function
>> entry.
>>
>> The compiler can then provide an environment where the GC can be VERY
>> accurate, not jkust conservative, as it is now. The compiler would
>> emit a set of tables containing for each scope the addresses of all
>> pointer marked as GC. The GC algorithm would be then like this:
>>
>> 1) From the current frame, mark as used all pointers in the current
>> function.
>>
>> 2) Use the stack unwind info to retrieve the calling function, mark
>> those until the global scope is reached and mark all that one too.
>>
>> 3) Do this for each thread.
>>
>> 4) Unmarked memory is free.
>
> This seems to rule out having GC qualified pointers in allocated
> storage.  That's going to seriously reduce its usefulness.
>

Suppose:

struct S { int a; char *GC; };

int foo() {
    struct S s;

// ...
}

The compiler can then emit the offset of the pointer in the structure 
and allow the GC to follow the pointers in the allocated data.

> <snip>
>

[toc] | [prev] | [next] | [standalone]

#91727

jacobnavia <jacob@jacob.remcomp.fr> writes:

> Le 05/08/2016 à 10:59, Ben Bacarisse a écrit :
>> jacobnavia <jacob@jacob.remcomp.fr> writes:
>>
>>> We have discussed here many times the GC feature. I think this could
>>> be solved by introducing a new kind of pointers that have restricted
>>> access:
>>
>> You don't say what the problem is that is being solved by the suggestion
>> that follows.  Since GC largely works with C as it is, you should say
>> what the specific problem is.  I think, from what you write below, it's
>> all about avoiding the "false positives" of current GC schemes.
>
> Obviously. But I should have said that explicitely. It is a proposal
> to make GC not just "conservative" but 100% accurate.
>
<snip>
>>> 1: Assignment/initializations: They can be only initialized or
>>> assigned from another pointer also marked as "GC".
>>
>> Are casts permitted?  Given a void *vp, the expression (char *GC)vp is a
>> GC qualified pointer.  Could that be used?
>
> Of course, we are in C. You can do today:
>
> char *p = (char *)0xdeadbeef;
>
> *p = '?';
>
> and your propgram will crash. And it is your fault.

That's missing the point!  Is it *valid* to take a pointer and cast it
to be being GC qualified?

>> I would imagine not, but
>> since the overall goal of this scheme is unclear, maybe I've got that
>> wrong.
>
> The main goal is to make an accurate description of memory to be used
> with the GC.

So, no.  You can't add GC qualification with a cast (nor cast it away?)
and still have a correct program.  Is that about right?

>>> 2: Once initialized they can't be changed (they are all implicit
>>> "const").
>>
>> Do you really mean initialised or do you mean "first assigned"?

It would really help if you answered this.

>> If you mean initialised (in the C sense), then there will be lots of
>> important cases where you can't use GC qualified pointers.  I'm
>> thinking of classic GC use cases such as dynamic lists and trees.
>>
>
> 1: If you allocate the nodes of the list using the GC it will work
> without any problems.
>
> typedef struct tagNode { char * GC next; int data; } Node;
>
> In this cases all nodes are allocated with the GC attribute. You can
> then have all Node pointers garbage collected.

I can't square that with the other things you've said.  You say that GC
qualified pointers can't be assigned (they are implicitly const) so how
does the 'next' pointer get a new value?

And if the allocator must know the types, you can't have any GC
qualified pointers in malloc'd storage.  That's fine, but I think you
need to say it.

> Note that a normal pointer can receive the value of a GC allocated
> pointer to go through the list or to keep a pointer to the last node
> or whatever.

Ah, this sounds dangerous.  If I go through the list with a non-GC
pointer there may be times when that is the only pointer to a node
(during unlinking of a node for example).  Now you can say that the
programmer just made a mistake but surely you want to make memory
management less prone to hard to find bugs.  I would ban casting away GC
qualification.

>>> 3: They can't be stored in unions.
>>>
>>> 4: If not initialized at the start of the function, non-initialized gc
>>> pointers would be automatically initialized to NULL at the function
>>> entry.
>>>
>>> The compiler can then provide an environment where the GC can be VERY
>>> accurate, not jkust conservative, as it is now. The compiler would
>>> emit a set of tables containing for each scope the addresses of all
>>> pointer marked as GC. The GC algorithm would be then like this:
>>>
>>> 1) From the current frame, mark as used all pointers in the current
>>> function.
>>>
>>> 2) Use the stack unwind info to retrieve the calling function, mark
>>> those until the global scope is reached and mark all that one too.
>>>
>>> 3) Do this for each thread.
>>>
>>> 4) Unmarked memory is free.
>>
>> This seems to rule out having GC qualified pointers in allocated
>> storage.  That's going to seriously reduce its usefulness.
>>
>
> Suppose:
>
> struct S { int a; char *GC; };
>
> int foo() {
>    struct S s;
>
> // ...
> }
>
> The compiler can then emit the offset of the pointer in the structure
> and allow the GC to follow the pointers in the allocated data.

There is no allocated storage (in the C sense) here.  I was talking
about malloc and friends.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#91760

On Friday, August 5, 2016 at 3:34:16 AM UTC-5, jacobnavia wrote:
> We have discussed here many times the GC feature. I think this could be 
> solved by introducing a new kind of pointers that have restricted access:
> 
> The declarations would be in the "attributes" format. Since the 
> committee is discussing this  as an enhancement to the language let's 
> keep the (gcc) __attribute__ syntax or the microsoft __declspec syntax

Thank you very much for adding this to the conversation. This is
exactly the sort of thing I was curious about: what sort of compiler
gymnastics would enable better GC.

<snip>

But this:
 
> 3: They can't be stored in unions.
> 

is a deal-breaker for most of my projects which rely on tag-unions
extensively.

My thought was to add function pointers to the gc_alloc function.

void *gc_alloc (size_t sz, TYPE (*iter)(), TYPE2(*final)());

I don't know what the TYPEs should be here.

And something to set the strategy and enable/disable for performance-
critical sections.

I think the compiler could find my root sets, but it would need help
to peek through the custom typing layer that a language interpreter 
tends to need. 

But maybe other applications don't need this.

[toc] | [prev] | [next] | [standalone]

#91763

On Friday, August 5, 2016 at 2:18:48 PM UTC-5, luser droog wrote:
> But this:
>  
> > 3: They can't be stored in unions.
> > 
> 
> is a deal-breaker for most of my projects which rely on tag-unions
> extensively.

In .NET languages (e.g. C#), it's possible to use explicit structure layout
attributes to create structures that behave like unions, but the system will
vigorously enforce a rule that any part of a structure which is used to hold
a reference type (like a pointer, but more tightly controlled) cannot also
be used to hold any other type.  If two structures both have a field of type
Bitmap (a reference type) at offset 4, both structures may be placed at
offset 0 since their Bitmap fields would coincide, but one could not overlay
one of those structures with another structure type which had e.g. an "Int32"
at offset 4 since that would result in an "Int32" and a "Bitmap" overlapping.
While .NET won't mind if code overlays e.g. two "UInt16" values on top of a
"UInt32" values, it will absolutely not tolerate overlaying a reference field
with anything else unless all type-safety checking is disabled.

[toc] | [prev] | [next] | [standalone]

#91766

Le 05/08/2016 à 21:32, supercat@casperkitty.com a écrit :
> On Friday, August 5, 2016 at 2:18:48 PM UTC-5, luser droog wrote:
>> But this:
>>
>>> 3: They can't be stored in unions.
>>>
>>
>> is a deal-breaker for most of my projects which rely on tag-unions
>> extensively.
>
> In .NET languages (e.g. C#), it's possible to use explicit structure layout
> attributes to create structures that behave like unions, but the system will
> vigorously enforce a rule that any part of a structure which is used to hold
> a reference type (like a pointer, but more tightly controlled) cannot also
> be used to hold any other type.  If two structures both have a field of type
> Bitmap (a reference type) at offset 4, both structures may be placed at
> offset 0 since their Bitmap fields would coincide, but one could not overlay
> one of those structures with another structure type which had e.g. an "Int32"
> at offset 4 since that would result in an "Int32" and a "Bitmap" overlapping.
> While .NET won't mind if code overlays e.g. two "UInt16" values on top of a
> "UInt32" values, it will absolutely not tolerate overlaying a reference field
> with anything else unless all type-safety checking is disabled.
>
>

Yes, very interesting. The rule could be relaxed to "No unions of GC 
pointer with anything else but a GC pointer"

[toc] | [prev] | [next] | [standalone]

#91771

jacobnavia <jacob@jacob.remcomp.fr> writes:

> Le 05/08/2016 à 21:32, supercat@casperkitty.com a écrit :
>> On Friday, August 5, 2016 at 2:18:48 PM UTC-5, luser droog wrote:
>>> But this:
>>>
>>>> 3: They can't be stored in unions.
>>>
>>> is a deal-breaker for most of my projects which rely on tag-unions
>>> extensively.
>>
>> In .NET languages...

<snip>
> Yes, very interesting. The rule could be relaxed to "No unions of GC
> pointer with anything else but a GC pointer"

Given

  struct s1 { struct s1 *GC next; char c; };
  struct s2 { double d; struct s1 *GC left, *CG right; };

  union us1s2 { struct s1 *GC lp; struct s2 *GC tp; } u;

how do you determine what pointers need to be followed?  Obviously the
content of u, but then what?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#91774

On Friday, August 5, 2016 at 3:50:20 PM UTC-5, Ben Bacarisse wrote:
>   union us1s2 { struct s1 *GC lp; struct s2 *GC tp; } u;
> 
> how do you determine what pointers need to be followed?  Obviously the
> content of u, but then what?

In .NET languages, such situations would be handled by using the
type-descriptor pointer which is stored with every GC-eligible
object.  If pointer arithmetic were forbidden on gc pointers,
but there were a "pin" function that returned a non-GC-qualified
pointer that had to be given to an "unpin" function, such an
approach would be workable in C as well if compilers included type
information within the executable.

[toc] | [prev] | [next] | [standalone]

#91778

Le 05/08/2016 à 22:50, Ben Bacarisse a écrit :
> how do you determine what pointers need to be followed?  Obviously the
> content of u, but then what?

This is equivalent to figuring out embedded pointers in a data structure.

The compiler leaves to the gc information about which pointers are at 
which offsets in the types of us1s2. The first points  to an s1 
structure that has a pointer to be followed at offset zero. The second 
points to a structure s2 with pointers to be followed at offset 8 and 16.

Since the types of those are known, the gc marks them and goes on 
following each of them in sequence.

Thanks for conributing to this thread Mr Becarisse. As you see I am 
trying to figure out what would need to be generated for a GC in C, but 
not a probabilistic one but one powered by information the compiler 
leaves to it.

That eliminates false positives. It leaves the question of infinite 
loops in circular structures.

Then, this GC would MUCH faster and simpler than the one of Mr Boehm's.

That is an impressive piece of software of course, but it has a brute 
force algorithm. This one is much faster since it doesn't chase pointers 
blindly in all space but knows where are the real pointers!

Besides, obvious speed ups can be detected at compile time:

At function exit any GC pointer that is local to that function and has 
not been passed to any function can be safely freed immediately.

[toc] | [prev] | [next] | [standalone]

#91779

On Sat, 6 Aug 2016 00:05:07 +0200
jacobnavia <jacob@jacob.remcomp.fr> wrote:

> 
> Then, this GC would MUCH faster and simpler than the one of Mr
> Boehm's.
> 
> That is an impressive piece of software of course, but it has a brute 
> force algorithm. This one is much faster since it doesn't chase
> pointers blindly in all space but knows where are the real pointers!
Does that helps in case of swapping ?
Weakest thing about GC vs manual is when processes are partly swapped...
> 

[toc] | [prev] | [next] | [standalone]

#91795

jacobnavia <jacob@jacob.remcomp.fr> writes:

> Le 05/08/2016 à 22:50, Ben Bacarisse a écrit :
>> how do you determine what pointers need to be followed?  Obviously the
>> content of u, but then what?
>
> This is equivalent to figuring out embedded pointers in a data structure.
>
> The compiler leaves to the gc information about which pointers are at
> which offsets in the types of us1s2. The first points  to an s1
> structure that has a pointer to be followed at offset zero. The second
> points to a structure s2 with pointers to be followed at offset 8 and
> 16.

I know how that part works -- the point of the example was that run-time
information must be maintained needed for unions.  Languages that do
this "GC assist" usually have discriminated unions, but that's hard to
do in C (not impossible, I'm sure, but I can't see how right now).

You seem to be hoping for a method that avoids tracking any changing
type information at run-time, but I don't think that's possible without
crippling the language.

<snip>
> That eliminates false positives. It leaves the question of infinite
> loops in circular structures.

What collection algorithm are you thinking of using?  Handling circular
references comes for free in many GC algorithms.

<snip>
-- 
Ben.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web