Re: [boost] library proposal: garbage collection
In-Reply-To: <dpsep6$t6q$1@sea.gmane.org> axilmar@b-online.gr (Achilleas Margaritis) wrote (abridged):
the following proposal is about a small library for multithreaded garbage collection using only boost threads.
Am I right in thinking your approach does not allow pointers to objects to be embedded into other objects? They have to be on the stack? If so, I imagine that would be a fairly severe limitation. It prevents you from having circular chains of pointers, support for which is usually one of the reasons for adopting GC. -- Dave Harris, Nottingham, UK.
The purpose of the class gc_ptr<T> is to know where the global/stack pointers are. Member pointers do not need a special class, since each heap object is fully scanned for pointers to other objects. Here is an example of my approach: class MyClass : public gc_object { public: MyClass *other; }; gc_ptr<MyClass> obj1 = new MyClass; obj1->other = new MyClass; The above approach assumes that GC objects are heap-allocated. There are alternatives though, if one wishes to have GC objects either in heap or stack: ------------------------------------------------------- Alternative 1 - using gc_ptr<T> for global, stack and member pointers. It is possible to use the gc_ptr class for global, stack and member pointers. The class would have to check if it belongs in the last-known created object by checking its address against the address of the last created object. If the pointer falls within the memory area of the last created object, then it is a member pointer, otherwise it is a global/stack pointer. Example code: template < class T > class gc_ptr { public: gc_ptr() { if this not within last created object then { pointer stack->push(this); } } }; Advantages of this approach: 1) only one special pointer class to use. Disadvantages of this approach: 1) non-precise garbage collection, since the system does not know which pointers exist 2) slower sweep, as memory blocks need to be scanned fully 3) slower than alternative #2, since the check for if the pointer is a global/stack or member pointer is repeated for root pointers as well. ------------------------------------------------------- Alternative 2 - using two different pointer classes. A better alternative (for performance reasons) is to use two different pointer classes, one for member pointers and one for root pointers. Example: template < class T > class member_ptr { public: member_ptr() { if this not within last created object then { pointer stack->push(this); } else last created object->register_member_ptr(this); } }; template < class T > class root_ptr { public: root_ptr() { pointer stack->push(this); } ~root_ptr() { pointer stack->pop(this); } }; Then usage will be: class MyClass : public gc_object { public: member_ptr<MyClass> other; }; root_ptr<MyClass> obj1 = new MyClass; obj1->other = new MyClass; advantages of this alternative: 1) precise garbage collection, since only garbage-collected pointers are scanned 2) faster sweep phase, since only garbage-collected pointers are scanned disadvantages of this alternative: 1) a performance hit, since member pointers need to be initialized as well. 2) it needs more memory, since each allocated block needs space for storing member pointer offsets. "Dave Harris" <brangdon@cix.compulink.co.uk> wrote in message news:memo.278799@cix.compulink.co.uk...
In-Reply-To: <dpsep6$t6q$1@sea.gmane.org> axilmar@b-online.gr (Achilleas Margaritis) wrote (abridged):
the following proposal is about a small library for multithreaded garbage collection using only boost threads.
Am I right in thinking your approach does not allow pointers to objects to be embedded into other objects? They have to be on the stack?
If so, I imagine that would be a fairly severe limitation. It prevents you from having circular chains of pointers, support for which is usually one of the reasons for adopting GC.
-- Dave Harris, Nottingham, UK.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On 01/11/2006 08:27 AM, Achilleas Margaritis wrote: [snip]
------------------------------------------------------- Alternative 1 - using gc_ptr<T> for global, stack and member pointers.
It is possible to use the gc_ptr class for global, stack and member pointers. The class would have to check if it belongs in the last-known created object by checking its address against the address of the last created object. If the pointer falls within the memory area of the last created object, then it is a member pointer, otherwise it is a global/stack pointer. Example code:
template < class T > class gc_ptr { public: gc_ptr() { if this not within last created object then {
This test, IIUC, requires access to a global object (pointer to last created object or something similar). Wouldn't this then require synchronization between threads; hence, cause a big slowdown for each gc_ptr creation?
pointer stack->push(this); } } };
"Larry Evans" <cppljevans@cox-internet.com> wrote in message news:dq36jf$7c0$1@sea.gmane.org...
On 01/11/2006 08:27 AM, Achilleas Margaritis wrote: [snip]
------------------------------------------------------- Alternative 1 - using gc_ptr<T> for global, stack and member pointers.
It is possible to use the gc_ptr class for global, stack and member pointers. The class would have to check if it belongs in the last-known created object by checking its address against the address of the last created object. If the pointer falls within the memory area of the last created object, then it is a member pointer, otherwise it is a global/stack pointer. Example code:
template < class T > class gc_ptr { public: gc_ptr() { if this not within last created object then {
This test, IIUC, requires access to a global object (pointer to last created object or something similar). Wouldn't this then require synchronization between threads; hence, cause a big slowdown for each gc_ptr creation?
If the pointer stack is thread-specific storage, then synchronization is not be needed.
pointer stack->push(this); } } };
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On 01/11/2006 09:56 AM, Achilleas Margaritis wrote:
"Larry Evans" <cppljevans@cox-internet.com> wrote in message [snip]
gc_ptr() { if this not within last created object then {
This test, IIUC, requires access to a global object (pointer to last created object or something similar). Wouldn't this then require synchronization between threads; hence, cause a big slowdown for each gc_ptr creation?
If the pointer stack is thread-specific storage, then synchronization is not be needed.
Ah, yes. I failed to remember you first post mentioned:
a) each garbage-collected thread shall have its own pointer stack allocated as thread-local-storage. The size of the pointer stack shall be analogous to the size of the hardware stack for the size of pointer of the machine.
Now, wouldn't this require the gc_ptr::CTOR to *never* take a raw pointer? This is because to test: this not within last created object within gc_ptr::CTOR, the pointee to the last created object would have to be stored in some thread-local-storage by another gc_ptr, and the only way this could happen is if the first gc_ptr first: 1) allocated the storage for the pointee 2) stored the last-created-pointer in some thread-local-storage 3) created the pointee with placement new (this requiring knowlege about the pointee's CTOR) 4) then zeroed the last-created-pointer Does this make sense? [snip]
"Larry Evans" <cppljevans@cox-internet.com> wrote in message news:dq3b38$sme$1@sea.gmane.org...
On 01/11/2006 09:56 AM, Achilleas Margaritis wrote:
"Larry Evans" <cppljevans@cox-internet.com> wrote in message [snip]
gc_ptr() { if this not within last created object then {
This test, IIUC, requires access to a global object (pointer to last created object or something similar). Wouldn't this then require synchronization between threads; hence, cause a big slowdown for each gc_ptr creation?
If the pointer stack is thread-specific storage, then synchronization is not be needed.
Ah, yes. I failed to remember you first post mentioned:
a) each garbage-collected thread shall have its own pointer stack allocated as thread-local-storage. The size of the pointer stack shall be analogous to the size of the hardware stack for the size of pointer of the machine.
Now, wouldn't this require the gc_ptr::CTOR to *never* take a raw pointer? This is because to test:
this not within last created object
within gc_ptr::CTOR, the pointee to the last created object would have to be stored in some thread-local-storage by another gc_ptr, and the only way this could happen is if the first gc_ptr first:
1) allocated the storage for the pointee 2) stored the last-created-pointer in some thread-local-storage 3) created the pointee with placement new (this requiring knowlege about the pointee's CTOR) 4) then zeroed the last-created-pointer
Does this make sense? [snip]
No, the new object will be placed in a thread-local-storage list by operator new. Here is the sequence of operations: 1) operator new is invoked: it allocates memory for the new block and places the block in a thread-local-storage object list. 2) gc_ptr::CTOR is invoked: it looks at the last entry of the thread-local-storage object list. If not inside that block, it adds itself to the thread-local-storage pointer stack.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On 01/11/2006 10:39 AM, Achilleas Margaritis wrote: [snip]
1) allocated the storage for the pointee 2) stored the last-created-pointer in some thread-local-storage 3) created the pointee with placement new (this requiring knowlege about the pointee's CTOR) 4) then zeroed the last-created-pointer
Does this make sense? [snip]
No, the new object will be placed in a thread-local-storage list by operator new.
Here is the sequence of operations:
1) operator new is invoked: it allocates memory for the new block and places the block in a thread-local-storage object list. 2) gc_ptr::CTOR is invoked: it looks at the last entry of the thread-local-storage object list. If not inside that block, it adds itself to the thread-local-storage pointer stack.
-------------- cut here ------------- The only gc_ptr on the stack is on_stk.other; yet,
OK, but in my mental trace of the following code: <------------- cut here -------------- class MyClass : public gc_object { public: gc_ptr<MyClass> other; MyClass(unsigned n=0) : other(n?new MyClass(n-1):(MyClass1*)0) {} }; MyClass on_stk(3); the others are put on the stack because, in each case, the last created gc_object is the one used in the argument to the gc_ptr CTOR. Am I missing something? If so, could you maybe do a quick prototype to illustrate what I'm missing? TIA.
On 01/12/2006 06:31 AM, Larry Evans wrote: [snip]
-------------- cut here ------------- The only gc_ptr on the stack is on_stk.other; yet, ^actually the others are put on the stack because, in each The above line should be:
the others are pushed onto the 'pointer stack' because, in each [snip]
participants (3)
-
Achilleas Margaritis -
brangdon＠cix.compulink.co.uk -
Larry Evans