request for discussion - yet another approach to automated memory management that solves the cycles problem and is very efficient
Dear boost members, The file 'mm2.zip' (in boost vault/memory) contains yet another solution for automatic memory management. The solution has the following attributes: 1) it solves the problem of cycles. 2) it releases resources deterministically. 3) it does not scan the graph of objects for reachability. It uses simple numeric values (i.e. keys) to determine if an object can be collected or not. The idea is very simple: pointers obtain keys during their construction (a simple global variable that is incremented). The key remains constant throughout the lifetime of a ptr. During pointer release, the pointers that point to an object are scanned: if there is no pointer that points to the object that has a lower key from the key of the releasing pointer, then the object can be deleted. The pointer semantics are normal C pointer semantics, except for the construction: the solution requires that pointers that are lvalues should obtain a key before the heap object that they will be assigned to. i.e. you can't do this: ptr p1 = new object; You have to do this: ptr p1; p1 = new object; All the operations have O(1) complexity, except the release operation, which has O(N) complexity, whereas N is the number of pointers that point to an object. Practically, the complexity is minimal, because it is rare to have that many different pointers to a single object (I think :-)). I have no idea if it works for all cases. The file 'main2.cpp' contains a lot of tests, which all pass. I have also included the benchmark of the Boehm GC modified to use my special ptr classes. In my machine, an Athlon 64 2.2 GHz, the benchmark is executed, using boost pools, at roughly 1900 milliseconds, whereas the Boehm gc benchmark, using the Boehm gc collector, is executed at roughly 1200 milliseconds (and the Java benchmark at roughly 600 milliseconds). The amazing thing is that it looks like it works, but I am not sure. I am sure there is a catch :-).
On 02/26/09 18:07, Achilleas Margaritis wrote: [snip]
3) it does not scan the graph of objects for reachability. It uses simple numeric values (i.e. keys) to determine if an object can be collected or not.
The idea is very simple: pointers obtain keys during their construction (a simple global variable that is incremented). The key remains constant throughout the lifetime of a ptr.
During pointer release, the pointers that point to an object are scanned: if there is no pointer that points to the object that has a lower key from the key of the releasing pointer, then the object can be deleted.
Hi Achilleas. Could you explain why this should work? IOW, why does the test:
if there is no pointer that points to the object that has a lower key from the key of the releasing pointer,
assure that it's OK to delete the object? Also, to conduct the test, it appears each pointee has to maintain a set of pointer's to itself, which, I think, doubles the number of pointers, i.e. if there's and edge a -> b in the pointer graph, there most also be an edge b -> a stored in b somewhere. Is that right? -regards, Larry [snip]
Hi Achilleas.
Could you explain why this should work?
The idea is this the following: An object is deleted if all the ptrs that point to it expired. Each ptr has an age. When a ptr releases an object, it checks if the object has any other ptrs with age older than the ptr. If not so, then it means the released ptr is the oldest one, and therefore the object should be deleted. I have updated the Boost Vault files with an example with better unit testing. It works, except when ownership of an object with cycles is transferred to a newer ptr.
On 02/27/09 07:21, Achilleas Margaritis wrote:\ [snip]
The idea is this the following:
An object is deleted if all the ptrs that point to it expired.
Each ptr has an age.
When a ptr releases an object, it checks if the object has any other ptrs with age older than the ptr. If not so, then it means the released ptr is the oldest one, and therefore the object should be deleted.
I unsure about that last sentence. Why does release of oldest ptr imply there are no other live ptr's pointing to the object? [snip]
It works, except when ownership of an object with cycles is transferred to a newer ptr.
This seems a serious shortcoming. To justify this, I guess you'd have to somehow argue that this use-case doesn't happen very often or that if it does, the user can easily detect that it happens and take corrective active. Then, to justify this method vs. the use of weak-ptrs, you'd have to argue why it's easier for the user to detect "transferred to a newer ptr" than it is to detect where a cycle is created.
This seems a serious shortcoming. To justify this, I guess you'd have to somehow argue that this use-case doesn't happen very often or that if it does, the user can easily detect that it happens and take corrective active. Then, to justify this method vs. the use of weak-ptrs, you'd have to argue why it's easier for the user to detect "transferred to a newer ptr" than it is to detect where a cycle is created.
Indeed. I think the algorithm works for immutable ptrs only.
On 02/27/09 14:13, Achilleas Margaritis wrote:
This seems a serious shortcoming. To justify this, I guess you'd have to somehow argue that this use-case doesn't happen very often or that if it does, the user can easily detect that it happens and take corrective active. Then, to justify this method vs. the use of weak-ptrs, you'd have to argue why it's easier for the user to detect "transferred to a newer ptr" than it is to detect where a cycle is created.
Indeed. I think the algorithm works for immutable ptrs only.
Aren't mutable ptrs necessary for creating cycles? Suppose the ptr graph is B->A->B. (IOW, object B has pointer, B.ptr which points to object A, and object A has pointer, A.ptr which points to B.) Now, either A or B must be created first. When the first one is created (suppose it's B) it can't be constructed already pointing to A because A hasn't been created yet. Consequently, B.ptr must be mutable in order to eventually point to A. Am I missing something?
Achilleas Margaritis wrote:
Hi Achilleas.
Could you explain why this should work?
The idea is this the following:
An object is deleted if all the ptrs that point to it expired.
This statement contradicts with
When a ptr releases an object, it checks if the object has any other ptrs with age older than the ptr. If not so, then it means the released ptr is the oldest one, and therefore the object should be deleted.
If the last one is correct, the idea seems equal to the following: int* new_ptr; { std::auto_ptr<int> oldest(new int(42)); new_ptr = oldest.get(); } *new_ptr = 43; // boom
Dear boost members, anyony can check the code below? the way that I am using boost/pool is correct? it is too slow in my "linux 2.6+Intel(R) Core(TM)2 Duo CPU E6850 @ 3.00GHz" pc thanks! ********* #include "boost/pool/object_pool.hpp" #include <sys/time.h> #include <pthread.h> #include <asm/atomic.h> #include <stdlib.h> class Rational { public: Rational(int a = 0,int b = 1):n(a),d(b) { } private: int n; int d; }; atomic_t gv; boost::object_pool<Rational> pool; void *thread_function(void *arg) { struct timeval tpstart,tpend; atomic_t *v=(atomic_t *)arg; Rational *array[1000]; // Start timing here gettimeofday(&tpstart,NULL); for (int j = 0; j < 50000; j++) { for (int i = 0; i < 1000; i++) { array[i] = pool.construct(i); } for (int i = 0; i < 1000; i++) { pool.destroy(array[i]); } } gettimeofday(&tpend,NULL); int timeuse = (tpend.tv_sec-tpstart.tv_sec)*1000000 + (tpend.tv_usec-tpstart.tv_usec); printf("time= %d usec\n",timeuse); atomic_add(timeuse, v); } int main(int argc,char **argv) { if (argc != 2) { perror("usuage:Mempool numberOfThreads\n"); exit(-1); } /* * initialize atomic_t */ atomic_set(&gv, 0); char *end; int numThreads = strtol(argv[1],&end,10); pthread_t a_thread[numThreads]; void *thread_result; int res; for (int i=0; i < numThreads;i++) { res = pthread_create(&a_thread[i], NULL, thread_function, (void *)&gv); } for (int i=0; i < numThreads;i++) { res = pthread_join(a_thread[i], &thread_result); } printf("\nTotal time= %d usec\n",gv); } Regards, zhou rui
boost::object_pool is not thread-safe. 2009/3/10 <jon_zhou@agilent.com>:
Dear boost members,
anyony can check the code below? the way that I am using boost/pool is correct?
it is too slow in my "linux 2.6+Intel(R) Core(TM)2 Duo CPU E6850 @ 3.00GHz" pc
thanks!
********* #include "boost/pool/object_pool.hpp" #include <sys/time.h> #include <pthread.h> #include <asm/atomic.h> #include <stdlib.h>
class Rational { public: Rational(int a = 0,int b = 1):n(a),d(b) { }
private: int n; int d;
};
atomic_t gv; boost::object_pool<Rational> pool;
void *thread_function(void *arg) {
struct timeval tpstart,tpend; atomic_t *v=(atomic_t *)arg; Rational *array[1000]; // Start timing here gettimeofday(&tpstart,NULL);
for (int j = 0; j < 50000; j++) { for (int i = 0; i < 1000; i++) { array[i] = pool.construct(i);
} for (int i = 0; i < 1000; i++) { pool.destroy(array[i]); } } gettimeofday(&tpend,NULL); int timeuse = (tpend.tv_sec-tpstart.tv_sec)*1000000 + (tpend.tv_usec-tpstart.tv_usec); printf("time= %d usec\n",timeuse); atomic_add(timeuse, v); }
int main(int argc,char **argv) { if (argc != 2) { perror("usuage:Mempool numberOfThreads\n"); exit(-1); } /* * initialize atomic_t */ atomic_set(&gv, 0); char *end; int numThreads = strtol(argv[1],&end,10); pthread_t a_thread[numThreads];
void *thread_result; int res; for (int i=0; i < numThreads;i++) { res = pthread_create(&a_thread[i], NULL, thread_function, (void *)&gv); }
for (int i=0; i < numThreads;i++) { res = pthread_join(a_thread[i], &thread_result); }
printf("\nTotal time= %d usec\n",gv); }
Regards, zhou rui
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
hi seems only singleton_pool is thread-safe? but it just only alloc memory and does not call ctor... why object_pool is not designed as thread-safe? Regards, zhou rui -----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of 邱宇舟 Sent: Tuesday, March 10, 2009 6:49 PM To: boost@lists.boost.org Subject: Re: [boost] [object_pool]too slow? boost::object_pool is not thread-safe. 2009/3/10 <jon_zhou@agilent.com>:
Dear boost members,
anyony can check the code below? the way that I am using boost/pool is correct?
it is too slow in my "linux 2.6+Intel(R) Core(TM)2 Duo CPU E6850 @ 3.00GHz" pc
thanks!
********* #include "boost/pool/object_pool.hpp" #include <sys/time.h> #include <pthread.h> #include <asm/atomic.h> #include <stdlib.h>
class Rational { public: Rational(int a = 0,int b = 1):n(a),d(b) { }
private: int n; int d;
};
atomic_t gv; boost::object_pool<Rational> pool;
void *thread_function(void *arg) {
struct timeval tpstart,tpend; atomic_t *v=(atomic_t *)arg; Rational *array[1000]; // Start timing here gettimeofday(&tpstart,NULL);
for (int j = 0; j < 50000; j++) { for (int i = 0; i < 1000; i++) { array[i] = pool.construct(i);
} for (int i = 0; i < 1000; i++) { pool.destroy(array[i]); } } gettimeofday(&tpend,NULL); int timeuse = (tpend.tv_sec-tpstart.tv_sec)*1000000 + (tpend.tv_usec-tpstart.tv_usec); printf("time= %d usec\n",timeuse); atomic_add(timeuse, v); }
int main(int argc,char **argv) { if (argc != 2) { perror("usuage:Mempool numberOfThreads\n"); exit(-1); } /* * initialize atomic_t */ atomic_set(&gv, 0); char *end; int numThreads = strtol(argv[1],&end,10); pthread_t a_thread[numThreads];
void *thread_result; int res; for (int i=0; i < numThreads;i++) { res = pthread_create(&a_thread[i], NULL, thread_function, (void *)&gv); }
for (int i=0; i < numThreads;i++) { res = pthread_join(a_thread[i], &thread_result); }
printf("\nTotal time= %d usec\n",gv); }
Regards, zhou rui
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Hi, Lock is slow. The pool lib is for performance. 2009/3/12 <jon_zhou@agilent.com>:
hi
seems only singleton_pool is thread-safe? but it just only alloc memory and does not call ctor...
why object_pool is not designed as thread-safe? Just like the stl container vector,list... are not thread-safe. The user should lock his mutex by himself if it's in need.
Object pool is very slow. destroy() is O(n) where n is the number of free objects. Therefore if you allocate N objects and then destroy N objects, you end up with a O(N^2) runtime. LET ME SAY THAT AGAIN: ObjectPool is O(n^2) FOR THE TYPICAL USAGE OF A POOL!!! The ( bad IMHO ) reason for doing this is in order to keep the free list sorted so that ~ObjectPool() runs in O(n) instead of O(n^2). However, if it wanted to ~ObjectPool() could just sort the free list in O(n logn) so there is no need at all for destroy() to keep it sorted. However, my personal feelings about a pool is that the pool should not be calling the destructors on any objects that are still allocated when the pool is destroyed. I know that standard containers will call distructors, but a pools are NOT a container. The usage of a pool is closer to the new and delete operator. If you 'new' an object, and then do an exit(), your object does not get deleted before the process is destroyed. Why should a pool work any differently? If you want to create a bunch of objects and then destroy them all at once, then use a container. If you have any allocated objects still around when a pool is destroyed, It is a bug unless the process is about to exit. I thought about submitting a patch, but I don't think there is anyone who is maintaining boost::pool. The workaround to make object pool fast is just to modify object pool header to use free() instead of orderedFree() and then modify the destructor to not call the destructors of the objects that are still allocated. On Wed, Mar 11, 2009 at 11:42 PM, Qiu Yuzhou <qbowater@gmail.com> wrote:
Hi,
Lock is slow. The pool lib is for performance.
2009/3/12 <jon_zhou@agilent.com>:
hi
seems only singleton_pool is thread-safe? but it just only alloc memory and does not call ctor...
why object_pool is not designed as thread-safe? Just like the stl container vector,list... are not thread-safe. The user should lock his mutex by himself if it's in need.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
AMDG Ben Muzal wrote:
However, my personal feelings about a pool is that the pool should not be calling the destructors on any objects that are still allocated when the pool is destroyed.
If that's what you want, then use boost::pool instead of boost::object_pool. In Christ, Steven Watanabe
Like I said, if you want the destructors called when the pool is destroyed, you should be using a container not a pool. (allocators are not containers. containers delete the objects they hold because they own them. Allocators however do not own the objects that they allocate.) But that is not really the point of my post. That 'feature' of the destructor will have to stay so that it does not break any existing code. My real problem is the O(n^2) nature of allocating then dealocating N objects. Am I wrong that the O(n^2) behavior should be considered a BUG? --Ben On Mon, Mar 16, 2009 at 1:58 PM, Steven Watanabe <watanabesj@gmail.com> wrote:
AMDG
Ben Muzal wrote:
However, my personal feelings about a pool is that the pool should not be calling the destructors on any objects that are still allocated when the pool is destroyed.
If that's what you want, then use boost::pool instead of boost::object_pool.
In Christ, Steven Watanabe
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
AMDG Ben Muzal wrote:
Like I said, if you want the destructors called when the pool is destroyed, you should be using a container not a pool. (allocators are not containers. containers delete the objects they hold because they own them. Allocators however do not own the objects that they allocate.)
You're missing the point of boost::object_pool.
But that is not really the point of my post. That 'feature' of the destructor will have to stay so that it does not break any existing code.
This feature has to stay because it is the the reason object_pool exists as a separate class.
My real problem is the O(n^2) nature of allocating then dealocating N objects.
Am I wrong that the O(n^2) behavior should be considered a BUG?
I do consider it a bug, although this isn't really the intended usage of object_pool. In Christ, Steven Watanabe
Object pool is very slow. destroy() is O(n) where n is the number of free objects. Therefore if you allocate N objects and then destroy N objects, you end up with a O(N^2) runtime. < I know nothing about the classes in question, but an O(n) followed by (plus) another O(n) operation is still O(n) NOT O(n^2)
yes, but O(n) n times is O(n^2) On Mon, Mar 16, 2009 at 4:22 PM, Paul Baxter <pauljbaxter@hotmail.com> wrote:
Object pool is very slow. destroy() is O(n) where n is the number of free objects. Therefore if you allocate N objects and then destroy N objects, you end up with a O(N^2) runtime. < I know nothing about the classes in question, but an O(n) followed by (plus) another O(n) operation is still O(n) NOT O(n^2)
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (9)
-
Achilleas Margaritis -
Ben Muzal -
Ilya Sokolov -
jon_zhou＠agilent.com -
Larry Evans -
Paul Baxter -
Qiu Yuzhou -
Steven Watanabe -
邱宇舟