portable precise garbage collector for C++
Dear boost developers, You can find a new version of my portable precise C++ garbage collector in vault/memory. Is any one interested? Can I submit my library to be part of boost? Achilleas Margaritis
On 09/16/07 16:56, Achilleas Margaritis wrote:
Dear boost developers,
You can find a new version of my portable precise C++ garbage collector in vault/memory.
Is any one interested? How does this collector determine the location of pointers on the stack and within the heap?
Larry Evans wrote:
On 09/16/07 16:56, Achilleas Margaritis wrote:
Dear boost developers,
You can find a new version of my portable precise C++ garbage collector in vault/memory.
Is any one interested? How does this collector determine the location of pointers on the stack and within the heap?
An internal bit map is used as a pointer database. Each bit represents one pointer location in memory. When the class gc_ptr<T> is created, the bit that corresponds to the pointer's address is set. When a pointer is destroyed, the same bit is reset. The bitmap is organized in pages of 4K and allocated dynamically. The collector sweeps unused pages at collection time.
On 09/17/07 03:30, Achilleas Margaritis wrote:
Larry Evans wrote:
On 09/16/07 16:56, Achilleas Margaritis wrote:
Dear boost developers,
You can find a new version of my portable precise C++ garbage collector in vault/memory. [snip]
Is any one interested? How does this collector determine the location of pointers on the stack and within the heap?
An internal bit map is used as a pointer database. Each bit represents one pointer location in memory.
When the class gc_ptr<T> is created, the bit that corresponds to the pointer's address is set.
What about gc_ptr<T*>? IOW, what if the pointer is actually a pointer to a c array of T or a std::vector<T> or a pointer to std::list<T>. OOPS. Just read the cppgc.txt which says: 4) manage arrays of objects However, I'm still wondering if it cppgc can handle gc_ptr<std::vector<T> > or pointer to any other std container. Do you have tests for these cases?
Larry Evans wrote:
On 09/17/07 03:30, Achilleas Margaritis wrote:
Larry Evans wrote:
On 09/16/07 16:56, Achilleas Margaritis wrote:
Dear boost developers,
You can find a new version of my portable precise C++ garbage collector in vault/memory. [snip] Is any one interested? How does this collector determine the location of pointers on the stack and within the heap? An internal bit map is used as a pointer database. Each bit represents one pointer location in memory.
When the class gc_ptr<T> is created, the bit that corresponds to the pointer's address is set.
What about gc_ptr<T*>? IOW, what if the pointer is actually a pointer to a c array of T or a std::vector<T> or a pointer to std::list<T>.
OOPS. Just read the cppgc.txt which says:
4) manage arrays of objects
However, I'm still wondering if it cppgc can handle gc_ptr<std::vector<T> > or pointer to any other std container. Do you have tests for these cases?
It's very easy to make an STL allocator for gc: the allocator's pointer type will be gc_ptr<T>. The following will be possible: gc_ptr<std::vector<gc_ptr<Foo> > foos = gc_new std::vector<gc_ptr<Foo> , gc_allocator<T> >;
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On 09/17/07 09:55, Achilleas Margaritis wrote:
Larry Evans wrote: [snip]
However, I'm still wondering if it cppgc can handle gc_ptr<std::vector<T> > or pointer to any other std container. Do you have tests for these cases?
It's very easy to make an STL allocator for gc: the allocator's pointer type will be gc_ptr<T>.
The following will be possible:
gc_ptr<std::vector<gc_ptr<Foo> > foos = gc_new std::vector<gc_ptr<Foo> , gc_allocator<T> >;
Could you provide one in some test code which demonstrates that the garbage is actually collected and which handles cycles. For example, a gc_ptr<std::vector<T> > where T contains a gc_ptr<std::vector<T> > which points to the containing vector.
O/H Larry Evans έγραψε:
On 09/17/07 09:55, Achilleas Margaritis wrote:
Larry Evans wrote: [snip]
However, I'm still wondering if it cppgc can handle gc_ptr<std::vector<T> > or pointer to any other std container. Do you have tests for these cases? It's very easy to make an STL allocator for gc: the allocator's pointer type will be gc_ptr<T>.
The following will be possible:
gc_ptr<std::vector<gc_ptr<Foo> > foos = gc_new std::vector<gc_ptr<Foo> , gc_allocator<T> >;
Could you provide one in some test code which demonstrates that the garbage is actually collected and which handles cycles. For example, a gc_ptr<std::vector<T> > where T contains a gc_ptr<std::vector<T> > which points to the containing vector.
I updated the code in the vault with the example you requested.
On 09/17/07 13:29, Achilleas Margaritis wrote: [snip]
I updated the code in the vault with the example you requested.
Thanks, but could you also rm or guard with #if..#endif the non-portable MSVC parts. I'm using linux; hence, can't compile the code as written. TIA. -regards, Larry
On 09/17/07 13:29, Achilleas Margaritis wrote:
O/H Larry Evans έγραψε: [snip]
Could you provide one in some test code which demonstrates that the garbage is actually collected and which handles cycles. For example, a gc_ptr<std::vector<T> > where T contains a gc_ptr<std::vector<T> > which points to the containing vector.
I updated the code in the vault with the example you requested.
Could you be more specific about where the test code is? I tried finding it without success: cd ~/prog_dev/boost-svn/ro/trunk/sandbox/axilmar/ find . -name \*.[ch]pp -exec grep vector {} \; -ls #include <vector> typedef std::vector<T *> _vector; _vector _entries; 6488878 12 -rw-r--r-- 1 evansl evansl 12135 Sep 17 2007 ./include/cppgc.hpp Compilation finished at Mon Sep 17 14:01:32
Larry Evans wrote:
On 09/17/07 13:29, Achilleas Margaritis wrote:
O/H Larry Evans έγραψε: [snip]
Could you provide one in some test code which demonstrates that the garbage is actually collected and which handles cycles. For example, a gc_ptr<std::vector<T> > where T contains a gc_ptr<std::vector<T> > which points to the containing vector. I updated the code in the vault with the example you requested.
Could you be more specific about where the test code is? I tried finding it without success:
cd ~/prog_dev/boost-svn/ro/trunk/sandbox/axilmar/ find . -name \*.[ch]pp -exec grep vector {} \; -ls #include <vector> typedef std::vector<T *> _vector; _vector _entries; 6488878 12 -rw-r--r-- 1 evansl evansl 12135 Sep 17 2007 ./include/cppgc.hpp
Compilation finished at Mon Sep 17 14:01:32
I have not yet made the GC STL allocator. The example I put was about cycles.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On 09/17/07 09:55, Achilleas Margaritis wrote: [snip]
However, I'm still wondering if it cppgc can handle gc_ptr<std::vector<T> > or pointer to any other std container. Do you have tests for these cases?
It's very easy to make an STL allocator for gc: the allocator's pointer type will be gc_ptr<T>.
The following will be possible:
gc_ptr<std::vector<gc_ptr<Foo> > foos = gc_new std::vector<gc_ptr<Foo> , gc_allocator<T> >;
I think you'd have to change the implementation of the std containers to make it work because many would use pointers and these would have to be derived from the 'struct _ptr' defined in cppgc.hpp in order for them to be registered in the pointer data base as described in my other post: http://archives.free.net.ph/message/20070920.142319.8368416a.en.html Do you have any other idea about how it can be done?
On 09/20/07 14:33, Larry Evans wrote: [snip]
I think you'd have to change the implementation of the std containers to make it work because many would use pointers and these would have to be derived from the 'struct _ptr' defined in cppgc.hpp in order for them to be registered in the pointer data base as described in my other post:
http://archives.free.net.ph/message/20070920.142319.8368416a.en.html
Do you have any other idea about how it can be done?
IOW, if std::list were implemented like the _list in cppgc.hpp then _list::_begin would have to be derived from _ptr. Hm... What prevents the contents of _list from being garbage collected... Oh yeah, it's created with std::new not gc_new.
O/H Larry Evans έγραψε:
On 09/17/07 09:55, Achilleas Margaritis wrote: [snip]
However, I'm still wondering if it cppgc can handle gc_ptr<std::vector<T> > or pointer to any other std container. Do you have tests for these cases? It's very easy to make an STL allocator for gc: the allocator's pointer type will be gc_ptr<T>.
The following will be possible:
gc_ptr<std::vector<gc_ptr<Foo> > foos = gc_new std::vector<gc_ptr<Foo> , gc_allocator<T> >;
I think you'd have to change the implementation of the std containers to make it work because many would use pointers and these would have to be derived from the 'struct _ptr' defined in cppgc.hpp in order for them to be registered in the pointer data base as described in my other post:
http://archives.free.net.ph/message/20070920.142319.8368416a.en.html
Do you have any other idea about how it can be done?
I thought std containers use the allocator::pointer type for their pointers.
On 09/20/07 18:06, Achilleas Margaritis wrote:
O/H Larry Evans έγραψε: [snip]
I think you'd have to change the implementation of the std containers to make it work because many would use pointers and these would have to be derived from the 'struct _ptr' defined in cppgc.hpp in order for them to be registered in the pointer data base as described in my other post:
http://archives.free.net.ph/message/20070920.142319.8368416a.en.html
Do you have any other idea about how it can be done?
I thought std containers use the allocator::pointer type for their pointers.
So then it should be easy. Just make the allocator template parameter to the container template have allocator::pointer == gc_ptr<T> or something like that. Maybe you could have an example of this in the next version?
On 9/21/07, Achilleas Margaritis <axilmar@ath.forthnet.gr> wrote:
I thought std containers use the allocator::pointer type for their pointers.
In theory yes. In practice the standard gives standard library implementors an explicit "temporary" permission to always assume that allocator::pointer is a raw pointer. It is mostly a quality of implementation issue, as there are standard libraries that do not make use of this permission. The upcoming revision of the standard will very likely remove this permission. gpd
At 2:06 AM +0300 9/21/07, Achilleas Margaritis wrote:
I thought std containers use the allocator::pointer type for their pointers.
Unfortunately, not necessarily. They're permitted to bypass that and use T* directly. Ion Gaztañaga ran into this when trying to put containers into shared memory for boost.interprocess.
O/H Kim Barrett έγραψε:
At 2:06 AM +0300 9/21/07, Achilleas Margaritis wrote:
I thought std containers use the allocator::pointer type for their pointers.
Unfortunately, not necessarily. They're permitted to bypass that and use T* directly. Ion Gaztañaga ran into this when trying to put containers into shared memory for boost.interprocess. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
The collector offers the possibility of customizing the scanning procedure (the procedure which scans a block for pointers) through the class gc_traits<T>. So if there is a data structure where gc_ptr<T> can not be used, a custom scan routine especially coded for the data structure in question can solve the problem.
On 09/21/07 04:14, Achilleas Margaritis wrote:
O/H Kim Barrett έγραψε:
At 2:06 AM +0300 9/21/07, Achilleas Margaritis wrote:
I thought std containers use the allocator::pointer type for their pointers. Unfortunately, not necessarily. They're permitted to bypass that and use T* directly. Ion Gaztañaga ran into this when trying to put containers into shared memory for boost.interprocess.
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
The collector offers the possibility of customizing the scanning procedure (the procedure which scans a block for pointers) through the class gc_traits<T>. So if there is a data structure where gc_ptr<T> can not be used, a custom scan routine especially coded for the data structure in question can solve the problem.
Given the following: std::list<gc_ptr<Node> > node_list; where Node is defined in cppgc/src/main.cpp, then no gc_ptr's within node_list would be registered as root pointers; so, wouldn't any Nodes of the gc_ptr's pushed into node_list be collected? I guess I don't understand how a customized scanner would help. Sure, once it's known that node_list contains gc_ptr's, the scanner could be called, but the collector first needs to be notified of that fact. Am I missing something.
On 09/21/07 04:14, Achilleas Margaritis wrote: [snip] The collector offers the possibility of customizing the scanning
procedure (the procedure which scans a block for pointers) through the class gc_traits<T>. So if there is a data structure where gc_ptr<T> can not be used, a custom scan routine especially coded for the data structure in question can solve the problem.
Given the following:
std::list<gc_ptr<Node> > node_list;
where Node is defined in cppgc/src/main.cpp, then no gc_ptr's within node_list would be registered as root pointers; so, wouldn't any Nodes of the gc_ptr's pushed into node_list be collected? I guess I don't understand how a customized scanner would help. Sure, once it's known that [snip] boost-vault/memory/main_stl.zip contains a main program showing a segfault. The only diff with cppgc/src/main.cpp is that GCBench is templated so that the Node's contained gc_ptr<Node>'s are either stored in std::pair or in std::list, depending on newly added template
On 09/21/07 06:26, Larry Evans wrote: param to GCBench. The zip also contains a gdb session showing the segfault when using std::pair.
O/H Larry Evans έγραψε:
On 09/21/07 04:14, Achilleas Margaritis wrote:
O/H Kim Barrett έγραψε:
At 2:06 AM +0300 9/21/07, Achilleas Margaritis wrote:
I thought std containers use the allocator::pointer type for their pointers. Unfortunately, not necessarily. They're permitted to bypass that and use T* directly. Ion Gaztañaga ran into this when trying to put containers into shared memory for boost.interprocess.
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
The collector offers the possibility of customizing the scanning procedure (the procedure which scans a block for pointers) through the class gc_traits<T>. So if there is a data structure where gc_ptr<T> can not be used, a custom scan routine especially coded for the data structure in question can solve the problem.
Given the following:
std::list<gc_ptr<Node> > node_list;
where Node is defined in cppgc/src/main.cpp, then no gc_ptr's within node_list would be registered as root pointers; so, wouldn't any Nodes of the gc_ptr's pushed into node_list be collected? I guess I don't understand how a customized scanner would help. Sure, once it's known that node_list contains gc_ptr's, the scanner could be called, but the collector first needs to be notified of that fact.
Am I missing something.
You have to define the appropriate allocator (in this case, gc_allocator<Node>) for the std::list to get its member pointers registered with the collector. gc_allocator<T> defines its pointer as gc_ptr<T>: std::list<gc_ptr<Node>, gc_allocator<gc_ptr<Node> > > node_list; Although I made the allocator, it does not work with the VC8 STL or the mingw STL, for the reason mentioned above (STL implementors choosing T* over allocator::pointer). Is there an STL implementation without this problem? perhaps STLPort? I have to try it myself, but if anyone knows, please tell me.
On 09/21/07 11:26, Achilleas Margaritis wrote:
O/H Larry Evans έγραψε:
On 09/21/07 04:14, Achilleas Margaritis wrote:
O/H Kim Barrett έγραψε:
At 2:06 AM +0300 9/21/07, Achilleas Margaritis wrote:
I thought std containers use the allocator::pointer type for their pointers. Unfortunately, not necessarily. They're permitted to bypass that and use T* directly. Ion Gaztañaga ran into this when trying to put containers into shared memory for boost.interprocess.
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
The collector offers the possibility of customizing the scanning procedure (the procedure which scans a block for pointers) through the class gc_traits<T>. So if there is a data structure where gc_ptr<T> can not be used, a custom scan routine especially coded for the data structure in question can solve the problem. Given the following:
std::list<gc_ptr<Node> > node_list;
where Node is defined in cppgc/src/main.cpp, then no gc_ptr's within node_list would be registered as root pointers; so, wouldn't any Nodes of the gc_ptr's pushed into node_list be collected? I guess I don't understand how a customized scanner would help. Sure, once it's known that node_list contains gc_ptr's, the scanner could be called, but the collector first needs to be notified of that fact.
Am I missing something.
You have to define the appropriate allocator (in this case, gc_allocator<Node>) for the std::list to get its member pointers registered with the collector. gc_allocator<T> defines its pointer as
I thought the user-defined scanner was supposed to overcome this limitation of the stl implementations. At least that what I *thought* you were implying by:
The collector offers the possibility of customizing the scanning procedure (the procedure which scans a block for pointers) through the class gc_traits<T>. So if there is a data structure where gc_ptr<T> can not be used, a custom scan routine especially coded for the data structure in question can solve the problem.
So... are you saying the UDS(User Defined Scanner) cannot overcome the "flawed" stl container use of raw pointer instead of allocator<T>::pointer?
gc_ptr<T>:
std::list<gc_ptr<Node>, gc_allocator<gc_ptr<Node> > > node_list;
Although I made the allocator, it does not work with the VC8 STL or the mingw STL, for the reason mentioned above (STL implementors choosing T* over allocator::pointer).
Is there an STL implementation without this problem? perhaps STLPort? I have to try it myself, but if anyone knows, please tell me.
Wouldn't it be pretty easy to modify the _list template in cppgc.hpp to take a new allocator template parameter and then modify the pointers in _list to use this instead of raw pointers? That way you could easily test to see if future (the ones required to use allocator::pointer) stl containers could be used. You could modify the main_stl I announced in my previous post to do this.
O/H Larry Evans έγραψε:
On 09/21/07 11:26, Achilleas Margaritis wrote:
O/H Larry Evans έγραψε:
On 09/21/07 04:14, Achilleas Margaritis wrote:
O/H Kim Barrett έγραψε:
At 2:06 AM +0300 9/21/07, Achilleas Margaritis wrote:
I thought std containers use the allocator::pointer type for their pointers. Unfortunately, not necessarily. They're permitted to bypass that and use T* directly. Ion Gaztañaga ran into this when trying to put containers into shared memory for boost.interprocess.
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
The collector offers the possibility of customizing the scanning procedure (the procedure which scans a block for pointers) through the class gc_traits<T>. So if there is a data structure where gc_ptr<T> can not be used, a custom scan routine especially coded for the data structure in question can solve the problem. Given the following:
std::list<gc_ptr<Node> > node_list;
where Node is defined in cppgc/src/main.cpp, then no gc_ptr's within node_list would be registered as root pointers; so, wouldn't any Nodes of the gc_ptr's pushed into node_list be collected? I guess I don't understand how a customized scanner would help. Sure, once it's known that node_list contains gc_ptr's, the scanner could be called, but the collector first needs to be notified of that fact.
Am I missing something. You have to define the appropriate allocator (in this case, gc_allocator<Node>) for the std::list to get its member pointers registered with the collector. gc_allocator<T> defines its pointer as
I thought the user-defined scanner was supposed to overcome this limitation of the stl implementations. At least that what I *thought* you were implying by:
The collector offers the possibility of customizing the scanning procedure (the procedure which scans a block for pointers) through the class gc_traits<T>. So if there is a data structure where gc_ptr<T> can not be used, a custom scan routine especially coded for the data structure in question can solve the problem.
So... are you saying the UDS(User Defined Scanner) cannot overcome the "flawed" stl container use of raw pointer instead of allocator<T>::pointer?
Yes, the user defined scanner can overcome the limitation, but someone has to write it, and each version must match the data structure layout of the STL container of the used STL library. For example, if the std::vector is defined as: template <class T> class vector { T *_first; T *_last; }; Then the scanner routine should be: void scan(void *p) { vector<T> *v = (vector<T> *)p; gc::scan(v->_first); } But it is not possible to automate scanning of STL data structures (C++ does not provide struct member metadata), so you have to scan the whole block: void scan(void *p) { vector<T> *v = (vector<T> *)p; for(void **p = v; p < v + sizeof(vector<T>); ++p) { gc::scan(*p); } } But the above makes the collector not precise, which invalidates the whole effort. If STL containers used allocator::pointer, then declaring a container on the stack would register the pointer members of the container as root pointers, and there would not be any issues.
gc_ptr<T>:
std::list<gc_ptr<Node>, gc_allocator<gc_ptr<Node> > > node_list;
Although I made the allocator, it does not work with the VC8 STL or the mingw STL, for the reason mentioned above (STL implementors choosing T* over allocator::pointer).
Is there an STL implementation without this problem? perhaps STLPort? I have to try it myself, but if anyone knows, please tell me.
Wouldn't it be pretty easy to modify the _list template in cppgc.hpp to take a new allocator template parameter and then modify the pointers in _list to use this instead of raw pointers? That way you could easily test to see if future (the ones required to use allocator::pointer) stl containers could be used. You could modify the main_stl I announced in my previous post to do this.
The _list template has been replaced with boost::intrusive::list. But what does it have to do with the STL anyway? _list was there in order to keep blocks around, as a faster alternative to std::list.
On 09/21/07 12:45, Achilleas Margaritis wrote:
O/H Larry Evans έγραψε:
O/H Larry Evans έγραψε:
On 09/21/07 04:14, Achilleas Margaritis wrote:
O/H Kim Barrett έγραψε:
At 2:06 AM +0300 9/21/07, Achilleas Margaritis wrote: > I thought std containers use the allocator::pointer type for their pointers. Unfortunately, not necessarily. They're permitted to bypass that and use T* directly. Ion Gaztañaga ran into this when trying to put containers into shared memory for boost.interprocess. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
The collector offers the possibility of customizing the scanning procedure (the procedure which scans a block for pointers) through the class gc_traits<T>. So if there is a data structure where gc_ptr<T> can not be used, a custom scan routine especially coded for the data structure in question can solve the problem. Given the following:
std::list<gc_ptr<Node> > node_list;
where Node is defined in cppgc/src/main.cpp, then no gc_ptr's within node_list would be registered as root pointers; so, wouldn't any Nodes of the gc_ptr's pushed into node_list be collected? I guess I don't understand how a customized scanner would help. Sure, once it's known that node_list contains gc_ptr's, the scanner could be called, but the collector first needs to be notified of that fact.
Am I missing something. You have to define the appropriate allocator (in this case, gc_allocator<Node>) for the std::list to get its member pointers registered with the collector. gc_allocator<T> defines its pointer as I thought the user-defined scanner was supposed to overcome this
On 09/21/07 11:26, Achilleas Margaritis wrote: limitation of the stl implementations. At least that what I *thought* you were implying by:
The collector offers the possibility of customizing the scanning procedure (the procedure which scans a block for pointers) through the class gc_traits<T>. So if there is a data structure where gc_ptr<T> can not be used, a custom scan routine especially coded for the data structure in question can solve the problem.
So... are you saying the UDS(User Defined Scanner) cannot overcome the "flawed" stl container use of raw pointer instead of allocator<T>::pointer?
Yes, the user defined scanner can overcome the limitation, but someone has to write it, and each version must match the data structure layout of the STL container of the used STL library.
For example, if the std::vector is defined as:
template <class T> class vector { T *_first; T *_last; };
Then the scanner routine should be:
void scan(void *p) { vector<T> *v = (vector<T> *)p; gc::scan(v->_first); }
But it is not possible to automate scanning of STL data structures (C++ does not provide struct member metadata), so you have to scan the whole block:
void scan(void *p) { vector<T> *v = (vector<T> *)p; for(void **p = v; p < v + sizeof(vector<T>); ++p) { gc::scan(*p); } }
But the above makes the collector not precise, which invalidates the whole effort.
If STL containers used allocator::pointer, then declaring a container on the stack would register the pointer members of the container as root pointers, and there would not be any issues.
Yes, I understand, but the scanner, as you've shown above, doesn't do this (it doesn't register the root pointer) so, it can't overcome the problem which I thought we were talking about, how to register the root pointer. I'm not concerned, at this point, about precision, I'm only concerned about somehow registering the root pointers. The above scan(void *P) doesn't help at all in doing this. Right?
gc_ptr<T>:
std::list<gc_ptr<Node>, gc_allocator<gc_ptr<Node> > > node_list;
Although I made the allocator, it does not work with the VC8 STL or the mingw STL, for the reason mentioned above (STL implementors choosing T* over allocator::pointer).
Is there an STL implementation without this problem? perhaps STLPort? I have to try it myself, but if anyone knows, please tell me.
Wouldn't it be pretty easy to modify the _list template in cppgc.hpp to take a new allocator template parameter and then modify the pointers in _list to use this instead of raw pointers? That way you could easily test to see if future (the ones required to use allocator::pointer) stl containers could be used. You could modify the main_stl I announced in my previous post to do this.
The _list template has been replaced with boost::intrusive::list. But what does it have to do with the STL anyway? _list was there in order to keep blocks around, as a faster alternative to std::list.
I'm not saying modify _list in the collector, I'm only saying you could modify it to use: Allocator<T>::pointer _list<T>::_begin; instead of: T* _list<T>::_begin; where, in the case of _list used in your collector, it would default to what it is now, but for the _list used in GCBench (as defined in main_stl.cpp) it would be Allocator::<T>::pointer which would be: gc_ptr<T> So you'd be reusing the _list code as part of the collector implementation; yet, also to demonstrate how std::list could be modified so that it would work with your collector.
On 09/21/07 13:07, Larry Evans wrote: [snip]
The _list template has been replaced with boost::intrusive::list. But what does it have to do with the STL anyway? _list was there in order to keep blocks around, as a faster alternative to std::list.
I'm not saying modify _list in the collector, I'm only saying you could modify it to use:
Allocator<T>::pointer _list<T>::_begin;
instead of:
T* _list<T>::_begin;
Sorry, I didn't look closely enough a _list. It doesn't allocate any nodes. I thought (based on std::list interface) that it did. Please disregard suggestions about adding allocator template parameter to _list.
O/H Larry Evans έγραψε:
On 09/21/07 13:07, Larry Evans wrote: [snip]
The _list template has been replaced with boost::intrusive::list. But what does it have to do with the STL anyway? _list was there in order to keep blocks around, as a faster alternative to std::list.
I'm not saying modify _list in the collector, I'm only saying you could modify it to use:
Allocator<T>::pointer _list<T>::_begin;
instead of:
T* _list<T>::_begin;
Sorry, I didn't look closely enough a _list. It doesn't allocate any nodes. I thought (based on std::list interface) that it did. Please disregard suggestions about adding allocator template parameter to _list.
Ok :-)
I'm not saying modify _list in the collector, I'm only saying you could modify it to use:
Allocator<T>::pointer _list<T>::_begin;
instead of:
T* _list<T>::_begin;
where, in the case of _list used in your collector, it would default to what it is now, but for the _list used in GCBench (as defined in main_stl.cpp) it would be Allocator::<T>::pointer which would be:
gc_ptr<T>
So you'd be reusing the _list code as part of the collector implementation; yet, also to demonstrate how std::list could be modified so that it would work with your collector.
Sorry, I haven't seen main_stl.cpp. Can I get it from somewhere?
On 09/21/07 15:27, Achilleas Margaritis wrote: [snip]
Sorry, I haven't seen main_stl.cpp. Can I get it from somewhere?
Same place as your code in boost vault. BTW, I'm trying to do std::list<T> correctly; however, I'm having problems. It appears allocator::pointer doesn't help when using: struct node { T elem; node* next_; node* prev_; }; because the begin/end pointers are to node* not to T*.
O/H Larry Evans έγραψε:
On 09/21/07 15:27, Achilleas Margaritis wrote: [snip]
Sorry, I haven't seen main_stl.cpp. Can I get it from somewhere?
Same place as your code in boost vault.
BTW, I'm trying to do std::list<T> correctly; however, I'm having problems. It appears allocator::pointer doesn't help when using:
struct node { T elem; node* next_; node* prev_; };
because the begin/end pointers are to node* not to T*.
Yeah, I originally thought that all STL implementations would use allocator<T>::pointer. Shame on me. So I guess only a re-implementation of STL containers would actually solve the problem. I am quite dissapointed. I have been battling with STL libraries all day, but without success. Microsoft, Mingw32, STLPort use T* instead of allocator::pointer. It's 2 am in the morning here, and I have just finished trying Rogue Wave's STL (actually, apache). Although it uses allocator::pointer, I can't compile a program with it: it says that namespace __rw is not allowed, although it compiles fine on some other files. Documentation is non-existence or hidden, so I am out of options, and also really tired of battling with every little detail of every implementation. With all these years of C++ development, I thought that these trivial issues would have been solved by now. Instead of that, it's like it is 1996 all over. It's a shame, because even if my garbage collector is not very good, it's an essential step for bringing really complicated data structures to C++ for the average C++ programmers like me. :-(
Larry Evans wrote:
BTW, I'm trying to do std::list<T> correctly; however, I'm having problems. It appears allocator::pointer doesn't help when using:
struct node { T elem; node* next_; node* prev_; };
because the begin/end pointers are to node* not to T*.
That's what the rebind mechanism is for. Suppose your allocator parameter is Alloc: template<typename T, typename Alloc = std::allocator<T> > class list { }; Then first you need the node allocator: typedef typename Alloc::template rebind<node<T> >::other node_allocator; Then you can get the new allocator's pointer type: typedef typename node_allocator::pointer node_ptr; class node { T elem; node_ptr next; node_ptr prev; }; Don't forget to construct the node_allocator member you'll hold from the allocator you're passed in. All allocators must have a templated constructor for this purpose. Something most implementations do, by the way, is that they are written in such a way that EBO applies to the allocator if it has no state. Sebastian Redl
O/H Sebastian Redl έγραψε:
Larry Evans wrote:
BTW, I'm trying to do std::list<T> correctly; however, I'm having problems. It appears allocator::pointer doesn't help when using:
struct node { T elem; node* next_; node* prev_; };
because the begin/end pointers are to node* not to T*.
That's what the rebind mechanism is for. Suppose your allocator parameter is Alloc:
template<typename T, typename Alloc = std::allocator<T> > class list { };
Then first you need the node allocator:
typedef typename Alloc::template rebind<node<T> >::other node_allocator;
Then you can get the new allocator's pointer type:
typedef typename node_allocator::pointer node_ptr;
class node { T elem; node_ptr next; node_ptr prev; };
Don't forget to construct the node_allocator member you'll hold from the allocator you're passed in. All allocators must have a templated constructor for this purpose. Something most implementations do, by the way, is that they are written in such a way that EBO applies to the allocator if it has no state.
But STL containers do not use the rebind struct for their internal allocations or for their member pointers. They just use T* instead of allocator<T>::rebind<U>::pointer.
On 09/22/07 08:00, Achilleas Margaritis wrote:
O/H Sebastian Redl έγραψε: [snip]
Then first you need the node allocator:
typedef typename Alloc::template rebind<node<T> >::other node_allocator;
Then you can get the new allocator's pointer type:
typedef typename node_allocator::pointer node_ptr;
class node { T elem; node_ptr next; node_ptr prev; };
Don't forget to construct the node_allocator member you'll hold from the allocator you're passed in. All allocators must have a templated constructor for this purpose. Something most implementations do, by the way, is that they are written in such a way that EBO applies to the allocator if it has no state.
But STL containers do not use the rebind struct for their internal allocations or for their member pointers. They just use T* instead of allocator<T>::rebind<U>::pointer.
The main_stl.zip in boost-vault/memory uses Sebastian's suggestion and it seems to work. It runs a little std_list test, then a GCBench with std:pair, then GCBench with std_list<., gc_allocator>. As (I think) you're pointing out above, the std_list<T,gc_allocator<T> > would define gc_allocator<T>::pointer as gc_ptr<T>, which is never used in std_list at all because the std_list stores the complete T (not T*) in std_list<...>::node. I can see where this would be confusing and is a shortcoming of the allocator model. It just happens to work in this case.
O/H Larry Evans έγραψε:
On 09/22/07 08:00, Achilleas Margaritis wrote:
O/H Sebastian Redl έγραψε: [snip]
Then first you need the node allocator:
typedef typename Alloc::template rebind<node<T> >::other node_allocator;
Then you can get the new allocator's pointer type:
typedef typename node_allocator::pointer node_ptr;
class node { T elem; node_ptr next; node_ptr prev; };
Don't forget to construct the node_allocator member you'll hold from the allocator you're passed in. All allocators must have a templated constructor for this purpose. Something most implementations do, by the way, is that they are written in such a way that EBO applies to the allocator if it has no state.
But STL containers do not use the rebind struct for their internal allocations or for their member pointers. They just use T* instead of allocator<T>::rebind<U>::pointer.
The main_stl.zip in boost-vault/memory uses Sebastian's suggestion and it seems to work. It runs a little std_list test, then a GCBench with std:pair, then GCBench with std_list<., gc_allocator>.
As (I think) you're pointing out above, the std_list<T,gc_allocator<T> > would define gc_allocator<T>::pointer as gc_ptr<T>, which is never used in std_list at all because the std_list stores the complete T (not T*) in std_list<...>::node. I can see where this would be confusing and is a shortcoming of the allocator model. It just happens to work in this case.
I am not really following you. Does your STL list class use the class gc_allocator<T> or not? and if it does, does it use it fully for all its operations or for some of them?
On 09/23/07 13:31, Achilleas Margaritis wrote:
O/H Larry Evans έγραψε: [snip]
The main_stl.zip in boost-vault/memory uses Sebastian's suggestion and it seems to work. It runs a little std_list test, then a GCBench with std:pair, then GCBench with std_list<., gc_allocator>.
As (I think) you're pointing out above, the std_list<T,gc_allocator<T> > would define gc_allocator<T>::pointer as gc_ptr<T>, which is never used in std_list at all because the std_list stores the complete T (not T*) in std_list<...>::node. I can see where this would be confusing and is a shortcoming of the allocator model. It just happens to work in this case.
I am not really following you. Does your STL list class use the class gc_allocator<T> or not? and if it does, does it use it fully for all its operations or for some of them?
It can, just like std::list can. IOW, it can be the 2nd template parameter. The list_pair template (derived from std_list) uses gc_allocator as the 2nd template parameter of its superclass, std_list<Node,gc_allocator<Node> >. It doesn't use it for any operations because it's part of the nested std::list<.,.>::node used to implement the list. Only push_back was coded since that's the only one used. I guess the std_list::empty is not standard; however, that's not really important since the only purpose was to demonstrate how, possibly a future std::list, could be coded to allow your gc_allocator to be used. Now that I think about it, maybe only the std_list::node::_next needs to be a gc_ptr<.>. That would save some time.
O/H Larry Evans έγραψε:
On 09/23/07 13:31, Achilleas Margaritis wrote:
O/H Larry Evans έγραψε: [snip]
The main_stl.zip in boost-vault/memory uses Sebastian's suggestion and it seems to work. It runs a little std_list test, then a GCBench with std:pair, then GCBench with std_list<., gc_allocator>.
As (I think) you're pointing out above, the std_list<T,gc_allocator<T> > would define gc_allocator<T>::pointer as gc_ptr<T>, which is never used in std_list at all because the std_list stores the complete T (not T*) in std_list<...>::node. I can see where this would be confusing and is a shortcoming of the allocator model. It just happens to work in this case. I am not really following you. Does your STL list class use the class gc_allocator<T> or not? and if it does, does it use it fully for all its operations or for some of them?
It can, just like std::list can. IOW, it can be the 2nd template parameter. The list_pair template (derived from std_list) uses gc_allocator as the 2nd template parameter of its superclass, std_list<Node,gc_allocator<Node> >.
It doesn't use it for any operations because it's part of the nested std::list<.,.>::node used to implement the list. Only push_back was coded since that's the only one used. I guess the std_list::empty is not standard; however, that's not really important since the only purpose was to demonstrate how, possibly a future std::list, could be coded to allow your gc_allocator to be used. Now that I think about it, maybe only the std_list::node::_next needs to be a gc_ptr<.>. That would save some time.
Ah, ok, now I get it :-). You are coding your own list. All you have to do is make every pointer gc_ptr<T> and allocate every object using the collector. The node object must be allocated using gc_new.
On 09/23/07 15:45, Achilleas Margaritis wrote: [snip]
your gc_allocator to be used. Now that I think about it, maybe only the std_list::node::_next needs to be a gc_ptr<.>. That would save some time.
Ah, ok, now I get it :-). You are coding your own list.
All you have to do is make every pointer gc_ptr<T> and allocate every object using the collector.
The node object must be allocated using gc_new.
So, instead of: //adds an element as the last entry inline void push_back(T const& elem) { node_ptr new_node=new node(elem); ... } It should be: //adds an element as the last entry inline void push_back(T const& elem) { node::allocator node_allocator; node_ptr new_node=node_allocator(1); new_node->_elem=elem; ... } at least, AFAICT. Haven't tested.
O/H Larry Evans έγραψε:
On 09/23/07 15:45, Achilleas Margaritis wrote: [snip]
your gc_allocator to be used. Now that I think about it, maybe only the std_list::node::_next needs to be a gc_ptr<.>. That would save some time.
Ah, ok, now I get it :-). You are coding your own list.
All you have to do is make every pointer gc_ptr<T> and allocate every object using the collector.
The node object must be allocated using gc_new.
So, instead of:
//adds an element as the last entry inline void push_back(T const& elem) { node_ptr new_node=new node(elem); ... }
It should be:
//adds an element as the last entry inline void push_back(T const& elem) { node::allocator node_allocator; node_ptr new_node=node_allocator(1); new_node->_elem=elem; ... }
at least, AFAICT. Haven't tested.
Indeed.
I have placed version 0.10 which includes a gc_allocator for use with STL data structures. Unfortunately, all STL implementations I have used, including STLPort, do not make use of allocator::pointer, so the collector does not work with STL containers. Aren't standards useful? :-)
Achilleas Margaritis wrote:
Is there an STL implementation without this problem? perhaps STLPort? I have to try it myself, but if anyone knows, please tell me.
Didn't Ion Gaztanaga effectively rewrite all STL containers for Interprocess to make them use the allocator's pointer type? These containers might be suitable for normal use, too. Sebastian Redl
O/H Sebastian Redl έγραψε:
Achilleas Margaritis wrote:
Is there an STL implementation without this problem? perhaps STLPort? I have to try it myself, but if anyone knows, please tell me.
Didn't Ion Gaztanaga effectively rewrite all STL containers for Interprocess to make them use the allocator's pointer type? These containers might be suitable for normal use, too.
I tried STLPort, it compiles, but it does not use allocator::pointer as well :(. Are these STL containers available somewhere? are they part of boost? I can't find them.
Hi There are some GC for C++. http://sourceforge.net/projects/sgcl/ http://smieciuch.sourceforge.net/ http://www.morefor.org/documentation/gc.html http://sourceforge.net/projects/librtgc/ Regards. -- |\/\/| Seweryn Habdank-Wojewódzki \/\/
O/H Seweryn Habdank-Wojewódzki έγραψε:
Hi
There are some GC for C++.
http://sourceforge.net/projects/sgcl/ http://smieciuch.sourceforge.net/ http://www.morefor.org/documentation/gc.html http://sourceforge.net/projects/librtgc/
Regards.
Thanks. I took a little time to study them. The following text contains a short review for each one. 1) http://sourceforge.net/projects/sgcl/ : I don't understand anything, the documentation is in the author's native language, which is not English. It is supposed to be a concurrent parallel-marking conservative collector. From looking at the sources, I saw references to VirtualQuery and other Win32 functions, so I presume it is a Windows-only collector. It does not have any special ptr class, because it checks all stack areas and globals. It's 2500 lines of code. The collector reads the data and copies them to another area in order to examine them. I think all parallel collectors work like that. 2) http://smieciuch.sourceforge.net/ : It's a C++ only collector (did not see any O/S specific code). The basics are the same as in my collector: special smart ptr classes are registered with the collector. The pointer registration routine searches the available objects to determine if a pointer is on the heap or is a root pointer. From what I can understand, the author has done some nice tricks with vectors and sorting to quickly locate the block a pointer belongs to. The code is a little on the difficult-to-read side. 3) http://www.morefor.org/documentation/gc.html: Practically the same as above, but a little more naive: the search for the block that a pointer falls into is sequential. Must be really slow for large data sets. The code is a little bit on the ugly side. 4) http://sourceforge.net/projects/librtgc/: C++ only collector. It uses reference counting, but it separates stack ref counting from heap ref counting. Basically, it works like this: 1) a DRef (direct reference) is a reference from the stack or global data. 2) a IRef (indirect reference) is a reference from other heap objects. If the direct reference count drops to 0, then the object is examined if it should be collected. An object is collectable if all the references it has is IRefs. In order for this to be achieved, special coding is required so as that member pointers are linked with owner objects. Overall, #1 seems to be good work but it is Windows-only, #2 and #3 are based on the same principle as mine (a pointer not on the heap is a root), and #4 is based on reference counting. I really doubt any of the above, except #1, could be used for serious work. #2 and #3 seem very slow, and #4 is difficult to program for. I think that the solution with bit-maps is the fastest possible for precise collection.
On 09/17/07 03:30, Achilleas Margaritis wrote:
Larry Evans wrote:
On 09/16/07 16:56, Achilleas Margaritis wrote: [snip] How does this collector determine the location of pointers on the stack and within the heap?
An internal bit map is used as a pointer database. Each bit represents one pointer location in memory.
When the class gc_ptr<T> is created, the bit that corresponds to the pointer's address is set.
When a pointer is destroyed, the same bit is reset.
The bitmap is organized in pages of 4K and allocated dynamically.
The collector sweeps unused pages at collection time.
So the essential difference from the Boehm conservative collector: http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcdescr.html is in the mark phase where, instead of: Any bit patterns that represent addresses inside heap objects managed by the collector are viewed as pointers. your collector would have: Any memory location contained in the pointer database must be pointer. Hence, during the scan of memory, if a memory location is in the pointer database, that memory location is dereferenced to arrive at another memory location which is then marked and then the memory from that location to that location + size (where size is stored somewhere else) is scanned. Is that about right?
O/H Larry Evans έγραψε:
On 09/17/07 03:30, Achilleas Margaritis wrote:
Larry Evans wrote:
On 09/16/07 16:56, Achilleas Margaritis wrote: [snip] How does this collector determine the location of pointers on the stack and within the heap? An internal bit map is used as a pointer database. Each bit represents one pointer location in memory.
When the class gc_ptr<T> is created, the bit that corresponds to the pointer's address is set.
When a pointer is destroyed, the same bit is reset.
The bitmap is organized in pages of 4K and allocated dynamically.
The collector sweeps unused pages at collection time.
So the essential difference from the Boehm conservative collector:
http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcdescr.html
is in the mark phase where, instead of:
Any bit patterns that represent addresses inside heap objects managed by the collector are viewed as pointers.
your collector would have:
Any memory location contained in the pointer database must be pointer.
Hence, during the scan of memory, if a memory location is in the pointer database, that memory location is dereferenced to arrive at another memory location which is then marked and then the memory from that location to that location + size (where size is stored somewhere else) is scanned.
Is that about right?
You are correct, but that's not the only difference. Boehm's gc is about 20,000 lines of code custom-built for each operating system. Mine's is about 500 lines of portable code, excluding the examples and dlmalloc, of course.
On 09/17/07 13:31, Achilleas Margaritis wrote:
O/H Larry Evans έγραψε:
On 09/17/07 03:30, Achilleas Margaritis wrote:
Larry Evans wrote:
On 09/16/07 16:56, Achilleas Margaritis wrote: [snip] How does this collector determine the location of pointers on the stack and within the heap? An internal bit map is used as a pointer database. Each bit represents one pointer location in memory. [snip] I'm still fuzzy about how this collector works. On:
http://www.hpl.hp.com/personal/Hans_Boehm/gc/complexity.html there's: A mark-sweep garbage collector traverses all reachable objects in the heap by following pointers beginning with the "roots", i.e. pointers stored in statically allocated or stack allocated program variables. All such reachable objects are marked. A sweep over the entire heap is the performed to restore unmarked objects to a free list, so they can be reallocated. How does this collector determine whether a pointer in the database is a root pointer? Wouldn't that method have to be non-portable or at least dispatch on the OS type to the appropriate method?
Larry Evans wrote:
On 09/17/07 13:31, Achilleas Margaritis wrote:
O/H Larry Evans έγραψε:
On 09/17/07 03:30, Achilleas Margaritis wrote:
Larry Evans wrote:
On 09/16/07 16:56, Achilleas Margaritis wrote: [snip] How does this collector determine the location of pointers on the stack and within the heap? An internal bit map is used as a pointer database. Each bit represents one pointer location in memory. [snip] I'm still fuzzy about how this collector works. On:
http://www.hpl.hp.com/personal/Hans_Boehm/gc/complexity.html
there's:
A mark-sweep garbage collector traverses all reachable objects in the heap by following pointers beginning with the "roots", i.e. pointers stored in statically allocated or stack allocated program variables. All such reachable objects are marked. A sweep over the entire heap is the performed to restore unmarked objects to a free list, so they can be reallocated.
How does this collector determine whether a pointer in the database is a root pointer? Wouldn't that method have to be non-portable or at least dispatch on the OS type to the appropriate method?
The collector keeps internally a map of memory page information structure allocated on demand from the heap. Each page information structure contains: 1) a bit map of pointers. 2) a heap reference count. When a heap block is allocated on a page, the page's reference count is increased. When a heap block is freed, the page's reference count is decreased. When a pointer is created, the bit that corresponds to the pointer's address is set. When a pointer is destroyed, the same bit is reset. When we scan for root pointers, we look at the heap reference count of the page: if it is greater than 0, the page contains heap data, and therefore we do not check if the page has any pointers, because even if it does, it is not a root page. The whole mechanism is based on the fact that heap, global data and thread data can not be on the same page.
On 09/18/07 09:22, Achilleas Margaritis wrote:
Larry Evans wrote: [snip]
How does this collector determine whether a pointer in the database is a root pointer? Wouldn't that method have to be non-portable or at least dispatch on the OS type to the appropriate method?
The collector keeps internally a map of memory page information structure allocated on demand from the heap. Each page information structure contains:
1) a bit map of pointers. 2) a heap reference count.
When a heap block is allocated on a page, the page's reference count is increased. When a heap block is freed, the page's reference count is decreased.
At first I thought, "make perfect sense", then I thought "if a page is on the heap, it remains there; so, why not use a bitflag instead of refcount?". Then I thought about the stack and heap growing to meet each other in the middle so I thought "a page could be on the heap at one point, but then, after all objects on that page were deleted, it could, after more functions calls, be on the stack" so I guess the refcount is used to detect when "all objects on that page were deleted" in which case, it would be put back into the gc::_page_pool. Is that the reason refcount (actually `size_t _page::_heap_ref`) is used instead of a `bool _page::_on_heap;` ? Since other people trying to understand the method will probably have the same question, it would be nice to have such an explanation as detailed (or more detailed) than the one above.
When a pointer is created, the bit that corresponds to the pointer's address is set. When a pointer is destroyed, the same bit is reset.
By pointer, you actually mean the smart-pointer, _pgr, from cppgc.hpp: //base class for gc_ptr struct _ptr { //the actual pointer value void *_value; //constructor from value; registers the pointer in the gc by setting the relevant bit inline _ptr(void *v) : _value(v) { gc::_init(); gc::_set_ptr(this); } ... //destructor; unregisters the pointer in the gc by resetting the relevant bit inline ~_ptr() { gc::_reset_ptr(this); } ... }; where the gc::_{set,reset}_ptr(this) does the registration and deregistration in "bitmap of pointers", implemented, at least partly, in gc::_pages[_MAX_PAGES]. BTW, couldn't 1048576 in: //number of 4K pages that fit inside the 32-bit address space enum { _MAX_PAGES = 1048576 }; be calculated as some function of values in <limits> rather than hard-coded. This would make the code more portable, IIUC.
When we scan for root pointers, we look at the heap reference count of the page: if it is greater than 0, the page contains heap data, and therefore we do not check if the page has any pointers, because even if it does, it is not a root page.
The whole mechanism is based on the fact that heap, global data and thread data can not be on the same page.
This *sounds* like it works; however, it also sounds so simple (although I couldn't think of it :( ) I'm surprised it hasn't been tried before. Maybe you should post this method to some gc newsgroup: http://dir.gmane.org/index.php?prefix=gmane.comp.programming.garbage-collect... and ask for feedback.
Right on! :-) Larry Evans wrote:
On 09/18/07 09:22, Achilleas Margaritis wrote:
Larry Evans wrote: [snip]
How does this collector determine whether a pointer in the database is a root pointer? Wouldn't that method have to be non-portable or at least dispatch on the OS type to the appropriate method?
The collector keeps internally a map of memory page information structure allocated on demand from the heap. Each page information structure contains:
1) a bit map of pointers. 2) a heap reference count.
When a heap block is allocated on a page, the page's reference count is increased. When a heap block is freed, the page's reference count is decreased.
At first I thought, "make perfect sense", then I thought "if a page is on the heap, it remains there; so, why not use a bitflag instead of refcount?". Then I thought about the stack and heap growing to meet each other in the middle so I thought "a page could be on the heap at one point, but then, after all objects on that page were deleted, it could, after more functions calls, be on the stack" so I guess the refcount is used to detect when "all objects on that page were deleted" in which case, it would be put back into the gc::_page_pool. Is that the reason refcount (actually `size_t _page::_heap_ref`) is used instead of a `bool _page::_on_heap;` ? Since other people trying to understand the method will probably have the same question, it would be nice to have such an explanation as detailed (or more detailed) than the one above.
When a pointer is created, the bit that corresponds to the pointer's address is set. When a pointer is destroyed, the same bit is reset.
By pointer, you actually mean the smart-pointer, _pgr, from cppgc.hpp:
//base class for gc_ptr struct _ptr { //the actual pointer value void *_value;
//constructor from value; registers the pointer in the gc by setting the relevant bit inline _ptr(void *v) : _value(v) { gc::_init(); gc::_set_ptr(this); } ... //destructor; unregisters the pointer in the gc by resetting the relevant bit inline ~_ptr() { gc::_reset_ptr(this); } ... };
where the gc::_{set,reset}_ptr(this) does the registration and deregistration in "bitmap of pointers", implemented, at least partly, in gc::_pages[_MAX_PAGES]. BTW, couldn't 1048576 in:
//number of 4K pages that fit inside the 32-bit address space enum { _MAX_PAGES = 1048576 };
be calculated as some function of values in <limits> rather than hard-coded. This would make the code more portable, IIUC.
When we scan for root pointers, we look at the heap reference count of the page: if it is greater than 0, the page contains heap data, and therefore we do not check if the page has any pointers, because even if it does, it is not a root page.
The whole mechanism is based on the fact that heap, global data and thread data can not be on the same page.
This *sounds* like it works; however, it also sounds so simple (although I couldn't think of it :( ) I'm surprised it hasn't been tried before. Maybe you should post this method to some gc newsgroup:
http://dir.gmane.org/index.php?prefix=gmane.comp.programming.garbage-collect...
and ask for feedback.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On 09/20/07 09:37, Achilleas Margaritis wrote:
Right on! :-)
Larry Evans wrote: [snip]
This *sounds* like it works; however, it also sounds so simple (although I couldn't think of it :( ) I'm surprised it hasn't been tried before. Maybe you should post this method to some gc newsgroup:
http://dir.gmane.org/index.php?prefix=gmane.comp.programming.garbage-collect...
and ask for feedback.
In particular, this thread:
http://thread.gmane.org/gmane.comp.programming.garbage-collection.general/30...
Larry Evans wrote:
On 09/16/07 16:56, Achilleas Margaritis wrote:
Dear boost developers,
You can find a new version of my portable precise C++ garbage collector in vault/memory.
Is any one interested? How does this collector determine the location of pointers on the stack and within the heap?
I forgot to add that the bit map's pages are marked as belonging to the heap if a memory block is dynamically allocated on them. At collection time, the pointers' bit map is traversed in order to locate root pointers; any pages marked as 'heap' are ignored.
Larry Evans wrote:
On 09/16/07 16:56, Achilleas Margaritis wrote:
Dear boost developers,
You can find a new version of my portable precise C++ garbage collector in vault/memory.
The file:
src/cppgc.cpp
contains:
void __fastcall _gc_traits::scan(register void *ptr) {
is __fastcall portable?
In platforms fastcall not supported, a #define can be used to make functions cdecl.
Larry Evans wrote:
On 09/16/07 16:56, Achilleas Margaritis wrote:
Dear boost developers,
You can find a new version of my portable precise C++ garbage collector in vault/memory.
The file:
src/cppgc.cpp
contains:
void __fastcall _gc_traits::scan(register void *ptr) {
is __fastcall portable?
No it's an MSVC'ism. John.
John Maddock wrote:
Larry Evans wrote:
On 09/16/07 16:56, Achilleas Margaritis wrote:
Dear boost developers,
You can find a new version of my portable precise C++ garbage collector in vault/memory.
The file:
src/cppgc.cpp
contains:
void __fastcall _gc_traits::scan(register void *ptr) {
Don't use __fastcall because it's faster - it's probably not! It dictates the compiler how to arrange the registers, which can result in less efficient code (spilling on the stack for reordering).
is __fastcall portable?
No it's an MSVC'ism.
Interesting... Are you sure (as it's most prominently used by Delphi)? Regards, Tobias
Tobias Schwinger wrote:
John Maddock wrote:
Larry Evans wrote:
On 09/16/07 16:56, Achilleas Margaritis wrote:
Dear boost developers,
You can find a new version of my portable precise C++ garbage collector in vault/memory.
The file:
src/cppgc.cpp
contains:
void __fastcall _gc_traits::scan(register void *ptr) {
Don't use __fastcall because it's faster - it's probably not!
Ok, note taken. I will remove it as soon as possible.
It dictates the compiler how to arrange the registers, which can result in less efficient code (spilling on the stack for reordering).
is __fastcall portable? No it's an MSVC'ism.
Interesting... Are you sure (as it's most prominently used by Delphi)?
Regards, Tobias
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
No, __fastcall is not portable, but it's largely irrelevant to the algorithm. I think the top-1 question will be: how does it handle cycles? Steven "Larry Evans" <cppljevans@cox-internet.com> wrote in message news:fclt2h$2v4$1@sea.gmane.org...
On 09/16/07 16:56, Achilleas Margaritis wrote:
Dear boost developers,
You can find a new version of my portable precise C++ garbage collector in vault/memory.
The file:
src/cppgc.cpp
contains:
void __fastcall _gc_traits::scan(register void *ptr) {
is __fastcall portable?
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Steven Burns wrote:
No, __fastcall is not portable, but it's largely irrelevant to the algorithm. I think the top-1 question will be: how does it handle cycles?
Steven
Cycles are handled as in every other garbage collector, i.e. objects connected cyclically do not remain for ever in memory.
"Larry Evans" <cppljevans@cox-internet.com> wrote in message news:fclt2h$2v4$1@sea.gmane.org...
On 09/16/07 16:56, Achilleas Margaritis wrote:
Dear boost developers,
You can find a new version of my portable precise C++ garbage collector in vault/memory.
The file:
src/cppgc.cpp
contains:
void __fastcall _gc_traits::scan(register void *ptr) {
is __fastcall portable?
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Achilleas Margaritis wrote:
Steven Burns wrote:
No, __fastcall is not portable, but it's largely irrelevant to the algorithm. I think the top-1 question will be: how does it handle cycles?
Steven
Cycles are handled as in every other garbage collector, i.e. objects connected cyclically do not remain for ever in memory.
"Larry Evans" <cppljevans@cox-internet.com> wrote in message news:fclt2h$2v4$1@sea.gmane.org...
On 09/16/07 16:56, Achilleas Margaritis wrote:
Dear boost developers,
You can find a new version of my portable precise C++ garbage collector in vault/memory.
The file:
src/cppgc.cpp
contains:
void __fastcall _gc_traits::scan(register void *ptr) {
is __fastcall portable?
I uploaded a new version in the vault which does not have __fastcall. But it's noticeably slower without it, so I might introduce a macro in the future for those platforms that support it.
On 09/18/07 09:16, Achilleas Margaritis wrote: [snip]
I uploaded a new version in the vault which does not have __fastcall. But it's noticeably slower without it, so I might introduce a macro in the future for those platforms that support it. Good idea; however, it's still not portable because there's the #include "windows.h" as well as several other things:
cd /home/evansl/prog_dev/boost-svn/ro/trunk/sandbox/axilmar/ make -k ./build/main.o g++ -I./include -c ./src/main.cpp -o build/main.o In file included from ./src/main.cpp:1: ./include/performancecounter.hpp:5:21: error: windows.h: No such file or directory ./include/performancecounter.hpp:27: error: 'LARGE_INTEGER' does not name a type ./include/performancecounter.hpp:28: error: 'LARGE_INTEGER' does not name a type ./include/performancecounter.hpp:29: error: 'LARGE_INTEGER' does not name a type ./include/performancecounter.hpp: In constructor 'PerformanceCounter::PerformanceCounter()': ./include/performancecounter.hpp:11: error: '_frequency' was not declared in this scope Could you provide a Makefile or something to enable the unix folks to test your code. Some in-source comments would also be helpful ;)
On 09/18/07 11:40, Larry Evans wrote: [snip]
Could you provide a Makefile or something to enable the unix folks to test your code. Some in-source comments would also be helpful ;)
-- cut here -- I get similar results as the Makefile in my previous post: <-- cut here -- gcc.compile.c++ ../../bin.v2/sandbox/axilmar/gcc-4.1/debug/main.o In file included from src/main.cpp:1: include/performancecounter.hpp:5:21: error: windows.h: No such file or
A Jamfile would be better since I'm guessing you don't have access to a unix-like OS. Of course that means you'd have to download boost build: http://www.boost.org/doc/html/bbv2.html Here's the Jamfile I just used: <-- cut here -- project : requirements <include>include : default-build debug <include>include ; obj main.obj : ./src/main.cpp ; directory include/performancecounter.hpp:27: error: 'LARGE_INTEGER' does not name a type include/performancecounter.hpp:28: error: 'LARGE_INTEGER' does not name a type include/performancecounter.hpp:29: error: 'LARGE_INTEGER' does not name a type include/performancecounter.hpp: In constructor 'PerformanceCounter::PerformanceCounter()': ...
-- cut here --
Larry Evans wrote:
On 09/18/07 09:16, Achilleas Margaritis wrote: [snip]
I uploaded a new version in the vault which does not have __fastcall. But it's noticeably slower without it, so I might introduce a macro in the future for those platforms that support it. Good idea; however, it's still not portable because there's the #include "windows.h" as well as several other things:
cd /home/evansl/prog_dev/boost-svn/ro/trunk/sandbox/axilmar/ make -k ./build/main.o g++ -I./include -c ./src/main.cpp -o build/main.o In file included from ./src/main.cpp:1: ./include/performancecounter.hpp:5:21: error: windows.h: No such file or directory ./include/performancecounter.hpp:27: error: 'LARGE_INTEGER' does not name a type ./include/performancecounter.hpp:28: error: 'LARGE_INTEGER' does not name a type ./include/performancecounter.hpp:29: error: 'LARGE_INTEGER' does not name a type ./include/performancecounter.hpp: In constructor 'PerformanceCounter::PerformanceCounter()': ./include/performancecounter.hpp:11: error: '_frequency' was not declared in this scope
Could you provide a Makefile or something to enable the unix folks to test your code. Some in-source comments would also be helpful ;)
Draft version 0.3 has the following changes: 1) added a PerformanceCounter for unix systems based on gettimeofday. I hope it works, as I don't have a unix system to test it. 2) added comments. I have boost jam on my pc (I used it to compile boost), so I will see if I can get a jam file for my project (it's a matter of having free time to study boost jam).
On 09/19/07 06:21, Achilleas Margaritis wrote:
Larry Evans wrote: [snip]
Could you provide a Makefile or something to enable the unix folks to test your code. Some in-source comments would also be helpful ;)
Draft version 0.3 has the following changes:
1) added a PerformanceCounter for unix systems based on gettimeofday. I hope it works, as I don't have a unix system to test it.
2) added comments. Great!
I have boost jam on my pc (I used it to compile boost), so I will see if I can get a jam file for my project (it's a matter of having free time to study boost jam). I tried with the attached Jamfile, but got: <-- cut here -- gcc.compile.c++ ../../../bin.v2/sandbox/axilmar/0.3/gcc-4.1/debug/cppgc.o src/cppgc.cpp:130: warning: ignoring #pragma warning src/cppgc.cpp:179: warning: ignoring #pragma warning include/cppgc.hpp: In constructor '_address::_address(size_t, size_t, size_t)': include/cppgc.hpp:283: warning: '_address::<anonymous struct>::_index' will be initialized after include/cppgc.hpp:280: warning: 'size_t _address::<anonymous struct>::_word' include/cppgc.hpp:303: warning: when initialized here include/cppgc.hpp:280: warning: '_address::<anonymous struct>::_word' will be initialized after include/cppgc.hpp:277: warning: 'size_t _address::<anonymous struct>::_bit' include/cppgc.hpp:303: warning: when initialized here include/cppgc.hpp:277: warning: '_address::<anonymous struct>::_bit' will be initialized after include/cppgc.hpp:274: warning: 'size_t _address::<anonymous struct>::_1' include/cppgc.hpp:303: warning: when initialized here src/cppgc.cpp: In constructor 'gc::_init_::_init_()': src/cppgc.cpp:107: error: 'create_mspace' was not declared in this scope src/cppgc.cpp: In static member function 'static void gc::_cleanup()': src/cppgc.cpp:126: error: 'destroy_mspace' was not declared in this scope
"/usr/bin/g++-4.1" -ftemplate-depth-128 -O0 -fno-inline -Wall -g -fPIC -DBOOST_ALL_NO_LIB=1 -I"../../.." -I"include" -c -o "../../../bin.v2/sandbox/axilmar/0.3/gcc-4.1/debug/cppgc.o" "src/cppgc.cpp"
-- cut here --
HTH. -regards, Larry project : requirements <include>include : default-build debug <include>include ; obj main.obj : ./src/main.cpp ; obj dlmalloc.obj : ./src/dlmalloc.c ; obj cppgc.obj : ./src/cppgc.cpp ; exe main.exe : main.obj dlmalloc.obj cppgc.obj ;
Larry Evans wrote:
On 09/19/07 06:21, Achilleas Margaritis wrote:
Larry Evans wrote: [snip]
Could you provide a Makefile or something to enable the unix folks to test your code. Some in-source comments would also be helpful ;)
Draft version 0.3 has the following changes:
1) added a PerformanceCounter for unix systems based on gettimeofday. I hope it works, as I don't have a unix system to test it.
2) added comments. Great!
I have boost jam on my pc (I used it to compile boost), so I will see if I can get a jam file for my project (it's a matter of having free time to study boost jam). I tried with the attached Jamfile, but got: <-- cut here -- gcc.compile.c++ ../../../bin.v2/sandbox/axilmar/0.3/gcc-4.1/debug/cppgc.o src/cppgc.cpp:130: warning: ignoring #pragma warning src/cppgc.cpp:179: warning: ignoring #pragma warning include/cppgc.hpp: In constructor '_address::_address(size_t, size_t, size_t)': include/cppgc.hpp:283: warning: '_address::<anonymous struct>::_index' will be initialized after include/cppgc.hpp:280: warning: 'size_t _address::<anonymous struct>::_word' include/cppgc.hpp:303: warning: when initialized here include/cppgc.hpp:280: warning: '_address::<anonymous struct>::_word' will be initialized after include/cppgc.hpp:277: warning: 'size_t _address::<anonymous struct>::_bit' include/cppgc.hpp:303: warning: when initialized here include/cppgc.hpp:277: warning: '_address::<anonymous struct>::_bit' will be initialized after include/cppgc.hpp:274: warning: 'size_t _address::<anonymous struct>::_1' include/cppgc.hpp:303: warning: when initialized here src/cppgc.cpp: In constructor 'gc::_init_::_init_()': src/cppgc.cpp:107: error: 'create_mspace' was not declared in this scope src/cppgc.cpp: In static member function 'static void gc::_cleanup()': src/cppgc.cpp:126: error: 'destroy_mspace' was not declared in this scope
"/usr/bin/g++-4.1" -ftemplate-depth-128 -O0 -fno-inline -Wall -g -fPIC -DBOOST_ALL_NO_LIB=1 -I"../../.." -I"include" -c -o "../../../bin.v2/sandbox/axilmar/0.3/gcc-4.1/debug/cppgc.o" "src/cppgc.cpp"
-- cut here --
HTH.
-regards, Larry
Ah yes, there was a problem with an ifdef. I posted the fixed version in the vault. I am downloading Fedora Core and I will install it under VMWare, so as that I can compile the code for Linux as well.
On 09/19/07 09:57, Achilleas Margaritis wrote:
Larry Evans wrote: [snip] Ah yes, there was a problem with an ifdef. I posted the fixed version in the vault.
This works: <-- cut here -- cd /home/evansl/prog_dev/boost-svn/ro/trunk/sandbox/axilmar/ bjam main.exe ... ./0.5/cppgc/include/cppgc.hpp:283: warning: 'size_t _address::<anonymous struct>::_1' ./0.5/cppgc/include/cppgc.hpp:316: warning: when initialized here gcc.link ../../bin.v2/sandbox/axilmar/gcc-4.1/debug/main ...updated 3 targets...
-- cut here --
Of course I modified my Jamfile slightly to use the 0.5 subdirectory. It's attached.
I am downloading Fedora Core and I will install it under VMWare, so as that I can compile the code for Linux as well.
Great! version = 0.5/cppgc ; project : requirements <include>./$(version)/include : default-build debug <include>./$(version)/include ; obj main.obj : ./$(version)/src/main.cpp ; obj dlmalloc.obj : ./$(version)/src/dlmalloc.c ; obj cppgc.obj : ./$(version)/src/cppgc.cpp ; exe main.exe : main.obj dlmalloc.obj cppgc.obj ; obj main_test.obj : ./$(version)/main_test.cpp ; exe main_test.exe : main_test.obj dlmalloc.obj ;
Larry Evans wrote:
On 09/19/07 09:57, Achilleas Margaritis wrote:
Larry Evans wrote: [snip] Ah yes, there was a problem with an ifdef. I posted the fixed version in the vault.
This works: <-- cut here -- cd /home/evansl/prog_dev/boost-svn/ro/trunk/sandbox/axilmar/ bjam main.exe
... ./0.5/cppgc/include/cppgc.hpp:283: warning: 'size_t _address::<anonymous struct>::_1' ./0.5/cppgc/include/cppgc.hpp:316: warning: when initialized here gcc.link ../../bin.v2/sandbox/axilmar/gcc-4.1/debug/main ...updated 3 targets...
-- cut here --
Of course I modified my Jamfile slightly to use the 0.5 subdirectory. It's attached.
I am downloading Fedora Core and I will install it under VMWare, so as that I can compile the code for Linux as well.
Great!
I've included your jam file under prj/boost. Next release will contain it along with contrib.txt stating your contributions. Version draft 0.6 includes weak pointers.
On 09/19/07 10:49, Achilleas Margaritis wrote: [snip]
I've included your jam file under prj/boost. Next release will contain it along with contrib.txt stating your contributions.
Actually, it was designed to be at top of a directory structure like: top Jamfile 0.5 cppgc-draft-0.5.zip cppgc include src 0.6 cppgc-draft-0.6.zip cppgc include src ... 0.N cppgc-draft-0.N.zip cppgc include src That way, when you publish a new draft zip file, I create a corresponding directory below top, download the new draft zip, unzip, then change one line at top of the Jamfile: version = 0.5/cppgc ; to point to the new directory and then do `bjam main.exe` from the top directory. So, as it is, it would be inappropriate to put it in the prj subdirectory without modification. Maybe just a slight modification would make it appropriate though. You might try that.
On 09/19/07 11:03, Larry Evans wrote: [snip]
So, as it is, it would be inappropriate to put it in the prj subdirectory without modification. Maybe just a slight modification would make it appropriate though. You might try that. I put the attached Jamfile under the prj directory and it seems to work: <-- cut here -- cd /home/evansl/prog_dev/boost-svn/ro/trunk/sandbox/axilmar/0.5-0.6/cppgc/prj/ bjam main.exe ... gcc.link ../../../../../bin.v2/sandbox/axilmar/0.5-0.6/cppgc/prj/gcc-4.1/debug/main ...updated 9 targets... -- cut here --
cppgc-top = .. ; project : requirements <include>./$(cppgc-top)/include : default-build debug <include>./$(cppgc-top)/include ; obj main.obj : ./$(cppgc-top)/src/main.cpp ; obj dlmalloc.obj : ./$(cppgc-top)/src/dlmalloc.c ; obj cppgc.obj : ./$(cppgc-top)/src/cppgc.cpp ; exe main.exe : main.obj dlmalloc.obj cppgc.obj ;
On 09/19/07 10:49, Achilleas Margaritis wrote: [snip]
I am downloading Fedora Core and I will install it under VMWare, so as that I can compile the code for Linux as well. I'm getting a segmentation fault:
gcc.link ../../bin.v2/sandbox/axilmar/gcc-4.1/debug/main_test Jamfile</home/evansl/prog_dev/boost-svn/ro/trunk/sandbox/axilmar>.capture-output ../../bin.v2/sandbox/axilmar/gcc-4.1/debug/main_test.output ***running ../../bin.v2/sandbox/axilmar/gcc-4.1/debug/main_test /bin/sh: line 2: 14060 Segmentation fault ../../bin.v2/sandbox/axilmar/gcc-4.1/debug/main_test ...updated 4 targets... I added some debug prints to the _page::new: //allocate page from mspaces void *_page::operator new(size_t size) { std::cout<<"_page::operator new at "<<__FILE__<<":"<<__LINE__<<"\n"; void*p= #if 1 _CPPGC_MALLOC(gc::_mem_space, size); #else 0; #endif std::cout<<"_page::operator new at p=" //<<p <<"\n"; return p; } When the '#if 1' is changed to '#if 0', I get: ***running ../../bin.v2/sandbox/axilmar/gcc-4.1/debug/main_test _page::operator new at ./cppgc/include/cppgc.hpp:648 _page::operator new at p= running main_test.cpp p=0x8456008 a_page=0 ...updated 4 targets... Compilation finished at Wed Sep 19 12:41:55 main_test only contains: #include "cppgc.hpp" #include <iostream> int main(void) { void*p=dlmalloc(20); void*a_page=_page::operator new(sizeof(_page)); std::cout<<"running "<<__FILE__<<"\n"; std::cout<<"p="<<p<<"\n"; std::cout<<"a_page="<<a_page<<"\n"; return 0; }
O/H Larry Evans έγραψε:
On 09/19/07 10:49, Achilleas Margaritis wrote: [snip]
I am downloading Fedora Core and I will install it under VMWare, so as that I can compile the code for Linux as well. I'm getting a segmentation fault:
gcc.link ../../bin.v2/sandbox/axilmar/gcc-4.1/debug/main_test Jamfile</home/evansl/prog_dev/boost-svn/ro/trunk/sandbox/axilmar>.capture-output ../../bin.v2/sandbox/axilmar/gcc-4.1/debug/main_test.output ***running ../../bin.v2/sandbox/axilmar/gcc-4.1/debug/main_test /bin/sh: line 2: 14060 Segmentation fault ../../bin.v2/sandbox/axilmar/gcc-4.1/debug/main_test ...updated 4 targets...
I added some debug prints to the _page::new:
//allocate page from mspaces void *_page::operator new(size_t size) { std::cout<<"_page::operator new at "<<__FILE__<<":"<<__LINE__<<"\n"; void*p= #if 1 _CPPGC_MALLOC(gc::_mem_space, size); #else 0; #endif std::cout<<"_page::operator new at p=" //<<p <<"\n"; return p; }
When the '#if 1' is changed to '#if 0', I get:
***running ../../bin.v2/sandbox/axilmar/gcc-4.1/debug/main_test _page::operator new at ./cppgc/include/cppgc.hpp:648 _page::operator new at p= running main_test.cpp p=0x8456008 a_page=0 ...updated 4 targets...
Compilation finished at Wed Sep 19 12:41:55
main_test only contains:
#include "cppgc.hpp" #include <iostream> int main(void) { void*p=dlmalloc(20); void*a_page=_page::operator new(sizeof(_page)); std::cout<<"running "<<__FILE__<<"\n"; std::cout<<"p="<<p<<"\n"; std::cout<<"a_page="<<a_page<<"\n"; return 0; }
Should I remove dlmalloc temporarily? I need mspaces so as that when the code becomes threaded, each thread will have its own mspace.
O/H Larry Evans έγραψε:
On 09/19/07 10:49, Achilleas Margaritis wrote: [snip]
I am downloading Fedora Core and I will install it under VMWare, so as that I can compile the code for Linux as well. I'm getting a segmentation fault:
gcc.link ../../bin.v2/sandbox/axilmar/gcc-4.1/debug/main_test Jamfile</home/evansl/prog_dev/boost-svn/ro/trunk/sandbox/axilmar>.capture-output ../../bin.v2/sandbox/axilmar/gcc-4.1/debug/main_test.output ***running ../../bin.v2/sandbox/axilmar/gcc-4.1/debug/main_test /bin/sh: line 2: 14060 Segmentation fault ../../bin.v2/sandbox/axilmar/gcc-4.1/debug/main_test ...updated 4 targets...
I added some debug prints to the _page::new:
//allocate page from mspaces void *_page::operator new(size_t size) { std::cout<<"_page::operator new at "<<__FILE__<<":"<<__LINE__<<"\n"; void*p= #if 1 _CPPGC_MALLOC(gc::_mem_space, size); #else 0; #endif std::cout<<"_page::operator new at p=" //<<p <<"\n"; return p; }
When the '#if 1' is changed to '#if 0', I get:
***running ../../bin.v2/sandbox/axilmar/gcc-4.1/debug/main_test _page::operator new at ./cppgc/include/cppgc.hpp:648 _page::operator new at p= running main_test.cpp p=0x8456008 a_page=0 ...updated 4 targets...
Compilation finished at Wed Sep 19 12:41:55
main_test only contains:
#include "cppgc.hpp" #include <iostream> int main(void) { void*p=dlmalloc(20); void*a_page=_page::operator new(sizeof(_page)); std::cout<<"running "<<__FILE__<<"\n"; std::cout<<"p="<<p<<"\n"; std::cout<<"a_page="<<a_page<<"\n"; return 0; }
I removed dlmalloc...I will try to compile it under Linux as soon as possible.
On 09/19/07 13:46, Achilleas Margaritis wrote: [snip]
I added some debug prints to the _page::new:
//allocate page from mspaces void *_page::operator new(size_t size) { std::cout<<"_page::operator new at "<<__FILE__<<":"<<__LINE__<<"\n"; void*p= #if 1 _CPPGC_MALLOC(gc::_mem_space, size); #else 0; #endif std::cout<<"_page::operator new at p=" //<<p <<"\n"; return p; }
When the '#if 1' is changed to '#if 0', I get:
***running ../../bin.v2/sandbox/axilmar/gcc-4.1/debug/main_test _page::operator new at ./cppgc/include/cppgc.hpp:648 _page::operator new at p= running main_test.cpp p=0x8456008 a_page=0 ...updated 4 targets...
Compilation finished at Wed Sep 19 12:41:55
main_test only contains:
#include "cppgc.hpp" #include <iostream> int main(void) { void*p=dlmalloc(20); void*a_page=_page::operator new(sizeof(_page)); std::cout<<"running "<<__FILE__<<"\n"; std::cout<<"p="<<p<<"\n"; std::cout<<"a_page="<<a_page<<"\n"; return 0; }
I removed dlmalloc...I will try to compile it under Linux as soon as possible.
I'm mystified by what's happening because when I changed main to: _page*a_page=new _page; I got the segfault again even when the _page::operator new had: void*p= #if 0 _CPPGC_MALLOC(gc::_mem_space, size); #else 0; #endif ???
On 09/19/07 14:11, Larry Evans wrote: [snip]
main_test only contains:
#include "cppgc.hpp" #include <iostream> int main(void) { void*p=dlmalloc(20); void*a_page=_page::operator new(sizeof(_page)); std::cout<<"running "<<__FILE__<<"\n"; std::cout<<"p="<<p<<"\n"; std::cout<<"a_page="<<a_page<<"\n"; return 0; } I removed dlmalloc...I will try to compile it under Linux as soon as possible.
I'm mystified by what's happening because when I changed main to:
_page*a_page=new _page;
I got the segfault again even when the _page::operator new had:
void*p= #if 0 _CPPGC_MALLOC(gc::_mem_space, size); #else 0; #endif
??? OOPS. Maybe because a _page cannot be constructed at location 0 :)
Anyway, I tried running with: void*p=::operator new(size); and it worked, then tried with src/main.cpp but it never terminated until I manually aborted. Hope you can get the unix working soon. Good luck!
On 09/19/07 14:11, Larry Evans wrote:
and it worked, then tried with src/main.cpp but it never terminated until I manually aborted.
Hope you can get the unix working soon.
Good luck!
Draft version 0.8 contains a makefile for gcc under prj/gcc directory. I compiled the example with gcc from OpenSuse 10.2. I left the executable and object files (for 80x86) in the zip file so I hope some other people can run it in case there is a problem. What impressed me is how fast the benchmark was compared to Microsoft's compiler. The malloc routine of gcc must be very good. Larry, what are you trying to run the program on? is it a PowerPC machine? if so, your version may crash due to different endianess (perhaps because pointer addresses are used as bitfields?)...
On 09/19/07 17:15, Achilleas Margaritis wrote: [snip]
Draft version 0.8 contains a makefile for gcc under prj/gcc directory. I compiled the example with gcc from OpenSuse 10.2. I left the executable and object files (for 80x86) in the zip file so I hope some other people can run it in case there is a problem.
What impressed me is how fast the benchmark was compared to Microsoft's compiler. The malloc routine of gcc must be very good.
Larry, what are you trying to run the program on? is it a PowerPC machine? if so, your version may crash due to different endianess (perhaps because pointer addresses are used as bitfields?)...
It's a compaq 4400 (bought 7/12/2002) so its an iX86, not PowerPC. Maybe I just didn't let it run long enough. So for (about 3-5min) I get: cd ~/prog_dev/boost-svn/ro/trunk/bin.v2/sandbox/axilmar/gcc-4.1/debug/ ./main Garbage Collector Test Live storage will peak at 8194272 bytes. Stretching memory with a binary tree of depth 18 Creating a long-lived binary tree of depth 16 Creating a long-lived array of 500000 doubles Creating 33824 trees of depth 4 Top down construction took 820.000000 msec Bottom up construction took 980.000000 msec Creating 8256 trees of depth 6 Top down construction took 824.000000 msec Bottom up construction took 987.000000 msec Creating 2052 trees of depth 8 Top down construction took 868.000000 msec Bottom up construction took 1390.000000 msec Creating 512 trees of depth 10 Top down construction took 1359.000000 msec Bottom up construction took 60733.000000 msec Creating 128 trees of depth 12 Top down construction took 921.000000 msec Bottom up construction took 1989.000000 msec Creating 32 trees of depth 14 Top down construction took 1788.000000 msec Bottom up construction took 1738.000000 msec Creating 8 trees of depth 16 Top down construction took 2475.000000 msec Bottom up construction took 3060.000000 msec Completed in 80657.000000 msec heap size = 0 Compilation interrupt at Wed Sep 19 18:14:01
Could you run it with optimizations? Larry Evans wrote:
On 09/19/07 17:15, Achilleas Margaritis wrote: [snip]
Draft version 0.8 contains a makefile for gcc under prj/gcc directory. I compiled the example with gcc from OpenSuse 10.2. I left the executable and object files (for 80x86) in the zip file so I hope some other people can run it in case there is a problem.
What impressed me is how fast the benchmark was compared to Microsoft's compiler. The malloc routine of gcc must be very good.
Larry, what are you trying to run the program on? is it a PowerPC machine? if so, your version may crash due to different endianess (perhaps because pointer addresses are used as bitfields?)...
It's a compaq 4400 (bought 7/12/2002) so its an iX86, not PowerPC. Maybe I just didn't let it run long enough. So for (about 3-5min) I get:
cd ~/prog_dev/boost-svn/ro/trunk/bin.v2/sandbox/axilmar/gcc-4.1/debug/ ./main Garbage Collector Test Live storage will peak at 8194272 bytes.
Stretching memory with a binary tree of depth 18
Creating a long-lived binary tree of depth 16 Creating a long-lived array of 500000 doubles Creating 33824 trees of depth 4 Top down construction took 820.000000 msec Bottom up construction took 980.000000 msec Creating 8256 trees of depth 6 Top down construction took 824.000000 msec Bottom up construction took 987.000000 msec Creating 2052 trees of depth 8 Top down construction took 868.000000 msec Bottom up construction took 1390.000000 msec Creating 512 trees of depth 10 Top down construction took 1359.000000 msec Bottom up construction took 60733.000000 msec Creating 128 trees of depth 12 Top down construction took 921.000000 msec Bottom up construction took 1989.000000 msec Creating 32 trees of depth 14 Top down construction took 1788.000000 msec Bottom up construction took 1738.000000 msec Creating 8 trees of depth 16 Top down construction took 2475.000000 msec Bottom up construction took 3060.000000 msec Completed in 80657.000000 msec heap size = 0
Compilation interrupt at Wed Sep 19 18:14:01
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On 09/20/07 04:55, Achilleas Margaritis wrote:
Could you run it with optimizations?
Larry Evans wrote: [snip]
Maybe I just didn't let it run long enough. So for (about 3-5min) I get:
cd ~/prog_dev/boost-svn/ro/trunk/bin.v2/sandbox/axilmar/gcc-4.1/debug/ ./main Garbage Collector Test Live storage will peak at 8194272 bytes. [snip] Bottom up construction took 3060.000000 msec Completed in 80657.000000 msec heap size = 0
Compilation interrupt at Wed Sep 19 18:14:01 It's interactive. It has getchar() as the statement before 'return 0;' in main. I just had to hit CR.
On Wed, 19 Sep 2007, Achilleas Margaritis wrote:
I am downloading Fedora Core and I will install it under VMWare, so as that I can compile the code for Linux as well.
In case you didn't know, there are many publicly available virtual machine images with Fedora (and other free OSs) already installed. http://www.thoughtpolice.co.uk/vmware/ http://www.oszoo.org etc. This might save you some time. - Daniel
I really look forward to it, I hope you can submit it. Even though some of us are religiously strict RAII followers, a precise garbage collector would come handy for certain types of applications. Not to mention keeping C++ attractive to newcomers. Steven "Achilleas Margaritis" <axilmar@ath.forthnet.gr> wrote in message news:fck8vt$tr4$1@sea.gmane.org...
Dear boost developers,
You can find a new version of my portable precise C++ garbage collector in vault/memory.
Is any one interested?
Can I submit my library to be part of boost?
Achilleas Margaritis
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Achilleas Margaritis wrote:
Dear boost developers,
You can find a new version of my portable precise C++ garbage collector in vault/memory.
Is any one interested?
Can I submit my library to be part of boost?
Achilleas Margaritis
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
This looks very interesting. A garbage collected weak pointer would be a nice feature. --Johan Råde
Johan Råde wrote:
Achilleas Margaritis wrote:
Dear boost developers,
You can find a new version of my portable precise C++ garbage collector in vault/memory.
Is any one interested?
Can I submit my library to be part of boost?
Achilleas Margaritis
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
This looks very interesting.
A garbage collected weak pointer would be a nice feature.
--Johan Råde
It's quite possible to do weak pointers with the algorithm I use. All it takes is a second pointer bit map for weak pointers. I think weak pointers is necessary tool. I 'll put a note down in the todo list.
On 09/16/07 16:56, Achilleas Margaritis wrote: [snip]
You can find a new version of my portable precise C++ garbage collector in vault/memory.
[snip] Why doesn't cppgc.hpp use std::list instead of _list defined in cppgc.hpp and why isn't the boost pool: http://www.boost.org/libs/pool/doc/index.html used instead of the _pool of cppgc.hpp?
I think std::list is slower than my list (I could be wrong of course), because it allocates memory from the heap for each node, whereas my list requires the elements to have the node embedded in them, and so blocks are also nodes. As for pool, I wasn't aware that boost had one, and I am not sure it is useful. If, in the end, we find that it's good to have a pool, and if the library is accepted in boost, I will use the boost pool, provided that it is fast enough for the collector. My pool uses the same trick as the list, i.e. the elements must also be nodes. I will try to run a test to see if boost's pool is efficient enough for the collector. The most important thing in this type of software is to try to keep as much as possible in the cache, and having linked list nodes embedded into the elements is one way to achieve less cache thrashing. Larry Evans wrote:
On 09/16/07 16:56, Achilleas Margaritis wrote: [snip]
You can find a new version of my portable precise C++ garbage collector in vault/memory. [snip] Why doesn't cppgc.hpp use std::list instead of _list defined in cppgc.hpp and why isn't the boost pool:
http://www.boost.org/libs/pool/doc/index.html
used instead of the _pool of cppgc.hpp?
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Achilleas Margaritis ha escrito:
I think std::list is slower than my list (I could be wrong of course), because it allocates memory from the heap for each node, whereas my list requires the elements to have the node embedded in them, and so blocks are also nodes.
Maybe you can then replace your private intrusive list with Boost.Intrusive: http://igaztanaga.drivehq.com/intrusive which is already included in the SVN trunk. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Thanks for the tip, I will look into it. I've done a small benchmark to check how fast an std::list is compared to cppgc::_list, and the difference is very large. std::list duration = 4929.17 _list duration = 3.40211 Perhaps the std::list requires a special allocator class to become as efficient as an intrucive list. The benchmark (which can be wrong - I am not a specialist) is attached as a file. Joaquín Mª López Muñoz wrote:
Achilleas Margaritis ha escrito:
I think std::list is slower than my list (I could be wrong of course), because it allocates memory from the heap for each node, whereas my list requires the elements to have the node embedded in them, and so blocks are also nodes.
Maybe you can then replace your private intrusive list with Boost.Intrusive:
http://igaztanaga.drivehq.com/intrusive
which is already included in the SVN trunk.
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
#include <iostream> #include <list> using namespace std; #ifdef WIN32 #include <windows.h> class PerformanceCounter { public: PerformanceCounter() { QueryPerformanceFrequency(&_frequency); } void start() { QueryPerformanceCounter(&_start); } void end() { QueryPerformanceCounter(&_end); } double duration() const { return (((double)_end.QuadPart - (double)_start.QuadPart) / (double)_frequency.QuadPart) * 1000.0; } private: LARGE_INTEGER _frequency; LARGE_INTEGER _start; LARGE_INTEGER _end; }; #else #include <sys/time.h> class PerformanceCounter { public: PerformanceCounter() { } void start() { _start = clock(); } void end() { _end = clock(); } double duration() const { return _end - _start; } private: double _start; double _end; static double clock(void) { struct timeval t; struct timezone tz; if (gettimeofday( &t, &tz ) == -1) return 0; return (t.tv_sec * 1000 + t.tv_usec / 1000); } }; #endif //WIN32 //a double-linked list class where nodes have embedded links to previous/next items template <class T> struct _list { public: //initializes the object; use instead of constructor; //the data structure is allocated statically and initialized manually; //it solves the problem of initialization order of static data inline void _init() { _begin = &_begin_elem; _end = &_end_elem; _begin_elem._list_next = _end; _end_elem._list_prev = _begin; } inline void _cleanup() { } //get first element inline T * begin() const { return _begin_elem._list_next; } //get end element inline const T *end() const { return &_end_elem; } //adds an element as the last entry inline void add(T *elem) { elem->_list_next = &_end_elem; elem->_list_prev = _end_elem._list_prev; _end_elem._list_prev->_list_next = elem; _end_elem._list_prev = elem; } //removes an element inline void remove(T *elem) { elem->_list_prev->_list_next = elem->_list_next; elem->_list_next->_list_prev = elem->_list_prev; } private: T *_begin; T *_end; T _begin_elem; T _end_elem; }; class Foo1 { public: Foo1 *_list_next, *_list_prev; int i, j; Foo1() { _list_next = _list_prev = 0; i = j = 0; } }; class Foo2 { public: int i, j; Foo2() { i = j = 0; } }; int main() { typedef _list<Foo1> foo1_list_t; typedef std::list<Foo2 *> foo2_list_t; foo1_list_t foo1_list; foo1_list._init(); foo2_list_t foo2_list; PerformanceCounter pc; static const size_t _MAX = 100000; static Foo1 foo1[_MAX]; static Foo2 foo2[_MAX]; pc.start(); for(size_t i = 0; i < _MAX; ++i) { foo2_list.push_back(foo2 + i); } for(foo2_list_t::iterator it = foo2_list.begin(); it != foo2_list.end(); ++it) { Foo2 *f = *it; ++f->i; ++f->j; } while (!foo2_list.empty()) { foo2_list.pop_front(); } pc.end(); cout << "std::list duration = " << pc.duration() << endl; pc.start(); for(size_t i = 0; i < _MAX; ++i) { foo1_list.add(foo1 + i); } for(Foo1 *f = foo1_list.begin(); f != foo1_list.end(); f = f->_list_next) { ++f->i; ++f->j; } while (foo1_list.begin() != foo1_list.end()) { foo1_list.remove(foo1_list.begin()); } pc.end(); cout << "_list duration = " << pc.duration() << endl; getchar(); return 0; }
I apologize for the (perhaps) stupid question, but where exactly is Boost.intrusive? I downloaded the latest boost version but I can not find it anywhere. Is it not part of the boost library yet? Joaquín Mª López Muñoz wrote:
Achilleas Margaritis ha escrito:
I think std::list is slower than my list (I could be wrong of course), because it allocates memory from the heap for each node, whereas my list requires the elements to have the node embedded in them, and so blocks are also nodes.
Maybe you can then replace your private intrusive list with Boost.Intrusive:
http://igaztanaga.drivehq.com/intrusive
which is already included in the SVN trunk.
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On 9/20/07, Achilleas Margaritis <axilmar@ath.forthnet.gr> wrote:
I apologize for the (perhaps) stupid question, but where exactly is Boost.intrusive? I downloaded the latest boost version but I can not find it anywhere. Is it not part of the boost library yet?
You will need to download from SVN, it is not in a point release yet. -- Cory Nelson
I've done a test with boost::intrusive::list and boost::object_pool. The boost's intrusive list is faster than mine, so I am going to use it. But the object_pool is noticeably slower, as it is not intrusive: each time a chunk is removed from the pool, the internal table is searched, one by one, to locate the pool's entry. Joaquín Mª López Muñoz wrote:
Achilleas Margaritis ha escrito:
I think std::list is slower than my list (I could be wrong of course), because it allocates memory from the heap for each node, whereas my list requires the elements to have the node embedded in them, and so blocks are also nodes.
Maybe you can then replace your private intrusive list with Boost.Intrusive:
http://igaztanaga.drivehq.com/intrusive
which is already included in the SVN trunk.
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On 09/20/07 09:39, Achilleas Margaritis wrote:
I've done a test with boost::intrusive::list and boost::object_pool.
The boost's intrusive list is faster than mine, so I am going to use it.
But the object_pool is noticeably slower, as it is not intrusive: each time a chunk is removed from the pool, the internal table is searched, one by one, to locate the pool's entry.
When you get around to documentation, in some sort of "maintainer's guide", this information would be useful to prevent a future maintainer or someone who thinks they've got a better implementation from going down the same dead-end road. In particular, a benchmark so this "future someone" could easily test is "maybe better" implementation. It's more work, but it'd help other's and maybe yourself in the future in case boost::object_pool improves it's implementation.
Ok, note taken. Larry Evans wrote:
On 09/20/07 09:39, Achilleas Margaritis wrote:
I've done a test with boost::intrusive::list and boost::object_pool.
The boost's intrusive list is faster than mine, so I am going to use it.
But the object_pool is noticeably slower, as it is not intrusive: each time a chunk is removed from the pool, the internal table is searched, one by one, to locate the pool's entry.
When you get around to documentation, in some sort of "maintainer's guide", this information would be useful to prevent a future maintainer or someone who thinks they've got a better implementation from going down the same dead-end road. In particular, a benchmark so this "future someone" could easily test is "maybe better" implementation.
It's more work, but it'd help other's and maybe yourself in the future in case boost::object_pool improves it's implementation.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
There is also the problem of initialization order of static variables. If I place a std::list as a static member of class gc, it may be initialized after a block has been allocated as a static variable in the main file. Larry Evans wrote:
On 09/16/07 16:56, Achilleas Margaritis wrote: [snip]
You can find a new version of my portable precise C++ garbage collector in vault/memory. [snip] Why doesn't cppgc.hpp use std::list instead of _list defined in cppgc.hpp and why isn't the boost pool:
http://www.boost.org/libs/pool/doc/index.html
used instead of the _pool of cppgc.hpp?
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On 09/16/07 16:56, Achilleas Margaritis wrote: [snip]
You can find a new version of my portable precise C++ garbage collector in vault/memory. There are at least 2 literal numbers on lines 541 and 554 of cppgc.hpp with no indication of what they mean. I'd suggest you define these as named constants together with minimal documentation at the definitions somewhere earlier in the code and then use these names in place of the literals.
Ok, next version will have these changes. Larry Evans wrote:
On 09/16/07 16:56, Achilleas Margaritis wrote: [snip]
You can find a new version of my portable precise C++ garbage collector in vault/memory. There are at least 2 literal numbers on lines 541 and 554 of cppgc.hpp with no indication of what they mean. I'd suggest you define these as named constants together with minimal documentation at the definitions somewhere earlier in the code and then use these names in place of the literals.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (13)
-
Achilleas Margaritis -
Cory Nelson -
dherring＠ll.mit.edu -
Giovanni Piero Deretta -
Joaquín Mª López Muñoz -
Johan Råde -
John Maddock -
Kim Barrett -
Larry Evans -
Sebastian Redl -
Seweryn Habdank-Wojewódzki -
Steven Burns -
Tobias Schwinger