Re: Lock-free reference counting
- From: Jon Harrop <jon@xxxxxxxxxxxxxxxxx>
- Date: Tue, 02 Dec 2008 00:31:44 +0000
Stephen Howe <sjhoweATdialDOTpipexDOTcom> wrote:
On Mon, 01 Dec 2008 17:33:50 +0000, Jon Harrop <jon@xxxxxxxxxxxxxxxxx>
wrote:
Stephen Howe <sjhoweATdialDOTpipexDOTcom> wrote:
You said, "Which are scattered across memory.". I am pointing out that
the counters are _NOT_ scattered in memory...
That is incorrect.
if the reference counters are instrusive, the reference counters are
adjacent in memory to the object they count.
The objects themselves are scattered across memory => the references in
them are also scattered.
No. Effectively when memory was allocated for object it was
sizeof(object)+sizeof(counter). The counter is _ADJACENT_ to the
object. Granted if you had 4000 objects they may be scattered
thoughout memory, but in every case, their counters are adjacent.
The counters are in with the object and the objects are scattered across
memory, yes.
You are describing extrusive pointers (where the counter maybe
somewhere else in memory from the object)...
No, that is not what I am describing.
Reference counts only exist to get bumped and they are bumped under a
variety of different circumstances including many where the data in the
object itself is not touched.
Even swapping a pair of reference counted smart pointers in an array over
incurs several memory accesses to locations that would otherwise have been
untouched.
Not necessarily so with C++. swap may be specialised for the reference
countered pointers. I make that 2 reads, 2 writes for that swap
(assuming that a pointer & counter can be moved to a register) which
any decent compiler will do.
A triumph of hope over reality. Here is an example program that runs 2x
slower than necessary when compiled with GCC 4.3.2 on x86:
#include <iostream>
#include <vector>
#include <algorithm>
#include <boost/shared_ptr.hpp>
using namespace std;
using namespace boost;
int cmp(shared_ptr<int> a, shared_ptr<int> b)
{
return *a < *b;
}
int main(int argc, char *argv[])
{
vector<shared_ptr<int> > a;
const int n = (argc > 1 ? atoi(argv[1]) : 1000000);
cout << n << endl;
for (int i=0; i<n; ++i)
{
shared_ptr<int> k(new int);
*k = n - i;
a.push_back(k);
}
sort(a.begin(), a.end(), cmp);
return 0;
}
Profiling shows that 60% of the time is spent bumping counters precisely
because GCC fails to make that optimization.
An example: swap is specialised for std::vector which allows 2 vectors
to be swapped without swapping container contents at all (providing
the allocators are the same). It amounts to swapping 3 pointers.
The same is true for std::deque and other containers. More to the
point, the objects that the vectors are managing are untouched after
the swap.
Same is true std::string. You can swap strings, not a single character
is copied or moved. Nothing is allocated or deallocated.
And I stress again that your array example of bumping is only true if
the array is an array of smart pointers. If those are references or
pointers the bumpoing does not occur (mind you there is now an extra
level of indirection, you have not gained much).
I agree that such optimizations exist and can even be done by hand but then
you've lost the only advantage reference counting ever had: simplicity.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
.
- References:
- Re: Lock-free reference counting
- From: Stephen Howe
- Re: Lock-free reference counting
- From: Jon Harrop
- Re: Lock-free reference counting
- From: Stephen Howe
- Re: Lock-free reference counting
- Prev by Date: Re: Lock-free reference counting
- Next by Date: Re: Linux Sockets UDP and fragmentation
- Previous by thread: Re: Lock-free reference counting
- Next by thread: Re: Lock-free reference counting
- Index(es):
Relevant Pages
|
