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

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

Extending C with GC?

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

Contents

  Extending C with GC? luser droog <luser.droog@gmail.com> - 2016-07-31 15:31 -0700
    Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-07-31 15:52 -0700
      Re: Extending C with GC? Tim Rentsch <txr@alumni.caltech.edu> - 2016-07-31 17:21 -0700
      Re: Extending C with GC? Jean-Marc Bourguet <jm@bourguet.org> - 2016-08-01 20:34 +0200
        Re: Extending C with GC? supercat@casperkitty.com - 2016-08-01 12:14 -0700
        Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-01 12:46 -0700
          Re: Extending C with GC? "James R. Kuyper" <jameskuyper@verizon.net> - 2016-08-01 15:56 -0400
            Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-01 14:28 -0700
          Re: Extending C with GC? Jean-Marc Bourguet <jm@bourguet.org> - 2016-08-01 23:37 +0200
            Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-01 15:03 -0700
            Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-02 00:11 +0200
              Re: Extending C with GC? "James R. Kuyper" <jameskuyper@verizon.net> - 2016-08-01 18:19 -0400
                Re: Extending C with GC? BGB <cr88192@hotmail.com> - 2016-08-02 12:46 -0500
      Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-03 15:26 -0700
        Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-03 15:49 -0700
          Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-04 14:07 +1200
            Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-03 19:26 -0700
              Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-04 14:55 +1200
            Re: Extending C with GC? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-08-03 20:38 -0700
              Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-04 05:10 -0700
                Re: Extending C with GC? Siri Cruise <chine.bleu@yahoo.com> - 2016-08-04 05:57 -0700
                  Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-04 06:13 -0700
                Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-05 07:24 +1200
                  Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-04 12:47 -0700
                    Re: Extending C with GC? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-08-04 23:32 -0700
                      Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-05 10:09 +0100
                    Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-05 20:32 +1200
                      Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-05 06:14 -0700
                        Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-06 04:14 -0700
                          Re: Extending C with GC? Melzzzzz <mel@zzzzz.com> - 2016-08-06 13:23 +0200
                            Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-06 04:38 -0700
                          Re: Extending C with GC? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-08-06 04:34 -0700
                            Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-06 05:28 -0700
                              Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-06 06:05 -0700
                                Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-06 06:12 -0700
                            Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-06 14:02 +0100
                              Re: Extending C with GC? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-08-06 06:11 -0700
                                Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-06 14:50 +0100
                                  Re: Extending C with GC? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-08-06 07:57 -0700
                                    Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-06 17:02 +0100
                                Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-06 19:20 +0200
                              Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-06 14:27 +0100
                                Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-06 14:45 +0100
                                Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-06 09:59 -0700
                                  Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-06 19:38 +0100
                                    Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-06 17:03 -0700
                                      Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-07 09:54 +0100
                                        Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-07 21:53 +1200
                                          Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-07 11:34 +0100
                                            Re: Extending C with GC? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-08-07 12:06 +0000
                                            Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-07 14:10 +0100
                                              Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-07 15:38 +0100
                                                Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-07 14:32 -0700
                                                  Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-07 23:44 +0100
                                                    Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-07 16:12 -0700
                                                      Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-08 01:42 +0100
                                                        Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-07 18:56 -0700
                                                          Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-08 10:20 +0100
                                                            Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-08 09:39 -0700
                                                Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-08 02:30 +0100
                                              Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-07 20:15 +0100
                                                Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-08 01:24 +0100
                                                  Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-08 02:08 +0100
                                                    Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-07 18:49 -0700
                                                    Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-08 03:28 +0100
                                                      Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-08 12:14 +0100
                                            Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-08 07:37 +1200
                                              Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-07 20:56 +0100
                                                Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-08 08:11 +1200
                                                  Re: Extending C with GC? Melzzzzz <mel@zzzzz.com> - 2016-08-07 22:19 +0200
                                                  Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-07 22:23 +0100
                                                    Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-07 14:29 -0700
                                                      Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-07 22:36 +0100
                                                        Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-07 15:04 -0700
                                                        Re: Extending C with GC? jameskuyper@verizon.net - 2016-08-07 15:19 -0700
                                                          Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-08 00:04 +0100
                                                            Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-07 16:20 -0700
                                                            Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-08 15:21 +1200
                                                              Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-08 10:35 +0100
                                                                Re: Extending C with GC? Gareth Owen <gwowen@gmail.com> - 2016-08-08 18:13 +0100
                                                                  Re: Extending C with GC? supercat@casperkitty.com - 2016-08-08 11:53 -0700
                                                                    Re: Extending C with GC? raltbos@xs4all.nl (Richard Bos) - 2016-08-10 12:58 +0000
                                                                      Re: Extending C with GC? supercat@casperkitty.com - 2016-08-10 07:05 -0700
                                                                      Re: Extending C with GC? Ken Brody <kenbrody@spamcop.net> - 2016-08-10 12:29 -0400
                                                                  Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-08 21:15 +0100
                                                          Re: Extending C with GC? supercat@casperkitty.com - 2016-08-08 08:57 -0700
                                                        Re: Extending C with GC? luser droog <luser.droog@gmail.com> - 2016-08-07 15:37 -0700
                                                    Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-07 14:58 -0700
                                                    Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-08 15:26 +1200
                                                      Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-08 10:26 +0200
                                                        Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-08 21:13 +1200
                                                          Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-08 10:41 +0100
                                                          Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-08 12:00 +0200
                                                            Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-08 22:07 +1200
                                                            Re: Extending C with GC? David Brown <david.brown@hesbynett.no> - 2016-08-08 12:57 +0200
                                                            Re: Extending C with GC? Gareth Owen <gwowen@gmail.com> - 2016-08-08 18:12 +0100
                                                        Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-08 21:25 +1200
                                                          Re: Extending C with GC? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-08-08 02:57 -0700
                                            Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-07 13:28 -0700
                                        Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-07 05:42 -0700
                                Re: Extending C with GC? Florian Weimer <fw@deneb.enyo.de> - 2016-08-07 11:49 +0200
                              Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-06 19:18 +0200
                                Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-06 12:35 -0700
                            Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-06 19:27 +0200
                              Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-06 10:55 -0700
                              Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-06 12:31 -0700
        Re: Extending C with GC? James Kuyper <jameskuyper@verizon.net> - 2016-08-03 22:36 -0400
          Re: Extending C with GC? David Brown <david.brown@hesbynett.no> - 2016-08-04 10:57 +0200
            Re: Extending C with GC? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-08-04 04:09 -0700
              Re: Extending C with GC? David Brown <david.brown@hesbynett.no> - 2016-08-04 14:01 +0200
          Re: Extending C with GC? supercat@casperkitty.com - 2016-08-04 07:52 -0700
        Re: Extending C with GC? Tim Rentsch <txr@alumni.caltech.edu> - 2016-08-04 08:57 -0700
          Re: Extending C with GC? supercat@casperkitty.com - 2016-08-04 09:19 -0700
            Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-04 12:30 -0700
              Re: Extending C with GC? supercat@casperkitty.com - 2016-08-04 15:21 -0700
                Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-04 16:50 -0700
                  Re: Extending C with GC? supercat@casperkitty.com - 2016-08-05 07:31 -0700
            Re: Extending C with GC? Tim Rentsch <txr@alumni.caltech.edu> - 2016-08-05 16:01 -0700
          Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-04 21:00 +0200
            Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-04 20:26 +0100
              Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-05 10:37 +0200
                Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-05 15:52 +0100
                Re: Extending C with GC? antispam@math.uni.wroc.pl - 2016-08-21 00:09 +0000
                  Re: Extending C with GC? Gareth Owen <gwowen@gmail.com> - 2016-08-21 08:58 +0100
                  Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-21 10:48 +0200
                  Re: Extending C with GC? "Pascal J. Bourguignon" <pjb@informatimago.com> - 2016-08-21 19:58 +0200
                  Re: Extending C with GC? supercat@casperkitty.com - 2016-08-22 08:46 -0700
                    Re: Extending C with GC? Öö Tiib <ootiib@hot.ee> - 2016-08-26 02:24 -0700
                      Re: Extending C with GC? supercat@casperkitty.com - 2016-08-26 13:37 -0700
                        Re: Extending C with GC? Melzzzzz <mel@zzzzz.com> - 2016-08-27 00:41 +0200
                        Re: Extending C with GC? Öö Tiib <ootiib@hot.ee> - 2016-08-28 06:12 -0700
              Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-05 10:06 +0100
                Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-05 15:26 +0100
            Re: Extending C with GC? Tim Rentsch <txr@alumni.caltech.edu> - 2016-08-05 08:11 -0700
              Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-05 17:43 +0200
                Re: Extending C with GC? Tim Rentsch <txr@alumni.caltech.edu> - 2016-08-05 15:28 -0700
          Re: Extending C with GC? BGB <cr88192@hotmail.com> - 2016-08-04 17:11 -0500
    Re: Extending C with GC? Tim Rentsch <txr@alumni.caltech.edu> - 2016-07-31 17:35 -0700
    Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-01 07:45 +0200
      Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-01 08:49 -0700
      Re: Extending C with GC? supercat@casperkitty.com - 2016-08-01 09:06 -0700
        Re: Extending C with GC? Aleksandar Kuktin <akuktin@gmail.com> - 2016-08-05 18:11 +0000
          Re: Extending C with GC? luser droog <luser.droog@gmail.com> - 2016-08-05 11:24 -0700
    Re: Extending C with GC? "Chris M. Thomasson" <invalid@invalid.invalid> - 2016-08-08 22:12 -0700

Page 7 of 8 — ← Prev page 1 2 3 4 5 6 [7] 8  Next page →

#91709

Le 04/08/2016 à 21:26, Ben Bacarisse a écrit :
> jacobnavia <jacob@jacob.remcomp.fr> writes:
>
>> Le 04/08/2016 à 17:57, Tim Rentsch a écrit :
>>> To avoid dealing with ambiguous roots, the language needs to
>>> operate in an environment where:  one, the type of every memory
>>> cell is known (so the collector knows whether it's a pointer or
>>> not);  two, pointers cannot be "disguised" so that they are
>>> stored in places that the collector doesn't know about.  I think
>>> it would be very hard for a C implementation to satisfy the first
>>> property, and essentially impossible to satisfy the second
>>> property, assuming full C is allowed.
>>
>> That environment can be provided by the compiler. At each line of code
>> there is the Current scope. That scope and all other above it, contain
>> data that has types, of course, and all pointers are known. The
>> compiler can generate a table of locations within the function, that
>> points to the table of all valid pointers in the program and their
>> addresses.
>
>   void f(void *vp)
>   {
>       union { int i; void *p; } u.i = 42;
>       if (g()) u.p = vp;
>       ...
>   }
>
> What pointers need to be in the table here?
>

None since GC-pointers can't be stored in unions.
And they can't be assigned from normal pointers

As I said:

>> Note that only the pointers marked as GC-pointers will be included in
>> the tables.
>
> How is this achieved?  What lets you identify GC-pointers from
> non-GC-pointers?  Are you suggesting tracking pointer assignments at
> run-time?
>

int *pint;

#pragma(gc-pointer,pint)

>> All other pointers are not concerned by the GC. The
>> malloc/free system continues to work as always and you can write
>> 0xdeadbeef into any of those pointers with a simple cast.
>>
>> GC-pointers however, are not allowed to be cast into anything else but
>> a GC-pointer of (maybe) a different type.
>
> You say below that your scheme does not imply ANY change to the language
> (besides the GC interface names) but this looks like a language change
> rule to me.
>
>> GC:
>> 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.
>
> What about pointers in pointed-to objects, particularly malloc'd ones?

Are they marked as GC pointers?

if (yes) mark them
else ignore them

>
>> 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 names.
>
> You imply there is some new kind of pointer (called a GC-pointer) which
> may not be cast in certain ways.  That sounds like a language change to
> me.

No, it is a restriction of pointers that are used for the GC.

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

#91729

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

> Le 04/08/2016 à 21:26, Ben Bacarisse a écrit :
>> jacobnavia <jacob@jacob.remcomp.fr> writes:
>>
>>> Le 04/08/2016 à 17:57, Tim Rentsch a écrit :
>>>> To avoid dealing with ambiguous roots, the language needs to
>>>> operate in an environment where:  one, the type of every memory
>>>> cell is known (so the collector knows whether it's a pointer or
>>>> not);  two, pointers cannot be "disguised" so that they are
>>>> stored in places that the collector doesn't know about.  I think
>>>> it would be very hard for a C implementation to satisfy the first
>>>> property, and essentially impossible to satisfy the second
>>>> property, assuming full C is allowed.
>>>
>>> That environment can be provided by the compiler. At each line of code
>>> there is the Current scope. That scope and all other above it, contain
>>> data that has types, of course, and all pointers are known. The
>>> compiler can generate a table of locations within the function, that
>>> points to the table of all valid pointers in the program and their
>>> addresses.
>>
>>   void f(void *vp)
>>   {
>>       union { int i; void *p; } u.i = 42;
>>       if (g()) u.p = vp;
>>       ...
>>   }
>>
>> What pointers need to be in the table here?
>>
>
> None since GC-pointers can't be stored in unions.
> And they can't be assigned from normal pointers

I think this reflects your new proposal which I've talked about in the
other thread.  Oddly, though, you talk here about #pragma to "mark"
pointers.  Do you have two different proposals?  If yes, I'll comment
further on this one, but not until I know it's still an alternative.

<snip>
-- 
Ben.

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

#92556

jacobnavia <jacob@jacob.remcomp.fr> wrote:
> None since GC-pointers can't be stored in unions.
> And they can't be assigned from normal pointers

So you eliminate most interesting uses of GC.  GC is attractive
when one has complicated data structure connected via pointers.
If you forbid unions, then possible data structures are
signifcantly restricted.  More precisely, one has to replace
unions by structs, which is likely to lead to much higher
memory use.

Let me add that I dealt with a few C programs using GC.
_Each_ heavily used unions containing GC pointers.
In each case there were restrictions on unions, essentially
union had to contain a tag field to tell GC which union
branch is active.

-- 
                              Waldek Hebisch

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

#92557

antispam@math.uni.wroc.pl writes:

> jacobnavia <jacob@jacob.remcomp.fr> wrote:
>> None since GC-pointers can't be stored in unions.
>> And they can't be assigned from normal pointers
>
> So you eliminate most interesting uses of GC.  GC is attractive
> when one has complicated data structure connected via pointers.
> If you forbid unions, then possible data structures are
> signifcantly restricted.

I'm sure that's your experience, but my experience is significantly
different. In all the code on which I've worked, unions are a fairly
niche data structure, mainly restricted to convenience device for
accessing memory mapped registers.

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

#92558

Le 21/08/2016 à 02:09, antispam@math.uni.wroc.pl a écrit :
> jacobnavia <jacob@jacob.remcomp.fr> wrote:
>> None since GC-pointers can't be stored in unions.
>> And they can't be assigned from normal pointers
>
> So you eliminate most interesting uses of GC.  GC is attractive
> when one has complicated data structure connected via pointers.
> If you forbid unions, then possible data structures are
> signifcantly restricted.  More precisely, one has to replace
> unions by structs, which is likely to lead to much higher
> memory use.
>

So what?

You declare everything as normal pointers and then you can do anything 
you want as it is now.

And if you make a mistake the program will crash.

What I am proposing is an OPTIONAL pointer type (a GC aware pointer) 
that can't be used as freely as normal pointer and thus avoids the most 
common pitfalls.

> Let me add that I dealt with a few C programs using GC.
> _Each_ heavily used unions containing GC pointers.
> In each case there were restrictions on unions, essentially
> union had to contain a tag field to tell GC which union
> branch is active.
>

Sure. You will be able to go on doing that, you just do not use the GC 
pointers!

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

#92566

antispam@math.uni.wroc.pl writes:

> jacobnavia <jacob@jacob.remcomp.fr> wrote:
>> None since GC-pointers can't be stored in unions.
>> And they can't be assigned from normal pointers
>
> So you eliminate most interesting uses of GC.  GC is attractive
> when one has complicated data structure connected via pointers.
> If you forbid unions, then possible data structures are
> signifcantly restricted.  More precisely, one has to replace
> unions by structs, which is likely to lead to much higher
> memory use.
>
> Let me add that I dealt with a few C programs using GC.
> _Each_ heavily used unions containing GC pointers.
> In each case there were restrictions on unions, essentially
> union had to contain a tag field to tell GC which union
> branch is active.

With a conservative garbage collector such as Boehm GC, this would not
matter: as soon as there is a bit-pattern in the live memory
corresponding to a pointer (an address in the live memory), the pointed
block won't be collected.  The conservative garbage collector won't care
whether the bit-pattern is stored in a union field, in a char array or
wherever.

Unfortunately, if you want to activate a garbace collector
without recompiling all the libraries, you will have to use such a
conservative garbage collector.

Happily, this doesn't lead to a lot of false-live blocks, and C programs
don't often store live pointers so garbled than they wouldn't be seen by
the GC (eg. the trick of xor-ing next and previous pointers in a single
field for double-linked lists is not used in practice in programs where
you would use a garbage collector).

http://www.hboehm.info/gc


-- 
__Pascal Bourguignon__

Croire en l'histoire officielle, c'est croire des criminels sur parole.
-- Simone WEIL (1909-1943) philosophe Française.

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

#92585

On Saturday, August 20, 2016 at 7:10:04 PM UTC-5, anti...@math.uni.wroc.pl wrote:
> So you eliminate most interesting uses of GC.  GC is attractive
> when one has complicated data structure connected via pointers.
> If you forbid unions, then possible data structures are
> signifcantly restricted.  More precisely, one has to replace
> unions by structs, which is likely to lead to much higher
> memory use.

The trick is to use discriminated unions in such a way that a single word
at the start of a nested structure of any complexity will identify a type
descriptor which either identifies the whereabouts of all GC references
stored within the object or else identifies it as containing run-time-sized
arrays and indicates where the GC can find the dimensions.

C does not presently have any concept of unions that are discrimitated in
such fashion, but most C++ implementations do [if a type with virtual
methods has several types derived from it, a pointer to the original type
will behave as a pointer to a union containing that type and all derived
types].

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

#92713

On Monday, 22 August 2016 18:46:15 UTC+3, supe...@casperkitty.com  wrote:
> 
> C does not presently have any concept of unions that are discrimitated in
> such fashion, but most C++ implementations do [if a type with virtual
> methods has several types derived from it, a pointer to the original type
> will behave as a pointer to a union containing that type and all derived
> types].

What you claim is like claiming that pointer to struct that contains
'int' member is pointer to 'int'. 

Yes  if we have 'struct X {int val; int *p; };' then at address of that struct
there is required to be 'int' object but that is because int member was 
very first member. 

In C++ we can have multiple base classes and if those contain data
then according sub-objects can't all be the very first things in derived
class object.


 

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

#92760

On Friday, August 26, 2016 at 4:24:54 AM UTC-5, Öö Tiib wrote:
> On Monday, 22 August 2016 18:46:15 UTC+3, supe...@casperkitty.com  wrote:
> > 
> > C does not presently have any concept of unions that are discrimitated in
> > such fashion, but most C++ implementations do [if a type with virtual
> > methods has several types derived from it, a pointer to the original type
> > will behave as a pointer to a union containing that type and all derived
> > types].
> 
> What you claim is like claiming that pointer to struct that contains
> 'int' member is pointer to 'int'. 

If `class foo` contains virtual methods, the compiler will generally have
to store for every instance of any class derived from it information
sufficient to distinguish among all possible derived types in all cases
where it may affect how a virtual method gets dispatched.  The compiler is
not required to make that information available to the programmer, and
could omit it if it could statically determine the effect of every virtual
method call, but the idea that compilers may, at their leisure, store some
kind of type-related information within objects has always been part of
C++.

> Yes  if we have 'struct X {int val; int *p; };' then at address of that struct
> there is required to be 'int' object but that is because int member was 
> very first member. 
> 
> In C++ we can have multiple base classes and if those contain data
> then according sub-objects can't all be the very first things in derived
> class object.

My point was that a C++ compiler is allowed to, at its leisure, include
type-related within objects; if the type system had different types for
"pointer to an object with a type descriptor" and "pointer to something
that does not contain any pointers to objects with type descriptors",
and if objects with type descriptors could not be treated as sequences
of bytes, then a GC could identify every pointer that could ever be
reachable.

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

#92768

On Fri, 26 Aug 2016 13:37:58 -0700 (PDT)
supercat@casperkitty.com wrote:

> On Friday, August 26, 2016 at 4:24:54 AM UTC-5, Öö Tiib wrote:
> > On Monday, 22 August 2016 18:46:15 UTC+3, supe...@casperkitty.com
> > wrote:  
> > > 
> > > C does not presently have any concept of unions that are
> > > discrimitated in such fashion, but most C++ implementations do
> > > [if a type with virtual methods has several types derived from
> > > it, a pointer to the original type will behave as a pointer to a
> > > union containing that type and all derived types].  
> > 
> > What you claim is like claiming that pointer to struct that contains
> > 'int' member is pointer to 'int'.   
> 
> If `class foo` contains virtual methods, the compiler will generally
> have to store for every instance of any class derived from it
> information sufficient to distinguish among all possible derived
> types in all cases where it may affect how a virtual method gets
> dispatched.  The compiler is not required to make that information
> available to the programmer, and could omit it if it could statically
> determine the effect of every virtual method call, but the idea that
> compilers may, at their leisure, store some kind of type-related
> information within objects has always been part of C++.
> 
> > Yes  if we have 'struct X {int val; int *p; };' then at address of
> > that struct there is required to be 'int' object but that is
> > because int member was very first member. 
> > 
> > In C++ we can have multiple base classes and if those contain data
> > then according sub-objects can't all be the very first things in
> > derived class object.  
> 
> My point was that a C++ compiler is allowed to, at its leisure,
> include type-related within objects; if the type system had different
> types for "pointer to an object with a type descriptor" and "pointer
> to something that does not contain any pointers to objects with type
> descriptors", and if objects with type descriptors could not be
> treated as sequences of bytes, then a GC could identify every pointer
> that could ever be reachable.
> 

You miss the whole point. GC works with chunks of data. What GC needs
is special pointer type that will register itself to GC or have some
additional data so that GC can distinguish what is pointer and what is
not.
C++ pointers (except member pointers) are just ones like in C.

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

#92844

On Friday, 26 August 2016 23:38:10 UTC+3, supe...@casperkitty.com  wrote:
> On Friday, August 26, 2016 at 4:24:54 AM UTC-5, Öö Tiib wrote:
> > On Monday, 22 August 2016 18:46:15 UTC+3, supe...@casperkitty.com  wrote:
> > > 
> > > C does not presently have any concept of unions that are discrimitated in
> > > such fashion, but most C++ implementations do [if a type with virtual
> > > methods has several types derived from it, a pointer to the original type
> > > will behave as a pointer to a union containing that type and all derived
> > > types].
> > 
> > What you claim is like claiming that pointer to struct that contains
> > 'int' member is pointer to 'int'. 
> 
> If `class foo` contains virtual methods, the compiler will generally have
> to store for every instance of any class derived from it information
> sufficient to distinguish among all possible derived types in all cases
> where it may affect how a virtual method gets dispatched.  The compiler is
> not required to make that information available to the programmer, and
> could omit it if it could statically determine the effect of every virtual
> method call, but the idea that compilers may, at their leisure, store some
> kind of type-related information within objects has always been part of
> C++.

That is all true but does not make pointer to base into pointer to union.
In typical implementation a pointer to base sub-object is still just
memory address of that sub-object and virtual function call (that
compiler can't figure out compile time) is typically dispatched
using pointer to vtable within that base class sub-object pointed at.

> 
> > Yes  if we have 'struct X {int val; int *p; };' then at address of that struct
> > there is required to be 'int' object but that is because int member was 
> > very first member. 
> > 
> > In C++ we can have multiple base classes and if those contain data
> > then according sub-objects can't all be the very first things in derived
> > class object.
> 
> My point was that a C++ compiler is allowed to, at its leisure, include
> type-related within objects; if the type system had different types for
> "pointer to an object with a type descriptor" and "pointer to something
> that does not contain any pointers to objects with type descriptors",
> and if objects with type descriptors could not be treated as sequences
> of bytes, then a GC could identify every pointer that could ever be
> reachable.

C++ compiler has some freedom but that is not unrestricted. There is a
need for interoperability with other implementations and other 
programming languages and so there is desire to keep (at least part of)
ABI standardized. C++ is sort of lucky since following RAII idiom makes
it difficult to produce any garbage and so there is less need for GC.

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

#91712

On 04/08/2016 20:26, Ben Bacarisse wrote:

>   void f(void *vp)
>   {
>       union { int i; void *p; } u.i = 42;

(Is this supposed to be valid C? It doesn't compile.)

-- 
Bartc

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

#91724

BartC <bc@freeuk.com> writes:

> On 04/08/2016 20:26, Ben Bacarisse wrote:
>
>>   void f(void *vp)
>>   {
>>       union { int i; void *p; } u.i = 42;
>
> (Is this supposed to be valid C? It doesn't compile.)

Yes, it was supposed to be valid.  I put the designated initialiser in
the wrong place:

  union { int i; void *p; } u = { .i = 42 };

Thanks for spotting that.

-- 
Ben.

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

#91731

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

> Le 04/08/2016 at 17:57, Tim Rentsch wrote :
>> To avoid dealing with ambiguous roots, the language needs to
>> operate in an environment where:  one, the type of every memory
>> cell is known (so the collector knows whether it's a pointer or
>> not);  two, pointers cannot be "disguised" so that they are
>> stored in places that the collector doesn't know about.  I think
>> it would be very hard for a C implementation to satisfy the first
>> property, and essentially impossible to satisfy the second
>> property, assuming full C is allowed.
>
> That environment can be provided by the compiler.  At each line of code
> there is the Current scope.  That scope and all other above it, contain
> data that has types, of course, and all pointers are known.  The
> compiler can generate a table of locations within the function, that
> points to the table of all valid pointers in the program and their
> addresses.
>
> Note that only the pointers marked as GC-pointers will be included in
> the tables.  All other pointers are not concerned by the GC.  The
> malloc/free system continues to work as always and you can write
> 0xdeadbeef into any of those pointers with a simple cast.
>
> GC-pointers however, are not allowed to be cast into anything else but
> a GC-pointer of (maybe) a different type.
>
> GC:
> 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 names.

My comments were meant to be understood in the context of
standard C, ie, without any language extensions.  Any compiler
that differentiates between "GC pointers" and "non-GC pointers",
by whatever extension, is not standard C.  That is not to say
such an extension is not worth discussing, it may very well be,
but it isn't what I was talking about.

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

#91738

Le 05/08/2016 à 17:11, Tim Rentsch a écrit :

> My comments were meant to be understood in the context of
> standard C, ie, without any language extensions.  Any compiler
> that differentiates between "GC pointers" and "non-GC pointers",
> by whatever extension, is not standard C.  That is not to say
> such an extension is not worth discussing, it may very well be,
> but it isn't what I was talking about.
>

Yes, it is a very small extension since there are a lot of pointers already

char *a;
char *const a;
const char *a;
char  * volatile a;

The "GC" qualifier would be another of those.
I think that the goal is to make a 100% accurate GC, not just a 
conservative one.


All examples of problems, false positives, etc comes from the GC not 
being able to know where are all pointers in the program.

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

#91780

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

> Le 05/08/2016  <<E0>>  17:11, Tim Rentsch a ecrit :
>
>> My comments were meant to be understood in the context of
>> standard C, ie, without any language extensions.  Any compiler
>> that differentiates between "GC pointers" and "non-GC pointers",
>> by whatever extension, is not standard C.  That is not to say
>> such an extension is not worth discussing, it may very well be,
>> but it isn't what I was talking about.
>
> Yes, it is a very small extension since there are a lot of pointers already
>
> char *a;
> char *const a;
> const char *a;
> char  * volatile a;
>
> The "GC" qualifier would be another of those.
> I think that the goal is to make a 100% accurate GC, not just a
> conservative one.
>
>
> All examples of problems, false positives, etc comes from the GC not
> being able to know where are all pointers in the program.

Right.  I was only trying to clarify the distinction between the
two contexts.  Your extension proposal (ie, to enable an exact
collector rather than a conservative collector) is interesting.
I hope you are able to discover what it takes to implement it.

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

#91687

On 8/4/2016 10:57 AM, Tim Rentsch wrote:
> Keith Thompson <kst-u@mib.org> writes:
>

<snip>

>> I'm fairly sure this is a well known issue.  Perhaps there are
>> solutions I don't know about.
>
> GC in the face of ambiguous roots has gotten a lot of attention,
> and is generally accepted as workable in a practical engineering
> sense.  The issue of how much memory is "lost" due to false
> positives has been studied and measured (my memory is that the
> amount is "small", maybe in the neighborhood of 10%, but that is
> a very fuzzy memory so take it for what it's worth).
>

I have noted before that some areas of the address space are more likely 
to get a lot more false positives than others.

a notable example (for 32-bit targets) is stuff around 0x3E000000 to 
0x41000000, which are very likely to get false positives coming from 
floating-point numbers (which tend to form a cluster centralized around 
0x3F800000, also around 0xBF800000 but this is less of an issue).

one workaround is to deliberately put something here which is not part 
of the GC heap, which can somewhat reduce false positives due to FP 
(which may actually save more than the space taken up by this region).


other helpful strategies include having allocator support for explicit 
types (so the GC can use more precise strategies in many cases), and to 
differentiate memory that may or may not contain pointers to other objects.


> In terms of avoiding the problem of ambiguous roots, something
> that has been tried in another programming language is to have a
> "safe subset" where collection can be done reliably, and "unsafe
> features" that must be used with caution to avoid blowing up the
> collector.  That situation is superficially like C, but I don't
> know how workable (or unworkable) it would be to look for a "safe
> subset" of C where collection could be done without ambiguity.
> The problem of course is that any "safe subset" of C might be
> so limited that it would never be used.  Since a conservative
> collector (ie, that deals with ambiguous roots) seems to work
> fairly well, other avenues probably won't get much attention.
>

yeah.

another tradeoff is whether pointers are allowed to point into the body 
of an object (vs just pointing at the start of the object).

if internal pointers are allowed, this makes a much larger window for 
false positives. a case can be made for either not allowing internal 
pointers, or for only allowing internal pointers to certain object types.

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

#91447

luser droog <luser.droog@gmail.com> writes:

> In a recent thread that touched upon closures, it was made apparent
> that automatic storage reclamation would be a practical necessity
> to support closures.
>
> So how would C work with a garbage collector?  How do existing
> extensions work?  Is there a new allocator function to allow a
> "mixed" style, where you manually free the things that are easy
> and rely on the GC for the things that are hard?  Or does it
> take-over malloc(), if so what does free() do?

The Boehm collector can (and normally does?) work as a drop-in
replacment for malloc(), with free() being turned into a no-op.

A different scheme could have a different call (eg, NEW()) that
would allocate automatically reclaimed memory.  A scheme like
this could be implemented with wrappers around calls to
malloc(), realloc(), free(), etc, so that any still-active
blocks could be scanned for roots during a collection.  A scheme
like this would allow intermixing of manual deallocation and
automatic deallocation.  It imposes a performance overhead on
malloc() and free(), etc, but I believe that can be an O(1) cost
in time (perhaps amortized time) and O(blocks allocated) cost in
space.

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

#91453

Le 01/08/2016 à 00:31, luser droog a écrit :
> In a recent thread that touched upon closures, it was made apparent
> that automatic storage reclamation would be a practical necessity
> to support closures.
>
> So how would C work with a garbage collector? How do existing
> extensions work? Is there a new allocator function to allow a
> "mixed" style, where you manually free the things that are easy
> and rely on the GC for the things that are hard? Or does it
> take-over malloc(), if so what does free() do?
>
> Since I use C primarily as the implementation language for other
> programming languages, I'd love to stop writing gc code.
>

Lcc-win offers a GC in standard since 2005.

You have
gc_malloc()


IF you write (or use the corresponding header) you will get

#define gc_malloc malloc
#define free

(Or similar). There is no modification at all for the syntax of the 
language or the library.

Besides the stupid cases pointed out by thompson (WHAT IF you write a 
pointer to a file and then retrieve it later, etc) there are no changes 
to the software.

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

#91493

jacobnavia <jacob@jacob.remcomp.fr> writes:
[...]
> Lcc-win offers a GC in standard since 2005.
>
> You have
> gc_malloc()
>
>
> IF you write (or use the corresponding header) you will get
>
> #define gc_malloc malloc
> #define free

Did you mean
    #define malloc gc_malloc
?

> (Or similar). There is no modification at all for the syntax of the 
> language or the library.
>
> Besides the stupid cases pointed out by thompson (WHAT IF you write a 
> pointer to a file and then retrieve it later, etc) [...]

Cases which I explicitly acknowledged do not prevent the practical
use of GC with C.  (Incidentally, I spell my last name with an
uppercase 'T'.  Or you can use my first name if you like.)

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

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

Page 7 of 8 — ← Prev page 1 2 3 4 5 6 [7] 8  Next page →

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

csiph-web