Hi, I'm writing an application with intense usage of integers and one of the operations that might have a performance impact is swapping two numbers. I don't know the internals of the CLN library and I see there is no swap operation in the headers. Could someone please elaborate how much stuff happens internally when I do the usual swap: void swap(cl_I& a, cl_I& b) { (1) cl_I temp; (2) temp = a; (3) a = b; (4) b = temp; (5) } My worst-case guess is: (1) a sequence of constructors (2) reconstruction of a (3) destruction of a, reconstruction of b (4) destruction of b, reconstruction of temp (5) destruction of temp Also, would massive amount of swaps lead to internal memory fragmentation due to construction/destruction? Thanks, Dejan
Dejan Jovanović wrote:
I'm writing an application with intense usage of integers and one of the operations that might have a performance impact is swapping two numbers. I don't know the internals of the CLN library and I see there is no swap operation in the headers.
Could someone please elaborate how much stuff happens internally when I do the usual swap:
void swap(cl_I& a, cl_I& b) { (1) cl_I temp; (2) temp = a; (3) a = b; (4) b = temp; (5) }
My worst-case guess is: (1) a sequence of constructors (2) reconstruction of a (3) destruction of a, reconstruction of b (4) destruction of b, reconstruction of temp (5) destruction of temp
No, thanks to reference counting, your implementation of swap(a,b) is of O(1) in the integer length of both operands. The manual has mention of the reference counting in some places.
Also, would massive amount of swaps lead to internal memory fragmentation due to construction/destruction?
No, no reason to worry. -richy. -- Richard B. Kreckel <http://www.ginac.de/~kreckel/>
Hi Dejan,
I see there is no swap operation in the headers.
There is no swap operations in the headers because the code with assignments that you wrote is fast enough.
would massive amount of swaps lead to internal memory fragmentation due to construction/destruction?
No. Every heap-allocated object of CLN has a reference count. Therefore, swapping the contents of two variables really only swaps pointers and is O(1), regardless of the magnitude or precision of the numbers.
Could someone please elaborate how much stuff happens internally when I do the usual swap:
void swap(cl_I& a, cl_I& b) { (1) cl_I temp; (2) temp = a; (3) a = b; (4) b = temp; (5) }
(1) temp gets assigned a default value (0 IIRC). (2) The reference count of the object pointed to by a gets incremented. (3) The reference count of the object pointed to by b gets incremented, and the reference count of the object originally pointed to by a gets decremented. (4) The reference count of the object originally pointed to by a gets incremented, and the reference count of the object originally pointed to by b gets decremented. (5) The reference count of the object originally pointed to by a gets decremented. For fixnums, which have no memory allocation, of course no reference count exists. If even this O(1) is code turns out to be a bottleneck, there is also the possibility of using the placement-new operator. But since it is easy to produce memory leaks with this technique, I don't recommend it unless you *really* have a bottleneck here. Bruno
Hi, Thanks for the swift replies! That clarifies things, reference counting should be fine. Another question on somewhat similar topic. I'll be doing my own management of small structures, and some of them will include the numbers. Is it reasonable to assume that plain copying of (the cl_I) data to increase memory size (via realloc), or when doing garbage-collection, will not break anything? Best, Dejan 2010/8/25 Bruno Haible <bruno@clisp.org>:
No. Every heap-allocated object of CLN has a reference count. Therefore, swapping the contents of two variables really only swaps pointers and is O(1), regardless of the magnitude or precision of the numbers.
Dejan Jovanović wrote:
Is it reasonable to assume that plain copying of (the cl_I) data to increase memory size (via realloc), or when doing garbage-collection, will not break anything?
Here you need to be careful. Moving a cl_I from one place in memory to another address is not a problem. But when you use realloc to grow an array of cl_I, say, from 10 to 15 elements, the last 5 elements will not be initialized. Accessing these elements may crash. In order to initialize these elements, you need to call the no-argument constructor cl_I::cl_I() on them (via a placement-new expression). And symmetrically, before you shrink an array of 15 elements to 10 elements, you need to call the destructor cl_I::~cl_I() on the 5 elements that will be freed. Otherwise you will have a memory leak. You can avoid these complexities by using the C++ memory allocators new[]/ delete[] instead of the C memory allocator malloc/free. Bruno
Hi, Bruno Haible wrote:
You can avoid these complexities by using the C++ memory allocators new[]/ delete[] instead of the C memory allocator malloc/free.
Since it is easy to produce memory leaks with this technique, I don't recommend it unless you *really* have a bottleneck here. Instead, I would just go with std::vector<cln::cl_I> and not worry about memory management too much. It smells like premature optimization. -richy. -- Richard B. Kreckel <http://www.ginac.de/~kreckel/>
participants (3)
-
Bruno Haible
-
Dejan Jovanović
-
Richard B. Kreckel