Live data from Hacker News

Baby's First Garbage Collector

journal.stuffwithstuff.com

11–20 of 90 posts

Re: Baby's First Garbage Collector

#11
post #8

Not having studied the topic in depth, my first thought is whether true pointers and a garbage collector can coexist (without artificially removing parts of the language). The big condition for knowing if something is still in use is whether any references exist to it. But in a language like C , you could cast a pointer to something else (like a void pointer for some quasi generic linked list), store it somewhere, an…

You don't need to give up pointers, or pointer arithmetic, just the ability to obscure what a pointer points to. Casting to void does not do this (and indeed, has no run time effect at all). Metadata is associated with the pointed-to block of memory, so as long as the address is recognizable as a pointer at runtime, you can do GC. Some of the things that break GC aren't even technically valid C code. For example, say…

it's illegal to dereference a pointer past the end of an allocation.

Yes, but there's a legal way to do this.

reference the other two areas with offsets relative to the first area

If you cast the pointers to uintptr_t, and perform your arithmetic on uintptr_t and cast your final pointer back (void * ) before using it, what you've done is perfectly legal and safe (albeit weird) since uintptr_t is an unsigned integer type with all the flexibility of unsigned integers, and if x = (uintptr_t)p then it's guaranteed that p == (void * )x.

In other words:

    char * x = malloc(100);
    char * y = malloc(100);
    ptrdiff_t yminusx = y - x;

    x[yminusx] = '\0'
is undefined behaviour, but

    char * x = malloc(100);
    char * y = malloc(100);
    uintptr_t yminusx = (uintptr_t)(y) - (uintptr_t)(x);

    *(char *)(void *)((uintptr_t)(x) + yminusx) = '\0'
is valid C (and has the same meaning on a DWIM compiler).

Re: Baby's First Garbage Collector

#12
post #4

Not having studied the topic in depth, my first thought is whether true pointers and a garbage collector can coexist (without artificially removing parts of the language). The big condition for knowing if something is still in use is whether any references exist to it. But in a language like C , you could cast a pointer to something else (like a void pointer for some quasi generic linked list), store it somewhere, an…

I don't know of any language that has pointers and a GC. Are there any? C# lets you use pointers but only if you tell the GC to not move your object and promise to behave.

You can have a GC without compaction.

Go has a GC and pointers, including internal pointers (e.g. to a field of a struct). Its GC started out fully conservative, then precise for the heap and conservative for the stack, and future versions will be fully precise.

Re: Baby's First Garbage Collector

#13
post #4

Not having studied the topic in depth, my first thought is whether true pointers and a garbage collector can coexist (without artificially removing parts of the language). The big condition for knowing if something is still in use is whether any references exist to it. But in a language like C , you could cast a pointer to something else (like a void pointer for some quasi generic linked list), store it somewhere, an…

I don't know of any language that has pointers and a GC. Are there any? C# lets you use pointers but only if you tell the GC to not move your object and promise to behave.

Some languages in the Wirth family have pointers and GC, e.g. Modula-3. It has a module-level notion of safety, so that modules using potentially unsafe pointer manipulation are marked as unsafe and break runtime safety guarantees. It also doesn't guarantee that all pointers will be roots for GC.

Re: Baby's First Garbage Collector

#14
post #8

Earlier quoted context omitted.

You don't need to give up pointers, or pointer arithmetic, just the ability to obscure what a pointer points to. Casting to void does not do this (and indeed, has no run time effect at all). Metadata is associated with the pointed-to block of memory, so as long as the address is recognizable as a pointer at runtime, you can do GC. Some of the things that break GC aren't even technically valid C code. For example, say…

it's illegal to dereference a pointer past the end of an allocation. Yes, but there's a legal way to do this. reference the other two areas with offsets relative to the first area If you cast the pointers to uintptr_t, and perform your arithmetic on uintptr_t and cast your final pointer back (void * ) before using it, what you've done is perfectly legal and safe (albeit weird) since uintptr_t is an unsigned integer t…

[deleted]

Re: Baby's First Garbage Collector

#15
post #8

Earlier quoted context omitted.

You don't need to give up pointers, or pointer arithmetic, just the ability to obscure what a pointer points to. Casting to void does not do this (and indeed, has no run time effect at all). Metadata is associated with the pointed-to block of memory, so as long as the address is recognizable as a pointer at runtime, you can do GC. Some of the things that break GC aren't even technically valid C code. For example, say…

it's illegal to dereference a pointer past the end of an allocation. Yes, but there's a legal way to do this. reference the other two areas with offsets relative to the first area If you cast the pointers to uintptr_t, and perform your arithmetic on uintptr_t and cast your final pointer back (void * ) before using it, what you've done is perfectly legal and safe (albeit weird) since uintptr_t is an unsigned integer t…

Right. You could also convert a pointer to a uintptr_t, XOR it with some value, then at some later point XOR it again to get back the original address and cast it back to a pointer and dereference it, and it would be legal despite breaking GC. However, a number of things that also break GC, like your first example, also happen not to be legal C even though they'll probably work on any existing implementation.

Re: Baby's First Garbage Collector

#16
post #4

Not having studied the topic in depth, my first thought is whether true pointers and a garbage collector can coexist (without artificially removing parts of the language). The big condition for knowing if something is still in use is whether any references exist to it. But in a language like C , you could cast a pointer to something else (like a void pointer for some quasi generic linked list), store it somewhere, an…

I don't know of any language that has pointers and a GC. Are there any? C# lets you use pointers but only if you tell the GC to not move your object and promise to behave.

Objective-C has pointers and a GC.

Re: Baby's First Garbage Collector

#17
post #4

Not having studied the topic in depth, my first thought is whether true pointers and a garbage collector can coexist (without artificially removing parts of the language). The big condition for knowing if something is still in use is whether any references exist to it. But in a language like C , you could cast a pointer to something else (like a void pointer for some quasi generic linked list), store it somewhere, an…

I don't know of any language that has pointers and a GC. Are there any? C# lets you use pointers but only if you tell the GC to not move your object and promise to behave.

> "I don't know of any language that has pointers and a GC. Are there any?"

Objective-C used to have a garbage collector, though (at least with regards to iOS) Apple removed this capability with the introduction or ARC. On the following URL is some discussion on the Objective-C garbage collector: http://cocoasamurai.blogspot.nl/2010/12/objective-c-memory-m...

Re: Baby's First Garbage Collector

#18
post #10
post #8

Earlier quoted context omitted.

You don't need to give up pointers, or pointer arithmetic, just the ability to obscure what a pointer points to. Casting to void does not do this (and indeed, has no run time effect at all). Metadata is associated with the pointed-to block of memory, so as long as the address is recognizable as a pointer at runtime, you can do GC. Some of the things that break GC aren't even technically valid C code. For example, say…

Does this still work if the GC compacts memory? I don't know much about GCs, but it seems like once your GC is advanced enough with generational collecting, compacting, etc, then allowing raw pointers seems at odds with what the GC is trying todo. I'm sure it's possible, but it's probably a heck of a lot easier just to not allow pointers.

It works fine as long as you have enough type information to know what is and is not a pointer.

Re: Baby's First Garbage Collector

#19
post #8

Earlier quoted context omitted.

You don't need to give up pointers, or pointer arithmetic, just the ability to obscure what a pointer points to. Casting to void does not do this (and indeed, has no run time effect at all). Metadata is associated with the pointed-to block of memory, so as long as the address is recognizable as a pointer at runtime, you can do GC. Some of the things that break GC aren't even technically valid C code. For example, say…

it's illegal to dereference a pointer past the end of an allocation. Yes, but there's a legal way to do this. reference the other two areas with offsets relative to the first area If you cast the pointers to uintptr_t, and perform your arithmetic on uintptr_t and cast your final pointer back (void * ) before using it, what you've done is perfectly legal and safe (albeit weird) since uintptr_t is an unsigned integer t…

It looks like the second is still valid C, but a C++11 compiler is allowed to break it if it declares "strict pointer safety" rules are in effect at runtime (which a GC implementation would presumably do)

Re: Baby's First Garbage Collector

#20
post #9
post #7

Earlier quoted context omitted.

The Boehm–Demers–Weiser garbage collector is a fairly famous implementation of a GC for vanilla C, pointers and all: http://en.wikipedia.org/wiki/Boehm_garbage_collector

Yeah I'm aware of optional GCs. What I meant was languages that ship with a GC as standard and also have pointers. In the case of Boehm, since you choose to bring it in yourself, it's up to you to make sure you don't abuse it.

Well, pretty much any language with a GC can abuse the GC, regardless of whether it's optional or designed in from the start. It just happens to be a lot harder to abuse a GC than to forget to free/delete something.
Post reply on HN