[pool] an O(1) implementation of object_pool::destroy()
I was looking at object_pool and noticed that there is a way to make object_pool::destroy() an O(1) operation instead of an O(n) operation. If I understand the problem correctly, object_pool::destroy() is O(n) because it keep the free list sorted. It keeps the free list sorted so that object_pool::~object_pool() runs in O(n) time instead of in O(n^2) time. However, I believe there is an implementation of object_pool::~object_pool() that will run in O(n) time without requiring a sorted free list. My suggestion is that ~object_pool() could use a mark-sweep strategy: It would first step through the free list and mark each free chunk as such. It would then go back and examine each chunk in the pool and call the destructor on the ones not marked as free. The each chunk's 'next' pointer could be used to store the marked-as-free flag so that no extra memory is needed. This may be related to Ticket #290. A similar mark-sweep method could be used for pool::release_memory(). The free list would have to be reconstructed afterworlds but that is also easy. Just step back through all of the chunks and connect the ones that are marked as free. While I am on the subject of the pool library, I would also like to see a pool constructor that allows the user to set the initial size of the pool and whether or not the pool was allowed to grow. This would be very useful for the memory limited, real time environments in which memory pools are popular. Any thoughts on these suggestions? If asked, I could help work on an implementation. --Ben
AMDG Ben Muzal wrote:
I was looking at object_pool and noticed that there is a way to make object_pool::destroy() an O(1) operation instead of an O(n) operation.
If I understand the problem correctly, object_pool::destroy() is O(n) because it keep the free list sorted. It keeps the free list sorted so that object_pool::~object_pool() runs in O(n) time instead of in O(n^2) time. However, I believe there is an implementation of object_pool::~object_pool() that will run in O(n) time without requiring a sorted free list.
My suggestion is that ~object_pool() could use a mark-sweep strategy: It would first step through the free list and mark each free chunk as such. It would then go back and examine each chunk in the pool and call the destructor on the ones not marked as free. The each chunk's 'next' pointer could be used to store the marked-as-free flag so that no extra memory is needed.
Extra memory is needed because only the free list contains next pointers. The chunks that are in use do not. What would be possible is to make object_pool::destroy O(1) and object_pool::~object_pool O(n log n) by sorting the free list only on destruction. In Christ, Steven Watanabe
Steven Watanabe wrote:
AMDG
Ben Muzal wrote:
I was looking at object_pool and noticed that there is a way to make object_pool::destroy() an O(1) operation instead of an O(n) operation.
If I understand the problem correctly, object_pool::destroy() is O(n) because it keep the free list sorted. It keeps the free list sorted so that object_pool::~object_pool() runs in O(n) time instead of in O(n^2) time. However, I believe there is an implementation of object_pool::~object_pool() that will run in O(n) time without requiring a sorted free list.
My suggestion is that ~object_pool() could use a mark-sweep strategy: It would first step through the free list and mark each free chunk as such. It would then go back and examine each chunk in the pool and call the destructor on the ones not marked as free. The each chunk's 'next' pointer could be used to store the marked-as-free flag so that no extra memory is needed.
Extra memory is needed because only the free list contains next pointers. The chunks that are in use do not.
What would be possible is to make object_pool::destroy O(1) and object_pool::~object_pool O(n log n) by sorting the free list only on destruction.
That seems a lot better. -- Michael Marcin
participants (3)
-
Ben Muzal -
Michael Marcin -
Steven Watanabe