I was wondering how a Garbage Collector can be implemented with C++ full power of pointers arithmetic. Also, In languages like Java, I can not assign literal addresses to references. In C++ it is very flexible.
I believe that C# has both, but again, the unsafe pointer in C# is the responsibility of the programmer.
EITD :: guys, I am asking if C++ pointers 'as they are currently' can be GCed in theory or not ?
Yes, a GC can be implemented independent of type safety, which C++ does not have to any great extent; but the optimization opportunities available to the GC will be limited by the amount of type leeway the language permits.
If one is willing to live with runtime-checked pointer operations, thereby re-achieving type safety where the language has given up, then a GC can be a lot more aggressive. As it is, garbage collected C++ is usually restricted to conservative collectors like the Boehm-Demers-Weiser GC.
It's written in C not C++, and is not a perfect match for C++ because it does not invoke destructors, but probably fits the bill more or less.
I am not an expert on GC implementation but if you allow the use of pointer arithmetic then you can not ever certain 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);
}
Effectively I've used pointer arithmetic in a very basic way to print out the contents of random locations in memory. This means that all the memory on the machine is essentialy reachable. And if it is reachable it can not be GCed.
Yes the above will likely cause a crash on modern Operating Systems but this code is perfectly legal C/C++. There is no way you can implement a GC that can protect against this kind of abuse if you allow pointer arithmetic :)
Yes. There was a system at NeXT back in the 1990s that worked like this: they keep track of every C/C++ memory block that has been allocated. Periodically they scan memory to see if the 4-byte (or 8-byte) value associated with that memory address is present. If it isn't, they assume there are no references, and they free the memory. It's neat and easy! But sometimes it screws up.
Here are some other approaches: http://www.hpl.hp.com/personal/Hans_Boehm/gc/
Sure why not? Pointer arithmetic from a garbage collector's perspective is no different than indexing into an array. It's things like the xor doubly linked list that screw up GC, but that's not pointer arithmetic, and undefined behavior besides. Also, Boehm exists, which is sort of empirical evidence, it's a garbage collector that works for C++. Heck for a while there they were threatening to include GC as an optional part of C++0x.
Pointer arithmetic isn't the fundamental problem. GC's have to deal with pointers being reassigned all the time, and pointer arithmetic is just another example of that. (Of course, if pointer arithmetic between pointers pointing to different buffers was allowed, it would cause problems, but it isn't. The only arithmetics you're allowed to perform on a pointer pointing into an array A are the ones that repositions it within that array.
The real problem is the lack of metadata. A GC has to know what is a pointer and what isn't.
If it encounters the value 0x27a2c230, it has to be able to determine if it is
It also has to be able to determine the extent of a struct. Assuming that value is a pointer, and it points into another struct, the GC has to be able to determine the size and extent of that struct, so it knows which range of addresses should be scanned for more pointers.
GC'ed languages have a lot of infrastructure to deal with this. C++ doesn't.
Boehm's GC is the closest you can generally get, and it basically just assumes everything is a pointer, which means some data is needlessly kept alive.
Alternatively, of course all this infrastructure could in principle be added to a C++ compiler. There's no rule in the standard that it's not allowed to exist. The problem is that it would be a major performance hit and eliminate a lot of optimization opportunities.
The question is why would you? 90% of the time where you think garbage collection would be nice, a smart pointer vector (as in a vector/map that deletes the object when it is removed) will suffice. Most of the rest of the 10% can be handled by using ref counted interfaces.
C++ pointer arithmetic allows you to construct N+1 pointers to a T[N], &T[0]...&T[N-1] and a sentinel &T[N-1]+1. These are all pointers to the T[N] array object. In that sense, they are similar to other "interior" pointers such as &foo.bar (address of object member).
Other pointer arithmetic is undefined behavior, and one obvious example of UB could be the unintentional deletion of the array by the GC.