Can GC be implemented using C ++ source pointers?

Question

I was wondering how the garbage collector can be implemented with the full degree of C ++ pointer arithmetic. Also, in languages ​​like Java, I cannot assign literals for references. In C ++, it is very flexible.

I believe that C # has both, but again, an unsafe pointer to C # is the responsibility of the programmer.

EITD :: guys, I ask if C ++ pointers, as they currently are, can in theory or not?

Answer 1

Pointer arithmetic is not a major issue. GC has to deal with reassigning pointers all the time, and pointer arithmetic is another example of this. (Of course, if the arithmetic of pointers between pointers pointing to different buffers were specified, this would create problems, but it is not. The only arithmetic that you allow to perform on a pointer pointing to array A is those that reposition it inside of this array.

The real problem is the lack of metadata. GC needs to know what a pointer is and what not.

If he meets the value 0x27a2c230 , he should be able to determine if it is

• pointer (in this case, it must follow the pointer to mark the destination as "in use" recursively)
• Integer (the same value is a valid integer. Perhaps this is not a pointer)
• or something else, say a little line.

He should also be able to determine the degree of structure. Assuming this value is a pointer and it points to a different structure, the GC should be able to determine the size and extent of this structure, so it knows which address range should be scanned for more pointers.

GC languages ​​have a lot of infrastructure to solve this problem. C ++ does not.

The Boehm GC is the closest you can usually get, and it is conservative in the sense that if something can be a pointer, GC assumes that it is one, which means that some data is uselessly stored alive. That way, it will probably save the data that should be GC'ed.

As an alternative, of course, all this infrastructure can in principle be added to the C ++ compiler. There is no rule in the standard so that it is not allowed to exist. The problem is that it will be a serious blow to productivity and will exclude many optimization opportunities.

Answer 2

Yes. In the 1990s, there was a NeXT system that worked as follows: they track every block of C / C ++ memory that has been allocated. They periodically scan the memory to see if there is a 4-byte (or 8-byte) value associated with this memory address. If this is not the case, they assume that there are no links, and they free up memory. It is neat and easy! But sometimes it drags on.

Here are a few other approaches: http://www.hpl.hp.com/personal/Hans_Boehm/gc/

http://developers.sun.com/solaris/articles/libgc.html

Answer 3

Do you mean something like smart_ptr ?

Answer 4

Boehm GC ?

It is written in C not C ++ and is not an ideal combination for C ++ because it does not call destructors, but is probably more suitable for a bill.

Answer 5

Sure why not? Arithmetic of the pointer from the point of view of the garbage collector does not differ from indexing into an array. This is similar to the xor double-linked list that screwed up the GC, but it is not pointer arithmetic, nor is it undefined behavior. In addition, there is Boehm, which is a kind of empirical evidence, it is a garbage collector that runs in C ++. For some time, they threatened to include GC as an optional part of C ++ 0x.

Answer 6

The question is, why would you? 90% of the time when you think that garbage collection would be nice, a bright vector of the pointer will be enough (like in a vector / map that deletes an object when it is deleted). Most of the remaining 10% can be handled with ref counted interfaces.

Answer 7

Arithmetic of pointers in C ++ allows you to create N + 1 pointers to T [N], & T [0] ... & T [N-1] and sentinel & T [N-1] + 1. All this points to an object array T [N]. In this sense, they are similar to other "internal" pointers, such as & foo.bar (the address of an object member).

Another pointer arithmetic is undefined behavior, and one obvious example of UB might be the inadvertent deletion of a GC array.

Answer 8

Yes, GC can be implemented regardless of type safety, which C ++ does not have to a large extent; but the optimization options available to the GC will be limited by the number of type restrictions that the language allows.

If someone wants to live with the proven operations of a time pointer, thereby re-creating type safety where the language is refused, then the GC can be much more aggressive. Be that as it may, the garbage collector collected by C ++ is usually limited to conservative collectors such as the Boehm-Demers-Weiser GC .

Answer 9

I am not an expert on GC implementation, but if you allow the use of pointer arithmetic, then you can never say that a given address in memory can no longer be referenced.

as an example

 int *crazy_pointer; srand ( time(NULL) ); while(true) { crazy_pointer = (int *) rand() % MAX_SIZE_OF_MEMORY: printf("$d",*crazy_pointer); } 

In fact, I used pointer arithmetic in the easiest way to print the contents of random locations in memory. This means that all the memory on the machine is very important. And if it is available, it cannot be GCed.

Yes, this can lead to a crash in modern operating systems, but this code is completely legal C / C ++. It is not possible to implement a GC that can protect against this kind of abuse if you allow pointer arithmetic :)